16.09.2011, Изучение быстродействия и оптимизация алгоритма БПФ

Материал из SRNS
Перейти к: навигация, поиск
 
(не показаны 17 промежуточных версий 1 участника)
Строка 1: Строка 1:
<accesscontrol>SuperUsers</accesscontrol>
 
 
<summary [ hidden ]>Попытки ускорить БПФ на ARM</summary>
 
<summary [ hidden ]>Попытки ускорить БПФ на ARM</summary>
  
 
Под исходные коды заведен проект [https://code.google.com/p/fft-for-arm-search fft-for-arm-search].
 
Под исходные коды заведен проект [https://code.google.com/p/fft-for-arm-search fft-for-arm-search].
  
Исследуется БПФ от 2048 точек. В изначальном варианте оценка свертки мс-ого сигнала для 10 частот - 300 мс.  
+
Исследуется БПФ от 2048 точек.  
  
Согласно изученной литературе, минимальное количество операций достижимо для БПФ размером четной степени двойки. Для него:
+
Согласно изученной литературе, минимальное количество операций достижимо для БПФ размером <math>N=2^{2n}</math> ("четной степени двойки"). Для него:
 
:<math>3/8 N log_2(N)</math> - число комплексных умножений;
 
:<math>3/8 N log_2(N)</math> - число комплексных умножений;
 
:<math>N log_2(N)</math> - число комплексных сложений.
 
:<math>N log_2(N)</math> - число комплексных сложений.
  
 +
Остаются два рычага власти: варьировать N и менять разрядность и тип переменных в функции (уменьшать время умножения и сложения).
 +
 +
По произведенным оценкам ARM'у на одно комплексное умножение (float+jfloat)*(float+jfloat) надо около 2.5-2.8 мкс (при расчете пришлось принять гипотезу исчезающе малого влияния суммирования на время вычисления). Отсюда, в изначальном варианте оценка свертки мс-ого сигнала для 10 частот - 300 мс.
  
 
{| class="wikitable" border="1"
 
{| class="wikitable" border="1"
Строка 16: Строка 18:
 
! ARM, ms
 
! ARM, ms
 
! Pentium, ms
 
! Pentium, ms
 +
! Расположение в приемнике
 
! Примечание
 
! Примечание
 +
 
|-
 
|-
 
| [https://code.google.com/p/fft-for-arm-search/source/detail?r=2 2]
 
| [https://code.google.com/p/fft-for-arm-search/source/detail?r=2 2]
 
| 23.3
 
| 23.3
| 0.28
+
| 0.3
 +
| Внешнее ОЗУ
 
| Исходный алгоритм с коэф, вх. и вых. данными во float
 
| Исходный алгоритм с коэф, вх. и вых. данными во float
 +
 
|-
 
|-
 
|  
 
|  
 
|  
 
|  
| 0.28
+
| 0.3
 +
| Внешнее ОЗУ
 
| Входные данные int: изменений не замечено
 
| Входные данные int: изменений не замечено
 +
 +
|-
 +
| [https://code.google.com/p/fft-for-arm-search/source/detail?r=3 3]
 +
| 84.5
 +
| 0.3
 +
| Внешнее ОЗУ
 +
| Все float переведены в int. Грубая оценка быстродействия целочисленного алгоритма.
 +
 +
|-
 +
| [https://code.google.com/p/fft-for-arm-search/source/detail?r=4 4]
 +
| 66
 +
| -
 +
| Внешнее ОЗУ
 +
| Все int переведены в int16. Грубая оценка быстродействия целочисленного алгоритма с int16.
 +
 +
|-
 +
| [https://code.google.com/p/fft-for-arm-search/source/detail?r=5 5]
 +
| 83
 +
| -
 +
| Внешнее ОЗУ
 +
| Все int переведены в int16, но значения ограничены 8 битами. Грубая оценка быстродействия целочисленного алгоритма с int16, но маленькими числами.
 
|}
 
|}
 +
 +
Перенос программы и данных в TCM выигрыша в быстродействии не дал.
 +
 +
== Бонус ==
 +
 +
In this figure we compare the performance in MFLOPS of a complex-complex 5*n*log2(n)/t, where n is the length of the sequence and t is the time for one transform. The computations are done on one processor of the IBM Winterhawk II with 375-MHz Power3-II processors. We compare FFTPACK 5 by P. Swarztrauber, NCAR (FFTPACK), the new Spectral Toolkit by Rodney James, NCAR (STK), FFTW by M. Frigio and S. Johnson, MIT (FFTW), and the IBM ESSL Library (ESSL).
 +
 +
<center>'''Performance comparison of new spectral toolkit library with existing libraries'''</center>
 +
[[Image:20110916_Fft.gif|center]]
 +
 +
== См. также ==
 +
* [http://fpga.parallel.ru/fft/ Основная схема быстрого преобразования Фурье]
 +
 +
[[Категория:НИИ КП]]
 
{{wl-publish: 2011-09-16 14:37:37 +0400 | Korogodin }}
 
{{wl-publish: 2011-09-16 14:37:37 +0400 | Korogodin }}

Текущая версия на 02:44, 18 марта 2013

Под исходные коды заведен проект fft-for-arm-search.

Исследуется БПФ от 2048 точек.

Согласно изученной литературе, минимальное количество операций достижимо для БПФ размером N=2^{2n} ("четной степени двойки"). Для него:

3/8 N log_2(N) - число комплексных умножений;
N log_2(N) - число комплексных сложений.

Остаются два рычага власти: варьировать N и менять разрядность и тип переменных в функции (уменьшать время умножения и сложения).

По произведенным оценкам ARM'у на одно комплексное умножение (float+jfloat)*(float+jfloat) надо около 2.5-2.8 мкс (при расчете пришлось принять гипотезу исчезающе малого влияния суммирования на время вычисления). Отсюда, в изначальном варианте оценка свертки мс-ого сигнала для 10 частот - 300 мс.

Ревизия ARM, ms Pentium, ms Расположение в приемнике Примечание
2 23.3 0.3 Внешнее ОЗУ Исходный алгоритм с коэф, вх. и вых. данными во float
0.3 Внешнее ОЗУ Входные данные int: изменений не замечено
3 84.5 0.3 Внешнее ОЗУ Все float переведены в int. Грубая оценка быстродействия целочисленного алгоритма.
4 66 - Внешнее ОЗУ Все int переведены в int16. Грубая оценка быстродействия целочисленного алгоритма с int16.
5 83 - Внешнее ОЗУ Все int переведены в int16, но значения ограничены 8 битами. Грубая оценка быстродействия целочисленного алгоритма с int16, но маленькими числами.

Перенос программы и данных в TCM выигрыша в быстродействии не дал.

[править] Бонус

In this figure we compare the performance in MFLOPS of a complex-complex 5*n*log2(n)/t, where n is the length of the sequence and t is the time for one transform. The computations are done on one processor of the IBM Winterhawk II with 375-MHz Power3-II processors. We compare FFTPACK 5 by P. Swarztrauber, NCAR (FFTPACK), the new Spectral Toolkit by Rodney James, NCAR (STK), FFTW by M. Frigio and S. Johnson, MIT (FFTW), and the IBM ESSL Library (ESSL).

Performance comparison of new spectral toolkit library with existing libraries
20110916 Fft.gif

[править] См. также

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.

Персональные инструменты
Пространства имён

Варианты
Действия
SRNS Wiki
Рабочие журналы
Приватный файлсервер
QNAP Сервер
Инструменты