基于FFT并行算法的并行I/O性能的研究

摘要：该研究对象为并行计算机的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变化的串p并行I/O的单机模拟数据 表2 FFT变化的串p并行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格式阅读原文。”