基于ＦＦＴ并行算法的并行Ｉ／Ｏ性能的研究

摘要：該研究對象為并行計算機的I/O性能，將任務分發給不同的處理結點，通過進程間的相互協調、有序合作完成FFT并行算法的實現。在完成任務的過程中，通過記錄I/O時間與計算時間，求出I/O 性能與計算性能，通過分析比較數據從而認識I/O性能的重要性。研究計算機的I/O性能對于如何進一步改進系統以及提高資源利用率具有重要意義。

關鍵詞：并行計算機系統；I/O性能；并行I/O；MPI；MPI-IO

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)33-1373-03

Research on Parallel I/O Performance Using FFT Parallel Algorithm

ZHANG Guan-hong，GAO Ling-ling

( Key Lab of Network and Intelligent Information Processiong，Heifei University， Hefei 230031， China)

Abstract: In this paper， the target for parallel computer I/O performance， the task will be distributed to the different treatment nodes， through the process of mutual coordination and cooperation in order to complete the FFT parallel algorithm to achieve. Upon completion of tasks in the process of adoption records of I/O time and computing time， obtained I/O performance and computing performance through the analysis of comparative data to understand I/O performance of the importance. On the computer I/O performance on how to further improve the system and improve the utilization of resources is of great significance.

Key words: parallel computer; I/O performance; parallel I/O; MPI， MPI-IO

1 引言

高性能并行計算是高科技、政府、經濟決策及軍事領域高性能計算的主要依靠，而目前，隨著處理機性能的不斷增長和多處理機系統的出現，計算機系統本身的處理能力得到了飛速的發展，但是I/O性能的增長速度卻跟不上系統本身處理能力的發展。從而使I/O性能成為高性能并行計算的主要性能瓶頸。要解決這一瓶頸，獲得高性能I/O，首先要了解并行環境中I/O的基本方法。根據存取技術不同，并行環境中I/O的基本方法可分為串行I/O和并行I/O[1]，在本文中，對并行文件I/O進行了研究，使用FFT并行算法進行實驗，分析了不同的實現方法對I/O帶寬的影響，為獲得高性能I/O提供了依據。

MPI 是消息傳遞函數庫的標準規范。MPI 由MPI 論壇開發，并在1994年公布該了該標準。MPI-2是MPI論壇在1997年宣布的MPI修改版本。原來的MPI被重命名為MPI-1。MPI-2 增加了許多特性， 其中最讓我們感興趣的特性是，它增加了MPI-IO 規范，即對可擴展I/O的支持。而MPI-1中根本未考慮I/O問題。

2 基于FFT并行算法的并行I/O

2.1 FFT變換的公式定義

一維離散序列的傅立葉(FFT)變換是指■，k=0，1，…，N-1，其中yk和xn均為長為N的復序列，wn=e-2π/n為N次單位原根。也可以記做：Y=FNX。其中：X=(x1，x2，∧，xn)T，Y=(y1，y2，∧，yn)。

2.2 FFT的并行求解分析

快速傅立葉變換并行計算的基本思想是分而治之，不妨設N為2的冥，令：

■

其中：■，i， j=1，2，…，N/2－1， 而WN/2=W2N為N/2次單位原根，則有：

■

其中μi，νi為向量U和V的第i個分量，它是一種遞推模型的計算格式，因向量U，V實際上是兩個輸入都為N/2的DFT問題，又可采用上述格式遞推求解。這就是快速傅立葉變換（FFT），其總計算量已經證明為O(NLogN)。

FFT的基-2并行計算過程如上圖的蝶網示意圖所示。利用蝶網的第一級邊，只需一步就可以計算出向量Y。如圖1所示，第0列的節點{i，0}(0≤i＜N/2)將接受直線邊傳來的數據μi和交叉邊傳來的數據νi，計算yi=μi+ωiNνi（設ωiN已存儲在其內部）；節點{i，0}（N/2≤i≤N－1）將接受直線邊傳來的數據νi-N/2與交叉邊傳來的數據μi-N/2，計算yi=μi-N/2+ωiNνi-N/2，即可得到向量Y。以此類推，向量U，V又可利用第1列，第2列的蝶網邊進行計算，……，直到第LogN層變為用原始向量X計算。可見，經過LogN個并行步后即可計算出一個N點一維FFT。相對與串行FFT的O(LogN)計算時間來說，已達到了線性加速比，應該來說，這是一種非常高效的并行算法。

2.3 FFT的并行算法設計

并行算法的設計實現過程實際上就是一個將類似于圖2的算法描述圖的節點映射到某個多處理機系統的節點上的過程，就是將FFT分塊處理。以下均假設一維FFT的問題規模為N=2t，圖2中的各行從上往下依次編號為0，1，∧，N-1，各列從右往左依次編號為0，1，∧，LogN-1，多處理機的節點數為P+2S，1≤S≤t，按照某種順序也編號為0，1，∧，P-1。

如圖2所示，各處理機間的任務之間進行任務通信，完成FFT變換的并行算法。若假設P=4，在并行處理第一階段，Task1、Task2和Task3、Task4交換數據結果，……，如果這樣遞歸計算，直到log2N/p+1次交換后，把結果數據計算得出。

采用Master/Slave（主/從）模型，在算法過程中，不但有Master節點和Slave節點之間的數據通信和傳遞，且Slave節點任務之間也要進行數據通信和傳遞，且在每一個循環階段，都要進行同步、，才可以進行下一步。

對Master節點：Master節點讀入原始復序列數據，并將該復序列整理，分成P塊，再將每快FFT復序列數據（長度為N/P）傳給將要對其進行處理的Slave節點。在最后算法將結束時，等到每個Slave節點完成任務，Master節點負責接收各個處理器返回的計算結果。

對Slave節點：在Master節點發送和回收數據期間，第一步，子處理器先處理N/P數據長度的快速傅立葉變換（FFT），等待進入并行計算的數據同步交換階段（要進行log2N/p+1次數據同步交換）；第二步，進入并行數據同步交換階段，找到要進行兩兩數據同步和交換的子任務，合成為一個組；第三步，在這個組內進行數據同步和交換，此時約定，先進行發送數據給對方，再接受對方發生過來的數據；第四步，利用自己節點上一階段計算出來的數據和同組成員發送過來的交換數據，根據快速傅立葉變換（FFT）的計算方法，得出數據結果；第五步，解散第二步已經形成的組；第六步，重復二、三、四、五步，直到log2N/p+1次數據交換和同步。

3 FFT的并行I/O性能的測試結果及分析

本實驗采用了Master/Slave（主/從）模型的Master發送FFT復序列和回收結果序列。主要原因是因為采用該模型的并行程序結構清楚明了，可讀性強。本實驗環境是在LINUX操作系統下使用了并行計算平臺（MPI-1.2.5），100M以太局域網；數據來源：由程序隨機生成數據長度為N的隨機復序列。

下面幾個表分別為FFT變化其中包含串行、并行算法運算時間的單機模擬和多機模擬上的實驗結果。單機模擬是指在單機上模擬完成Master和Slaver進程的運行及相互通信。這些進程相互并發執行。這種模擬可將傳輸數據之間的傳遞和進程間的通信不通過網絡而直接用單機進程傳遞，這樣可以使傳輸數據的時間模擬到最小，而忽略了網絡的數據傳輸因素。在單機模擬的情況下，由于只有一臺節點機來運行程序，所以這種情況下的并行算法的執行時間實際上大約表示為多個子任務所執行時間之和。因此，若拿單機模擬的并行運算時間和多機模擬的并行運算時間進行比較的話，應該將單機模擬的并行運算時間除以子任務數，即拿平均一個任務所需的時間來比較。多機模擬是指在局域網的環境下，任選定的一臺主節點運行Master進程，而其他的節點機各運行一個Slaver進程，數據之間的傳遞和進程之間通訊就在Master和Slaver之間，或Slaver和Slaver之間通過局域網的連接而進行。

表1FFT變化的串﹑并行I/O的單機模擬數據 表2 FFT變化的串﹑并行I/O的多機模擬數據

■

■

圖3FFT串并算法的并行效率比較 圖4FFT串并算法的運行時間比較

從表1、表2、圖3和圖4數據中，我們可以得出：

1）無論是單機模擬還是多機模擬，隨著進程數和節點機數的增加，問題的運行時間都在下降，這是由于將問題的計算時間和通信時間重疊進行。因此，可以看出MPI-2的并行I/O能夠大大的提高機群系統的I/O性能。

2）由于規模的增加，問題的計算時間占總的運行時間的比重增加，而任務之間的通訊時間占總的運行時間的比重相對就要減少。這樣對于運行時間的節省就越來越小了，但一直是處在減少的趨勢。

3）單機模擬的效率高于多機模擬效率。因為，單機模擬的進程通訊量要比多機模擬的通訊量少，這樣，單機模擬比多機模擬的加速比要大，單機模擬的效率要高。

4）隨著節點機數的增加，加速比增加呈增加趨勢（節點機的增加，同時增加了任務之間的通信代價），然而效率（加速比/節點機數）一直呈下降趨勢。

5）隨著問題規模N的增加，加速比和效率呈上升趨勢。

由表3和圖5可以看出：

1）隨著進程數的增加，三種I/O方式的執行時間都在減少，這表明并行I/O的處理性能要高于串行I/O。

2）顯式偏移文件并行I/O方式的執行時間要比另外兩種I/O方式的執行時間少的多，相差了幾個數量級，這充分說明了顯式偏移文件并行I/O方式的讀寫效率最高。

3）多視口文件并行I/O方式的執行時間和MPI-1的I/O方式的執行時間相差不多，甚至當進程數增大到某一數目時，多視口文件并行I/O方式的執行時間反而大于MPI-1的I/O方式的執行時間，這是由于多視口文件并行I/O方式需要額外的維護文件指針的開銷，它雖然增加了讀寫操作的靈活性，但同時也付出了降低效率的代價。

4 結論

本文討論了基于FFT并行算法的并行環境中I/O的基本方法——串行I/O方法和并行I/O方法，并使用MPI-1及MPI-2 對這兩種方法進行了實現， 分析了不同的實現方法對I/O 帶寬產生的影響。通過理論分析和實驗表明，基于MPI-2 的并行I/O 實現方法與其它I/O實現方法相比，可得到更高的I/O 帶寬；在MPI-2的并行I/O實現中，對于文件訪問次數少的I/O 請求，使用noncollectiveI/O 操作要優于collective I/O 操作。

參考文獻：

[1] 李小衛，羅省賢.基于MPI的并行I/O方法[J].微型機與應用，2003(3):13-21.

[2] 黃鎧，徐志偉.可擴展并行計算技術、結構與編程[M].北京: 機械工業出版社，2000.

[3] 李文，張大鵬，劉志勇，等.圖像恢復的高效并行算法及關鍵技術[J].計算機研究與發展，2002，39(7):848-854.

[4] 劉輝，胡靜，王振飛，等.MPI-2中的并行I/的使用分析[J].計算機工程，2003，29(2):229-232.

[5] Del Rosario J， Choudhary A. High Performance I/O for Parallel Computers: Problems and Prospects[J].Computer，1994，27(3):59-68.

[6] Kotz D. Appcications of Parallel I/O.Technical Report PCS-TR96-297[D].Dartmouth College，1996.

[7] Gropp W， Lusk E. A high-performance: portable implementation of the MPI message passing interface standard[M].Parallel Computing，1996.

[8] Lusk E， Gropp W. The implementation of the second generation MPICH ADI[J].Mathematics and Computer Science Division.USA:Argonne National Laboratory，1997.

[9] Gropp W，Lusk E.MPICH Working Note: The Second-Generation ADI for the MPICH Implementation of MPI[J].USA:Argonne National Laboratory，1995.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”