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

<accesscontrol>SuperUsers</accesscontrol>

Под исходные коды заведен проект 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.28	Исходный алгоритм с коэф, вх. и вых. данными во float
		0.28	Входные данные int: изменений не замечено
3	84.5		Все float переведены в int. Грубая оценка быстродействия целочисленного алгоритма.

Бонус

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