Comments 15
Вы даже не сказали, что понимаете под максимальной производительностью: минимизация числа арифметических операций, или числа тактов процессора (какого, кстати?), минимизация числа гейтов для asic и т. п.
Какие? C чем?На любой на ваш выбор машине запустите ДПФ на 256 точек тысячу раз подряд, и замерьте время работы для каждого приведённого варианта.
Самый известный БПФ алгоритм использует сложную логику перестановки адресов, которая в графическом виде напоминает крылья бабочки
Там проще всё. Плотную матрицу оператора преобразования заменяют произведением нескольких разреженных матриц, в число которых входит матрица перестановок. Вот и получаются бабочки. Сравнение с отцами-основателями (метод Чена или метод Кули-Тьюки) есть?
способы достижения максимальной производительности, превосходящей теоретическую
Хотелось бы видеть развёрнутое сравнение на эту тему, если заявлено в шапке статьи.
Для сравнения с отцами основателями нужно решить что делать с w (поворотные множители вычисляются в run-time), т.е. преобразовывать конкретный код или получит откуда-нибудь референс-код. А грубо и так понятно — достаточно сравнить ассемблерный цикл там и ХМАС здесь.
В планах бенчмарки с fftw, но…
Ага, и ещё заявлены "способы достижения максимальной производительности, превосходящей теоретическую" (посмеялся с человека, не знающего, что такое O(n), но пишущего статьи по оптимизации).
Зря вы так, люди зашли в надежде увидеть что-то интересное (я поначалу подумал, что вы просто ошиблись в процитированной фразе и имелось в виду "быстрее реализации в лоб", но вы даже это не проверили, увы) и обломались, сейчас вам минусов насуют...
Тем кто читает, скажу, что там нет новизны — все{ пардон, почти все} способы описаны в той или иной литературе. По отдельности. Часто, с очень сложной реализацией.
У меня их реализация ну очень проста. Хотя это конечно imho.
Я к тому, что "производительность, превосходящая теоретическую" в данном случае — это быстрее, чем за O(n*log(n)).
Причём O-нотация имеет смысл, когда n стремится к бесконечности, так что замеры для 16 или 64 отсчётов тут не годятся (хотя они интересны на практике — но для их оптимизации есть свои подходы… И тут может быть интересно исследование вида "взять алгоритм и доказать, что он реализует преобразование Фурье за минимально возможное количество операций", а потом построить ещё один алгоритм, который на реальном CPU работает быстрее за счёт минимизации cache misses. Но в любом случае в исследовании должны быть или замеры, или точный расчёт числа операций).
Для БПФ O-нотация не имеет большого смысла, количество инструкций конечно и известно заранее, ветвлений нет, регистров нужно много, инструкции нужны широкие. В общем, всё это отлично ложится на архитектуру VLIW, которая и популярна в DSP. Время исполнения кода в таком случае будет известно ещё до запуска программы.
Промахов по кэшу тоже не особо должно быть — прочли несколько кэш-линий из массива, и муссируем эти числа пока не выполним преобразование. Если регистров много и / или преобразование маленького размера (например, преобразования 4х4, 8х8 в видеокодеках), то БПФ делается целиком в регистрах. Полкило прочли, долго считаем в регистрах, полкило записали — идеальный алгоритм для тщательной оптимизации. Очень мало в нём непредсказуемых факторов.
В главном (предсказуемость бпф, возможности его оптимизаций под железо)я с вами согласен, но:
- O-нотация имеет смысл. Но только для больших размеров окна (как, собственно, всегда и было), для малых количество операций считается в лоб (ну и там куча оптимизаций типа того, чему равны синусы/косинусы 90 и 45 градусов).
- Суперскалярность и т.п. не влияют на O-оценки — только на константу перед n log(n). Но, надеюсь, вы помните, что O(100 n)==O(n)?
- Раз уж мы умеем оценивать число операций (неважно, в виде O(...) или точно) — о какой "производительности, превосходящей теоретическую" идёт речь? В идеале производительность будет в точности равна теоретической. Можно лишь сравнить с другими реализациями по бенчмаркам — но именно этого автор не сделал, хотя это главное.
Огромное спасибо за статью, буквально на днях искал что-то похожее
Достижение максимальной производительности Быстрого Преобразования Фурье на основе управления данными