Надо написать алгоритм КИХ фильтрации. Особенность процесса такова, что сигнал выдается фрагментами (начиная от 64 отсчетов).Светрку реализовили через БПФ в нескольких вариантах (overlap&save, overlap&add), но необходимой производительности достичь не удалось (получается в 2-8раз медленнее чем у существующих программ). Причем у программ-аналогов загрузка процессора практически не зависит от длины импульсной характеристики, а у нас - чем больше длина ИХ, тем больше времени требуется на обработку. Думали может БПФ медленное, заменили на Intel FFT которое в 10 раз быстрее общепринятых алгоритмов, но это существенно не помогло. Осталось попаробовать метод блоков переменной длины, но не совсем понятно как это работает. Что можно было бы сделать?

Понял не все из проблемы, но вроде бы понял то, что обработка идет блоками по 64 отсчета. ИХ фильтра судя по всему тоже должна быть примерно такого порядка. В этом случае БПФ наверное где-то 64-256 точек. А в этом случае выигрыша от фильтрации на базе перемножения спектров через БПФ и ОБПФ вроде и не должено получаться и то что Вы говорите вроде так и должно получаться. Если бы задача сводилась к использованию БПФ от нескольких тысяч, то тогда выигрыш почувствовали.

Забыл добавить - ИХ длинная >130тис. Выиграш есть конечно по сравнению с простыми алгоритмами - но все равно не то.

а Вы CUDA попробуйте.

...ну и что? Вы что, после каждого приращения буфера на 64 сэмпла делаете новое FFT на 4096(допустим) отсчета?

А откуда Вам знать, что там именно так сделано?

Даже не знаю, что сказать ...

Из цикла "аФФтАр пЕши ИСчО" ...


На 130 000 выигрыш FFT очень ощутим. Вот получили свои 130 000 и сделали один раз FFT...

[quote name='DRUID3' post='711474' date='Jan 31 2010, 17:42']...ну и что? Вы что, после каждого приращения буфера на 64 сэмпла делаете новое FFT на 4096(допустим) отсчета?

А откуда Вам знать, что там именно так сделано?
>>>>>>>>>А я и не знаю. Я только проверяю время обработки для своего алгоритма и программ-аналогов.


Из цикла "аФФтАр пЕши ИСчО" ...
>>>>>>>>> Ну это я не понял, но так для общей инфы: FFT которые описаны в общедоступной литературе, проигрывают в производительности некоторым оптимизированным алгоритмам, например FFTW, либо Intel MKL от 8 до 15 раз.

а Вы CUDA попробуйте.
>>>>> да я в курсе, но надо на СPU а не на GPU

Ну а вы оптимизацией подобных вычислительных алгоритмов раньше занимались? Опыт имеется?
"у существующих программ" решение вылизано. За вас в конференции никто это не сделает.
Хотите теории - Блейхут, "Быстрый алгоритмы цифровой обрабогтки ". Только вам это ни к чему IMHO.

Да не в Блейхуте дело, есть подозрение, что ребята сами не понимают что делают...

Вот меня эта фраза пугает... Ну и что, что фрагментами?

У меня тоже есть такое подозрение. Поэтому не могу исключить, что прочитав Блейхута они поймут, как использовать FFT для их фильтрации наиболее успешно. Понятно что алгоритмы коротких сверток Винограда им скорее всего не потребуются.

Ой, какие все пафосные, аж страшно...

Странный подход. Если раньше не занимались - то что, и пробовать нельзя?

Никто и не просил ДЕЛАТЬ что-либо за меня. Хотелось просто услышать мнения по поводу быстрых алгоритмов свертки и особенностей их применения для данной конкретной задачи, особенности которой в следующем:
а) входной сигнал поступает короткими блоками (64...2048)
б) импульсная характеристика имеет очень большую длину по сравнению с длиной блока (100000...500000)
в) обработка идет в реальном времени, т.е. на выход сигнал нужно выдавать блоками такой же длины, что и входные блоки, причем в ответ на каждый входной блок нужно выдать один выходной до того, как придет следующий входной блок (собственно, этот существенный момент не был упомянут ранее, что возможно и вызвало столь странную реакцию отвечающих). И еще один момент: чем короче блоки, тем чаще они поступают на вход и тем меньше времени на обработку.


Не поверите - читал. Очень хорошая и полезная книга. Кстати, после Блейхута были и другие люди, тоже занимавшиеся проблемой быстрых сверток...

Это вы к чему? Алгоритмы Винограда, как я понимаю, эффективнее для ОЧЕНЬ коротких сверток (пример со сверткой векторов длиной 2 и 3 действительно поучителен), и то еще вопрос, нужно ли стремиться уменьшать количество именно умножений за счет сложений, в то время как бОльшую часть времени занимают операции чтения-записи







Нет, делаю одно FFT на 64 отсчета. Алгоритм overlap-discard (то, которое "перекрытие с накоплением" у Блейхута) со сложением в частотной области и обратное FFT на те же 64 отсчета. Поэтому то, что

меня не сильно волнует.

130000 у меня есть до начала процесса обработки, FFT над ним я делаю один раз и далее все время использую при обработке каждого входного блока. Основная вычислительная работа - это умножение и суммирование в частотной области, время вычисления FFT по сравнению с ним - всего ничего...

Я решал похожую задачу (корреляция 2-х последовательностей длиной 16к отсчетов) следующим образом:
- Общую корреляцию разбивал на короткие (1к) блоки
- Вычислял корреляции этих блоков через бпф-перемножение спектров-обпф
- Результаты суммировал с перекрытием
С точки зрения числа операций выигрыша никакого. Только экономия памяти.

В вашем случае можно поступить аналогично исходя из размера входного блока:
Скажем, для 64-х входных отсчетов и длиной фильтра 130000 нужно вычислить
ceil(130000/64) = 2032 сверток. бпф-обпф размера 128 по основанию 2 займет ~ 1792 комплексных умножений-сложений. (За одно комплексное бпф вычисляется спектры 2-х вещественных последовательностей). Вычисление кроссспектра 6 вещ * 4 вещ + (если спектры не разделять) на точку. Или 390 вещ * 260 вещ +. Это явно меньше, чем затраты на бпф. Ну и на перекрытие с суммированием потребуется 63 вещ сложения.
Итого на всю свертку
2032*1792 = 3641344 комплексных */+ прямое-обратное дпф
2032*390 = 792480 вещественных * для вычисления кросспектра
2032*(260+63) = 656336 вещественных + для вычисления кросспектра и 64-х отсчетов результата.
Очевидно, что основные вычисления приходятся на преобразования. На перемножение спектров нужно не больше 5-10% всех вычислений.


Конечно, можно представить эту свертку набором совсем коротких сверток и выполнять все вычисления без дпф через алгоритмы быстрых сверток. Это даст дополнительную экономию времени только если операция умножения выполняется дольше сложения (нет аппаратного умножителя). Но скорее всего выигрыш будет незначительным...

Сообщение отредактировал thermit - Feb 1 2010, 11:34

Спасибо за ответ по сути!
Однако же, Вы не совсем правы
Во-первых, прямое БПФ размера 2*М, где М-длина блока, у меня вычисляется всего один раз - для каждого входного блока, т.к. БПФ импульсной характеристики я считаю перед началом процесса (импульсная характеристика разбивается на перекрывающиеся блоки длины 2*М).
Во-вторых, обратное БПФ того же размера у меня вычисляется, как ни удивительно это звучит, тоже всего один раз - за счет суммирования перекрывающихся результатов сверток в частотной области (см. статью: http://www.ramsete.com/Public/Presentations/mohonk_2003.pdf)
Таким образом, для каждого входного блока имеем при М=64:
1) БПФ+ОБПФ размера 128 по основанию 2: 1792 комплексных умножений-сложений
2) Умножение спектров: 2032*128*(6 вещ *, 4 вещ+) = 1560576*, 1040384+
3) Суммирование перекрытий в частотной области: 2031*128=259968+
Ну так и сколько там того БПФ?

Пояснение. Схема overlap-discard для частичных сверток входного блока с перекрывающимися кусочками ИХ используется "внутри" общей схемы overlap-add для свертки входных блоков с целой ИХ (блоки входного сигнала берутся без перекрытия).

ЗЫ. Схема работает (это если вдруг у кого появятся подозрения что это мухлеж и нельзя обойтись одной парой коротеньких БПФ-ОБПФ на блок )

Cправедливо. Я описал общий алгоритм.В частности БПФ исходного сигнала можно вычислять 1 раз, а вторая компонента свертки, если она константа, может храниться уже в виде спектра.



Ничего удивительного. Результат, который Вы получаете не свертка, а ее маленький кусок.



Да. БПФ-а тут мало. Если сигналы вещественные, то спектры их сопряжены относительно 0.
Из 128-и отсчетов спектра можно использовать 65.
Кроме того, комплексное умножение хочет 4 вещественных умножения и 2 сложения.

Сообщение отредактировал thermit - Feb 1 2010, 15:29

По крайней мере после ваших разъяснений относительно того, что вы делаете, вопрос стал чуть меньше похожим на "у меня ничего не работает - почему"? Впрочем, разбираться, что именно вы делаете, всё равно лень. Что за быстрое обновление через каждые 64 точки при длине фильтра 130000. Возможно задача просто вами сильно переусложнена, так как если этот фильтр симметричный, как бывает часто, то только групповое время задержки этого фильтра составляет 65000 отсчетов.

Что касается Блейхута: я и писал, что вам скорее всего он может понадобитья только в качестве смазки для мозгов. Прочитали - вот и здорово. Конечно, книжка довольно старая, тем не менее.

Хотелось было что-то объяснить по поводу

но поскольку

то и я тоже не буду тратить время