10.14489/vkit.2018.01.pp.044-050

DOI: 10.14489/vkit.2018.01.pp.044-050

Чкан А. В., Михайлов Д. В.
ПРИМЕНЕНИЕ МАСШТАБИРУЕМОЙ РАЗРЯДНОСТИ ДАННЫХ ПРИ ПРОГРАММНОЙ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
(c. 44-50)

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

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

Chkan A. V., Mikhailov D. V.
APPLICATION OF SCALABLE DIGIT CAPACITY OF DATA IN CASE OF PROGRAM IMPLEMENTATION OF THE FAST FOURIER TRANSFORM ON RECONFIGURABLE COMPUTING SYSTEMS
(pp. 44-50)

Abstract. Use of a format of representation number with the fixed-point in case of program implementation of algorithms of the fast Fourier transform (FFT) on the reconfigurable computing systems (RCS) allows saving significantly computing resources of field-programmable gate array (FPGA). However the narrow dynamic range of the fixed point requires monitoring of the intermediate results of arithmetical operations regarding possible overflowings of a bit grid and growth of the error of computation connected to scaling at different computing stages. As any of the existing methods of FFT realization doesn't allow to reduce number of the involved computing resources of FPGA without essential loss of calculation accuracy, the new methods of the fast Fourier transform realization on RCS which allow providing the high specific capacity and acceptable calculation accuracy have been developed. The first method is based on aprioristic search of the iterations demanding scaling and the subsequent scaling only on the chosen iterations. The method allows involving considerably smaller number of the computing resources of FPGA in comparison with the existing methods when ensuring the required calculation accuracy. The second method is based on stage-by-stage increase of a bit grid of results representation of FFT base operations by one bit. In comparison with the first method the best calculation accuracy for tasks with a large number of entrance data is provided, however the bigger number of computing resources is involved. The developed methods allow to exclude overflowings of a bit grid and to provide required calculation accuracy for different tasks of digital signal processing using FFT algorithms.

Keywords: Fast Fourier transform; Digital signal processing; Reconfigurable computing systems; Field-programmable gate array; Pipeline processing; Fixed point; Scaling; Methods of overflow elimination.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

А. В. Чкан, Д. В. Михайлов (ООО «Научно-исследовательский центр супер-ЭВМ и нейрокомпьютеров», Таганрог, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

A. V. Chkan, D. V. Mikhailov (Supercomputers and Neurocomputers Research Center, Taganrog, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Гузик В. Ф., Каляев И. А., Левин И. И. Реконфигурируемые вычислительные системы: учеб. пособие / под общ. ред. И. А. Каляева. Таганрог: ЮФУ, 2016. 472 с.
2. Зотов В. Ю. Проектирование встраиваемых микропроцессорных систем на основе ПЛИС фирмы Xilinx. М.: Горячая линия–Телеком, 2006. 520 с.
3. Каляев И. А., Левин И. И. Реконфигурируемые вычислительные системы с высокой реальной производительностью [Электронный ресурс] // Параллельные вычислительные технологии (ПаВТ’2009): тр. Междунар. науч. конф. Челябинск: ЮУрГУ, 2009. С. 186 – 195. URL: http://omega.sp.susu.ru/books/con-ference/PaVT2009/papers/full_papers/018.pdf (дата обращения: 18.05.2017).
4. Дордопуло А. И., Левин И. И. Программное обеспечение для решения вычислительно трудоемких задач на реконфигурируемых вычислительных сис-темах // Суперкомпьютерные системы и их примене-ние (SSA’2008): матер. II Междунар. науч. конф., 27 – 29 октября 2008. Минск: ОИПИ НАН Беларуси, 2008. С. 50 – 54.
5. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов / пер. с англ. А. Л. Зай-цева и др. М.: Мир, 1978. 848 с.
6. Масштабирование данных с фиксированной точкой в процедуре быстрой свертки / О. В. Ершова и др. // Радиотехника. 2015. № 4. С. 66 – 72.
7. Чкан А. В. Метод поиска итераций с переполнением разрядной сетки в алгоритмах быстрого преобразования Фурье при обработке данных в формате с фиксированной запятой // Вестник компьютерных и информационных технологий. 2016. № 7. С. 41 – 47.
8. Левин И. И., Дордопуло А. И., Гудков В. А. Программирование реконфигурируемых вычисли-тельных узлов на языке COLAMO: учеб. пособие. 2-е изд. доп. Ростов н/Д: Изд-во ЮФУ, 2016. 114 с.

Eng

1. Kaliaev I. A. (Ed.), Guzik V. F., Levin I. I. (2016). Reconfigurable computing systems: textbook. Taganrog: IuFU. [in Russian language]
2. Zotov V. Iu. (2006). Design of embedded micro-processor systems based on FPGA made by Xilinx com-pany. Moscow: Goriachaia liniia–Telekom. [in Russian language]
3. Kaliaev I. A., Levin I. I. (2009). Reconfigurable computing systems with high real performance. Parallel computing technologies (PaVT’2009): proceedings of the Internatioanl scientific conference, (pp. 186-195). Cheliabinsk: IuUrGU. Available at: http://omega.sp. susu.ru/books/conference/PaVT2009/papers/full_papers/018.pdf (Accessed: 18.05.2017). [in Russian language]
4. Dordopulo A. I., Levin I. I. (2008). Software for solving computationally time-consuming tasks on recon-figurable computing systems. Supercomputer systems and their application (SSA’2008): proceedings of the Second International scientific conference, (pp. 50-54). 27 – 29 October 2008. Minsk: OIPI NAN Belarusi. [in Russian language]
5. Rabiner L., Gould B. (1978). Theory and appli-cation of digital signal processing. Moscow: Mir. [in Russian language]
6. Ershova O. V., Kirichenko E. V., Semernikov E. A., Chkan A. V. (2015). Scaling of fixed point data in a fast convolution procedure. Radiotekhnika, (4), pp. 66- 72. [in Russian language]
7. Chkan A. V. (2016). Method of bit overflow iteration search in algorithms of the fast Fourier transform for fixed-point data processing. Vestnik komp'iuternykh i informatsionnykh tekhnologii, 146(7), pp. 41-47. doi: 10.14489/vkit.2016.07.pp.041-047 [in Russian language]
8. Levin I. I., Dordopulo A. I., Gudkov V. A. (2016). Programming of reconfigurable computing nodes in COLAMO: textbook. 2nd Ed. (complemented). Rostov-on-Don: Izdatel'stvo IuFU. [in Russian language]

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

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

Для заказа скопируйте doi статьи:

10.14489/vkit.2018.01.pp.044-050

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2018.01.pp.044-050

and fill out the form