Как стать автором
Обновить

Достижение максимальной производительности Быстрого Преобразования Фурье на основе управления данными

Время на прочтение1 мин
Количество просмотров19K
Всего голосов 23: ↑22 и ↓1+21
Комментарии15

Комментарии 15

Какие? C чем? И для чего нужны? Статья, собственно, выложена для сбора требований
Заявлено о достижении максимальной производительности, значит должно быть сравнение с prior art с подробнейшим разбором по косточкам.

Вы даже не сказали, что понимаете под максимальной производительностью: минимизация числа арифметических операций, или числа тактов процессора (какого, кстати?), минимизация числа гейтов для asic и т. п.
Я не «даже не сказал», я намеренно не сказал (см выше).
Какие? C чем?
На любой на ваш выбор машине запустите ДПФ на 256 точек тысячу раз подряд, и замерьте время работы для каждого приведённого варианта.
Это мне поможет найти заказчика?
Может лучше научиться делать ассемблерную версию или с фиксированной точкой?
Самый известный БПФ алгоритм использует сложную логику перестановки адресов, которая в графическом виде напоминает крылья бабочки


Там проще всё. Плотную матрицу оператора преобразования заменяют произведением нескольких разреженных матриц, в число которых входит матрица перестановок. Вот и получаются бабочки. Сравнение с отцами-основателями (метод Чена или метод Кули-Тьюки) есть?

способы достижения максимальной производительности, превосходящей теоретическую

Хотелось бы видеть развёрнутое сравнение на эту тему, если заявлено в шапке статьи.
Не заявлено. Заявлена попытка.
Для сравнения с отцами основателями нужно решить что делать с w (поворотные множители вычисляются в run-time), т.е. преобразовывать конкретный код или получит откуда-нибудь референс-код. А грубо и так понятно — достаточно сравнить ассемблерный цикл там и ХМАС здесь.
В планах бенчмарки с fftw, но…

Ага, и ещё заявлены "способы достижения максимальной производительности, превосходящей теоретическую" (посмеялся с человека, не знающего, что такое O(n), но пишущего статьи по оптимизации).
Зря вы так, люди зашли в надежде увидеть что-то интересное (я поначалу подумал, что вы просто ошиблись в процитированной фразе и имелось в виду "быстрее реализации в лоб", но вы даже это не проверили, увы) и обломались, сейчас вам минусов насуют...

Способы перечислены в главе «Дальнейшие оптимизации». — Тем кто проглядывает, а не читает.
Тем кто читает, скажу, что там нет новизны — все{ пардон, почти все} способы описаны в той или иной литературе. По отдельности. Часто, с очень сложной реализацией.
У меня их реализация ну очень проста. Хотя это конечно imho.

Я к тому, что "производительность, превосходящая теоретическую" в данном случае — это быстрее, чем за O(n*log(n)).
Причём O-нотация имеет смысл, когда n стремится к бесконечности, так что замеры для 16 или 64 отсчётов тут не годятся (хотя они интересны на практике — но для их оптимизации есть свои подходы… И тут может быть интересно исследование вида "взять алгоритм и доказать, что он реализует преобразование Фурье за минимально возможное количество операций", а потом построить ещё один алгоритм, который на реальном CPU работает быстрее за счёт минимизации cache misses. Но в любом случае в исследовании должны быть или замеры, или точный расчёт числа операций).

За счёт суперскалярности и инструкций типа FMA, процессор может выполнить алгоритм за меньшее число инструкций / циклов, чем шагов в алгоритме. Фактическая производительность в смысле числа элементарных шагов будет выше теоретической.

Для БПФ O-нотация не имеет большого смысла, количество инструкций конечно и известно заранее, ветвлений нет, регистров нужно много, инструкции нужны широкие. В общем, всё это отлично ложится на архитектуру VLIW, которая и популярна в DSP. Время исполнения кода в таком случае будет известно ещё до запуска программы.

Промахов по кэшу тоже не особо должно быть — прочли несколько кэш-линий из массива, и муссируем эти числа пока не выполним преобразование. Если регистров много и / или преобразование маленького размера (например, преобразования 4х4, 8х8 в видеокодеках), то БПФ делается целиком в регистрах. Полкило прочли, долго считаем в регистрах, полкило записали — идеальный алгоритм для тщательной оптимизации. Очень мало в нём непредсказуемых факторов.

В главном (предсказуемость бпф, возможности его оптимизаций под железо)я с вами согласен, но:


  1. O-нотация имеет смысл. Но только для больших размеров окна (как, собственно, всегда и было), для малых количество операций считается в лоб (ну и там куча оптимизаций типа того, чему равны синусы/косинусы 90 и 45 градусов).
  2. Суперскалярность и т.п. не влияют на O-оценки — только на константу перед n log(n). Но, надеюсь, вы помните, что O(100 n)==O(n)?
  3. Раз уж мы умеем оценивать число операций (неважно, в виде O(...) или точно) — о какой "производительности, превосходящей теоретическую" идёт речь? В идеале производительность будет в точности равна теоретической. Можно лишь сравнить с другими реализациями по бенчмаркам — но именно этого автор не сделал, хотя это главное.

Огромное спасибо за статью, буквально на днях искал что-то похожее

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории