平行快速傅立葉轉換

串行演算法回顧

在快速傅立葉轉換（FFT）的平行演算法中使用了蝶形連接網路。

平行演算法

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

將n個處理器排成${\sqrt {n}}\times {\sqrt {n}}$的二維網孔連接網路，假設輸入序列$\{a_{0},a_{1},......,a_{n-1}\}$已經存放在了各個處理器中。

下面以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為待轉換的序列大小。 那麼我們有公式：

$T_{o}=\sum _{l=0}^{d-1}(T_{s}+(T_{h}+T_{w}{\frac {n}{p}})z_{l})$

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

1. 在二維網孔上的等效率標準函式為：$W=2Kt_{w}{\sqrt {p}}\times 2^{2K{\frac {t_{w}}{t_{c}}}{\sqrt {p}}}$
2. 在超立方體上的等效率標準函式為：$W=Kt_{w}\times p^{K{\frac {t_{w}}{t_{c}}}}\times \log p$；

• 參考文獻：The Scability of FFT on Parallel Computers, Anshul Gupta and Vipim Kummar。

參閱

• 平行計算