Подбор БПФ-ветвлений методом bruteforce, кто слышал о таком?, оптимизейшн Опции

[tmtlib]

Давным-давно смотрел PDF, в котором рассказывалось о применении метода грубого перебора для поиска оптимальной конфигурации БПФ. Сейчас хотел заняться, но ничего не нашёл. Может кто-нибудь видел подобное?

Предыстория такова. Я сделал тупую программку, которая берёт простую корреляцию с синусом (суммы), а затем с учётом того, что тригонометрические таблицы с ограниченной точностью тасует их и разбивает на слагаемые (30+30 = можно использовать как 60 или даже как 59 и 61). Вначале мне казалось, что использование такого "округления" коэффициентов в области медленного изменения синуса могло бы дать прирост производительности. Плюс таблица - это четверть периода синуса, что дополнительно уменьшает количество перемножений. Но не дооптимизировался даже до простого radix-2! Умножений получилось раз в 10 больше. Конечно логичнее было бы начать с простенького фурье, но там уже надо как-то тасовать бабочки.

[phantom]

Если вы программируете на интел-процессорах или AMD , советую взять готовое Intel MKL или IPP, и не придумавать велосипед, быстрее их вы все равно не напишите. Кроме того, оно будет работать быстро на всех процессорах, а не только на вашей машине. У AMD есть тоже библиотеки с БПФ, и даже фри, но по-моему чуть-чуть хуже.

[Alexey Lukin]

FFTW как раз использует перебор в поиске наиболее быстрого кода.

[анатолий]

Оптимальная конфигурация БПФ- это та, что работает. Или лучшая из двух, что работают.
Это из моего опыта поиска оптимальных конфигураций БПФ за 30 лет.
Были у меня БПФ с программированием, микропрограммированием и на ПЛИС.
С программированием лучший БПФ - по основанию 2 или 4, так как организация выч. процесса съедает все экономии умножений и от прочих выкрутасов. В связи с этим часто лучше получается программирование в линию, когда соседние базовые операции склеиваются.
(Собственно, в основании 4 так и происходит).
От оснований 3,5,7,8,16 и т.п. - почти никакой пользы.
Правда, удостоверился, что по основанию 8 и 16 довольно неплохо получается в ПЛИС, да и то, если умножителей жалко.

[tmtlib]

Попробовал оптимизированное ДПФ с уменьшением разрядности табличного синуса до 11 бит - умножений становится меньше, но растёт какой-то шум. Про битность синуса написано в пейпере "Implementation of a Single FFT Processor". Что интересно, там написано что для 1024-точечного БПФ по данным 14-битного АЦП хорошо применимы 10-битные "twiddle factor" таблицы синусов. Может кому пригодится.

[alex_os]

Попробовал оптимизированное ДПФ с уменьшением разрядности табличного синуса до 11 бит - умножений становится меньше, но растёт какой-то шум. Про битность синуса написано в пейпере "Implementation of a Single FFT Processor". Что интересно, там написано что для 1024-точечного БПФ по данным 14-битного АЦП хорошо применимы 10-битные "twiddle factor" таблицы синусов. Может кому пригодится.

Вы на умножителях пытаетесь экономить ? Split Radix смотрели? Вроде там умножений меньше чем в radix4.

[AndeyP]

Давным-давно смотрел PDF, в котором рассказывалось о применении метода грубого перебора для поиска оптимальной конфигурации БПФ. Сейчас хотел заняться, но ничего не нашёл. Может кто-нибудь видел подобное?

http://www.spiral.net/ - лет 10 назад раздавали статический оптимизатор FFT, который собирал варианты кода заданным С компилятором, и измерял производительность. На выходе получался С код, якобы наиболее подходящий как для компилятора, так и для машины. Правда, особого толку от оптимизации заметно не было, но судя по сайту, они с тех пор здорово продвинулись...