Набір модулів для швидкого перетворення Фур’є

⇓Завантажити PDF

Праці 1 міжнародної конференції InfoCom’2015, 24-25 листопада 2015 р. − К.:НТУУ “КПІ”, ВПІ “Політехніка”. – 2015. − С. 52-53.

СЕРГІЄНКО А.А.,
СЕРГІЄНКО А.М.

НАБІР МОДУЛІВ ДЛЯ ШВИДКОГО ПЕРЕТВОРЕННЯ ФУРʼЄ

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

A set of soft IP cores for the Winograd small fast Fourier transform (FFT) is considered. The cores are intended for the high-speed pipelined FFT processors implemented in FPGA.

Вступ

Конвеєрні процесори швидкого перетворення Фурʼє (ШПФ) за основою, яка не дорівнює 2 ^k, k = 1,2 використовуються для передачі даних з ортогональним частотним розділенням каналів (OFDM), частотної обробки радіосигналів, виконання множення надвеликих цілих чисел та ін. Недоліками існуючих конвеєрних процесорів ШПФ, які використовують алгоритм зі взаємно-простими основами, є необхідність узгодження потоків даних між їх ступенями та високі апаратні витрати [1,2,3]. У доповіді розглядається проектування конвеєрних модулів ШПФ, які використовуються у процесорах ШПФ за взаємно-простими основами, що конфігуруються в ПЛІС.

Особливості реалізації конвеєрних процесорів у ПЛІС

Мінімальна тривалість тактового інтервалу T_C модуля, який зконфігуровано в ПЛІС, дорівнює затримці його критичного шляху, до якого входять послідовно з’єднані логічна таблиця (ЛТ), мережа розповсюдження переносу і мережа конфігурованих міжзʼєднань. Але слід врахувати, що затримка міжзʼєднань залежить від їх локальності, ступеня оптимізації розміщення ЛТ і може досягати 70-90% від T_C.

Віртуальні модулі конвеєрних процесорів ШПФ використовуються в ПЛІС більше десятиріччя і вони входять до складу бібліотек модулів САПР ПЛІС. Але вони, як правило, розраховані на чотиривходові ЛТ та велику кількість блоків множення. В результаті, такі процесори мають великі апаратні витрати у кількості сегментів конфігурованого логічного блоку (СКЛБ) і блоків множення, таких як DSP48, а також високе енергоспоживання. Крім того, затримка ступеня блоку множення приблизно удвічі перевищує затримку суматора на базі ЛТ. Високі параметри процесорів досягаються лише при ретельно розведених маршрутах міжзʼєднань та коли ЛТ мають оптимальні координати у ПЛІС.

За умови, коли не більше однієї ЛТ стоїть у критичному шляху, на основі чотиривходових ЛТ можлива побудова лише двохвходового мультиплексора або двовходового суматора. Якщо використовувати шестивходові ЛТ, які стоять у сучасних ПЛІС, можливості побудови різних арифметико-логічних схем значно зростають. На практиці встановлено, що компілятор-синтезатор Xilinx ISE в таких умовах синтезує чотиривходовий мультиплексор, трьохвходовий суматор, суматор з одним трьохвходовим мультиплексором.

Модулі для малоточкового ШПФ

Конвеєрний процесор ШПФ зі взаємнопростими основами має менші апаратні витрати і придатний для обробки послідовностей з іншою довжиною, ніж 2^k. Причому обчислення ШПФ для коротких послідовностей ефективно виконувати за алгоритмом Вінограда [3,4]. При цьому виникає проблема узгодження потоків
даних між модулями малоточкового ШПФ, оскільки група даних, яка видається одним модулем, не співпадає за числом даних та їх порядком з групою даних, яка примається іншим модулем [2]. Для узгодження двох модулів з паралельним виводом n даних та паралельним вводом m даних між ними слід встановити n⋅m блоків буферної памʼяті.

Найпростіше ця проблема вирішується тоді, коли за один такт блок видає чи сприймає лише одне дане. У цьому випадку період L-точкового ДПФ повинен дорівнювати L тактів, а не один, як у [2,3]. Тоді для організації покрокового введення та виведення даних з таких блоків вони повинні, по-перше, мати на своїх входах і виходах відповідні буферні схемі, по-друге, виконувати обчислення лише в кожному L-му такті.

При використанні методики побудови просторового графу синхронних потоків даних такі етапи синтезу конвеєрного процесора, як вибір ресурсів, складання розкладу, призначення операцій на ресурси і одержання структури виконуються за один крок, що дає змогу краще оптимізувати шукану конвеєрну структуру [5]. При цьому мінімізується як кількість суматорів, так і складність мультиплексорів на їх входах. Саме за цією методикою був розроблений набір модулів для малоточкового ШПФ. Кожен модуль виконує L-точкове ШПФ за алгоритмом Вінограда з періодом L тактів.

Результати реалізації модулів

Модулі малоточкового ШПФ описані мовою VHDL за методикою, викладеною в [5] і мають мінімальну кількість регістрів та суматорів. Причому вхідні та вихідні дані слідують у потрібному порядку. Для зменшення апаратних витрат та збільшення тактової частоти множення на постійні коефіцієнти виконується за допомогою зсувів та додавань множеного.

У таблиці 1 показані результати синтезу модулів для ПЛІС серії Xilinx Kintex-7 для 16-розрядних вхідних даних без особливих настроювань їх оптимізаціїї при синтезі, розміщенні та трасуванні.

Аналіз таблиці показує, що використання спеціалізованих блоків множення на константу дає змогу збільшити тактову частоту до 1,6 разів у порівнянні зі структурою з застосуванням інтегрованих блоків множення.

Табл. 1. Результати конфігурування процесорів у ПЛІС

Тактова частота модулів дорівнює частоті дискретизації сигналу. Вона є доволі високою і зменшується зі збільшенням складності модуля. Це розʼяснюється тим, що через складність розміщення та трасування на затримку у лініях звʼязку припадає 70-80% від загальної затримки у критичному шляху.

Висновки

Реалізація алгоримів малоточкового ДПФ у ПЛІС дає змогу одержати високопродуктивні конвеєрні процесори ШПФ з малими апаратними витратами. Встановлено, що модуль малоточкового ШПФ з уповільненням у L разів має велику тактову частоту і малі апаратні витрати за рахунок конвеєризації обчислень, використання власивостей шестивходових ЛТ ПЛІС, а також спеціалізованих блоків множення на константу. Деякі розроблені модулі ШПФ знаходяться у відкритому доступі для випробування та використання [6].

Перелік посилань

1. Lofgren J., Nilsson P. On hardware implementation of radix 3 and radix 5 FFT kernels for LTE systems // Proc. Norchip. −2011. −P. 1–4.

2. Greg Nash J. High-Throughput Programmable Systolic Array FFT Architecture and FPGA Implementations// International Conference on Computing, Networking and Communications (ICNC). − Honolulu, HI, Feb. 2014.

3. 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.

4. Нусбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. −М.: Радио и связь. −1985. −248 с.

5. Сергиенко А.М., Симоненко В.П. Отображение периодических алгоритмов в программируемые логические интегральные схемы //Электрон. моделирование. –2007.−T.29, № 2. −С. 49−61.

6. Sergiyenko A., Usenkov O. Pipelined FFT/IFFT 128 points processor. − Режим доступу: http://opencores.org/project,pipelined_fft_128

⇓Завантажити PDF