Реалізація конвеєрних процесорів швидкого перетворення Фур’є у ПЛІС
8-а наук. конф. магістрантів та аспірантів “Прикладна математика та комп’ютинг”. – 20-22 квітня 2016. −Київ: НТУУ “КПІ”, Просвіта. —2016. —С. 128 –131.
Cтудентка Сергієнко А. А.
Національний технічний університет України «Київський політехнічний інститут»
РЕАЛІЗАЦІЯ КОНВЕЄРНИХ ПРОЦЕСОРІВ ШВИДКОГО ПЕРЕТВОРЕННЯ ФУР’Є У ПЛІС
Abstract
Anastasia Serhienko, student
Implementation of Pipelined FFT Processors in FPGA
A set of soft IP cores for the Winograd r-point fast Fourier transform (FFT) is considered. The cores are intended for the high-speed pipelined FFT processors, which are implemented in FPGA.
Вступ
Алгоритм швидкого перетворення Фур’є (ШПФ) широко використовується в багатьох системах обробки сигналів і зв’язку. Конвеєрні процесори ШПФ мають високу пропускну спроможність та мінімізовані апаратні витрати завдяки розпаралелюванню обчислень та своїй спеціалізації. Як правило, такі процесори виконують алгоритм за основою r = 2 k , k = 1, 2. [1]. Реалізація архітектури конвеєрного процесора ШПФ в сучасних програмованих логічних інтегральних схемах (ПЛІС) забезпечує як обробку сигналів у реальному часі, так і невелике споживання енергії.
У роботі пропонується методика розробки конвеєрного процесора ШПФ, в якому використовується алгоритм за довільною основою і пропускна спроможність дорівнює одному відліку сигналу за такт. Методика призначена для автоматичної генерації проектів таких процесорів з заданими характеристиками довжини перетворення та точності обчислень.
Структура конвеєрного процесора ШПФ
Конвеєрний процесор ШПФ зі взаємно-простими основами r має менші апаратні витрати і придатний для обробки послідовностей з іншою довжиною, ніж 2 k [2]. Причому обчислення ШПФ для коротких послідовностей ефективно виконувати за алгоритмом Вінограда [2,3]. При цьому виникає проблема узгодження потоків даних між модулями малоточковогоШПФ, оскільки група даних, яка видається одним модулем, не співпадає за числом даних та їх порядком з групою даних, яка приймається іншим модулем. Для узгодження двох модулів з паралельним виводом r 2 даних та паралельним вводом r 1 даних між ними слід встановити r 1 ⋅ r 2 блоків буферної пам’яті.
Метою роботи є створення процесорів ШПФ, які при незначних апаратних витратах мають високу пропускну спроможність, необхідні довжину перетворення, точність обчислень і конфігуруються у ПЛІС.
Найпростіше проблема узгодження потоків даних в процесорах ШПФ вирішується тоді, коли за один такт блок видає чи сприймає лише один комплексний відлік сигналу. У цьому випадку період r = L -точкового ШПФ повинен дорівнювати L тактів, а не один, як, наприклад, у процесорі, описаному в [2]. Тоді для організації покрокового введення та виведення даних з таких блоків вони повинні, по-перше, мати на своїх входах і виходах відповідні буферні схеми, по-друге, виконувати обчислення лише в кожному L-му такті.
При використанні методики побудови просторового графу синхронних потоків даних такі етапи синтезу конвеєрного процесора, як вибір ресурсів, складання розкладу, призначення операцій на ресурси і одержання структури виконуються за один крок, що дає змогу краще оптимізувати шукану конвеєрну структур [4]. При цьому мінімізується як кількість суматорів, так і складність мультиплексорів на їх входах. Саме за цією методикою був розроблений набір модулів для малоточкового ШПФ. Кожен модуль виконує L-точкове ШПФ за алгоритмом Вінограда з періодом L тактів.
Результати реалізації модулів
Модулі малоточкового ШПФ описані мовою VHDL за методикою, викладеною в [5] і мають мінімальну кількість регістрів та суматорів. Причому вхідні та вихідні дані слідують у потрібному порядку. Для зменшення апаратних витрат та збільшення тактової частоти множення на постійні коефіцієнти виконується за допомогою зсувів та додавань множеного.
У таблиці 1 показані результати синтезу модулів для ПЛІС серії Xilinx Kintex-7 для 16-розрядних вхідних даних без особливих настроювань їх оптимізаціїї при синтезі, розміщенні та трасуванні.
Аналіз таблиці показує, що використання спеціалізованих блоків множення на константу дає змогу збільшити тактову частоту до 1,6 разів у порівнянні зі структурою з застосуванням інтегрованих блоків множення DSP48. Тактова частота модулів дорівнює частоті дискретизації сигналу. Вона є доволі високою і зменшується зі збільшенням складності модуля. Це пояснюється тим, що через складність розміщення та трасування на затримку у лініях зв’язку припадає 70-80% від загальної затримки у критичному шляху. Детально про модулі ШПФ викладено у роботі [5].
Табл. 1. Результати конфігурування процесорів у ПЛІС
| Кількість точок | Апаратні витрати, ЛТ + DSP48 | Тактова частота, МГц |
| 3 | 245 | 640 |
| 3 | 201 + 2 | 433 |
| 4 | 215 | 548 |
| 5 | 945 | 435 |
| 8 | 1187 | 424 |
| 15 = 3⋅5 | 2131 | 346 |
| 16 | 3616 | 368 |
| 64 = 8⋅8 | 1985 + 4 | 338 |
| 128 = 8⋅16 | 5277 + 4 | 324 |
Побудова процесорів ШПФ
Розроблені модулі ШПФ, які описані мовою VHDL, зібрані у бібліотеку. Додатково інтерфейс кожного модуля описано мовою XML у форматі стандарту IP-XACT. Такий опис вміщує метадані про модулі, що спрощують їх інтеграцію у систему у багатьох САПР ПЛІС, які підтримують стандарт IP-XACT. Це такі метадані, як імена портів вводу-виводу, їх розрядність, код ідентифікації модуля, опис алгоритму, який реалізовано у модулі, ім’я та місцезнаходження файлу опису модуля,
графічне зображення модуля, описане мовою SVG тощо. Наприклад, параметр nb, який задає розрядність даних, описується як:
<spirit:parameters>
<spirit:parameter maximum="32" minimum="8" type="int">
<spirit:name>nb</spirit:name>
<spirit:displayName>nb</spirit:displayName>
<spirit:value spirit:id="uuid_cd7f1ae6_bfb2">16</spirit:value>
<spirit:vendorExtensions>
<kactus2:vector>
<kactus2:left>15</kactus2:left>
<kactus2:right>0</kactus2:right>
</kactus2:vector>
</spirit:vendorExtensions>
</spirit:parameter>
</spirit:parameters>
Тоді структурну схему конвеєрного процесора ШПФ можна зібрати у графічному редакторі САПР, у даному випадку − в системі Kaсtus2, скомпілювати у VHDL-опис на структурному рівні та сконфігурувати у ПЛІС будь-якої підходящої серії та виробника. Слід додати, що Kaсtus2 – це проект з відкритим кодом, розроблений в університеті м. Тампере і оснований на стандарті IP-XACT. В табл. 1 вказані результати синтезу таких процесорів ШПФ для кількості точок 64 і 128.
Висновки
Реалізація r-точкових модулів в ПЛІС забезпечує проектування високошвидкісних конвеєрних процесорів ШПФ з оптимізованим об’ємом апаратних витрат. Показано, що модуль ШПФ, який виконує r-точкове перетворення за r тактів має високу тактову частоту і невеликий обсяг апаратних витрат за рахунок конвеєрних обчислень, властивості 6-вхідних ЛТ, а також застосування спеціалізованих блоків множення. Розроблені модулі ШПФ використані для створення конвеєрних процесорів ШПФ з довжиною перетворення 64, 128, і 256.
Виконується розробка WEB-застосування, яке забезпечує автоматичний синтез конвеєрних процесорів ШПФ на основі розроблених модулів з використанням стандарту IP-XACT.
Література
1. Chahardahcherik, A., Kavian, Y. S., Strobel, O., Rejeb R. Implementing FFT Algorithms on FPGA // International Journal of Computer
Science and Network Security. −V.11. −No.11, −2011, −Р.148-156.
2. Quershi F., Garrido M., Gustafsson O. Unified architecture for 2, 3, 4, 5, and 7-point DFTs based on Winograd Fourier transform algorithm //
Electronic Letters. −V.49. −N.5. −2013. −P.348 – 349.
3. Нусбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. −М.: Радио и связь. −1985. −248 с.
4. Сергиенко А.М., Симоненко В.П. Отображение периодических алгоритмов в программируемые логические интегральные схемы //Электрон. моделирование. –2007.−T.29, No 2. −С. 49−61 .
5. Сергієнко А. А., Сергієнко А. М. Набір модулів для швидкого перетворення Фур’є InfoCom’2015, 24-25 листопада 2015, – К.: НТУУ “КПІ” ВПІ ВПК “Політехніка”. − 2015. −C.52-53.