CUDA FFT - сила двух

Question

Я смотрю на пример FFT на CUDA SDK и мне интересно: почему CUFFT намного быстрее, когда половина добавленных данных является степенью двойки?(половина, потому что в частотной области половина избыточна)

Какой смысл иметь силу двойного размера для работы?

Answer 1

Я думаю, что это ваш ответ.Используются разные алгоритмы

http://forums.nvidia.com/index.php?showtopic=195094

"Я работал над похожей проблемой. В руководстве cuFFT объясняется, что cuFFT использует два разных алгоритма для реализации FFTОдним из них является метод Кули-Такки, а другим - алгоритм Блюштейна. Когда размерности имеют простые множители только 2,3,5 и 7, например (675 = 3 ^ 3 x 5 ^ 5), тогда 675 x 675 выполняет многонамного лучше, чем, скажем, 674 x 674 или 677 x 677. Это делается с помощью метода Кули-Тьюки. Если одним из простых факторов является простое число, а не 2,3,5 или 7, то БПФ для этого числа реализуется с использованиемметод Блюстейна. Метод Блюстейна медленнее и также есть некоторая потеря точности. "

Из руководства: http://developer.download.nvidia.com/compute/cuda/3_1/toolkit/docs/CUFFT_Library_3.1.pdf

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

• Вписывается в общую память CUDA
• Являются степенями одного фактора (например, степенями двух)

Эти преобразования также являются наиболее точными из-за числовой стабильности выбранного алгоритма БПФ.Для размеров преобразования, которые соответствуют первому критерию, но не второму, CUFFT использует более общий алгоритм смешанного радиуса FFT, который обычно медленнее и менее численно точен.Поэтому, если возможно, лучше всего использовать размеры, которые являются степенями двух или четырех, или степенями других небольших простых чисел (таких как три, пять или семь).Кроме того, алгоритм FFT с двумя степенями мощности в CUFFT максимально использует разделяемую память, блокируя суб-преобразования для сигналов, не соответствующих первому критерию.

Answer 2

Просто добавьте немного фона к ответу Аде:

В общем, дискретное преобразование Фурье требует больших вычислений. БПФ с одной размерностью из N точек принимает N * N умножений. БПФ (быстрые преобразования Фурье) быстрее только потому, что в случае, когда N является степенью 2, уравнения можно переписать так, чтобы вам потребовалось только N * log2 N умножений.

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

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