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			Все float переведены в int. Грубая оценка быстродействия целочисленного алгоритма.

См. также

• Основная схема быстрого преобразования Фурье

— Корогодин Илья • 14:37, 16 сентября 2011 • нет комментариев

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

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

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