串行演算法回顧
在快速傅立葉轉換(FFT)的平行演算法中使用了蝶形連接網絡。
平行演算法
- 二維網孔連接網絡上的FFT:
將n個處理器排成的二維網孔連接網絡,假設輸入序列已經存放在了各個處理器中。
下面以16點轉換來解釋這個問題,連成的網絡及編號如下圖所示:
根據快速傅立葉轉換的演算法,我們來研究這16個點計算時四次迴圈的具體執行情況。
- 同一列間隔一行的元素運算。
- 同一列間相鄰行的元素運算。
- 同一行間隔一列的元素運算。
- 同一行間相鄰列的元素運算。
由上面的演算法執行過程,我們發現,數據交換只在同一行或同一列之間的節點間進行。如果我們在第一,二步迴圈之後對網孔中的數據進行矩陣轉置,那麼就可以只在同一列節點之間進行運算。
- 超立方體連接網絡上的FFT:
如果我們按超立方體連接的格雷碼將待轉換點列填入,那麼我們發現,數據交換將只在相鄰節點間進行。因此數據通訊花費恆為O(1)。
演算法複雜度分析
可擴放性分析
首先,我們設訊息遞移平行計算機中通訊模型使用的是Store-and-forward而不是cut-through模型。下面令表示通訊開銷,表示通訊開始時間,表示傳送一個字的通訊時間,表示數據每一跳的延遲,表示第l次迴圈時的開銷,而表示進行一個單位元運算的時間。p為處理器數,d=log(p),n為待轉換的序列大小。 那麼我們有公式:
有這個公式,我們可以得出:
- 在二維網孔上的等效率標準函數為:
- 在超立方體上的等效率標準函數為:;
- 參考文獻:The Scability of FFT on Parallel Computers, Anshul Gupta and Vipim Kummar。
參閱
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.