Оптимизация оператора глубокого обучения — БПФ

Автор: Ян Цзяньвэнь | Архитектор MegEngine

задний план

В области цифровых сигналов и цифровых изображений изучение частотной области является важной отраслью. Изображения, которые мы «обрабатываем» каждый день, находятся на уровне пикселей, что называется пространственными данными изображения. Данные о воздушном пространстве представляют собой детали, которые мы «читаем». Если мы рассматриваем то же изображение как сигнал и выполняем спектральный анализ, мы можем получить данные изображения в частотной области. Обратите внимание на следующий набор картинок (источник), яркие пятна на диаграмме частотной области — это низкочастотные сигналы, представляющие большую часть энергии изображения, то есть основную информацию изображения. Темные пятна — это высокочастотные сигналы, которые представляют края и шум изображения. Как видно из групповой диаграммы, по сравнению с Гуфи, Деградированный Гуфи сохраняет «контур» Гуфи по примерному низкочастотному сигналу, а увеличение его высокочастотного сигнала делает фоновый шум более явным. Анализ в частотной области позволяет понять состав изображения, а затем выполнить более абстрактный анализ и детальную обработку.

Goofy and Degraded Goofy

Инструментом для реализации преобразования пространственной области изображения и частотной области является преобразование Фурье. Поскольку данные изображения пространственно дискретны, мы используем дискретную форму преобразования Фурье DFT (дискретное преобразование Фурье) и его обратное преобразование IDFT (обратное дискретное преобразование Фурье). Кули-Таки разработал более быстрый алгоритм FFT (Fast Fourier Transform) на основе DFT.

DFT/FFT также имеет несколько расширенных приложений в области цифровых изображений. Например, DCT на основе DFT (Discrete Cosine Transform, дискретное косинусное преобразование) используется в алгоритме сжатия изображения JPEG (источник) и алгоритм наложения водяных знаков на изображение (источник).

Кодирование JPEG реализуется посредством преобразования цветового пространства, блока дискретизации, преобразования DCT и кодирования с квантованием. Среди них использование преобразования DCT отличает низкочастотную информацию от высокочастотной информации изображения и сжимает небольшое количество низкочастотной информации и большое количество высокочастотной информации в процессе кодирования квантования для получения сжатие размера. На изображении мордочки кота видно, что качество изображения будет ухудшаться с увеличением степени сжатия, но основная информация все равно сохраняется.

Различное качество jpeg (коэффициент сжатия) для кошачьих мордочек

Алгоритм создания водяных знаков изображения преобразует исходное изображение в частотную область с помощью DCT, выбирает подходящую позицию для встраивания информации об изображении водяного знака и преобразует его обратно в исходное изображение с помощью IDCT. Таким образом, изменения исходного изображения малы и незаметны, а водяной знак можно извлечь с помощью операций.

DFT/FFT также имеет расширенные приложения в области глубокого обучения. Например, используя БПФ для уменьшения количества вычислений свертки, алгоритм FFT_Conv также стал распространенным алгоритмом свертки глубокого обучения. В этой статье мы рассмотрим принципы и стратегии оптимизации алгоритмов частотной области.

Принцип и оптимизация ДПФ

формула

Будь то многомерная операция DFT или DCT/FFT_Conv на основе DFT, базовой вычислительной единицей является DFT_1D. Следовательно, оптимизация DFT_1D является основой для оптимизации всего оператора, подобного БПФ. Формула расчета DFT_1D:

$X_{k}=\sum_{n=0}^{\mathrm{N}-1} x_{n} e^{-j 2 \pi k \frac{n}{N}} \quad k=0, \ldots, N-1$

в$x_{n}$входной сигнал длины N,$e^{-j 2 \pi k \frac{n}{N}}$является N-м корнем из 1,$X_{k}$выходной сигнал длины N. Матричная форма этой формулы:

$\left[\begin{array}{c}X(0) \\ X(1) \\ \vdots \\ X(N-1)\end{array}\right]=\left[W_{N}^{n k}\right]\left[\begin{array}{c} \left.x(0\right) \\ x(1) \\ \vdots \\ x(N-1)\end{array}\right]$

Свойства единичных комплексных корней

в ДПФ_1D$W_{N}^{nk} = e^{-j 2 \pi k \frac{n}{N}}$является единичным корнем из 1. Интуитивно комплексная плоскость делится на N частей, и окружность комплексной плоскости прокручивается против часовой стрелки в соответствии со значением k * n.

Единичный комплексный корень имеет периодичность и симметрию.Согласно этим двум свойствам, мы можем значительно упростить матрицу W, которая составляет основу быстрого алгоритма DFT_1D.

Периодический:$W_{N}^{k +N}=W_{N}^{k}$

симметрия:$W_{N}^{k+N / 2}=-W_{N}^{k}$

Cooley-Teckey Algorithe FFT

Среди многих быстрых алгоритмов DFT_1D наиболее часто используется алгоритм Cooley-Tuckey FFT. Алгоритм использует идею «разделяй и властвуй», разлагает входную последовательность размера N на подпоследовательности N/основания в соответствии с разным основанием и делит каждую подпоследовательность до тех пор, пока ее больше нельзя будет разделить. Для каждого подразделения можно получить этап, и все этапы объединяются снизу вверх для расчета окончательной выходной последовательности. Здесь мы берем N = 8, основание = 2 в качестве примера, чтобы показать процесс рассуждения. в$x(k)$представляет собой последовательность N=8,$X^{F}(k)$Выведите последовательность для ДПФ. По формуле расчета ДПФ

$X^{F}(k)=W_{8}^{0} x_{0}+W_{8}^{k} x_{1}+W_{8}^{2 k} x_{2}+W_{8}^{3k} x_{3}+W_{8}^{4k} x_{4} + W_{8}^{5k} x_{5}+W_{8}^{6k} x_{6} +W_{8}^{7k} x_{7}$

Разделить по четности и разделить на две последовательности длины 4$G(k)$, $H(k)$.

$X^{F}(k)= W_{8}^{0} x_{0}+W_{8}^{2 k} x_{2}+W_{8}^{4 k} x_{4}+W_{8}^{6 k} x_{6}$

$+W_{8}^{k}\left(W_{8}^{0} x_{1}+W_{8}^{2 k} x_{3}+W_{8}^{4 k} x_{5}+W_{8}^{6 k} x_{7}\right)$

$=G^{F}(k)+W_{8}^{k} H^{F}(k)$

$X^{F}(k+4)=W_{8}^{0} x_{0}+W_{8}^{2(k+4)} x_{2}+W_{8}^{4(k+4)} x_{4}+W_{8}^{6(k+4)} x_{6}$

$+W_{8}^{(k+4)}\left(W_{8}^{0} x_{1}+W_{8}^{2(k+4)} x_{3}+W_{8}^{4(k+4)} x_{5}+W_{8}^{6(k+4)} x_{7}\right)$

$=G^{F}(k)+W_{8}^{k+4} H^{F}(k)$

$=G^{F}(k)-W_{8}^{k} H^{F}(k)$

$G^{F}(k)$и$H^{F}(k)$за$G(k)$и$H(k)$Результаты ДПФ .$G^{F}(k)$и$H^{F}(k)$Умножить на соответствующий коэффициент поворота$W_{8}^{k}$, можно выполнить простую операцию сложения и вычитания, чтобы получить вывод$X^{F}(k)$. то же самое, да$G(k)$и$H(k)$Сделайте ту же итерацию,$A(k)$,$B(k)$, $C(k)$, $D(k)$все последовательности N = 2, и, объединив их результаты ДПФ, можно получить$G^{F}(k)$и$H^{F}(k)$.

$\begin{aligned} &G^{F}(k)=A^{F}(k) + W_{4}^{k}B^{F}(k)\\ \end{aligned}$

$\begin{aligned} &G^{F}(k+2)=A^{F}(k)-W_{4}^{k}B^{F}(k)\\ \end{aligned}$

$\begin{aligned} &H^{F}(k)=C^{F}(k)+W_{4}^{k}D^{F}(k)\\ \end{aligned}$

$\begin{aligned} &H^{F}(k+2)=C^{F}(k)-W_{4}^{k}D^{F}(k)\\ \end{aligned}$

Вычислить последовательность N=2$A^{F}(k)$, $B^{F}(k)$, $C^{F}(k)$, $D^{F}(k)$, так как$k=0$, коэффициент поворота$W_{2}^{0}$= 1. Просто сложите и вычтите, чтобы получить результат.

$\left[\begin{array}{l} A^{F}(0) \\ A^{F}(1) \end{array}\right]=\left[\begin{array}{ll} 1 & 1 \\ 1 & -1 \end{array}\right]\left[\begin{array}{l} x_{0} \\ x_{4} \\ \end{array}\right]$

$\left[\begin{array}{l} B^{F}(0) \\ B^{F}(1) \end{array}\right]=\left[\begin{array}{ll} 1 & 1 \\ 1 & -1 \end{array}\right]\left[\begin{array}{l} x_{2} \\ x_{6} \\ \end{array}\right]$

$\left[\begin{array}{l} C^{F}(0) \\ C^{F}(1) \end{array}\right]=\left[\begin{array}{ll} 1 & 1 \\ 1 & -1 \end{array}\right]\left[\begin{array}{l} x_{1} \\ x_{5} \\ \end{array}\right]$

$\left[\begin{array}{l} D^{F}(0) \\ D^{F}(1) \end{array}\right]=\left[\begin{array}{ll} 1 & 1 \\ 1 & -1 \end{array}\right]\left[\begin{array}{l} x_{3} \\ x_{7} \\ \end{array}\right]$

С точки зрения графики алгоритма вычисление каждого слоя будет генерировать несколько бабочек, поэтому алгоритм также называется алгоритмом бабочки. Здесь мы представим основные компоненты сети тарелок, которые будут полезны для анализа ниже.

N = 8 Диаграмма алгоритма тарелки

Последовательность расчета N=8 разделена на 3 уровня, каждый уровень (стадия) имеет один или несколько блоков (разделов), каждый блок содержит одну или несколько бабочек (бабочки), расчет формы бабочки - ДПФ. Ядро операции . Порядок расчета каждого этапа:

• принять участие
• Умножьте на коэффициент преобразования
• для section_num, для бабочки_num выполнить radixN_kernel
• Напишите вывод.

Глядя на диаграмму алгоритма бабочки N = 8, когда стадия = 1, операция делится на 4 секции, и бабочка_num = 1 для каждой секции. Когда stage = 2, section_num = 2,utter_num = 2. Когда stage = 3, section_num = 1 иutter_num = 4. Можно заметить, что в процессе слева направо, section_num продолжает уменьшаться, бабочка_num продолжает увеличиваться, а группа бабочек «становится больше и плотнее», но общее количество тарелок на каждом уровне остается прежним. Фактически, для алгоритма длины N, основанием = r, мы можем экстраполировать на:

$\text Sec$ _ $\text num$ = $N / r^ {S}$

$\text Butterfly$ _ $\text num$ =$r^{S-1}$

$\text Sec$ _ $\text stride =r^{S}$

$\text Butterfly$_$stride$= $1$

S 为当前的 stage，sec/butterfly_stride 是每个 section/butterfly 的间隔。

Этот алгоритм может уменьшить сложность с O(n^2) до O(nlogn), что является эффективным и элегантным. Основываясь на алгоритме бабочки, мы дополнительно разделяем и оптимизируем алгоритм для различных оснований, которые в основном делятся на две категории: основание - степень 2 и основание - не степень 2.

Оптимизация мощности radix-2

Ядро DFT_1D находится в матричной форме.$W_{N}^{nk}$матрица, мы анализируем ядро ​​radix_2^n.

Как упоминалось выше, матричная форма формулы ДПФ выглядит следующим образом:

$\left[\begin{array}{c}X(0) \\ X(1) \\ \vdots \\ X(N-1)\end{array}\right]=\left[W_{N}^{n k}\right]\left[\begin{array}{c} \left.x(0\right) \\ x(1) \\ \vdots \\ x(N-1)\end{array}\right]$

в$x(0)$ ~$x(N-1)$умножается на коэффициент поворота$W_{N}^{kn}$ввод после

Когда основание = 2, так как$W_{2}^1$= -1,$W_{2}^2$= 1, матричная форма ДПФ radix_2 может быть записана как:

$\left[\begin{array}{c}\mathrm{X}_{\mathrm{k}} \\ \mathrm{X}_{\mathrm{k}+\mathrm{N} / 2}\end{array}\right]$ $=\left[\begin{array}{cc}1 & 1 \\ 1 & -1\end{array}\right]\left[\begin{array}{l}\mathrm{W}_{\mathrm{N}}^{0} \mathrm{A}_{\mathrm{k}} \\ \mathrm{W}_{\mathrm{N}}^{\mathrm{k}} \mathrm{B}_{\mathrm{k}}\end{array}\right]$

Когда основание = 4, так как$W_{4}^1$ = -j, $W_{4}^2$ = -1, $W_{4}^3$ = j, $W_{4}^4$= 1, матричная форма ДПФ radix_4 может быть записана как:

$\left[\begin{array}{c}\mathrm{X}_{\mathrm{k}} \\ \mathrm{X}_{\mathrm{k}+\mathrm{N} / 4} \\ \mathrm{X}_{\mathrm{k}+\mathrm{N} / 2} \\ \mathrm{X}_{\mathrm{k}+3 \mathrm{~N} / 4}\end{array}\right]=\left[\begin{array}{cccc}1 & 1 & 1 & 1 \\ 1 & -\mathrm{j} & -1 & \mathrm{j} \\ 1 & -1 & 1 & -1 \\ 1 & \mathrm{j} & -1 & -\mathrm{j}\end{array}\right]\left[\begin{array}{c}\mathrm{W}_{\mathrm{N}}^{0} \mathrm{A}_{\mathrm{k}} \\ \mathrm{W}_{\mathrm{N}}^{\mathrm{k}} \mathrm{B}_{\mathrm{k}} \\ \mathrm{W}_{\mathrm{N}}^{2 \mathrm{k}} \mathrm{C}_{\mathrm{k}} \\ \mathrm{W}_{\mathrm{N}}^{3 \mathrm{k}} \mathrm{D}_{\mathrm{k}}\end{array}\right]$

Точно так же ядро ​​radix_8 получается как:

$\left[\begin{array}{cccccccc}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \mathrm{~W}_{8}^{1} & -j & \mathrm{~W}_{8}^{3} & -1 & -\mathrm{W}_{8}^{1} & j & -\mathrm{W}_{8}^{3} \\ 1 & -j & -1 & j & 1 & -j & -1 & j \\ 1 & \mathrm{~W}_{8}^{3} & j & \mathrm{~W}_{8}^{1} & -1 & -\mathrm{W}_{8}^{3} & -j & -\mathrm{W}_{8}^{1} \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & -\mathrm{W}_{8}^{1} & -j & -\mathrm{W}_{8}^{3} & -1 & \mathrm{~W}_{8}^{1} & j & \mathrm{~W}_{8}^{3} \\ 1 & j & -1 & -j & 1 & j & -1 & -j \\ 1 & -\mathrm{W}_{8}^{3} & j & -\mathrm{W}_{8}^{1} & -1 & \mathrm{~W}_{8}^{3} & -j & \mathrm{~W}_{8}^{1}\end{array}\right]$

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

В DFT1D для алгоритмов r-2/r-4/r-8 с разными основаниями каждый этап имеет одинаковое количество обращений: 2 * бабочка_число * основание = 2N, а количество этапов, соответствующих разным основаниям, существенно различается ($\log_2N$ vs $\log_4N$ vs $\log_8N$).

Следовательно, для DFT выбор ядра большего размера даст очевидные преимущества в доступе к памяти без значительного увеличения объема вычислений. Обратите внимание на производную диаграмму ядра, ядро ​​r-2 соответствует 4-кратному выполнению операций доступа к памяти и 2-кратному выполнению сложных операций сложения и вычитания с плавающей запятой для каждой бабочки. Каждый алгоритм бабочки ядра r-4 соответствует 8-кратному выполнению операций загрузки/сохранения и 8-кратному выполнению сложных операций сложения и вычитания с плавающей запятой (сочетая одну и ту же операцию).$\log_2N$Добраться до$\log_4N$, уменьшает общее количество обращений к памяти, поэтому производительность будет выше. Ядро r-8 имеет 16 загрузок/сохранений, 24 сложных сложения с плавающей запятой и 8 умножений с плавающей запятой на бабочку. Существование умножения с плавающей запятой увеличивает вычислительные затраты, и этап состоит из$\log_4N$дальше вниз к$\log_8N$, но так как N не слишком велико, уменьшение ступени с r-4 до r-8 неочевидно, поэтому оптимизация ограничена

Давайте снова посмотрим на вычислительные затраты. Обычно есть два способа уменьшить вычислительные затраты: уменьшить количество избыточных операций и распараллелить.

Взяв в качестве примера алгоритм r-4, вычисление части ядра:

• radix_4_first_stage(src, dst, sec_num, butterfly_num)
• radix_4_other_stage(src, dst, sec_num, butterfly_num)
  • for Sec_num
    • for butterfly_num
      • raidx_4_kernel

Поскольку данные radix4_first_stage равны k=0, а коэффициент поворота равен 1, эту часть операции сложного умножения можно опустить и оптимизировать отдельно. В части radix4_other_stage, начиная со второго этапа,utter_num = 4^(s-1) является кратным 4, и каждое чтение/сохранение массива бабочек разнесено. Развертывание цикла и векторизация могут выполняться в самом внутреннем цикле для достижения 4 или более операций бабочки параллельно. Использование развертывания цикла и SIMD-инструкций может не только улучшить параллелизм, но и повысить эффективность использования кэш-линии, что может привести к большему повышению производительности. Взяв в качестве примера SM8150 (armv8), параллельная оптимизация r-4 может повысить производительность в 1,6 раза по сравнению с r2.

Размер: 1*2048(r2c) Окружающая среда: Большое ядро ​​SM8150

Короче говоря, для оптимизации системы счисления-2^n выбор подходящей системы счисления для уменьшения накладных расходов на доступ к памяти, вызванных несколькими этапами, а также использование свойства единичного комплексного корня и распараллеливания для уменьшения накладных расходов на вычисления могут привести к большему повышению производительности.

radix - оптимизация не по степени 2

Когда входная длина N = radix1^m1 * radix2^m2... и основание не является степенью числа 2, если вы используете наивный алгоритм O (n ^ 2), производительность резко упадет. Общие решения включают 0-заполнение исходного длинного, используя алгоритм radix_N, специальный алгоритм radix_N (преобразование chirp-z). Метод степени от 0 до 2 добавляет много вычислений и памяти для входных данных большого размера, в то время как преобразование chirp-z использует свертку для вычисления ДПФ, и алгоритм слишком сложен. Поэтому также необходима оптимизация для системы счисления по основанию N, отличной от степени 2.

Процесс вычисления основания-N такой же, как степень основания-2.Мы также можем использовать периодичность и симметрию единичного комплексного корня, чтобы упростить вычисление ядра. Взяв в качестве примера основание-5, DFT_kernel основания-5:

$\left[\begin{array}{cccc} 1&1&1&1&1\\ 1 &\mathrm{W}_{\mathrm{5}}^{1} & \mathrm{W}_{\mathrm{5}}^{2} & \mathrm{W}_{\mathrm{5}}^{-2} & \mathrm{W}_{\mathrm{5}}^{-1} \\ 1 &\mathrm{W}_{\mathrm{5}}^{2} & \mathrm{W}_{\mathrm{5}}^{-1} & \mathrm{W}_{\mathrm{5}}^{1} & \mathrm{W}_{\mathrm{5}}^{-2} \\ 1 &\mathrm{W}_{\mathrm{5}}^{-2} & \mathrm{W}_{\mathrm{5}}^{1} & \mathrm{W}_{\mathrm{5}}^{-1} & \mathrm{W}_{\mathrm{5}}^{2} \\ 1 &\mathrm{W}_{\mathrm{5}}^{-1} & \mathrm{W}_{\mathrm{5}}^{-2} & \mathrm{W}_{\mathrm{5}}^{2} & \mathrm{W}_{\mathrm{5}}^{1} \\ \end{array}\right]$

$W_5^k$и$W_{5}^{-k}$Симметричный относительно оси x в комплексной плоскости, с той же реальной частью и противоположной мнимой частью. в соответствии с этим свойством. Как показано на рисунке ниже, для каждого этапа можно объединить общие элементы A, B, C и D, а затем можно рассчитать выход этапа в соответствии с общими элементами.

$A=\left(x_{1}+x_{4}\right) * W_{5}^{1} \cdot r+\left(x_{2}+x_{3}\right) * W_{5}^{2} \cdot r$

$B=(-j) * \left[\left(x_{1}-x_{4}\right) * W_{5}^{1} \cdot i+\left(x_{2}-x_{3}\right) * W_{5}^{2} \cdot i\right]$

$C=\left(x_{1}+x_{4}\right) * W_{5}^{2} \cdot r+\left(x_{2}+x_{3}\right) * W_{5}^{1} \cdot r$

$D=j * \left[\left(x_{1}-x_{4}\right) * W_{5}^{2} \cdot i-\left(x_{2}-x_{3}\right) * W_{5}^{1} \cdot i\right]$

$\begin{array}{l} X(k)=x_{0}+\left(x_{1}+x_{4}\right)+\left(x_{2}+x_{3}\right)\\ \end{array}$

$\begin{array}{l} X(k+N/5)=x_{0}+\mathrm{A}-\mathrm{B}\\ \end{array}$

$\begin{array}{l} X(k+2N/5)=x_{0}+\mathrm{C}+\mathrm{D}\\ \end{array}$

$\begin{array}{l} X(k+3N/5)=x_{0}+C-D\\ \end{array}$

$\begin{array}{l} X(k+4N/5)=x_{0}+\mathrm{A}+\mathrm{B}\\ \end{array}$

Этот алгоритм уменьшает количество повторяющихся операций. В то же время, когда stage>=2, цикл бабочки также разворачивается и распараллеливается для дальнейшего снижения вычислительных затрат. Идея оптимизации системы счисления-5 может быть экстраполирована на систему счисления-N. Для каждого этапа radix_N процесс вычисления:

• принять участие
• Умножьте на соответствующий коэффициент преобразования
• Вычислить общие термины, radix_N имеет N-1 общих терминов
• radix_N_kernel, выполняющий распараллеливание
• запись вывода

Другие оптимизации

Вышеуказанные две главы описывают общую оптимизацию DFT_1D. На этой основе можно выполнить более подробную оптимизацию. Вы можете обратиться к документам, цитируемым в этой статье.

• Для всех реальных входных данных, поскольку мнимая часть входных данных равна 0, будут избыточные операции и избыточное хранилище при выполнении сложных операций коэффициентов поворота и radix_N_kernel.Алгоритм разделения r2c можно использовать как сложную последовательность длины N/2. Вычислите результат ДПФ и выполните операцию разделения, чтобы получить результат N-длинной последовательности действительных чисел.
• Для алгоритма по основанию по основанию 2 повторное вычисление шага ввода/вывода каждого этапа для отмены переворота битов первого этапа может еще больше сократить накладные расходы на выборку памяти.
• Для алгоритма по основанию-N N = основание1 ^ m1 * основание2 ^ m2 в рамках смешанной базовой структуры и объединение меньшего основания с большим основанием, чтобы уменьшить этап.

Принцип и оптимизация алгоритма расширения ДПФ

DCT и FFT_conv являются двумя типичными алгоритмами, основанными на расширении DFT, и оптимизация DFT_1D/2D может хорошо использоваться в таких алгоритмах.

DCT

Алгоритм ДКП (дискретное косинусное преобразование, дискретное косинусное преобразование) можно рассматривать как алгоритм, в котором ДПФ берет свою синусоидальную составляющую и подвергается промышленной коррекции. Формула для расчета DFT_1D:

$\begin{aligned} X[k] &=C(k) \sum_{n=0}^{N-1} x[n] \cos \left(\frac{(2 n+1) \pi k}{2 N}\right) \\ &C(k)=\sqrt{\frac{1}{n}} \\&k=1 \\ &C(k)=\sqrt{\frac{2}{n}} \\&k!=1 \\ \end{aligned}$

Наивная реализация этого алгоритма — O(n^2), и мы преобразуем его в алгоритм DFT_1D, который снижает сложность алгоритма до O(nlogn). Поток алгоритма DCT, основанный на DFT:

• Для входной последовательности x[n] DCT создайте входную последовательность y[n] длины 2N, чтобы удовлетворить y[n] = x[n] + x[2N-n-1], то есть выполнить зеркальное отображение симметрия.
• Операция ДПФ выполняется над входной последовательностью y[n] для получения выходной последовательности Y[K].
• Вычислить выход X[K] исходной входной последовательности из Y[K].

Попробуем вывести этот алгоритм:

$\begin{array}{l} y[n]=x[n]+x [2 N-1-n] \\ \end{array}$

$\begin{array}{l} Y[k]=\sum_{n=0}^{N-1} x[n]\cdot e^{-j \frac{2 \pi k n}{2 N}} +\sum_{n=N}^{2 N-1} x[2 N-1-n] \cdot e^{-j \frac{2 \pi k n}{2 N}} \end{array}$

$\begin{array}{l} \\=\sum_{n=0}^{N-1} x[n]\cdot e^{-j \frac{2 \pi k n}{2 N}} +\sum_{n=0}^{N-1} x[n] \cdot e^{-j \frac{2 \pi k (2N-1-n)}{2 N}} \end{array}$

$\begin{array}{l} \\=e^{-j \frac{2 \pi k }{2 N}} \cdot \sum_{n=0}^{N-1} x[n] (e^{-j \frac{2\pi}{2 N} kn} \cdot e^{-j \frac{\pi}{2 N}k}+e^{j \frac{2\pi}{2 N} kn} \cdot e^{j \frac{\pi}{2 N}k}) \end{array}$

$\begin{array}{l} \\=e^{-j \frac{2 \pi k }{2 N}} \cdot \sum_{n=0}^{N-1} x[n] \cdot 2\cdot\cos(\frac{2n+1}{2N} k\pi) \end{array}$

$\begin{array}{l} \\=e^{-j \frac{2 \pi k }{2 N}} \cdot C(u) \cdot X[k] \end{array}$

Разверните y[n] в соответствии с формулой ДПФ, отсортируйте расширенные два термина и извлеките общие термины.$e^{-j \frac{2 \pi k }{2 N}}$, согласно формуле Эйлера и функции индукции, отсортировать непубличные члены$(e^{-j \frac{2\pi}{2 N} kn} \cdot e^{-j \frac{\pi}{2 N}k}+e^{j \frac{2\pi}{2 N} kn} \cdot e^{j \frac{\pi}{2 N}k})$. Можно видеть, что полученный результат является в точности произведением x[k] и коэффициентов, связанных с k. Это можно рассчитать сначала$Y[k]$получить вывод DCT x[n]$X[k]$.

На основе понимания алгоритма наша оптимизация DFT_1D может быть полностью применена к DCT. Процесс вычисления DCT_2D заключается в выполнении DCT_1D по очереди для строк и столбцов.Мы используем несколько потоков для распараллеливания DCT_1D, что может дополнительно оптимизировать алгоритм.

FFT_conv

Conv — наиболее распространенная операция в глубоком обучении.Распространенными методами вычисления conv являются IMG2COL+GEMM, Winograd и FFT_conv. Все три алгоритма имеют свои сценарии использования.

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

$f \underset{\text { Circ }}{*} g=\mathcal{F}^{-1}(\mathcal{F}(f) \cdot \mathcal{F}(g))$

Интуитивное теоретическое доказательство можно увидеть на следующем рисунке (источник).

${F}[f * g]$

$=\int_{-\infty}^{\infty}\left[\left(\int_{-\infty}^{\infty}g(z)f(x-z)dz\right)e^{-i k x}\right]dx$

$=\int_{-\infty}^{\infty} g(z)\left[\int_{-\infty}^{\infty} f(x-z) e^{-i k x} d x\right] d z$

$=\int_{-\infty}^{\infty} g(z)\left[\int_{-\infty}^{\infty} f(y) e^{-i k(y+z)} d y\right] d z$

$=\left[\int_{-\infty}^{\infty} g(z) e^{-i k z} d z\right]\left[\int_{-\infty}^{\infty} f(y) e^{-i k y} d y\right]$

$=\mathcal{F}[f] \cdot \mathcal{F}[g]$

Разложив формулу свертки и дискретное преобразование Фурье, изменив порядок интегралов и подставив переменные, можно доказать вывод. Обратите внимание, что свертка здесь — это круговая свертка, которая отличается от линейной свертки, обычно используемой в нашем глубоком обучении. Условием использования круговой свертки для вычисления линейной свертки является длина круговой свертки L⩾|f|+|g|−1. Поэтому мы делаем заполнение нулями на Feature Map и Kernel и берем эффективные линейные вычисления из конечного результата.

Поток алгоритма FFT_conv:

• Обнуление карты функций и ядра до одинакового размера для преобразования ДПФ. 
• матричное скалярное произведение
• Вычислите результат через IDFT.

Этот алгоритм преобразует свертку в точечное умножение.Сложность алгоритма составляет O(nlogn), что меньше, чем O(n^2) свертки.Когда размер входных данных относительно велик, количество вычислений может быть уменьшено, и это подходит для алгоритма преобразования больших ядер.

В расчете глубокого обучения размер ядра намного меньше, чем карта функций, поэтому заполнение нулями на первом этапе FFT_conv будет иметь много накладных расходов.В справочном документе 2 упоминается, что карта функций может должны быть разделены на блоки. Карту и ядро ​​​​должны быть заполнены до меньшего размера, что может значительно уменьшить накладные расходы этой части. Процесс расчета fft_conv после оптимизации:

• Организуйте кеш разумно, чтобы рассчитать подходящий размер плитки и заблокировать исходное изображение.
• Блок-схема и ядро ​​дополняются нулями, и выполняется операция ДПФ.
• Скалярное произведение матрицы миниатюр
• Сделайте обратную работу и комбинируйте в большую картину.

В то же время мы можем заметить, что основным вычислительным модулем FFT_conv по-прежнему является операция DFT для небольших графов, поэтому мы можем заменить здесь оптимизацию DFT из предыдущей главы, дополненную многопоточностью, для дальнейшего повышения эффективности вычислений. FFT_Conv.

использованная литература

1. Чен Тун, Ли Чжихао, Цзя Хайпэн, Чжан Юньцюань.Исследования по реализации и оптимизации многомерного БПФ на платформе ARMV8
2. Qinglin Wang,Dongsheng Li. Optimizing FFT-Based Convolutionon ARMv8 Multi-core CPUs
3. Aleksandar Zlateski, Zhen Jia, Kai Li, Fredo Durand. Свертки БПФ быстрее, чем Winograd на современных процессорах, и вот почему

Прикрепил:

Гитхаб:MegEngine Тяньюань

Официальный сайт:MegEngine — глубокое обучение, простая разработка

Добро пожаловать в группу технической биржи MegEngine QQ: 1029741705