Ответ 1
Недавно я нашел этот отличный PDF файл на построении высокопроизводительных БПФ Эриком Постщичем. Разработав несколько БПФ, я знаю, как трудно конкурировать с коммерческими библиотеками. Поверьте, у вас все хорошо, если ваш FFT всего в 4 раза медленнее Intel или FFTW, а не 40x! Однако вы можете конкурировать, и вот как.
Подводя итог этой статье, автор заявляет, что Radix2 FFT простые, но неэффективные, наиболее эффективной конструкцией является radix4 FFT. Еще более эффективным методом является Radix8, однако это часто не вписывается в регистры на CPU, поэтому Radix4 является предпочтительным.
БПФ могут быть построены поэтапно, поэтому для вычисления БПФ с 1024 точками вы можете выполнить 10 этапов Radix2 FFT (как 2 ^ 10 - 1024) или 5 этапов Radix4 FFT (4 ^ 5 = 1024). Вы можете даже вычислить БПФ с разрешением 1024 балла по этапам 8 * 4 * 4 * 4 * 2, если вы этого захотите. Меньше этапов означает меньшее количество чтения и записи в память (узким местом для производительности FFT является пропускная способность памяти), поэтому динамический выбор radix 4, 8 или выше является обязательным. Шаг Radix4 особенно эффективен, так как все веса равны 1 + 0i, 0 + 1i, -1 + 0i, 0-1i и код бабочки Radix4 могут быть записаны, чтобы полностью входить в кеш.
Во-вторых, каждый этап БПФ не является одним и тем же. На первом этапе веса все равны 1 + 0i. нет смысла вычислять этот вес и даже умножать на него, поскольку он комплексно умножается на 1, поэтому первый этап может выполняться без весов. Заключительный этап может также обрабатываться по-разному и может использоваться для выполнения Децимации во времени (разворот бит). Документ Эрика Postpischil охватывает все это.
Весы могут быть предварительно вычислены и сохранены в таблице. Расчеты Sin/cos занимают около 100-150 циклов на аппаратных средствах x86, поэтому их предварительная вычисление может сэкономить 10-20% от общего времени вычисления, поскольку доступ к памяти в этом случае будет быстрее, чем вычисления ЦП. Использование быстрых алгоритмов для вычисления sincos за один раз особенно полезно (обратите внимание, что cos равно sqrt (1,0 - синус * синус) или с использованием табличного поиска, cos - просто сдвиг фазы синуса).
Наконец, как только у вас будет супер оптимизированная реализация FFT, вы можете использовать векторизацию SIMD для вычисления 4x операций с плавающей запятой или 2x двойных операций с плавающей запятой за цикл внутри программы бабочки для повышения скорости на 100-300%. Принимая все вышесказанное, у вас будет очень быстрый и быстрый FFT!
Чтобы идти дальше, вы можете выполнять оптимизацию "на лету", предоставляя различные реализации этапов FFT, ориентированных на конкретные архитектуры процессоров. Размер кэша, количество регистров, наборов инструкций SSE/SSE2/3/4 и т.д. Различаются для каждой машины, поэтому выбор одного размера подходит для любого подхода часто избивается целевыми процедурами. Например, в FFTW многие БПФ меньшего размера представляют собой высоко оптимизированные развернутые (без циклов) реализации, предназначенные для конкретной архитектуры. Объединив эти небольшие конструкции (например, подпрограммы RadixN), вы можете выбрать самую быструю и лучшую процедуру для этой задачи.