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

Содержание к диссертации

Введение

1. Анализ методов и средств решения задач цифровой обработки сигналов на РВС 19

1.1. Современные многопроцессорные вычислительные системы ЦОС на базе универсальных процессоров 22

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

1.3. Современные многопроцессорные вычислительные системы ЦОС на базе ПЛИС 33

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

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

1.6. Выводы 64

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

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

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

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

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

2.5. Выводы 105

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

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

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

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

3.4. Выводы 135

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

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

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

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

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

4.5. Выводы 166

Заключение 168

Список использованных источников

• Современные многопроцессорные вычислительные системы ЦОС на базе ПЛИС
• Сравнительный анализ методов реализации БПФ на РВС
• Алгоритм согласованной фильтрации с поэтапным увеличением разрядности и масштабированием
• Алгоритм частотной фильтрации изображений с поэтапным увеличением разрядности и масштабированием

Введение к работе

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

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

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

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

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

производительность РВС для этого класса задач существенно зависит от эффективности реализации БПФ.

Важным фактором, влияющим на удельную производительность

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

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

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

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

Объектом исследований является программное обеспечение

реконфигурируемых вычислительных систем.

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

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

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

1. провести анализ методов и средств реализации алгоритмов ЦОС на многопроцессорных вычислительных системах;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая ценность работы.

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

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

Реализация и внедрение результатов работы. Материалы диссертационной работы использовались при выполнении ряда НИОКР в НИИ МВС ЮФУ:

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

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

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

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

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

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

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

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

Личный вклад автора заключается в разработке методов создания параллельных программ с масштабируемой разрядностью для реализации на РВС алгоритмов быстрого преобразования Фурье, согласованной фильтрации, двумерного БПФ и частотной фильтрации изображений; создании на основании разработанных методов и алгоритмов библиотеки программ, которая может использоваться при решении практических задач ЦОС на реконфигурируемых вычислительных системах. Публикации. Основные положения диссертации опубликованы в 16 научных печатных работах: из них 7 статей, из которых 3 статьи опубликованы в ведущих рецензируемых научных журналах, входящих в Перечень ВАК РФ, а также тезисы и материалы 9 докладов на российских и международных научно-технических конференциях. По теме диссертации получено свидетельство о государственной регистрации программ для ЭВМ. Результаты работы отражены в 5 отчетах о НИОКР.

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

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

Современные многопроцессорные вычислительные системы ЦОС на базе ПЛИС

Цифровые сигнальные процессоры (англ. DSP) [26, 27] являются широко востребованным и постоянно развивающимся классом микропроцессоров, предназначенным для обработки в реальном масштабе времени потоков данных, представляющих собой оцифрованные аналоговые сигналы. DSP обладают свойствами как однокристальных микроконтроллеров (гарвардская архитектура, встроенная память команд и данных, развитые интерфейсы для работы с внешними устройствами), так и универсальных процессоров, в частности, с RISC-архитектурой (конвейерная организация, программно-аппаратная поддержка операций с плавающей или фиксированной запятой). Кроме того, к положительным качествам DSP следует отнести [27, 28]: – аппаратное ускорение сложных вычислительных операций, в частности, выполнение за один такт команды MAC (умножение с накоплением); – возможность одновременной выборки двух операндов с целью непрерывной загрузки накапливающего умножителя (MAC), что является следствием реализации гарвардской архитектуры DSP; – аппаратная поддержка циклических буферов (актуально для таких алгоритмов ЦОС как свёртка, фильтрация); – высокая точность представления операндов и результата (достаточный запас разрядности) на выходе вычислительных блоков (умножителя, сумматора), особенно в DSP с фиксированной запятой; – аппаратная поддержка циклов с автоматической проверкой условий завершения цикла (в среднем позволяет сократить время выполнения цикла на 20% в сравнении с использованием программной проверки завершения цикла).

Последующие развитие DSP в направлении роста производительности связано со следующими техническими решениями: – применением конвейеров для выполнения операций над данными; – выполнением команд по мере готовности данных и ресурсов для текущей команды (а не в порядке следования команд в программе), с последующим учётом фактической последовательности команд; – минимизацией распространения сигналов на большие расстояния по кристаллу за счёт разбиения исполнительного ядра процессора на кластеры и исполнением максимального числа операций внутри одного кластера; – кэшированием памяти данных и памяти команд и размещением кэшпамять первого уровня на одном кристалле с процессором для ускорения обмена данными процессора и кэша; – дополнением структуры процессора предсказателями ветвления программы, повышающими эффективность кэш-памяти за счёт снижения процента промахов кэша; – использованием памяти с многократным доступом (с возможностью выполнения нескольких обращений к памяти за такт); – расширением системы команд; – применением повышенной частоты тактирования для внутренних исполнительных устройств процессора для исключения возможных интервалов ожидания со стороны других устройств; – применением многоядерных структур; – наращиванием дополнительных операционных узлов и модулей (сумматоры, умножители, АЛУ и др.); – исполнением на одном кристалле с процессором дополнительных специализированных устройств и сопроцессоров, реализующих специальные дополнительные функции для ускорения решаемых задач; – увеличением количества одновременно передаваемой информации за счёт расширения шин передачи данных. В настоящее время развитие и грамотное использование достоинств DSP позволяет разрабатывать на их основе высокопроизводительные МВС для решения сложных вычислительных задач ЦОС.

Примерами разработчиков современных МВС цифровой обработки сигналов на базе DSP являются такие компании как «CommAgility» (Великобритания) [29], «Advantech» (США) [30], АО «ПКК Миландр» (г. Зеленоград) [31], АО «МЦСТ» (г. Москва) [32]. Британская компания «CommAgility» является ведущим мировым разработчиком встраиваемых модулей обработки сигналов на базе DSP, а также гибридных вычислительных модулей, предполагающих совместное использование DSP и ПЛИС. Модули выполняются в двух стандартных интерфейсах: AMC (Advanced Mezzanine Card) для использования в MicroTCA и AdvancedTCA, и VPX для военного и промышленного применения с использованием защищённых корпусов, предназначенных для эксплуатации в условиях суровой окружающей среды.

Одним из примеров вычислительного модуля ЦОС с применением DSP является модель «AMC-4C6678» (рис. 1.2). Модуль ЦОС «AMC-4C6678»: а) внешний вид; б) структурная схема Высокопроизводительный модуль «AMC-4C6678» выполнен в компактном форм-факторе AMC и включает в себя четыре восьмиядерных DSP «TMS320C6678» типа СнК компании «Texas Instruments» (TI) [33] с частотой каждого ядра 1.25 ГГц (всего 32 DSP ядра), выполняющих обработку в формате с плавающей или с фиксированной запятой. Общая пиковая производительность платы составляет 640 Гфлопс и 1280 GMACS. Каждый DSP оперирует с 64-битным блоком памяти DDR3-1600 SDRAM объёмом 2 Гб. Для внешнего доступа к каждому DSP плата использует коммутаторы гигабитного Ethernet и PCI Express (8 Гбит/c).

Примером гибридного вычислительного модуля ЦОС является модель «AMC-V7-2C6678» (рис. 1.3). Модуль «AMC-V7-2C6678» также выполнен в форм-факторе AMC и содержит два современных восьмиядерных DSP «TMS320C6678» и ПЛИС Xilinx Virtex-7 «XC7VX415T». Каждый DSP оснащён 2 Гб оперативной памяти DDR3-1333 SDRAM (64-бит), ПЛИС Virtex-7 работает с 1 Гб оперативной памяти DDR3-1250 SDRAM (32-бит). Использование интерфейсов Serial RapidIO, Ethernet (1 Гбит) и PCI Express позволяет обеспечивать высокоскоростной ввод/вывод данных на плате.

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

В первом варианте, показанном на рис. 1.29, отбрасывается 15 значащих разрядов, которые были добавлены в результате умножения на 16-разрядный поворачивающий множитель Re[ ] или Im[ ], который, по сути, является дробным числом, не превышающем единицы. Этот вариант соответствует первому варианту выбора разрядностей для выхода Д+1 (рис. 1.28). Во втором варианте (рис. 1.29), отбрасывается 16 значащих разрядов, что соответствует третьему варианту выбора разрядностей с масштабированием для выхода Д+1 (рис. 1.28). Таким образом, получаемые на выходе базовой операции БПФ значения ReTAl, ІтГД.1 и ReTAl, ІтГДІ всегда имеют одинаковый коэффициент масштабирования.

При этом если коэффициент масштабирования для итерации ite[\..It] определяется соотношением kit = 2 Rit, где It = log2 (N) - число итераций БПФ; Rlt - число отбрасываемых младших разрядов при масштабировании на итерации it, то коэффициент масштабирования для БПФ может быть рассчитан по формуле it it КБПФ = Y[kit = 2КБПФ , где ЯБПФ = 2Х . (1.5) и=\ и=\ Для получения правильных порядков представления чисел на выходе алгоритма БПФ после применения операций масштабирования все полученные результаты необходимо разделить на КБПФ или умножить на К ПФ = 2КБПФ. В работе [13] было предложено три основных метода исключения переполнений в алгоритме БПФ с помощью масштабирования данных. Первый метод заключается в контроле уровня входных данных и масштабировании промежуточных результатов на выходе каждой итерации БПФ (кроме последней). При этом модуль чисел на входе БПФ не должен превышать 2ь 2, где b - количество бит системной длины слова. Этот метод наиболее прост и удобен в применении и может быть использован при конвейерной обработке данных в ПЛИС. Однако метод является наименее точным, так как применяет операцию масштабирования на каждой итерации.

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

Третий метод заключается в проверке на переполнение результатов выполнения каждой базовой операции БПФ. Если на текущей итерации при выполнении отдельной БО обнаружится переполнение, то производится масштабирование всего ранее просчитанного массива данных. Данный метод является самым точным, сводя количество операций масштабирования к минимуму, но такой подход также исключает возможность конвейерной реализации в ПЛИС. Помимо описанных методов, в случаях, когда параметры входного сигнала [72] известны заранее, поиск итераций, на которых необходимо применить масштабирование, можно осуществлять с помощью программного моделирования [73, 74, 75]. Далее вычислительная система программируется в соответствии с полученной моделью. Такой подход минимизирует величину погрешности масштабирования, но не гарантирует полное исключение переполнений. При этом в случае смены параметров сигнала требуются повторное моделирование и реконфигурация системы, поэтому чаще всего используется при тестировании и отладке устройств ЦОС.

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

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

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

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

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

Таким образом, метод реализации БПФ на РВС с поэтапным увеличением разрядности представления результатов вычислений в заданной группе итераций БПФ и масштабированием, с выбором максимально возможного числа значащих разрядов, на вычислительных этапах, требующих уменьшения разрядности данных, можно сформулировать следующим образом: 1) Выбор первой группы итераций БПФ c it start по it end для расчёта с использованием Р ступеней вычислительного конвейера, где: it _ start = \; it _end \P + it_start-\)если(P + it_start-1) It; It, если (P + it _start -1) It, It = log2 (N) - общее число итераций БПФ. 2) Расчёт группы итераций c it start по it end алгоритма БПФ посредством заданного числа Р ступеней вычислительного конвейера с увеличивающейся на один бит разрядностью представления результатов базовых операций БПФ для каждой итерации (рис. 2.2). Если все итерации БПФ рассчитаны, то происходит выход из алгоритма БПФ. При этом в случае необходимости осуществляется транзит данных через оставшиеся ступени вычислительного конвейера (если число итераций БПФ It некратно числу ступеней конвейера Р или it _end (P + it _start -1)). 3) Если не все итерации БПФ рассчитаны, то производится масштабирование данных с выбором максимально возможного числа значащих разрядов (способ масштабирования описан выше) на выходе последней ступени вычислительного конвейера (на выходе базовых операций итерации it end) с целью приведения разрядности чисел к разрядности входов конвейерных вычислительных блоков, реализующих базовые операции на первой ступени вычислительного конвейера. Переход к п. 4). 4) Выбор следующей группы итераций БПФ для расчёта с помощью реализованных Р ступеней вычислительного конвейера и переход на п.2): it_start = it_start + P; [lit end + P),если(it end + P) It; it end =V } _ [It,если(it_end + P) It. В качестве примера использования метода рассмотрим реализацию БПФ на 1024 входных комплексных отсчёта (7V=1024, It = log2 (і024) = 10) с применением четырехступенчатого вычислительного конвейера, показанного на рис. 2.2: 1) С помощью четырех ступеней вычислительного конвейера производится расчёт с 1-й по 4-ю итерации БПФ (it_start = l по it_end = 4). 20-разрядные результаты 4-й итерации масштабируются с выбором максимально возможного числа значащих разрядов и поступают на вход первой ступени вычислительного конвейера. 2) Производится расчёт с 5-й по 8-ю итерации БПФ (it_start = 5 по it_end = 8). 20-разрядные результаты 8-й итерации масштабируются с выбором максимально возможного числа значащих разрядов и поступают на вход первой ступени вычислительного конвейера. 3) Производится расчёт с 9-й по 10-ю итерации БПФ (it_start = 9 по it_end = 10) с помощью первых двух ступеней вычислительного конвейера, после чего полученные результаты работы алгоритма БПФ транзитом проходят оставшиеся две ступени конвейера к выходу схемы. Коэффициент масштабирования КШФ для данного метода будет равен произведению коэффициентов масштабирования, вычисляемых по формуле (2.11), после каждого произведённого масштабирования данных на выходе последней ступени вычислительного конвейера: G G КБПФ = ПА = 2 КБПФ КБПФ = 2Х (2-12) где g = [l..G] - номер текущего масштабирования; G = ceil\—]-l количество произведённых операций масштабирования при вычислении БПФ; ceil{x) - операция округления вещественного числа х до целого в большую сторону; kg - коэффициент масштабирования, вычисляемый по формуле (2.11) для g-го этапа вычислений; Rg - число бит сдвига.

Для получения правильных порядков представления чисел на выходе БПФ все полученные результаты необходимо разделить на КБПФ.

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

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

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

Расчёт аппаратных затрат производился для ПЛИС Xilinx семейства Virtex-7. При расчёте учитывались все основные операции, используемые при реализации соответствующего метода в ПЛИС (арифметические, логические, управляющие, коммутационные и др.), и занимаемый ими аппаратных ресурс (LUTs, FlipFlops).

Погрешность получаемых результатов оценивалась в сравнении с эталонным расчётом БПФ для данных в формате с плавающей запятой двойной точности (стандарт IEEE 754-2008 [63]).

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

Общий алгоритм расчёта согласованной фильтрации для представленного на рис. 3.2 примера будет выглядеть следующим образом. 1) На основании входных данных Sex(n), ne[0..N-\\ в блоке поиска итераций с масштабированием определяются итерации, на которых будет выполняться масштабирование для прямого и обратного БПФ. 2) Вычислительный конвейер с помощью управляющих команд с настраивается на расчёт прямого БПФ, а блоки управляемого масштабирования - на масштабирование данных для прямого БПФ на выходе базовых операций, соответствующих найденным итерациям, требующим масштабирования. 3) Входные данные и комплексные поворачивающие множители Wt, соответствующие текущей итерации, загружаются в первую ступень вычислительного конвейера, где производится расчёт итерации БПФ. После чего данные переходят во вторую 12, потом в третью 13 ступени вычислительного конвейера, где рассчитываются две последующие итерации. При этом блоки управляемого масштабирования «М» в соответствии с командами ки либо выполняют, либо не выполняют масштабирование, приводя текущие данные к требуемой разрядности. 4) Если не все итерации БПФ были рассчитаны, то данные снова поступают на вход первой ступени вычислительного конвейера /1, и выполняются действия в соответствии с пп. 3) и 4) алгоритма, пока не будет произведён расчёт всех итераций БПФ. В случае если расчёт всех итераций БПФ был завершён на ступени вычислительного конвейера, не равной последней, то через оставшиеся ступени конвейера данные проходят транзитом без изменений в соответствии с управляющей командой tit (рис. 3.2). 5) Полученный в результате расчёта прямого БПФ комплексный спектр входного сигнала SEn0(m), me[0..N-1] умножается на комплексно сопряжённый спектр эталонного сигнала Ё(т), а рассчитанные 32-разрядные произведения приводятся к 16-разрядным значениям с помощью выбора диапазона разрядов, начиная с 31-го по 16-й биты. 6) Вычислительный конвейер с помощью управляющих команд с настраивается на расчёт обратного БПФ, а блоки управляемого масштабирования - на масштабирование данных для обратного БПФ. 7) В соответствии с пп. 3), 4) производится расчёт обратного БПФ. Коэффициент масштабирования для изложенного алгоритма реализации согласованной фильтрации (СФ) можно рассчитать заранее по следующей формуле: КСФ=Ы- КШФ КОШФ, (3.5) где N - масштабирующий множитель, равный числу входных отсчётов, для расчёта обратного БПФ с помощью прямого БПФ (формула (3.1)); КБПФ 117 коэффициент масштабирования для прямого БПФ, рассчитанный по формуле (1.5), КОШФ - коэффициент масштабирования для обратного БПФ, рассчитываемый так же, как и КШФ. Таким образом, формула (3.5) запишется как КСФ=Ы-2 КБПФ 2" ф = N 2 {КБПФ+КОБПФ), где ЯШФ - число итераций с масштабированием для прямого БПФ, рассчитанных по формуле (2.9); ЯОБПФ - число итераций с масштабированием для обратного БПФ, рассчитанных по формуле (3.4).

Для получения правильных порядков представления чисел на выходе алгоритма согласованной фильтрации после использования масштабирования все полученные результаты необходимо разделить на КСФ или умножить на: K-L = — 2{Кшф+кБПф). (3.6)

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

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

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

Для снижения погрешностей, связанных с масштабированием, и повышения точности получаемых результатов при вычислении согласованной фильтрации (СФ) был предложен алгоритм СФ для РВС на основе метода реализации БПФ, с поэтапным увеличением разрядности в группе итераций и масштабированием с выбором максимально возможного числа значащих разрядов. Алгоритм включает в себя следующие этапы. 1) Расчёт алгоритма прямого БПФ в соответствии с методом поэтапного увеличения разрядности в заданной группе итераций БПФ и масштабирования (подраздел 2.2 диссертации). 2) Умножение полученного комплексного спектра ББПФ{т):, т є [0..N -1] входной последовательности S ri), п є [0..N -1] на комплексно-сопряжённый спектр эталонного сигнала Ё{т), т є [0..N -1]. 3) Приведение разрядности рассчитанных значений реальной и мнимой части комплексных произведений спектров SEn0{m)-E{m) к разрядности входов КВБ, реализующих БО на первой ступени вычислительного конвейера, с помощью операции масштабирования с выбором максимально возможного числа значащих разрядов в соответствии с описанным в параграфе 2.2 способом масштабирования на основе формулы (2.11). 4) Переключение конвейерных вычислительных блоков, реализующих БО БПФ в режим расчёта обратного БПФ. 5) Расчёт алгоритма обратного БПФ на основе прямого БПФ в соответствии с методом поэтапного увеличения разрядности в заданной группе итераций БПФ и масштабирования (параграф 2.2 диссертации).