並行快速傅立葉轉換

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

基本介紹

• 中文名：並行快速傅立葉變換
• 外文名：Parallel Fast Fourier transform
• 學科：數學
• 套用：信號處理
• 特性：高效快速

背景

（1）串列算法

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

（2）並行算法

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

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

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

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

下面以16點變換來解釋這個問題：

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

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

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

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

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

並行分析

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

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

1. 在二維網孔上的等效率標準函式為：
2. 在超立方體上的等效率標準函式為：