В настоящее время я реализую двумерное БПФ для реальных входных данных, используя opencl (точнее, быструю двумерную свертку с использованием БПФ, поэтому мне нужно только то, что ведет себя аналогично, чтобы применить к нему свертку).2D БПФ реализован с использованием 1D БПФ на строках, а затем 1D БПФ на столбцах.
Чтобы сделать это более эффективным, я пытаюсь использовать симметрии БПФ с реальным вводом, чтобы иметь возможностьрассчитать меньшие БПФ.Я обнаружил, что могу объединить две строки в одну, используя первую в качестве реального компонента, вторую в качестве мнимого компонента, выполнить первое 1D БПФ для результирующей строки и затем использовать свойства симметрии для построения результатов 1D БПФ индивидуальногостроки из этого.Итак, в основном я делаю следующее:
Позвольте f и g быть строками из матрицы.
- Construct
x = f + i * g - Преобразование для получения
F(x) = F(f) + i * F(g) - Используйте симметрии для извлечения
F(f) и F(g) из F(x)
Однако я не могу просто ввести результаты непосредственно во 2-й 1DБПФ, потому что в этом случае я бы преобразовал не всю матрицу, а две подматрицы.Однако извлечение данных между преобразованиями означает либо сохранение большего количества данных (n/2+1 записей, необходимых для выражения результата 1D БПФ на реальном вводе), либо объединение элементов с индексами 0 и индексом n/2 в один элемент (объединение с использованиемодин и тот же трюк, поскольку оба числа гарантированно являются действительными) и используют одинаковый объем памяти, но в моей свертке я должен сделать особый аргумент для этого.
Поскольку я стараюсь максимально использовать буферы (из-за ограниченного объема оперативной памяти, доступной на графическом процессоре), использование большего объема памяти не является хорошим решением.Кроме того, мои алгоритмы не оборудованы для работы с матрицами, размер которых не равен 2 / кратно 16 (варьируется от ядра к ядру).Я бы также предпочел не вводить специальные случаи, так как это сделало бы мои ядра более сложными, что негативно сказалось на эффективности (у меня уже возникают проблемы с минимизацией количества регистров, используемых каждым ядром).
Поэтому мой вопрос: есть лиэлегантный подход к этой проблеме, то есть такой, который будет работать без использования большего количества памяти или особых случаев для определенных элементов?
В идеале я хотел бы иметь возможность выполнять полное БПФ, не разбивая мои объединенные данные в серединеБПФ, но я не уверен, что это возможно.