[發明專利]一種快速傅里葉變換代碼的生成方法及裝置

有效

• 申請號: 201810823431.6
• 申請日: 2018-07-24
• 公開（公告）號: CN110750249B
• 公開（公告）日: 2021-08-20
• 發明（設計）人: 李志豪;齊霽;張邵敏;景玉超;賈海鵬
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F8/30
• 分類號: G06F8/30;G06F17/14
• 代理公司: 深圳市深佳知識產權代理事務所(普通合伙) 44285
• 代理人: 王仲凱

本申請公開了一種快速傅里葉變換代碼生成方法及裝置，用于生成快速傅里葉變換FFT代碼，將FFT代碼分解為多個原子模板，便于后續對原子模板進行優化，進一步提高FFT代碼的性能。方法包括：獲取需要進行快速傅里葉變換FFT的數據序列以及數據序列的長度；根據數據序列的長度確定數據序列的FFT分解方式，得到對應FFT分解方式的蝶形網絡的一個或多個級，每個級對應一種蝶形的基；根據每一級對應的蝶形的基確定每一級中需要調用的蝶形代碼以及每一級中的蝶形代碼被調用的調用次數；根據每一級中的蝶形代碼以及每一級中的蝶形代碼被調用的調用次數逐級生成各個級的代碼，以得到對數據序列進行快速傅里葉變換的FFT代碼。

技術領域

本申請涉及計算機領域，尤其涉及一種快速傅里葉變換代碼的生成方法及裝置。

背景技術

快速傅里葉變換(fast Fourier transform，FFT)是用于計算離散傅里葉變換(discrete Fourier transform，DFT)或其逆運算的快速算法，在工程、科學和數學領域的應用非常廣泛，例如信號分解、數字濾波、圖像處理等。通過傅里葉分析，源數據將會從原始域(通常是時間或空間)被變換到頻域的表示或者進行相反的逆變換。為了適應在計算機上進行的數值計算，需要將傅里葉變換離散化，稱為離散傅里葉變換DFT，其數學表示為公式(1)：

與傳統的算法相比，FFT算法能夠將計算離散傅里葉變換DFT的算法復雜度從N²降低到NlogN，其中N為輸入序列的長度。

目前應用最廣泛、最流行的FFT算法為庫利-圖基(Cooley-Tukey)FFT算法，主流的FFT庫如，FFTW、英特爾數學內核庫(Intel math kernel library，Intel MKL)、ARM高性能庫(ARM performance libraries，ARMPL)等均采用此算法。其核心可歸結為蝶形網絡的構建，如圖1A、圖1B所示的長度N＝8的基-2(radix-2)FFT蝶形網絡，圖1B中的蝶形網絡由級(stage)-段(section)-蝶形(butterfly)三級組成。該算法將公式(1)中的各項在時域上進行重新分組，并將e^-j2πkn/N用進行替換，其中，替換后的被稱之為“旋轉因子”(twiddle factor)，亦稱為“蝶形因子”。根據旋轉因子在計算過程中出現的不同位置，可以將FFT算法分為頻域抽取(decimation-in-frequency，DIF)和時域抽取(decimation-in-time，DIT)兩大類。頻域抽取DIF的旋轉因子出現在計算的輸出端，如圖1A所示；而時域抽取DIT的旋轉因子出現在計算的輸入端，如圖1B。如果采用時域抽取DIT，數據輸入是按照“位元翻轉”(bit-reversed order)來進行排列，數據輸出則是依序排列；而如果采用頻域抽取DIF，那么情況恰好相反，數據輸入是依序排列，數據輸出則是會按照“位元翻轉”(bit-reversed order)來進行排列。

現有的幾種方案在生成用于進行FFT變換的代碼(下文簡FFT代碼)過程中，需要通過人工分析，得到FFT不同基的計算及訪存特征，結合不同CPU的硬件細節，通過人工預取數據、重排指令等方法，有效地減少訪存開銷和流水線停頓等問題，進而加速應用程序。但現有的幾種方案在實現FFT庫時存在以下不足：需人工對不同CPU架構進行具體的高性能代碼實現，開發門檻高，生產效率低下，并且需要為不同架構或同一架構但規格不同的CPU實現不同的高性能代碼，當硬件平臺發生變化時，對生成的FFT代碼難以進行優化。

發明內容

本申請實施例提供了一種快速傅里葉變換代碼的生成方法及裝置，用于生成快速傅里葉變換FFT代碼，將FFT代碼分解為多個原子模板，便于后續對原子模板進行優化，進一步提高FFT代碼的性能。