Методы и средства создания параллельно-конвейерных программ с масштабируемой разрядностью для решения задач цифровой обработки сигналов на реконфигурируемых вычислительных системах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Чкан, Андрей Викторович

• Чкан, Андрей Викторович
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Чкан, Андрей Викторович

СОДЕРЖАНИЕ

стр.

ВВЕДЕНИЕ

1. АНАЛИЗ МЕТОДОВ И СРЕДСТВ РЕШЕНИЯ ЗАДАЧ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ НА РВС

1.1. Современные многопроцессорные вычислительные системы ЦОС

на базе универсальных процессоров

1.2. Современные многопроцессорные вычислительные системы ЦОС

на базе DSP

1.3. Современные многопроцессорные вычислительные системы ЦОС

на базе ПЛИС

1.4. Влияние форматов представления чисел на удельную производительность РВС

1.5. Проблемы реализации алгоритмов БПФ на РВС для данных с фиксированной запятой

1.6. Выводы

2. МЕТОДЫ СОЗДАНИЯ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ ДЛЯ РЕАЛИЗАЦИИ БПФ НА РВС ДЛЯ ДАННЫХ С ФИКСИРОВАННОЙ ЗАПЯТОЙ

2.1. Метод реализации БПФ на РВС с априорным поиском итераций, требующих масштабирования

2.2. Метод реализации БПФ на РВС с поэтапным увеличением разрядности и масштабированием

2.3. Сравнительный анализ методов реализации БПФ на РВС

2.4. Методика создания структурно-процедурных алгоритмов и параллельно-конвейерных программ для решения задач ЦОС на РВС

2.5. Выводы

3. АЛГОРИТМЫ СОГЛАСОВАННОЙ ФИЛЬТРАЦИИ С МАСШТАБИРУЕМОЙ РАЗРЯДНОСТЬЮ ДЛЯ РВС

3.1. Алгоритм согласованной фильтрации с априорным определением итераций, требующих масштабирования

3.2. Алгоритм согласованной фильтрации с поэтапным увеличением разрядности и масштабированием

3.3. Сравнительный анализ алгоритмов согласованной фильтрации с масштабируемой разрядностью для РВС

3.4. Выводы

4. АЛГОРИТМЫ ДВУМЕРНОГО БПФ И ЧАСТОТНОЙ ФИЛЬТРАЦИИ ИЗОБРАЖЕНИЙ С МАСШТАБИРУЕМОЙ РАЗРЯДНОСТЬЮ ДЛЯ РВС

4.1. Алгоритм частотной фильтрации изображений с априорным определением итераций, требующих масштабирования

4.2. Алгоритм частотной фильтрации изображений с поэтапным увеличением разрядности и масштабированием

4.3. Сравнительный анализ алгоритмов частотной фильтрации изображений с масштабируемой разрядностью для РВС

4.4. Библиотека программ на основе алгоритмов ЦОС с масштабируемой разрядностью для РВС

4.5. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ 1. ТЕКСТЫ ПРОГРАММ НА ЯЗЫКЕ СОЬАМО ДЛЯ РЕАЛИЗАЦИИ АЛГОРИТМОВ ЦОС С МАСШТАБИРУЕМОЙ

РАЗРЯДНОСТЬЮ НА РВС

ПРИЛОЖЕНИЕ 2. АКТЫ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИИ

Введение диссертации (часть автореферата) на тему «Методы и средства создания параллельно-конвейерных программ с масштабируемой разрядностью для решения задач цифровой обработки сигналов на реконфигурируемых вычислительных системах»

ВВЕДЕНИЕ

Актуальность работы. Стремительное развитие

высокопроизводительных вычислительных систем привело к повсеместному использованию технологий цифровой обработки сигналов (ЦОС). В свою очередь постановка новых трудоёмких вычислительных задач ЦОС является стимулом для разработок ещё более мощных вычислительных систем (ВС). Одним из актуальных классов трудоёмких вычислительных задач ЦОС является широкий класс задач потоковой обработки информации, подразумевающих обработку больших массивов данных в режиме реального времени с использованием одних и тех же алгоритмов [1], к которым относятся различные задачи гидро- и радиолокации, потоковой обработки изображений и многие другие.

Для решения этого класса задач используются многопроцессорные вычислительные системы (МВС), позволяющие добиваться высоких показателей реальной производительности за счёт развития следующих направлений [1, 2]:

- технологического, который заключается в совершенствовании технологий создания элементной базы, в том числе за счёт увеличения плотности компоновки вентилей на кристалле, приводящей к росту производительности процессоров;

- архитектурного - построении оптимальных архитектур ВС, предназначенных для решения заданных классов задач;

- алгоритмического - разработке эффективных математических методов;

- программного - разработке программ, максимально раскрывающих возможности программируемых ВС.

Успехи по каждому из направлений развития МВС дают новые качественные возможности в решении уже существующих сложных задач, а также открывают перспективы для решения новых ещё более трудоёмких

задач, выполнение которых до определённого момента было невозможным в силу недостаточной производительности вычислительных систем.

Одним из успешных архитектурных решений в области многопроцессорных вычислительных систем являются реконфигурируемые вычислительные системы (РВС) [1, 2], построенные на базе программируемых логических интегральных схем (ПЛИС, англ. БРОА) [3, 4]. Стремительное развитие РВС напрямую связано с их способностью достигать высокой реальной производительности 60-90% от пиковой для широкого класса трудоёмких задач [5, 6], так как РВС позволяют программировать свою вычислительную архитектуру, адаптируя её под структуру текущей решаемой задачи [1, 2].

Важным фактором, влияющим на реальную производительность РВС, является выбор формата представления чисел [7, 8]. Так, формат с плавающей запятой целесообразно применять для задач, требующих высокой точности вычислений и не столь критичных к скорости обработки данных и используемым аппаратным ресурсам ПЛИС. Однако в большинстве случаев точности, предоставляемой форматом с фиксированной запятой, бывает достаточно для решения широкого круга задач. Такой формат позволяет существенно повысить реальную производительность системы в сравнении с использованием формата с плавающей запятой и значительно уменьшить число задействованных аппаратных ресурсов ПЛИС. Это связано как со свойствами самого формата с фиксированной запятой, так и с возможностью использования данных переменной разрядности на разных вычислительных этапах, что характерно для задач ЦОС. Экономия аппаратного ресурса, в свою очередь, может позволить разместить на свободном аппаратном пространстве ПЛИС дополнительные вычислительные структуры, повышая удельную производительность системы.

Под удельной производительностью в данной работе будем понимать отношение реальной производительности вычислительной системы к

затрачиваемому аппаратному ресурсу (числу логических ячеек ПЛИС), необходимому для решения поставленной задачи [9, 10].

В задачах потоковой обработки широко используются алгоритмы быстрого преобразования Фурье (БПФ) [7, 11, 12], поэтому удельная и реальная производительность РВС при решении этого класса задач зависит от эффективности реализации алгоритмов БПФ.

Структурная реализация алгоритмов БПФ на РВС для данных в формате с плавающей запятой не составляет особых проблем ввиду широкого динамического диапазона и большой разрядности представления чисел (как правило, 32 или 64 разряда), но приводит к низкой удельной производительности вычислительных систем, так как в силу свойств формата задействует большое число аппаратных ресурсов ПЛИС.

Использование формата с фиксированной запятой при структурной реализации алгоритмов БПФ позволяет добиться высокой удельной и реальной производительности вычислительных систем, но может приводить к высокой погрешности вычислений и ошибкам переполнения разрядной сетки. Это связано как с узким динамическим диапазоном представления данных в формате с фиксированной запятой, так и с меняющейся разрядностью данных в процессе выполнения алгоритмов. Количество ошибок переполнений может возрастать при увеличении размерности БПФ и малой разрядности входных данных.

Устранение ошибок переполнений в ходе арифметических операций может быть осуществлено одним из двух способов:

- применение операции масштабирования (битового сдвига), которая заключается в отбрасывании младших значащих разрядов результата арифметической операции с целью его представления требуемым числом разрядов;

- увеличение разрядов для хранения результата арифметической операции.

Существующие методы реализации БПФ, исключающие ошибки переполнений с использованием операции масштабирования [13], не позволяют обеспечить повышение удельной производительности РВС без серьезной потери точности вычислений.

Применение способа увеличения разрядов для хранения результатов арифметических операций на выходе каждой итерации БПФ позволяет избежать погрешностей, вызванных масштабированием и, тем самым, сохранить точность вычислений, но приводит к существенному росту задействованного аппаратного ресурса ПЛИС для БПФ больших размерностей, что также является нежелательным.

Таким образом, актуальной задачей является разработка новых методов создания параллельно-конвейерных программ с масштабируемой разрядностью, реализующих алгоритмы БПФ на РВС и позволяющих обеспечить высокую удельную производительность и приемлемую точность вычислений при решении задач ЦОС.

Под масштабированием разрядности будем понимать процедуру ограниченного (целенаправленного) увеличения разрядности результатов операций на один разряд или согласованного применения операции масштабирования (битового сдвига) для гарантоспособности вычислений без переполнений и обеспечения требуемой точности.

Цель работы состоит в увеличении удельной производительности РВС при решении задач ЦОС.

Объектом исследований являются алгоритмы ЦОС и программное обеспечение РВС.

Предметом исследований являются методы реализации алгоритмов ЦОС на РВС.

Научная задача, решаемая в диссертации, - разработка методов создания параллельно-конвейерных программ с масштабируемой разрядностью, повышающих удельную производительность реконфигурируемых

вычислительных систем при решении задач ЦОС на основе быстрого преобразования Фурье для заданной точности вычислений.

Для достижения указанной цели решены следующие задачи:

1) проведён анализ методов и средств реализации алгоритмов ЦОС на

МВС;

2) разработаны методы создания параллельных программ для реализации БПФ на РВС для данных с фиксированной запятой;

3) разработаны алгоритмы согласованной фильтрации с масштабируемой разрядностью для РВС;

4) разработаны алгоритмы двумерного БПФ и частотной фильтрации изображений с масштабируемой разрядностью для РВС;

5) на основе разработанных методов и алгоритмов созданы библиотеки программ, которые могут быть использованы при решении практических задач ЦОС на РВС.

Методы исследований. При проведении исследований были использованы: теория цифровой обработки сигналов, теория математической статистики, методы конструирования аппаратных вычислительных устройств, методы структурно-процедурного параллельного программирования. Экспериментальные исследования проведены на действующих РВС.

Научная новизна диссертационной работы определяется тем, что в ней разработаны:

1) метод создания параллельных программ для реализации БПФ на РВС для данных с фиксированной запятой, отличающийся от известных априорным определением итераций БПФ, требующих масштабирования;

2) метод создания параллельных программ для реализации БПФ на РВС для данных с фиксированной запятой, отличающийся от известных поэтапным увеличением разрядности представления результатов вычислений в заданной группе итераций БПФ и масштабированием, с выбором максимально возможного числа значащих разрядов, на вычислительных этапах, требующих уменьшения разрядности данных;

3) алгоритмы согласованной фильтрации с масштабируемой разрядностью для РВС, отличающиеся или априорным определением итераций с масштабированием, или поэтапным увеличением разрядности с последующим масштабированием, как для прямого, так и для обратного БПФ;

4) алгоритмы двумерного БПФ и частотной фильтрации изображений с масштабируемой разрядностью для РВС, отличающиеся процедурой определения общего для всех строк (столбцов) входной двумерной матрицы коэффициента масштабирования.

Практическая значимость.

Применение методов создания параллельных программ для реализации БПФ на РВС для данных с фиксированной запятой позволило сократить задействованные аппаратные ресурсы ПЛИС, в сравнении с реализацией БПФ для данных с плавающей запятой, - в 3.7 раза при использовании метода с априорной оценкой итераций, требующих масштабирования, и в 2.9 раза при использовании метода, основанного на поэтапном увеличении разрядности и масштабировании; в сравнении с реализацией БПФ для данных с фиксированной запятой с изначально увеличенной разрядностью, - в 2.3 раза при использовании метода с априорной оценкой итераций, требующих масштабирования, ив 1.9 раза при использовании метода, основанного на поэтапном увеличении разрядности и масштабировании.

Аналогичные усреднённые сравнительные оценки получены для алгоритмов согласованной фильтрации и частотной фильтрации изображений, которые были реализованы на РВС с помощью созданных методов реализации БПФ.

Программные библиотеки, разработанные на основе созданных методов для различного числа входных данных, представленных в формате с фиксированной запятой, могут быть использованы в качестве готовых решений при реализации практических задач ЦОС на РВС.

Использование результатов работы. Материалы диссертации использовались при выполнении ряда НИОКР, среди которых наиболее значимыми являются:

- «Исследование возможности создания программируемого блока обработки сигналов из состава прибора 46 серийного образца изделия «Л-01»», отчет о НИР, № гос. рег. 01201360203, Таганрог, НИИ МВС ЮФУ, шифр «Лира», 2013;

- «Разработка реконфигурируемой вычислительной системы РВС-7 и организация на ее основе производства реконфигурируемых вычислительных систем с производительностью до 1015 операций в секунду в одностоечном конструктиве 47Ш, отчет об ОКР, № гос. рег. 49-15/259, Таганрог, НИИ МВС ЮФУ шифр «Плеяда», 2013;

- «Разработка и исследование методов синтеза прикладных программ для реконфигурируемых вычислительных систем на основе перспективных ПЛИС сверхвысокой степени интеграции», отчет о НИР, № гос. рег. 114061040060, Таганрог, НИИ МВС ЮФУ шифр «Шкала», 2014;

- «Разработка и исследование технологии создания ресурсонезависимого прикладного программного обеспечения высокопроизводительных вычислительных систем гибридного типа», отчет о НИР, № гос. рег. 140912077192, Таганрог, НИИ МВС ЮФУ, шифр «Русалка», 2014;

- «Разработка комплексов моделей, методов и масштабируемого программного обеспечения для предсказательного моделирования неблагоприятных и опасных явлений в водных системах на высокопроизводительных вычислительных системах», отчёт о НИР, № гос. рег. 01201461935, Таганрог, НИИ МВС ЮФУ, шифр «Хвеша-2», 2015.

Апробация работы. Основные результаты, представленные в диссертации, докладывались и обсуждались на всероссийских и международных научно-технических конференциях: IX, X, XI, XII ежегодных научных конференциях студентов и аспирантов базовых кафедр ЮНЦ РАН, Ростов-на-Дону; 2-й, 3-й, 4-й Всероссийских научно-технических

конференциях «Суперкомпьютерные технологии» (СКТ-2012, СКТ-2014, СКТ-2016), с. Дивноморское, Геленджик; Ш-ей международной заочной научно-практической конференции «Академическая наука - проблемы и достижения», Москва, 2014г.; 6-й и 8-й Всероссийских мультиконференциях по проблемам управления (МКПУ-2013, МКПУ-2015), с. Дивноморское, Геленджик.

Наиболее значительными публикациями по теме диссертации являются:

1. Чкан, А.В. Метод поиска итераций с переполнением разрядной сетки в алгоритмах быстрого преобразования Фурье при обработке данных в формате с фиксированной запятой [Текст] / А.В. Чкан // Вестник компьютерных и информационных технологий. - М.: Издательский дом «Спектр», 2016 г. - №7 (146), С. 41-47. (ведущий рецензируемый журнал, входит в перечень ВАК);

2. Чкан, А.В. Масштабирование данных с фиксированной точкой в процедуре быстрой свертки [Текст] / А.В. Чкан, О.В. Ершова, Е.В. Кириченко, Е.А. Семерников // Журнал «Радиотехника». - М.: «Радиотехника», 2015 г. -№4. - С. 66-72. (ведущий рецензируемый журнал, входит в перечень ВАК);

3. Чкан, А.В. Ошибки усечения результатов арифметических операций с фиксированной точкой в алгоритмах БПФ [Текст] / А.В. Чкан, О.В. Ершова, Е.В. Кириченко, Е.А. Семерников // Известия ЮФУ. Технические науки. -Таганрог: Изд-во ЮФУ, 2014г. - №12(161). - С. 138-148. (ведущий рецензируемый журнал, входит в перечень ВАК);

4. Чкан, А.В. Особенности обработки целочисленных данных с фиксированной точкой при расчете диаграммы направленности фазированной антенной решетки [Текст] / А.В. Чкан, Е.А. Семерников, М.С. Кочерга // Высокопроизводительные вычислительные системы // Труды молодых учёных ЮФУ и ЮНЦ РАН. - Таганрог: Изд-во ТТИ ЮФУ, 2011. - С. 102-107;

5. Чкан, А.В. Организация вычислений и анализ обработки данных в конвейерном вычислителе БПФ на основе ПЛИС семейства УЫех [Текст] / А.В. Чкан, Е.А. Семерников, М.С. Кочерга // Материалы 2-й Всероссийской

научно-технической конференции «Суперкомпьютерные технологии» (СКТ-2012). - Ростов-на-Дону: Изд-во ЮФУ, 2012. - Т.1 - С. 125-130;

6. Чкан, А.В. Источники погрешностей и способы их минимизации в алгоритме БПФ при обработке данных с фиксированной запятой [Текст] / А.В. Чкан // Материалы 6-й Всероссийской мультиконференции по проблемам управления (МКПУ-2013). - Ростов-на-Дону: Изд-во ЮФУ, 2013г. - С. 185-187.

По результатам исследований получено свидетельство о государственной регистрации программ для ЭВМ №2016663176, РФ. Программный модуль программных средств синтеза масштабируемых параллельно-конвейерных решений прикладных задач для многопроцессорной вычислительной системы гибридного типа. Зарегистрировано в Реестре программ для ЭВМ 29.11.2016 г. Правообладатель: Федеральное автономное государственное учреждение высшего профессионального образования «Южный федеральный университет». Левин И.И., Дордопуло А.И., Гуленок А.А., Чкан А.В.

Личный вклад автора. Все представленные в диссертации результаты получены лично автором.

Структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников и двух приложений.

Положения, выдвигаемые на защиту:

- применение разработанных методов создания параллельных программ с масштабируемой разрядностью позволяет повысить удельную производительность РВС при решении задач цифровой обработки сигналов на основе быстрого преобразования Фурье;

- разработанные методы создания параллельных программ с масштабируемой разрядностью позволяют обеспечить заданную точность вычислений при решении задач цифровой обработки сигналов на РВС.

Результаты, выдвигаемые на защиту:

- метод создания параллельных программ для реализации БПФ на РВС для данных с фиксированной запятой, отличающийся от известных априорным определением итераций БПФ, требующих масштабирования;

- метод создания параллельных программ для реализации БПФ на РВС для данных с фиксированной запятой, отличающийся от известных поэтапным увеличением разрядности представления результатов вычислений в заданной группе итераций БПФ и масштабированием, с выбором максимально возможного числа значащих разрядов, на вычислительных этапах, требующих уменьшения разрядности данных;

- алгоритмы согласованной фильтрации с масштабируемой разрядностью для РВС, отличающиеся или априорным определением итераций с масштабированием, или поэтапным увеличением разрядности с последующим масштабированием, как для прямого, так и для обратного БПФ;

- алгоритмы двумерного БПФ и частотной фильтрации изображений с масштабируемой разрядностью для РВС, отличающиеся процедурой определения общего для всех строк (столбцов) входной двумерной матрицы коэффициента масштабирования.

В первой главе проведен анализ современных многопроцессорных вычислительных систем, предназначенных для цифровой обработки сигналов.

Сделан вывод о том, что РВС на базе ПЛИС обладают существенными преимуществами в сравнении с МВС традиционных архитектур, позволяя настраивать вычислительное поле системы под структуру алгоритма решаемой задачи и обеспечивать более высокую реальную производительность, близкую к пиковой, при решении вычислительно-трудоёмких и сильносвязанных задач ЦОС в режиме реального времени. Близкий к линейному рост производительности РВС при увеличении числа процессоров в системе позволяет предсказуемо и экономично подбирать аппаратные средства под поставленные вычислительные задачи.

Показано, что использование формата представления данных с фиксированной запятой при решении задач ЦОС на РВС значительно повышает

удельную и реальную производительности системы, однако требует контроля над точностью вычислений и возможными переполнениями разрядной сетки в условиях ограниченной и изменяемой разрядности представления данных на различных вычислительных этапах.

Одним из наиболее используемых алгоритмов при решении вычислительно-трудоёмких задач ЦОС является алгоритм БПФ, однако в ходе анализа методов реализации алгоритмов БПФ в вычислительных системах не были найдены методы, позволяющие обеспечивать высокую удельную производительность РВС при заданной точности вычислений.

Доказана необходимость разработки методов реализации алгоритмов БПФ на РВС для данных с фиксированной запятой, позволяющих повысить удельную производительность вычислительных система и обеспечить необходимую точность вычислений при решении задач ЦОС.

Во второй главе разработан метод создания параллельно-конвейерных программ для реализации БПФ на РВС для данных с фиксированной запятой, использующий априорное определение итераций БПФ, на которых требуется выполнять масштабирование данных с целью исключения возможных переполнений разрядной сетки при выполнении арифметических операций.

Разработан метод создания параллельно-конвейерных программ для реализации БПФ на РВС для данных с фиксированной запятой, использующий увеличение разрядности представления результатов вычислений в базовых операциях заданной группы итераций БПФ и масштабирование с выбором максимально возможного числа значащих разрядов на вычислительных этапах, требующих уменьшения разрядности данных.

Проведён сравнительный анализ предложенных методов реализации БПФ с существующими, который показал преимущества разработанных методов, позволяющих существенно повысить удельную производительность РВС и обеспечить требуемую точность получаемых результатов при решении задач ЦОС для данных с фиксированной запятой.

Разработана методика создания структурно-процедурных алгоритмов и параллельно-конвейерных программ для решения задач ЦОС на РВС, позволяющая применять разработанные методы с масштабируемой разрядностью операндов в различных алгоритмах и задачах обработки сигналов, использующих БПФ.

В третьей главе, на основе разработанных методов и методики создания структурно-процедурных алгоритмов и параллельно-конвейерных программ, разработаны алгоритмы согласованной фильтрации с масштабируемой разрядностью для РВС, основанные либо на априорном поиске итераций, требующих масштабирования, как для прямого, так и обратного БПФ, либо на поэтапном увеличении разрядности в заданной группе итераций БПФ и масштабировании с выбором максимально возможного числа значащих разрядов на всех вычислительных этапах, требующих уменьшения разрядности данных. Разработанные алгоритмы позволяют синтезировать экономичную с точки зрения аппаратных затрат, унифицированную вычислительную структуру для прямого и обратного БПФ. Под унифицированной вычислительной структурой понимается структура, топология которой не меняется при организации различных информационных потоков.

Проведён сравнительный анализ разработанных алгоритмов согласованной фильтрации с масштабируемой разрядностью, который показал, что реализация с априорным поиском итераций, требующих масштабирования, позволяет экономить аппаратные ресурсы ПЛИС в среднем на 20% для и 30% для FlipFlops или при использовании DSP-блоков на 3% для ЦШб, на 36% для FlipFlops и на 33% для DSP48E1, что, соответственно, позволяет повысить удельную производительность РВС, однако обладает высокой погрешностью получаемых результатов, которая зависит от количества входных отсчётов и числа операций масштабирования, используемых при решении задачи ЦОС. Использование согласованной фильтрации с поэтапным увеличением разрядности и масштабированием позволяет существенно снизить погрешности получаемых результатов, в том числе и для большого числа входных отсчётов,

что делает целесообразным применение этого алгоритма для решения задач ЦОС с повышенным требованием к точности.

В четвёртой главе, на основе разработанных методов и методики создания структурно-процедурных алгоритмов и параллельно-конвейерных программ, разработаны алгоритмы двумерного БПФ и частотной фильтрации изображений с масштабируемой разрядностью для РВС, которые позволяют либо априорно, до начала расчёта БПФ по строкам (столбцам) матрицы изображений, определять общие для всех строк (столбцов) итерации, требующие масштабирования, либо использовать поэтапное увеличение разрядности в заданной группе итераций БПФ с последующим масштабированием по строкам (столбцам) матрицы на основе общего рассчитанного коэффициента, обеспечивая корректные одинаково отмасштабированные данные результирующего изображения и унифицированную вычислительную структуру для прямого и обратного БПФ.

Проведён сравнительный анализ разработанных алгоритмов частотной фильтрации изображений для РВС, который показал, что реализация с априорным поиском итераций, требующих масштабирования обеспечивает более высокую удельную производительность РВС, однако приводит к большим погрешностям получаемых решений. Использование реализации частотной фильтрации изображений с поэтапным увеличением разрядности и масштабированием, позволяет обеспечить более приемлемую точность получаемых результатов, с относительной погрешностью, не превышающей 1%, для разных размеров входных изображений.

Разработана библиотека программ, позволяющая использовать созданные алгоритмы с масштабируемой разрядностью при решении соответствующих задач ЦОС на РВС. Компоненты библиотеки написаны на языке высокого уровня СОЬЛМО. Взаимодействие пользователя с компонентами библиотеки и программным комплексом разработки приложений для РВС осуществляется с помощью разработанной прикладной программы, позволяющей организовать необходимый графический интерфейс.

Результаты диссертации внедрены в НИИ МВС ЮФУ (г. Таганрог), ООО «НИЦ СЭ и НК» (г. Таганрог), ОАО «РТИ» (г. Москва).

В заключении изложен основной научный результат диссертации, а также сформулированы теоретические и прикладные результаты диссертационной работы.

В приложениях приведены тексты программ, написанные на языке высокого уровня COLAMO и реализующие представленные в диссертации методы и алгоритмы; приведены копии актов о внедрении результатов диссертационной работы от организаций: НИИ МВС ЮФУ (г. Таганрог), ООО «НИЦ СЭ и НК» (г. Таганрог), ОАО «РТИ» (г. Москва).

1. АНАЛИЗ МЕТОДОВ И СРЕДСТВ РЕШЕНИЯ ЗАДАЧ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ НА РВС

В настоящее время технология цифровой обработки сигналов используется в различных технических областях:

- в средствах коммуникации и связи - коммутация, сжатие и обработка речевых сигналов, подавление шумов;

- в медицине - различные методы диагностики: рентгеноскопия, томография, ультразвук и др.;

- в промышленности - поиск нефтяных и газовых месторождений, полезных ископаемых;

- в научных направлениях - системы сбора, анализа и обработки данных (метеорологические, сейсмические и др.), моделирование различных процессов;

- в космических исследованиях - потоковая обработка и сжатие изображений и сигналов;

- в военной отрасли - гидро- и радиолокация, системы кодирования данных, системы интеллектуального управления техникой и оружием.

Список литературы диссертационного исследования кандидат наук Чкан, Андрей Викторович, 2016 год

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Каляев, И.А. Реконфигуриуемые мультиконвейерные вычислительные структуры [Текст] / И.А. Каляев, И.И. Левин, Е.А. Семерников, В. И. Шмойлов; под общ. ред. И.А. Каляева. - Изд. 2-е, перераб. и доп. - Ростов н/Д : ЮНЦ РАН, 2009. - 344 с. - ISBN 978-5-902982-61-6.

2. Гузик, В. Ф. Реконфигурируемые вычислительные системы: учебное пособие [Текст] / В.Ф. Гузик, И.А. Каляев, И.И. Левин; под общ. ред. И.А. Каляева. - Таганрог : ЮФУ, 2016. - 472 с. - ISBN 978-5-9275-1918-7.

3. https: //ru.wikipedia.org/wiki/FPGA.

4. Зотов, В.Ю. Проектирование встраиваемых микропроцессорных систем на основе ПЛИС фирмы Xilinx [Текст] / В.Ю. Зотов. - М. : Горячая линия -Телеком, 2006. - 520 с. - ISBN 5-93517-165-1.

5. Каляев, И.А. Реконфигурируемые вычислительные системы с высокой реальной производительностью [Электронный ресурс] / И.А. Каляев, И.И. Левин // Труды международной научной конференции "Параллельные вычислительные технологии" (ПаВТ'2009). Челябинск : ЮУрГУ, 2009. - С. 186195. - ISBN 978-5-696-03854-4. - Режим доступа:

http://omega.sp.susu.ru/books/conference/PaVT2009/papers/full_papers/018.pdf.

6. Дордопуло, А.И. Программное обеспечение для решения вычислительно трудоёмких задач на реконфигурируемых вычислительных системах [Текст] / А.И. Дордопуло, И.И. Левин // Материалы Второй Международной научной конференции"Суперкомпьютерные системы и их применение" (SSA'2008), 27-29 октября 2008. - Минск : ОИПИ НАН Беларуси, 2008. - С. 50-54.

7. Лайонс, Р. Цифровая обработка сигналов [Текст] / Ричард Лайонс; пер с англ. под ред. А. А. Бритова. - 2 изд. - М.: Бином-Пресс, 2006. - 656 с. - ISBN 5-9518-0149-4 (рус).

8. Сергиенко, А. Б. Цифровая обработка сигналов [Текст] : учеб. пособие / А. Б. Сергиенко - 3-е изд. - СПб. : БХВ-Петербург, 2011. - 768 с. - ISBN 978-50606-9.

9. Артамонов, Д.С. Метод оптимизации вычислительного процесса на реконфигурируемых вычислительных средах [Текст] / Д.С. Артамонов, М.Г. Путря // Информационные технологии и вычислительные системы. - М. : ИСА РАН, 2010, №3. - С. 19-26.

10. Бовкун, А.В. Автоматизированные методы повышения удельной производительности прикладных задач для реконфигурируемых вычислительных систем [Текст] / А.В. Бовкун // Известия ЮФУ. Технические науки. - Таганрог : Изд-во ТТИ ЮФУ, 2012. - №4. - С. 204-210.

11. ru.wikipedia.org/wiki/FFT.

12. Блейхут, Р. Быстрые алгоритмы цифровой обработки сигналов [Текст]: Пер. с англ. - М.: Мир, 1989. - 448с. - ISBN 5-09-001009-2.

13. Рабинер, Л. Теория и применение цифровой обработки сигналов [Текст] / Л. Рабинер, Б. Гоулд; пер. с англ. А. Л. Зайцева, Э. Г. Назаренко, Н. Н. Тетекина. - М. : Мир, 1978.

14. Айфичер, Э. С. Цифровая обработка сигналов [Текст] : практический подход [пер. с англ.] / Эммануил С. Айфичер, Барри У. Джервис. - 2-е изд. -М. : Вильямс, 2008. - 992 с. - ISBN 978-5-8459-0710-3 (рус.).

15. Гольденберг, Л. М. Цифровая обработка сигналов: Справочник [Текст] / Л. М. Гольденберг, Б. Д. Матюшкин, М. Н. Поляк. - М. : Радио и связь, - 1985. 312 с.

16. Афра, Б. DSP или FPGA? Как выбрать нужное устройство [Электронный ресурс] / Б.Афра, А.Кападийя // Электроника: Наука, Технология, Бизнес. - 2008. - №8 - С. 54-57. - Режим доступа: http://www.electronics.rU/files/article_pdf/0/article_488_493.pdf.

17. Воеводин, Вл.В. Вычислительное дело и кластерные системы [Текст] / Вл.В. Воеводин, С.А. Жуматий - М.: Изд-во МГУ, 2007. - 150 с. - ISBN 978-5211-05440-0.

18. Головкин, Б. А. Параллельные вычислительные системы [Текст] / Б. А. Головкин. - М. : Наука, 1980. - 519 с.

19. Воеводин, В. В. Параллельные вычисления [Текст] : [учебное пособие для студентов высших учебных заведений, обучающихся по направлению 510200 "Прикладная математика"] / В. В. Воеводин, Вл. В. Воеводин. - СПб. : БХВ-Петербург, 2004. - 608 с. - ISBN 5-94157-160-7.

20. Хорошевский, В. Г. Архитектура вычислительных систем: Учебное пособие [Текст] / В. Г. Хорошевский. - 2-е изд. перераб. и доп. - М. : МГТУ им. Н. Э. Баумана, 2008. - 520 с. - ISBN 978-5-7038-3175-5.

21. Беляев, А. А. Современные устройства цифровой обработки сигналов. Вместе или врозь? [Электронный ресурс] / А. А. Беляев, Т. В. Солохина, В. А. Юдинцев // Электроника: Наука, Технология, Бизнес. - 2009. - №1 - С. 28-35. -Режим доступа: http://www.electronics.ru/files/article_pdf/0/article_157_371.pdf.

22. Механов, В. Б. Особенности архитектуры универсальных микропроцессоров [Текст]: учебное пособие / В. Б. Механов. - Пенза : ПГУ, 2010. - 176 с.

23. http://www.intel.com.

24. http://www.kontron.com.

25. http://www.xilinx.com.

26. Витязев, С. В. Цифровые процессоры обработки сигналов [Электронный ресурс] / С. В. Витязев. - Рязань : РГРТУ, 2012. - Режим доступа : http://www.dspa.ru/cosvuz/VityazevSV/Chapter2_1 .pdf.

27. Шишков, А. Н. Цифровые сигнальные процессоры [Электронный ресурс] / А. Н. Шишков. - М. : МАИ, 2011. - Режим доступа:

http:// frela-mk.narod2.ru/lektsii/COSiCSP.pdf.

28. Проектирование систем цифровой и смешанной обработки сигналов [Текст] / под ред. Уолта Кестера. - М. : Техносфера, 2010. - 328 с. - ISBN 9785-94836-243-4.

29. http://www.commagility.com.

30. http://www.advantech.com.

31. http: //www.milandr.ru.

32. http://www.mcst.ru.

33. http://www.ti.com.

34. http://www.3l.com.

35. http://www.nxp.com.

36. http://www.analog.com.

37. http://multicore.ru.

38. Грушвицкий, Р.И. Проектирование систем на микросхемах с программируемой структурой [Текст] / Р.И. Грушвицкий, А.Х. Мурсаев, Е.П. Угрюмов. - 2-е изд., перераб. и доп. - СПб.: БХВ - Санкт-Петербург, 2006. -736 с. - ISBN 5-94157-657-9.

3 9. https: //ru.wikipedia.org/wiki/FPGA.

40. Попов, А. Ю. Проектирование цифровых устройств с использованием ПЛИС [Текст]: Учеб. пособие. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2009. - 80 с. - ISBN 978-5-7038-3317-9.

41. Тарасов, И. Возможности FPGA фирмы Xilinx для цифровой обработки сигналов [Электронный ресурс] / Илья Тарасов // Компоненты и технологии. 2007. - №5 - С. 68-74. - Режим доступа: http://www.kit-e.ru/assets/files/pdf/2007_05_68.pdf.

42. Макмуров, И. Выбор между микропроцессором и FPGA [Электронный ресурс] / Игорь Макмуров // Электронные компоненты. 2011. -№4 - С. 85-87. - Режим доступа:

http: //www.elcomdesign.ru/magazine/archive/magazine_67. html.

43. Тарасов, И. ПЛИС Xilinx и цифровая обработка сигналов. Особенности, преимущества, перспективы [Электронный ресурс] / Илья Тарасов // Электроника: Наука, Технология, Бизнес. 2011. - №3 - С. 70-74. -Режим доступа : http://www.electronics.ru/files/article_pdf/2/article_2788_434.pdf.

44. Угрюмов, Е. П. Цифровая схемотехника: учеб. пособие для вузов [Текст] / Е. П. Угрюмов. - 3-е изд., перераб. и доп. - СПб. : БХВ-Петербург, 2010. - 816 с. - ISBN 978-5-9775-0162-0.

45. http://www.alpha-data.com.

46. http://www.dinigroup.com.

47. http://www.dsol.ru.

48. http://www.insys.ru.

49. http://www.mlabsys.ru.

50. http://www.setdsp.ru.

51. http://www.mvs.sfedu.ru.

52. http://www.superevm.ru.

53. https://www.altera.com.

54. Каляев, И.А. Реконфигурируемые вычислительные системы [Текст] / И.А. Каляев, И.И. Левин, Е.А. Семерников // Гироскопия и навигация. - М.: Изд-во ЦНИИ «Электроприбор», 2009. ISSN 0869-7035 (спецвыпуск). - № 5. -С.13-26.

55. Чкан, А.В. Особенности обработки целочисленных данных с фиксированной точкой при расчете диаграммы направленности фазированной антенной решетки [Текст] / А.В. Чкан, Е.А. Семерников, М.С. Кочерга // Высокопроизводительные вычислительные системы. Труды молодых ученых ЮФУ и ЮНЦ РАН. - Таганрог: Изд-во ТТИ ЮФУ, 2011. - С. 102-107.

56. Чкан, А.В. Устройство для расчета диаграммы направленности фазированной антенной решетки [Текст] / А.В. Чкан, Е.А. Семерников, М.С. Кочерга // Высокопроизводительные вычислительные системы. Труды молодых ученых ЮФУ и ЮНЦ РАН. - Таганрог: Изд-во ТТИ ЮФУ, 2011. - С. 108-112.

57. Григорьев, Л.Н. Цифровое формирование диаграммы направленности в фазированных антенных решетках. - М.: Радиотехника, 2010. - 144 с., - ISBN 978-5-88070-243-5.

58. Левин, И.И. Язык программирования высокого уровня для многопроцессорной системы с программируемой архитектурой [Текст]: сборник трудов / И.И. Левин, В.Ф. Гузик, О.О. Сафронов // Распределенная обработка информации. Новосибирск, 1991.

59. Левин, И.И. Средства программирования реконфигурируемых вычислительных систем на основе ПЛИС Virtex-7 с использованием софт-архитектур [Текст] / И.И. Левин, А.И. Дордопуло, В.Б. Коваленко, В.А. Гудков, А.А. Гуленок // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. - 2015. - т.4, - №2. - С. 20-32 г.

60. Левин, И.И. Программирование реконфигурируемых вычислительных узлов на языке COLAMO [Текст]: Учебное пособие / И.И. Левин, А.И. Дордопуло, В.А. Гудков. 2-е изд. доп. - Ростов-на-Дону: Изд-во ЮФУ, 2016. -114 с.

61. Левин, И.И. Структурно-процедурная организация параллельных вычислений [Текст] / И.И. Левин // Материалы Четвертой Международной научной молодежной школы "Высокопроизводительные вычислительные системы". - Таганрог: Изд-во ТТИ ЮФУ, 2007. - С. 49-68.

62. Каляев, А.В. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений [Текст] / А.В. Каляев, И.И. Левин. - Москва: Изд-во "Янус-К", 2003. - 380 с.

63. http://www.softelectro.ru/ieee754.html.

64. http://neerc.ifmo.ru/wiki/index.php?title=&oldid=55454.

65. http://ru.wikipedia.org/?oldid=79197583.

66. Орлов, С. А. Организация ЭВМ и систем [Текст]: Учебник для вузов / С.А. Орлов, Б.Я. Цилькер. 2-е изд. - СПб.: Питер, 2011. - 688 с. - ISBN 978-549807-862-5.

67. Солонина, А. И. Алгоритмы и процессоры цифровой обработки сигналов [Текст] / А. И. Солонина, Д. А. Улахович, Л. А. Яковлев. - СПб. : БХВ - Петербург, 2002. - 464 с. - ISBN 5-94157-065-1.

68. Оппенгейм, А. Цифровая обработка сигналов [Текст] / А. Оппенгейм, Р. Шафер. - М.: Техносфера, 2006. - 856 с. - ISBN 5-94836-077-6.

69. Круг, П.Г. Процессоры цифровой обработки сигналов [Текст]: Учебное пособие. М. : МЭИ, 2001. - 128 с. - ISBN 5-7046-0778-0.

70. Чкан, А.В. Источники погрешностей и способы их минимизации в алгоритме БПФ при обработке данных с фиксированной запятой [Текст] / А.В. Чкан // Материалы 6-й Всероссийской мультиконференции по проблемам управления (МКПУ-2013). - Ростов-на-Дону: Изд-во ЮФУ, 2013г. - С. 185-187.

71. Чкан, А.В. Организация вычислений и анализ обработки данных в конвейерном вычислителе БПФ на основе ПЛИС семейства Virtex [Текст] / А.В. Чкан, Е.А. Семерников, М.С. Кочерга // Материалы 2-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии» (СКТ-2012). - Ростов-на-Дону: Изд-во ЮФУ, 2012. - Т.1 - С. 125-130. г.

72. Чкан, А.В. Моделирование тестовых сигналов для цифровой многоканальной системы обнаружения источников излучения [Текст] / А.В. Чкан, О.В. Ершова, Е.В. Кириченко, Е.А. Семерников // Радиотехника, Радиолокация и связь (Журнал в журнале). - М.: Радиотехника, 2014. - №1. С. 51-58.

73. Чкан, А.В. Особенности программного моделирования алгоритма БПФ для реализации в ПЛИС [Текст] / А.В. Чкан // Материалы 9-й ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН. -Ростов н/Д: Изд-во ЮНЦ РАН. - 2013. - С. 113-114.

74. Чкан, А.В. Особенности программной обработки данных с фиксированной запятой при моделировании алгоритмов, предназначенных для реализации в ПЛИС [Текст] / А.В. Чкан // Материалы 10-й ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН. - Ростов н/Д: Изд-во ЮНЦ РАН, - 2014. - С. 85-86.

75. Чкан, А.В. Библиотека математических операций для программного моделирования алгоритмов обработки данных с фиксированной запятой, предназначенных для реализации в ПЛИС [Текст] / А.В. Чкан // Труды 3-ей международной заочной научно-практической конференции «Академическая наука - проблемы и достижения». - Москва, - 2014 г. - С. 151-153.

76. Чкан, А.В. Метод поиска итераций с переполнением разрядной сетки в алгоритмах быстрого преобразования Фурье при обработке данных в формате

с фиксированной запятой [Текст] / А.В. Чкан // Вестник компьютерных и информационных технологий. - М.: Издательский дом «Спектр», 2016 г. -№7(146). - С. 41-47.

77. Чкан, А.В. Метод уточняющего поиска итераций с масштабированием в алгоритмах БПФ с прореживанием по времени и по частоте для данных с фиксированной запятой [Текст]/ А.В. Чкан // Материалы ХП-й ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН. -Ростов н/Д: Изд-во ЮНЦ РАН, 2016. - С. 113.

78. Чкан, А. В. Масштабирование данных с фиксированной точкой в процедуре быстрой свертки [Текст] / А. В. Чкан, О. В. Ершова, Е. В. Кириченко, Е. А. Семерников // Радиотехника, 2015. - N4 - С. 66-72.

79. Чкан, А.В. Априорная оценка количества итераций масштабирования в алгоритме БПФ для данных с фиксированной точкой [Текст] / А.В. Чкан // Материалы 11 -й ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН. - Ростов н/Д: Изд-во ЮНЦ РАН, - 2015. - С. 96.

80. Чкан, А.В. Управление масштабированием данных в процедуре согласованной фильтрации в зависимости от энергии сигнала [Текст] / А.В. Чкан, О.В. Ершова, Е.В. Кириченко, Е.А. . Семерников // Материалы 8-й Всероссийской мультиконференции по проблемам управления (МКПУ-2015). -Ростов-на-Дону: Издательство ЮФУ, - 2015. - Том 3. - С. 92-96.

81. Чкан, А.В. Ошибки усечения результатов арифметических операций с фиксированной точкой в алгоритмах БПФ [Текст] / А.В. Чкан, О.В. Ершова, Е.В. Кириченко, Е.А. Семерников // Известия ЮФУ. Технический науки. -Таганрог: Изд-во ЮФУ, 2014. - №12(161). - С. 138-148.

82. Чкан, А.В. Ошибки вычисления спектра при усечении результатов арифметических операций в алгоритмах быстрого преобразования Фурье с масштабированием данных [Текст] / А.В. Чкан, О.В. Ершова, Е.В. Кириченко, Е.А. Семерников // Материалы 4-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии» (СКТ 2016). - Ростов-на-Дону: Изд-во ЮФУ. - Том 1, С. 142-146.

83. Чкан, А.В. Ошибки усечения результатов арифметических операций с фиксированной точкой в алгоритмах БПФ [Текст] / А.В. Чкан, О.В. Ершова, Е.В. Кириченко, Е.А. Семерников // Материалы 3-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии» (СКТ-2014). -Ростов-на-Дону: Изд-во ЮФУ, 2014. - Т.1, С. 137-141.

84. Семерникова, Е.Е. Методы и средства создания прикладных программ с переменной разрядностью для реконфигурируемых вычислительных систем [Текст]: диссертация на соискание ученой степени кандидата технических наук, по специальности: 05.13.11 "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей", научный руководитель: д.т.н., проф. Левин И.И., дис. совет ЮФУ Д 212.208.24, - 2015. -187 с.

85. Гудков, В.А. Транслятор модифицированного языка программирования высокого уровня с неявным описанием параллелизма для реконфигурируемых вычислительных систем [Текст]: диссертация на соискание ученой степени кандидата технических наук, по специальности: 05.13.11 "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей", научный руководитель: д.т.н., проф. Левин И.И., дис. совет ТРТУ Д 212.208.24, - 2010. - 150 с.

86. Левин, И.И. Семантические особенности описания переменных на языке программирования COLAMO [Текст] / И.И. Левин, А.И. Дордопуло, В.А. Гудков // Труды Третьей международной научной конференции «Суперкомпьютерные системы и их применение. SSA'2010». - Республика Беларусь, Минск. - С. 176-179.

87. Макс, Ж. Методы и техника обработки сигналов при физических измерениях [Текст]: В 2-х томах. Пер. с франц. — М.: Мир, 1983. — Т. 2. 256 с.

88. Янакова, Е.С. Методы согласованной фильтрации широкополосных сигналов с минимальными временными задержками [Текст] / Е.С. Янакова // Проблемы разработки перспективных микро- и наноэлектронных систем - 2010.

Сборник трудов / под общ. ред. академика А.Л.Стемпковского. - М.:ИППМ РАН, 2010. - С. 478-481. - Режим доступа:

http://www.mes-conference.ru/data/year2010/papers/m10-103-46801.pdf.

89. Богнер, Р. Введение в цифровую фильтрацию [Текст] / Р. Богнер, А. Константинидис // М.: Мир, 1976. — 216 с.

90. Шахтарин, Б. И. Обнаружение сигналов [Текст] : учебное пособие : для студентов высших учебных заведений / Б. И. Шахтарин. - М.: МГТУ им. Н. Э. Баумана, 2005. - 487 с. - ISBN 5-7038-2647-0 : 100.

91. Методы компьютерной обработки изображений [Текст] / Под ред. В.А. Сойфера. 2-е изд. испр. - М.: ФИЗМАТЛИТ, 2003. - 784 с. - ISBN 5-92210270-2.

92. Обработка изображений и цифровая фильтрация [Текст] / Под ред. Т. Хуанга. - М.: Мир, 1979. - 320с.

93. Гонсалес, Р. Цифровая обработка изображений в среде Matlab [Текст] / Р. Гонсалес, Р. Вудс, С. Эддинс. - М.: Техносфера, 2006. - 616 с. - ISBN 5-94836-092-X.

94. Фисенко, В.Т. Компьютерная обработка и распознавание изображений [Текст]: учеб. пособие / В.Т. Фисенко, Т.Ю. Фисенко. - СПб: СПбГУ ИТМО, 2008. - 192 с.

95. Грузман, И.С. Цифровая обработка изображений в информационных системах [Текст]: Учебное пособие/ И.С.Грузман, В.С. Киричук, В.П. Косых, Г.И. Перетягин, А.А. Спектор. - Новосибисрк: Изд-во НГТУ, 2000. - 168 с.

96. Нуссбаумер, Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток [Текст]: Пер. с англ. - М.: Радио и связь, 1985. - 248 с.