並行快速傅立葉變換

並行快速傅立葉變換不同於平常的FFT算法，其更便於組織向量運算，效率高且性能好。

基本介紹

• 中文名：並行快速傅立葉變換
• 簡稱：並行FFT
• 用於：組織向量運算
• 學科：計算機
• 領域：計算機
• 性質：效率高且性能好

串列算法

在快速傅立葉變換（FFT）的並行算法中使用了蝶形連線網路。

並行算法

並行計算（英語：parallel computing）一般是指許多指令得以同時進行的計算模式。在同時進行的前提下，可以將計算的過程分解成小部分，之後以並發方式來加以解決。

電腦軟體可以被分成數個運算步驟來運行。為了解決某個特定問題，軟體採用某個算法，以一連串指令運行來完成。傳統上，這些指令都被送至單一的中央處理器，以循序方式運行完成。在這種處理方式下，單一時間中，只有單一指令被運行(processor level: 比較微處理器，CISC, 和RISC，即流水線Pipeline的概念，以及後來在Pipeline基礎上以提高指令處理效率為目的的硬體及軟體發展，比如branch-prediction, 比如forwarding，比如在每個運算單元前的指令堆疊，彙編程式設計師對programm code的順序改寫)。並行運算採用了多個運算單元，同時運行，以解決問題。

• 二維網孔連線網路上的FFT：

將n個處理器排成 的二維網孔連線網路，假設輸入序列 已經存放在了各個處理器中。

下面以16點變換來解釋這個問題，連成的網路及編號如下圖所示：

根據快速傅立葉變換的算法，我們來研究這16個點計算時四次循環的具體執行情況。

1. 同一列間隔一行的元素運算。
2. 同一列間相鄰行的元素運算。
3. 同一行間隔一列的元素運算。
4. 同一行間相鄰列的元素運算。

由上面的算法執行過程，我們發現，數據交換隻在同一行或同一列之間的節點間進行。如果我們在第一，二步循環之後對網孔中的數據進行矩陣轉置，那么就可以只在同一列節點之間進行運算。

• 超立方體連線網路上的FFT：

如果我們按超立方體連線的格雷碼將待變換點列填入，那么我們發現，數據交換將只在相鄰節點間進行。因此數據通信花費恆為O(1)。

可擴放性分析

首先，我們設訊息傳遞並行計算機中通信模型使用的是Store-and-forward而不是cut-through模型。下面令T_o表示通信開銷，T_s表示通信開始時間，T_w表示傳送一個字的通信時間，T_h表示數據每一跳的延遲， z_l表示第l次循環時的開銷，而t_c表示進行一個單位運算的時間。p為處理器數，d=log(p)，n為待變換的序列大小。 那么我們有公式：

有這個公式，我們可以得出：

在二維網孔上的等效率標準函式為：

在超立方體上的等效率標準函式為：

參閱

• 並行計算