基于集中式I/O技术的两阶段I/O算法优化

(1.内蒙古科技信息研究所，内蒙古 呼和浩特 010010;2.上海电机学院，上 海 200240)
摘 要： 文章在两阶段I/O的基础上，针对两阶段I/O中数据再分配算法，提出了一个全新改进 方案：统计——执行式I/O技术（statistic- executive I/O）。该方案针对最常见的按块 数据分布进行了I/O优化，这种优化策略将统计阶段的开销分摊到了若干I/O操作中。文章 评估统计——执行式I/O技术的性能，并与其他不同的集中式I/O技术进行了比较。
关键词：统计-执行式I/O；并行文件系统；性能评估；MPI I/O；并行程序
中图分类号：TP393  文献标识码：A  文章编号：1007—6921(2009)20—0070—03

在过去的几年中，计算机的处理能力成指数增长，但是，更多的迹象表明，I/O子系统逐渐 成为了并行体系结构中重要的瓶颈所在。因此，为了提高I/O子系统的性能，基于不同层次 的研究越来越多：硬件方面（例如存储区域网络），并行文件系统（例如 GPFS［1］ , PVFS［2］和Lustre［3］）和中间件（例如MPI I/O的库）。

本文主要研究现有的非连续数据的I/O技术。研究的重点是集中式I/O技术中的两 阶段I/O技术。在两阶段I/O研究的基础上，对两阶段I/O技术提出了优化方案，该优化方案 被称为统计——执行 I/O技术，这项技术与一般的两阶段I/O技术相比，有着较高的性能。 

本文提出了SE I/O技术，这个技术使用两种不同的策略来提高性能。首先，这个I/O技术被 分为两个阶段，第一个阶段是通信模式的计算，另一个阶段是执行通信和文件存取。这个策 略允许重复使用第一阶段产生的信息，因此，在相似的I/O操作经常执行的时候可以降低整 体的执行时间。第二个策略包括，通过利用进程之间交换数据来增加本地（局部）文件存取 。假设每一个进程存取相邻文件区域的独立的块，这些策略可以改善了I/O操作的效率。用 两阶段I/O算法与SE I/O算法相比较，我们的方法有若干的优势：首先是允许通信并行，在 每一个通信阶段，进程被组成进程对，并且执行私有的点对点的通信（接收/发送），这样 提供了更高级别的并行，因为若干个通信操作可以在同一时间执行。然后是，因为所有的进 程接收和发送相同的数据量，因此通信得到很好的平衡。

为了验证此方法的有效性，我们利用了科学应用中最常用的数据分配方式：按块分配对文 件进行划分［4］，然后分别执行两阶段I/O测试程序和SE I/O测试程序，基于实验 结果，可以得出结论：我们的算法可以大大减少整体I/O的开销。
1 两阶段I/O的概念

两阶段I/O方法通过分析集体I/O请求对数据的总体需求，把一次I/O操作分成两个阶段来完 成。

第一个阶段是所有进程交换彼此的I/O信息，确定每个进程的文件域，从磁盘上读取相应I/O 数据；第二个阶段是按照应用需求将缓冲区的数据交换分配到各进程的用户缓冲区，写操作 与读操作类似。在这两个阶段中，进程之间需要进行通信来使得同一通信域中的相关进程获 得自己的数据信息，从而得到程序总体的I/O行为信息，以便整合各个进程独立的I/O请求。 下面是一般情况下的两阶段方法［5］的简单描述。

第一阶段：①确定参加读取文件的进程，同步通信域中所有进程；②确定每个进程需要读取的数据；③每个进程计算进程访问的文件域(为文件的一个连续块)；④每个进程根据自己的文件域进行I/O访问，同步所有进程到每个进程I/O操作结束；第二阶段；⑤进行I/O数据的重分配；⑥同步所有进程到数据重分配结束。
2 统计——执行 I/O（SE I/O）概述

针对分布式系统，开发了一种新的I/O技术，称为SE I/O技术。方法是利 用快速通信网络来交换数据，目的是改善局部文件的访问，并且减小全局I/O操作的开销。 我们的技术通过通信操作，在文件系统执行存取操作之前，增加了本地数据，优化了两阶段 I/O（在ROMIO［6］基础上被广泛使用的集中式I/O）。

我们提出的统计——执行模式，将通信阶段和文件存取 模式从实际执行中分离开来。最终，通用的部分被计算一次，并且被多次重用。实验结果显 示：当与两阶段I/O技术相比较的时候，我们的方法获得了更好的性能。
2.1 统计——执行方式的集中式I/O算法

SEI/0的方法是：通过利用进程间的数据交换，来逐步增加本地的数据。在我们的算法中， 对于不连续的数据分布来说，数据类型结构可以通过统计程序来自动生成。这种程序分析了 数据分布和内存分配，并且选择了与数据传输相当的存储单元。

在这项工作中，我们将数据类型生成算法（统计程序）从执行阶段分离出去。执行阶段被看 作是数据传输和文件存取阶段。首先，阐述这一阶段，随后，对生成数据类 型的统计程序进行详细的描述。
2.2 执行阶段

在存储空间被分配完毕，并且数据类型也已经产生后，计算节点就要进行数据交换了。这个 操作是由一对进程发送和接收数据块这样的动作组成。

将进程交换数据块所需的阶段数标示为N。假设一个进程的进程号在进程数范围内，进 行数据交换的进程对的通信形式，相当于是一种基于树形结构的通信形式。

最终交换函数发送数据块到目标进程，并且从目标进程中接收相同数目的数据块。数据类型 用以整合被发送的数据。被接收的数据块以偏移量的值为起始地址，被连续存储。

一旦通信阶段结束了，I/O操作就可以执行了。在此之前，即将被发送的数据被打包，以增 加网络传输的执行效率。使用MPI_Pack函数来拷贝期望的数据到输出缓冲区。

执行阶段的最后一步是文件写回阶段。为每一个输出缓冲区决定文件偏移量是非常必 要的。write_disk函数是将输出缓冲区的内容写入文件的。需要注意的是，这些操作并行的 I/O操作，是在不重叠的数据文件数据块上进行的。
2.3 产生数据类型的统计程序

通常情况下，I/O阶段和计算阶段相互轮换（例如执行检查点）。基于这些原因，我们的技 术是让I/O以一种分离的方式工作：统计（数据类型的派生）只执行一次，提供的信息在每 一个执行阶段被反复重用。利用这种方式，可以将统计程序的开销分摊到多个I/O操作中。

数据类型生成算法的工作就像是一个统计程序：该程序执行数据的传输以及必要的文件存取 ，而对数据分布进行分析并产生数据类型。在阐述这些算法之前，介绍一些定义。

对于给定分布的数据块 ，为一个特定的进程定义一个特定数据块的物理地址，作为 该数据块所在的位置。值得注意的是，当X的数据块在通信阶段被交换的时候，某一特定的 数据块在不同的进程中可以有不同的物理地址。

对于给定分布的数据块 ，定义了一个特定的数据块的逻辑地址(Log_Addr)，作为该 数据块在原来的（不连续分布）矩阵中的位置。

一个数据块逻辑地址和物理地址的映射的代表符号是<m，n>。整型m和n相当于逻辑地址和物 理地址。第一个定义表述的是数据块的物理分布，它被用于派生数据类型。第二个定义描述 的是数据的排序，是决定数据块进行交换所必需的定义。

计算数据类型的问题在于如何找出这两个数值之间的关系。对于不连续的分布来说，我们假 设数据块最初的分布使用了数据类型（由偏移量和长度的序列组成）。根据给定的物理地址 计算逻辑地址，是通过分析数据类型的手段进行的。

数据类型派生算法包括三个阶段：内存映射表，通信和打包数据类型。

内存映射列表：在这个阶段，逻辑-物理地址映射会被储存在一个表结构中，表中的数据块 按照逻辑地址的值来排序。

通信和数据类型派生：一旦这样的列表被生成（注意，进程是并行执行的，每一个进程都会 计算出它的列表），这些列表就成为必不可少的决定因素，它决定在每一个通信阶段中哪 些数据块被传输。

对于给定的列表，如果目标进程号高于当前进程号，列表的后半部被发送（有高位逻辑地址 的），否则，列表的前半部被发送。一旦数据类型被生成，就被传输到目标进程。最后一步 是在于获得那些接收数据类型的每个数据块的逻辑地址和物理地址。

所有的元素都处理完成之后，新的通信阶段就能够被评价了。在描述了SE I/O算法的 内部结构之后，下面评估这项技术的性能。
3 实验结果

测试环境：所有的实验都是在相同的机群环境下运行的，测试环境是：实验是在一个 四节点的机群系统中进行的。该机群系统中每个节点的硬件配置为:CPU为Xeon 2.8GHz^、2 ，内存1.0GB，硬盘为36GB^、2，1000MB的双网卡，各节点间通过100Mbps的交换机相连接。 我们使用的操作系统是RedHat Linux 8.0，使用的编程语言是MPI-1.2.5 消息传递接口和C  语言。利用网络文件系统NFS 和网络信息服务NIS 实现了全局文件系统管理和全局用户管理 ，从而实现单一系统映像。

我们测试的是整体的I/O 时间，通过记录多次的I/O 时间运行，得到运行时间的数据。然后 对数据进行平均，利用平均值来进行测试结果的对比。

我们进行对比的是：按照两阶段I/O方法实现的I/O测试程序和使用SE I/O方法实现的I/O测 试程序。程序运行在多个进程上，我们利用输入文大小和运行测试程序的进程个数两个方面 的所得数据，对测试结果进行分析，进而进行带宽比较。按块分配策略的I/O测试结果分析 ：

图6、图7、图8 给出了数据分配为块分配（block-block）时两种实现方法使用1、2、4、8 、16 个进程读取不同大小（512×512、1024×1024和2048×2048）的文件所得的I/O 带宽 的比较。

这里的I/O带宽值是：每个进程数对应的I/O带宽的平均值。利用这个平均值，我们可以更加 清晰地看到I/O性能变化的趋势。

从图中我们可看到，使用两阶段I/O访问块分配数据时，在对三个大小

不同的文件进行操作 的时候，获得的平均带宽分别为： 512×512时，I/O平均带宽为1.114593Mbps；10241024 时，I /O平均带宽为1.170532Mbps；20482048时，I/O平均带宽为1.270621Mbps。而使用SE I/O方 法访问块分配数据时，在对三个大小不同的文件进行操作的时候，获得的平均带宽分别为： 512×512时，I/O平均带宽为1.1307Mbps；1024×1024时，I/O平均带宽为119533Mbps；2 048×2048时，I/O平均带宽为1.307796Mbps。

我们发现SE I/O的性能相对于两阶段I/O，带宽分别提升了0.275%，0.931%，2.926%，可见 ， SE I/O性能要好于两阶段I/O。而对于进程数来说，当进程数与节点数相一致的时候，带 宽的增长率是最大的，因此，当节点数与进程数相一致时 ，SE I/O技术在I/O时间中的通信 开销所占比例相对两阶段I/O技术来说，是减少幅度最大的（通信开销下降的比较快），因 此带宽的增长率是最大的。

对于每一种输入文件的大小，我们可以得到一个文件大小对于I/O性能影响的趋势，如图4  所示，当文件大小逐一递增的时候，I/O带宽的增长率逐渐增大，或者说，SE I/O技术的带 宽与两阶段I/O技术的平均带宽的差值越来越大。这就说明，当文件越来越大的时候，与两 阶段I/O相比，SE I/O技术的优势越来越明显。


4 结论

在对同一文件进行I/O操作的时候，随着进程数的增加，I/O 带宽随之降低。这是因为： 随着进程数的增加，交换数据块的开销逐渐增大，与读写数据的开销相比，在整体I/O时间 中所占的比重越来越大。

随着文件大小的增加，不论是两阶段I/O技术还是SE I/O技术，I/O的带宽的变化都是呈 上升趋势，这是因为：当数据块变大的时候，利用进程间交换数据得来的本地数据的数量也 随之增大，这时，读写数据的工作量变大，统计阶段产生用于数据交换的信息的工作量不变 ，交换数据的开销在整体I/O时间中所占的比重变得越来越小，因此，利用两阶段I/O技术和 SE I/O技术可以得到较好的I/O性能。

相比较两阶段I/O技术和SE I/O技术，SE I/O技术优化了数据再分配阶段的算法，提高了 统计阶段产生信息的重用性。同时，运行通信并行：在每一个通信阶段，进程被组成进程对 ，并且执行私有的点对点的通信。由于接收和发送的数据量是一致的，因此得到了很好的通 信平衡。
［参考文献］
［1］ Schmuck F, Haskin R，GPFS: A shared-disk file system for large compu ting clusters， Proceedings of FAST，2002,231～244.
［2］ Ligon WB, Ross RB ，An overview of the parallel virtual file system ， Proceedings of the extreme Linux workshop，1999,391～430.
［3］ Lustre: A scalable, high-performance file system，Cluster File Syste ms Inc white paper, 2002,version 1.0, 221～232.
［4］ 陈国良.并行计算——结构·算法·编程［M］. 北京:高等教育出版社, 1999. 
［5］ Rajeev Thakur，Alok Choudhary，An Extended Two-Phase Method for Acce ssing Sections of Out-of-Core Arrays LJJ，Scientific Programming，1996， 5(4)：3 01～317.
［6］ 张磊，赵军基于MPI-I/O的非连续I/O访问分析［J］计算机应用研究，200 8，1296～1297.
［7］ 张晨曦，王志英，张春元，戴葵，肖晓强计算机体系结构［M］北京：高 等教育出版社， 2005.