16.09.2011, Изучение быстродействия и оптимизация алгоритма БПФ
Korogodin (обсуждение | вклад) (Новая страница: «<accesscontrol>SuperUsers</accesscontrol> <summary [ hidden ]>Попытки ускорить БПФ на ARM</summary> Под исходные коды завед...») |
Admin (обсуждение | вклад) |
||
(не показаны 20 промежуточных версий 1 участника) | |||
Строка 1: | Строка 1: | ||
− | |||
<summary [ hidden ]>Попытки ускорить БПФ на ARM</summary> | <summary [ hidden ]>Попытки ускорить БПФ на ARM</summary> | ||
Строка 5: | Строка 4: | ||
Исследуется БПФ от 2048 точек. | Исследуется БПФ от 2048 точек. | ||
+ | |||
+ | Согласно изученной литературе, минимальное количество операций достижимо для БПФ размером <math>N=2^{2n}</math> ("четной степени двойки"). Для него: | ||
+ | :<math>3/8 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" | ||
Строка 11: | Строка 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. | + | | 0.3 |
+ | | Внешнее ОЗУ | ||
+ | | Исходный алгоритм с коэф, вх. и вых. данными во float | ||
+ | |||
+ | |- | ||
+ | | | ||
+ | | | ||
+ | | 0.3 | ||
+ | | Внешнее ОЗУ | ||
+ | | Входные данные 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 и менять разрядность и тип переменных в функции (уменьшать время умножения и сложения).
По произведенным оценкам 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).
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.