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



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

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.

УДК 004.383

Вступ

Конвеєрні процесори швидкого перетво­рен­ня Фурʼє (ШПФ) за основою, яка не дорівнює ${{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 andradix 5 FFT kernels for LTE systems // Proc. Norchip. -2011. -P. 1–4.

  2. GregNash 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. SergiyenkoA., Usenkov O. Pipelined FFT/IFFT 128 points processor. - Режим доступу: http://opencores.org/project,pipelined\_fft\_128
Jun 13, 2016