（计算机系统结构专业论文）集中式io技术研究及数据再分配算法优化.pdf

内蒙古大学硕士学位论文 集中式i 0 技术研究及数据再分配算法优化 摘要 本文对集中式i l o 技术进行了研究，并在此基础上讨论了如何提高对非连 续数据访问的性能。在许多并行应用中，每个进程需要访问在文件中存放位置 不连续的小块数据。访问这种不连续的小块数据需要很多的i o 请求，这样势 必会导致并行i 0 性能的下降。因此i 0 操作已经成为了影响并行应用程序 效率的主要瓶颈。如何对数据进行组织、存储以及有效的访问数据成为了迫 切需要研究的问题。 本文在两阶段i o 的基础上，针对两阶段i o 中数据再分配算法，提出了 一个全新改进方案：统计一执行式i o 技术( s t a t i s t i c - e x e c u t i v ei 0 ) 。该 方案针对最常见的块数据分布和循环数据分布进行了i o 优化。我们将并行 i o 分为两个阶段：统计阶段和执行阶段。在统计阶段，通信模式被计算出来， 并且自动生成所需的数据类型。这些信息在执行阶段( 执行通信和文件存取) 被使用。这两个阶段是独立的，所以，对于重复的文件存取模式，统计阶段的 计算可以执行一次，计算的结果被执行阶段多次重用。这种策略将统计阶段的 开销分摊到了若干i o 操作中。在本文中，我们评估统计一执行式i 0 技术的 性能，并且与其他不同的集中式i o 技术进行比较。基于按块分配和按循环分 配的策略，对两阶段i o 进行了优化，实验结果显示，本文的方法优于一般的 两阶段i o 技术。 关键词：统计一执行式i 0 ，并行文件系统，性能评估，m p ii o ，并行程序 集中式i o 技术研究及数据再分配算泫优化 t h es t u d yo fc o l l e c t i v ei oa n dt h eo p t i m i z a t i o n o f d a t ar e a l l o c a t ea l g o r i t h m a b s t r a c t a ni n t e g r a t e dr e s e a r c ho nc o l l e c t i v ei ot e c h n o l o g yi sm a d e ，a n daf u r t h e re x p l o r e d m e a s u r e st oa d v a n c et h ea c c e s st on o n c o n t i n u o u sd a t ai sd i s c u s s e di n t h i se s s a y i nm a n y p a r a l l e la p p l i c a t i o n s ，e a c hp r o c e s sn e e d st oa c c e s so fd a t aw i t hn o n - c o n t i n u o u sp o s i t i o n ，a n dt h e d a t aw h i c ha r es t o r e di nt h ed o c u m e n t n u m e r o u si or e q u e s t sw o u l db en e c e s s a r yi no r d e rt o o b t a i na c c e s st ot h i sk i n do fn o n c o n t i n u o u sf r a g m e n t so fd a t a ，w h i c hw o u l dd e f i n i t e l y u n d e r m i n et h ep e r f o r m a n c eo fp a r a l l e li o t h e r e f o r e ，i oo p e r a t i o nh a sa l r e a d yb e c o m et h e b o t t l e n e c kf o rt h ee f f i c i e n c yo fp a r a l l e la p p l i c a t i o n s h o wt oo r g a n i z e ，s t o r ea n de f f i c i e n t l y a c c e s sd a t a ，r i m si n t oap r o b l e mc r y i n gf o rr e s e a r c h b a s e do nt h et w o - p h a s ei o ，an o v e li m p r o v e m e n ts o l u t i o ni sp r e s e n t e df o rt h ea l g o r i t h mo f d a t ar e a l l o e a t i o ni nt h et w o - p h a s ei o ：s t a t i s t i c - e x e c u t i v ei o ，w h i c ho p t i m i z e st h ei oo ft h e m o s tf a m i l i a rc y c l i c - c y c l i ca n db l o c k - b l o c kd a t ad i s t r i b u t i o n w ed i v i d et h ep a r a l l e li oi n t ot w o p h a s e s ：s t a t i s t i ca n de x e c u t i v e c o m m u n i c a t i o nm o d e sa r ec a l c u l a t e da n da u t o m a t i c a l l yb u i l d i n t on e e d e dd a t at y p e sd u r i n gs t a t i s t i cp h a s e t h i si n f o r m a t i o ni su s e dd u r i n gt h ee x e c u t o rs t a g e i np e r f o r m i n gt h ec o m m u n i c a t i o na n df i l ea c c e s s e s t h et w op h a s e sa r ed e c o u p l e d t h e r e f o r e ，i n r e p e a t e df i l ea c c e s sp a t t e r n s ，t h ec o m p u t a t i o n sf r o ms t a t i s t i cp h a s ec o u l db ep e r f o r m e do n c ea n d r e u s e ds e v e r a lt i m e sd u r i n ge x e c u t i v ep h a s e t h i ss t r a t e g ya l l o w st oa m o r t i z et h es t a t i s t i cc o s t o v e rs e v e r a li oo p e r a t i o n s i nt h i st h e s i s ，w ee v a l u a t et h ep e r f o r m a n c eo fm u l t i p l ep h a s ei o c o l l e c t i v et e c h n i q u ea n dw ec o m p a r ei tw i t ho t h e rs t a t eo ft h ea r ta p p r o a c h e s e x p e r i m e n t a l r e s u l t ss h o wt h a tf o rc y c l i c c y c l i ca n db l o c k - b l o c kd a t ad i s t r i b u t i o n ，o u rm e t h o do u t p e r f o r m si n t h el a r g em a j o r i t yo ft w o - p h a s ei oo p t i m i z a t i o n st e c h n i q u e s k e y w o r d s ：s t a t i s t i c e x e c u t i v ei o ，p a r a l l e lf i l es y s t e m s ，p e r f o r m a n c ee v a l u a t i o n ，m p ii o ， p a r a l l e lp r o g r a m m i n g 内蒙古大学硕士学位论文 图表目录 图2 - 1 分布式存储系统并行i o 的一般结构7 图2 - 2n f s 中的并行文件访问结构图：9 图2 - 3 并行文件系统中的并行文件访问结构图1 0 图3 - 1s p m d 执行模型1 4 图3 - 2s p m d 程序的并行执行过程1 4 图4 - 1r o m i o 结构模型1 7 图4 - 2 数据筛选1 8 图4 - 3b l o c k b l o c k 划分的数据再分配图示2 l 图4 - 4p o 和p 1 的数据分布2 2 图4 - 5p o 缓冲区中的数据分布2 2 图4 - 6p 1 缓冲区中的数据分布2 2 图4 - 7 用户缓冲区中的数据分布2 3 图4 - 8 按块分配的简单实现2 3 图4 - 9 按循环分配的简单实现2 4 图5 - 1n x = 1 6 ，n p = 4 的数据分布图示2 6 图5 - 2s ei o 算法的伪代码2 7 图5 - 3 数据块根据s ei o 算法在四个进程中的分布2 7 图5 - 4c o m p u t e _ o f f s e t 函数伪代码2 9 图5 - 5 阶段0 之后的数据分布3 0 图5 - 6 阶段1 后的数据分布3 0 图5 - 7 打包后的数据分布3 1 图5 - 8 在打包之后，s e 算法最终的数据分布( p o ，n x ：3 2 ，n p = 4 ) 3 2 图5 - 9p h y 2 l o g 程序的伪代码3 4 图5 - 1 0s ei o 数据类型派生算法伪代码3 4 图5 - 1 1x 派生数据类型实例。3 5 图5 - 1 2c o m p u t ed a t a t y p e 程序伪代码3 6 图5 - 1 3c a c h e - 主存层次结构3 9 v 集中式i o 技术研究及数据再分配算法优化 图5 - 1 4 多级存储层次3 9 图5 - 1 5 未采取措施( b l o c k - b l o c k ) 4 0 图5 - 1 6 未采取措施( c y c l i c c y c l i c ) 4 0 图5 - 1 7 分别采取两种措施后i o 读数据的带宽4 l 图5 - 1 8 采取措施后( b l o c k - b l o c k ) 4 2 图5 - 1 9 采取措施后( c y c l i c c y c l i c ) 4 2 图5 - 2 0 文件大小为5 1 2 5 1 2 的i o 带宽( b l o c k - b l o c k ) 4 4 图5 2 l 文件大小为1 0 2 4 1 0 2 4 的i o 带宽( b l o c k - b l o c k ) 4 4 图5 - 2 2 文件大小为2 0 4 8 * 2 0 4 8 的i o 带宽( b l o c k - b l o c k ) 4 4 图5 - 2 3 读取不同大小文件的i 0 性能( b l o c k - b l o c k ) 4 5 图5 - 2 4 文件大小为5 1 2 5 1 2 的i o 带宽( c y c l 工c - c y c l i c ) 4 5 图5 - 2 5 文件大小为1 0 2 4 1 0 2 4 的i o 带宽( c y c l i c c y c l i c ) 4 5 图5 - 2 6 文件大小为2 0 4 8 * 2 0 4 8 的i 0 带宽( c y c l i c c y c l i c ) 4 6 图5 - 2 7 读取不同大小文件的i o 性能( c y c l i c - c y c l i c ) 4 6 表5 一b i n r a n k 、n u m o n e s 和a l l o c o f f s e t 的值( n x = 1 6 ，n p = 4 ) 2 8 表5 2 进行交换数据的进程对( n p = 8 ，n p h = 3 ) 2 9 表5 3 每个阶段每个进程的r e c v f f s e t 值( n x = 1 6 ，n p = 4 ) 2 9 表5 4b i n r a n k ，p e r m _ b i nr a n k ，f i l e o f f s e t 的值( n x = 1 6 ，n p = 4 ) 3 1 v i 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。除本文已 经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得囱墓直盔堂 及其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 学位论文作者签名： 日期： 指导教师签名： 日期： 餮主 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，e p 内蒙古大学有权将学位论文的 全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允许编入有关数据库进行 检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。为保护学院和导师的知识产权，作 者在学期间取得的研究成果属于内蒙古大学。作者今后使用涉及在学期间主要研究内容或研究成果，须 征得内蒙古大学就读期间导师的同意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公 开发表。 学位论文作者签名： 日期： 内蒙古大学硕士学位论文 1 1 论文研究背景 第一章绪论 在科学计算中，并行应用程序需要读取文件内大量的非连续的数据。因此，并行i o 性能的高低，已经成为了影响并行应用程序的主要瓶颈。虽然在当前的并行系统中已经 应用到了很多高性能的i o 技术，但是并行应用的i o 带宽只能达到峰值i o 带宽的十分 之一或者更少n 1 ，造成这种情况的主要原因是，并行应用程序主要是面对小块数据的i o 请求，而并行u o 系统是面对数据块的操作请求，由于并行应用程序需要执行大量的i o 操作，因此，如何对数据进行有效的组织、存储以及访问，成为了提高并行系统i o 性能 的关键问题。 在过去的几年中，计算机的处理能力成指数增长，但是，更多的迹象表明，i o 子系 统逐渐成为了并行体系结构中重要的瓶颈所在。因此，为了提高i o 子系统的性能，基于 不同层次的研究越来越多：硬件方面( 例如存储区域网络) ，并行文件系统( 例如g p f s 口1 ， p v f s 3 1 和l u s t r e “1 ) 和中间件( 例如m p ii o 的库) 。 本文的主要贡献是，针对分布式系统，开发了一种新的i o 技术，我们称为s f i o 技术。我们的方法是，利用快速通信网络交换数据，目的是改善局部文件的访问，并且减 小全局i o 操作的开销。我们的技术通过通信操作，在文件系统执行存取操作之前，增加 了本地数据。优化了两阶段i o 。我们提出了一种基于统计一执行的模式。这种模式将通信 阶段和文件存取模式从实际执行中分离开来。最终，通用的部分被计算一次，而被多次重 用。我们提出了一种实验方法来评估我们的算法的有效性，实验结果显示：当与_ 两阶段i o 技术相比较的时候，我们的方法在文件大小不同的情况下，分别以按块分配和按循环分配 为数据分配方式，i o 带宽有了一定的提高。 1 2 论文研究的内容 并行应用的进程经常通过发出大量的小规模的y o 请求来进行常用数据的存取。集中 式i o 通过合并小的独立的请求为大的全局的请求解决了问题，从而优化了网络和磁盘的 性能。根据合并请求产生的位置，我们可以区别两种集中式y o 。如果合并请求产生在y o 节点，则被称为磁盘向导式g o 乜纠，如果合并请求发生在中间节点或计算节点，该方法被 集中式b o 技术研究及数据再分配算法优化 称为两阶段式的i o 瞳5 | 。两阶段式i o 执行在r o m i o 接口( r o m i o 是对m p i i o 这一m p i 2 中的并行f o 接口的一个移植实现) ，r o m i o 是一种非常流行的m p i f o 接口。我们的技 术同样是致力于通过通信操作来增加本地数据，但是，相比之下，这是一个有着若干通信 阶段的多层次算法，这种算法带来了更高的性能。 另一个并行i o 优化技术是列表式i o ，在这种方式中，非连续数据的存取被指定为， 是通过在连续内存空间或文件区域内有偏移量的列表实现的，这个列表是一系列长度毗连 地区。对于基于m p i 的并行i o 来说，m p i f o 是一个标准接口。m p i 的数据类型被m p i f o y 用于声明视口【2 u 和执行非连续数据的存取。视口对于一个文件中潜在的不连续数据来说， 是一个连续的窗口，在一个文件上声明了视口之后，进程可以以一种连续的方式查看和存 取文件中的非连续的数据，从而改善了非连续数据存取的管理，从而增大了数据吞吐量。 许多研究人员已经为优化m p ii o 数据操作做出了贡献：数据筛选【6 】，非连续存储【” 7 1 ， 集中式缓存【8 】，整合后写缓冲区【9 】集中式i o 和整合缓冲区技术综合等。而另一些技术， 则是对m p if o 文件自动生成优化的配置方案【n 】。 g p f s 2 1 ，p v f s 3 1 和l u s t r e 4 】都是并行文件系统，全球前5 0 0 名的超级计算机中的大多 数使用了这些文件系统，来管理集群的存储。数据条带化是在g p f s 下的一项集中式的优 化技术。使用l u s t r e 文件连接( 将两个文件合并成一个文件) 来提高集中式i o 的性能的 方法在 1 2 】中被提出。 对于集中式i o 技术中的两阶段i o ，我们提出了一个统计阶段，这个阶段自动生成数 据类型，这些数据类型被用于选择将要被交换的数据、分配远程的数据以及数据传送到磁 盘。这个是一项新的设计，这项设计可以处理最常用的块分布和循环分布。另外，与其他 集中式i o 不同的是：统计阶段与执行阶段( 数据交换和磁盘数据迁移) 是分开的，这样 就允许将统计阶段的开销分摊到了若干存取模式中。 1 3 论文的结构 本文共分为六个章节： 第一章介绍了论文的研究背景以及论文研究的主要内容，简要介绍了s ei o 技术对并 行系统i o 性能的改善情况。 第二章介绍了并行系统i o 性能的研究现状和它的研究重点；介绍了并行应用中非连 续i o 产生的原因、影响f o 性能的因素以及提高并行系统i o 性能的方法。 内蒙古大学硕士学位论文 第三章对m p i 进行了简单的介绍，同时对这种基于消息传递的并行程序的特点进行了 描述。在对数据分配进行介绍之后，简要叙述了m p i 2 对并行环境的f o 实现的基本方法。 第四章讨论了非连续数据访问的几种不同的实现方法：数据筛选、集中式i o 、列表 f o 和视口i o 。着重对集中式i o 方法中的两阶段i o 技术进行说明，介绍了两阶段i o 中数据的分配方式和两阶段f o 技术的实现思路。 第五章首先介绍了s ei o 技术的设计思路，并且在不同的数据分配方式下进行了实现。 通过例子，对s ei o 技术的执行过程和优化方法进行了详细的介绍。通过对最终试验数据 的分析，比较了s ei o 技术与两阶段f o 技术对并行系统i o 性能的影响。 第六章对全文的工作进行总结并提出了进一步的工作方向。 3 集中式i o 技术研究及数据再分配算法优化 2 1 并行i o 研究现状 第二章并行i 0 技术概述 随着处理机性能的不断增长和多处理机系统的出现，计算机系统本身的处理能力得到 了飞速的发展。但是i o 性能的增长速度却跟不上系统本身处理能力的发展，目前在i 0 子系统性能和系统本身的处理能力之间存在着很大的差距。由于在处理能力和i o 性能之 间存在着这种差距，因此问题的求解速度将由i 0 的速度来决定n 3 1 。 如今，因为硬件价格的降低和技术的逐渐成熟，并行计算的应用日趋广泛。然而，通 常并行计算所关注的问题往往只是与计算有关，诸如尽最大可能挖掘处理器的潜力等等。 对于i o 处理，则通常继承了串行程序设计时的思路。不过从现实的情况来看，i o 设备性 能的发展速度往往落后于系统整体的处理能力。因此，它在很多情形下都成为了系统的瓶 颈。 传统的大型并行计算系统往往有一个专门的节点用于进行磁盘输入输出操作。这样的 好处就在于结构简洁，实现方便。从物理结构来看，这些节点往往具备“冗余磁盘阵列” ( r a i d ，r e d u n d a n ta r r a yo fi n e x p e n s i v ed is k s ) ，即把很多个磁盘集成在起作为整体 工作。它包括很多种不同的实现，如r a i d0 ，r a i d1 等等。这种技术具有两个优点：一是 通过并发读写，加快速度，二是可以进行数据的冗余备份，加强可靠性n 引。从某种意义上 说，这也可以算是一种“并行i o ”，然而并不是本文讨论的重点。首先大型的r a i d 系统成 本很高，可扩展性受到物理空间上的制约；其次对于网络有很高要求，否则速度的优越性 不能充分发挥。当今有越来越多的并行计算是借助子集群技术，这就需要新的并行i o 技 术。 现代高性能计算最常见的：分布式的并行i o ，也就是把文件分散到各个节点上去。它 的好处在于不仅仅使得并行读写磁盘得以实现，而且充分利用了网络通道的并行传输，可 扩展性也比较强，成本却不高。这种技术包含两种方式n 利：第一种方式是把一个大的文件 分割成为多个数据块，然后按照某种策略分布在许多节点上；第二种方式是把许多完整的 小文件分布在不同的节点上。这两种实现对应于不同的应用。比如，在天气预报，石油勘 探等应用中，海量数据是主要的问题。而在邮件服务器等网络应用中，往往会负担大量用 户的数据，每个用户的数据是由一系列零散的小文件构成。 4 内蒙古大学硕士学位论文 2 2i o 技术面临的问题与解决的途径 2 2 1i 0 技术面临的问题 在并行i o 系统中，结点以及它们的本地磁盘通过网络连接起来。i o 系统可达到的带 宽依赖于两个参数：磁盘带宽和网络带宽。在并行i o 操作中，平衡这两个参数以消除瓶 颈是非常重要的。当数据处于远程结点时，在一个并行i o 操作中，通信开销较大。如果 在磁盘之间的数据分布与应用程序的访问行为不是合适地匹配，更可能会导致额外的通信 开销，在最坏的情况下，网络带宽会成为并行i 0 的限制因素。举例来说，如果把1 0 个字 节的小文件分成1 0 部分放在1 0 个节点上，表面看是充分利用了磁盘的并行读写能力，可 使用中却不得不大量通过网络传输，这就与原始目标背道而驰了。文件拆分与分配策略， 对于一个并行i o 系统的性能也有着重要的影响，因为它规定了一个文件的不同部分是如 何分布到不同结点的磁盘中。举例来说，假如把一个文件分成两部分，分别放到a 、b 两个 节点上，结果实际使用中a 节点反而在更多的时候去b 节点读取数据，b 节点则去读a 节点， 这就显得不够经济n 钔。 在并行i o 系统中，文件的组织方式是多种多样的，并不仅仅是把一个文件平均的分 段然后按顺序的存放。首先可以分类为一维存储与多维存储。一维存储的含义是把文件分 为若干段，然后存放在以文件名为名的目录下面。还有一些是按照二维甚至多维的方式组 织，二维情况是：每个文件分为若干长度未必一致的子文件，而每个子文件再分为许多长 度相同的文件分支。当然这种维数不应该太高，否则就成了无穷无尽的磁盘碎片。分成多 维主要是因为，有时候这种分布是与文件内容和使用方式有关系的，甚至不一定遵循文件 原先的连续性。举个例子来说，文件中存放的是大型矩阵，而文件本身是按照“行”来存 储的。另一方面，在程序中读写却要按照“列 来进行操作。如果依然按照文件原来的组 织方式，按照行平均分成若干段，放在不同的节点上，那么读取效率就会比较低。相反， 如果按列来分块，虽然文件在表面上看没有遵循原有的连续性，但使用中却提高了效率。 2 2 2 解决的途径 p u r a k a y a s t h a 等人概括了并行计算领域一个有趣的法则：9 0 的磁盘数据访问量是由占 请求总数不到1 0 的较大的数据请求要求的，而访问请求总数中的9 0 的请求是较小的数据 请求n4 】。在并行i 0 系统中，不仅仅要研究文件的存储方式，还应该研究文件的访问方式。 集中式i 0 技术研究及数据再分配算法优化 这方面的优化方法主要有三种： 1 )不连续访问优化。这种优化方式是将一个进程中的多个分离的i o 操作合并为一 个。这种方式的优点在于将计算节点中的零散操作合并起来，减少通信开销。实现的方式 主要为提供特殊的i o 库函数，使得程序员在编写程序的时候可以简单的调用，而不需要 知道实现细节。 2 ) 集中式i o 。这种方法也是将若干个i o 操作合并，与第一种不同的地方在于，它 是将不同进程的i o 操作合并，因此是更高层次的优化。从输出来看，从多个进程读取数 据后，形成大的连续数据块，然后写磁盘。从输入来看，从磁盘上读取连续的数据块，然 后分发给不同进程。 3 )自适应方法。与前两者不同，这一方法含义很广，并不是特指某一种操作。比如， 在并行计算中，有时候负载不均衡，有的节点还在计算，有的节点已经算完了。这时候通 过某些算法，估计程序的需要，让空闲的节点预先把磁盘中的数据读入内存。这些算法可 能是：根据现有的文件指针，把下面的数据读入；根据访问量，把需求最频繁的数据读入 等等。当然这也有风险，比如读入了一些并不需要的东西。因此怎样设计合理的算法是非 常重要的。需要说明的是上面这些优化方法通常并不要求程序员具体的参与细节操作，而 是通过诸如编译器优化等方式进行。这样的好处是，使得i o 操作被封装在黑箱里，程序 员在编程的时候并不需要大规模改写过去的代码，感觉就好像只是换了个环境而已，这大 大加强了程序的可移植性。 由于并行程序需要访问的数据量比较庞大，因此，在整个并行应用中，i o 性能占有很 重要的地位。虽然i o 速度一直低于计算速度，但是通过一系列的措施，我们仍然可以获 得较高的i o 性能。如：高速i o 硬件、适合的文件系统、适合的应用程序接口以及a p i 的高性能实现工具组合等。 2 3 并行i o 概述 对于应用来说，无论是串行还是并行，都会去访问存放在文件中的数据，如读取初始 化的数据、设置检查点、分析数据以及可视化、写结果等。我们关注的焦点在于，由多个 进程参与的并行应用程序。在这些应用中，访问存放在文件中的数据是由多个进程完成的。 我们定义并行i 0 ，从而使文件中的数据可以被一个并行应用的多个进程同时读取。一 般有两种访问方式，第一种访问方式：每个进程访问一个独立的文件( 在进程间没有文件 6 内蒙古大学硕：l ：学位论文 的共享) ，这种访问方式在某些情况下可以被看做是并行i 0 ，然而，它实际是通过大量的 进程，独立的执行串行i o 来实现的：第二种访问方式：所有的进程访问单一的共享文件。 而这种情况是真正的并行i o ，因为它是由所有的进程访问一个共享文件来实现的。 近些年来，随着c p u 的速度和通信性能的提升，c p u 性能与i o 性能的差距越来越大， 虽然存储器的存储密度得到了很大的提升，但是，单个磁盘的性能并没有因此而得到大幅 提升。随着并行机和并行技术的发展，科学应用越来越多的使用这些技术来解决大量计算 的问题，同时，也越来越多的使用这些技术来解决一些大量数据的访问问题。因此，提升 i o 性能的工作显得尤为重要。 2 4 并行i 0 的结构 目前，并行机中存在的并行i o 的基本构造如下： l 、分布式存储集群n 5 1e 1 6 ：主要包括i b ms p 、a s c ir e d 、c r a yt 3 e 、工作站机群等。 早期的机群系统有t h i n k i n gm a c h i n e sc m - 5 、i n t e lp a r a g o n 、i p s c 超立方体等。 计算节点 图2 1 分布式存储系统并行l ，o 的一般结构 f i g u r e2 - 1g e n e r a lp a r a l l e li oa r c h i t e c t u r eo f d i s t r i b u t e d - m e m o r ys y s t e m 图2 - 1 给出了分布式存储机群中并行i o 的一般结构，在这个机群中除了计算节点外， 还有一组i o 节点。i o 节点通过网络与计算节点连接。每个i o 节点连接一个或更多 的存储设备，每个磁盘或者是一个单独的磁盘或者是一个磁盘矩阵，例如r a i d ( r e d u n d a n t 7 集中式i o 技术研究及数据再分配算法优化 a r r a yo fi n e x p e n s i v ed i s k ) 。i o 节点作为服务器为并行文件系统工作。并行文件系统 在i o 节点和磁盘问条形划分文件，把文件划分成许多更小的单元，称其为条形单元，并 把这些单元以循环的方式存放到磁盘中。文件的条形划分可提供更高的i 0 带宽，并且能 够使多个计算节点同时访问文件的不同部分。 一般来说，i 0 节点不参与计算，它通常是服务于i 0 的。但是在有些机群系统中，每 个计算节点都有自己的本地磁盘，其他节点不能直接访问这些磁盘，这些磁盘不属于通用 i 0 系统，它们是用来储存操作系统使用的文件和每个进程本地划分的文件的。这种结构允 许多个节点同时请求，以实现同步访问。并行通过以下方式产生：并行数据从计算节点到 i o 节点的路径、多个i o 节点和文件系统服务器、以及多个存储设备( 磁盘) 。 2 、共享式存储器机群n 踟没有单独的i o 节点。这样的机群系统有：s g io r ig i n 2 0 0 0 、 c r a yt 9 0 、h pe x e m p l a r 、n e cs x 一4 。 在这些机群中，、操作系统放置在计算节点的文件系统服务器上。这些机群与多个磁盘 相连，文件系统在磁盘间划分文件。与在分布式存储器系统中一样，这些磁盘通过s c s i 或 光纤管道( f i b r ec h a n n e l ) 与机器相连。 这种结构是控制并行机制，它并不是由数据独立性单独决定而是由程序员决定。控制 并行机制的一个简单模型是共享内存模型，在该模型中，每个进程有权访问单个的共享地 址空间，并对单个共享地址空间进行存取访问，如果多个进程同时访问一个地址时，通过 封锁机制来协调处理。 2 5 并行文件系统概述 并行文件系统是构建大规模集群系统的重要组成部分，为应用程序提供高吞吐率的i o 以及单一的i o 系统映像n 。 所谓并行文件系统，是指应用于多机环境的网络文件系统，单个文件的数据采用分条 等形式存放于不同的i 0 节点之上，支持多机多个进程的并发存取，同时支持元数据和数 据的分布存放，并提供单一的目录空间。而要实现一个完整的并行文件系统，需要实现如 下两个方面n 刁：第一，实现单一的文件映像，并行文件存放在盘阵上的具体分布情况对于 用户来说是透明的，并行文件系统在用户看来是一完整的树型结构，在调用时只要给出文 件名即可；第二，采用条带化( s t r i p e ) 和分区( p a r t i t i o n ) 技术，支持一个文件数据在 多个磁盘之上和多个进程之间的分布，即多个进程并发读写多个磁盘上的数据。 8 内蒙古大学硕士学位论文 数据条带化是在g p f s 下的一项集中式的优化技术。使用l u s t r e 文件连接( 将两个文 件合并成一个文件) 来提高集中式i o 的性能的方法在n 2 1 中被提出。 一个并行文件系统必须具备如下的特征n 利： ( 1 ) 单一系统映象，即整个文件系统呈现给用户的是一个唯一的、巨大的文件系统映 象，它将局部和全局磁盘以及其它文件设备( 如磁带) 透明的结合在一起。 ( 2 ) 良好的可扩展性，即并行文件系统易于适应机群文件系统中结点和用户数目的增 长。 ( 3 ) 良好的性能。 2 5 1 并行文件访问的特点 与传统的顺序文件访问方式相比，并行应用程序以完全不同的方式对文件进行访问。 一些分布式文件系统是基于下面的假设而设计的：即文件的写共享访问几乎不发生，如网 络文件系统( n f s ) 的体系结构【1 8 】。如图3 - 2 所示。包括n f s 服务器和n f s 客户机，n f s 服 务器输出本地文件到几个n f s 客户机上，n f s 客户机驻留在网络中的其他节点上。如果几个 客户机以并行的方式访问同一个文件，请求就会在服务器上串行化，因此，这种结构是不 可扩展的。 2 5 2 并行文件系统现状 n f ss e r v e r 图2 2n f s 中的并行文件访问结构图 f i g u r e2 - 2p a r a l l e lf i l ea c c e s ss t r u c t u r eo l ln f s 目前已有的大多数并行文件系统，如v e s t a 、n c u b e 并行i 0 系统、g a l l e y 、p p f s 、p i o u s 、 p v f s 、m p i - i o 、p a n d a 以及v i p i o s 等n 引。对于数据文件都是条带化分割并分布于具有磁盘 9 集中式i o 技术研究及数据再分配算法优化 的多个节点上，这些存储数据的节点称之为i o 节点。当一些客户机( 计算节点，c o m p u t e r n o d e ) 以并行方式访问一个文件时，如图2 3 所示，访问请求会直接发送到不同的并行i 0 节点上。因此i 0 子系统可以通过增加i 0 节点的数量来扩大计算规模。然而，不同的文 件分割条带化方式、不同的访问请求调度策略会对系统的性能和可扩展性产生显著的影响。 圈2 - 3 并行文件系统中的并行文件访问结构图 f i g u r e2 - 3p a r a l l e lf i l ea c c e s ss t r u c t u r eo np a r a l l e lf i l es y s t e m 2 6 应用程序接口 在并行i o 中，应用程序接口有着重要的作用。u n i xi o 接口n 5 1 是目前最通用的并行 i o 接口。然而，它主要是针对那些单一处理器的文件系统以及在单一处理的程序中所使用 的通用模式而设计的。另外，该接口允许用户一次仅访问个数据链，它不适用于来自多 个处理器的集中式i o 请求。对于u n i xi o 接口，每一个进程必须定位到文件中的具体位 置，读或写- - , j , 部分连续的数据，之后，定位到下一个不连续的位置，读或写- - d , 部分连 续的数据，等等。其结果是每个处理器为了文件系统的各个小块数据要制造成百上千的请 求。因此，大多数用户使用u n i xa p i 都会获得很差的i o 性能。 相反，如果i oa p i 允许用户获取每个进程的整体访问信息，就像所有进程同时需要 同步访问文件样，其实现就可连续地读取整个文件，再将适当的数据块向适当的进程进 行简单的发送。这种优化方法能够大大地改善i o 性能，这种被称作集中式i o 的技术 已被广泛了解。 虽然并行i o 的研究已经取得了很大的进步，但是它仅保持了为并行i o 性能和可移 植性所说明的单一的、标准的、兼于语言的a p i 设计的某些关键性的需要。幸运的是，现 l o 内蒙古大学硕： ：学位论文 在这种a p i 已经存在了。它是作为m p i - 2 规范的一部分而定义的i o 接e l ，通常将其称为 m p i i 0 。 集中式i 0 技术研究及数据再分配算法优化 3 1m pi 概述 第三章m pi 消息传递并行编程模型 并行程序设计是对给定算法构造并行程序的活动。目前两种最重要的并行编程模型是 数据并行和消息传递，数据并行编程模型的编程级别比较高，编程相对简单，但它仅适用 于数据并行问题；消息传递编程模型的编程级别相对较低，但消息传递编程模型可以有更 广泛的应用范围。 m p i 是m e s s a g ep a s s i n gi n t e r f a c en 刚的缩写，称为消息传递接口，是一种编程接口 标准，而不是一种具体的编程语言。该标准是由消息传递接口论坛( m e s s a g ep a s s i n g i n t e r f a c ef o r u m ，m p i f ) 发起讨论并进行规范化的。 m p i 标准从1 9 9 2 年开始起草，于1 9 9 4 年发布的第一个版本m p i l ( m p iv 1 0 ，进而发 展出1 1 和l - 2 版) ，到1 9 9 7 年发布的第二个版本m p i 一2 ( m p iv 2 0 ) 。m p i 至今已经有 1 5 年的历史了。经过这1 5 年的改进和完善，也伴随着高性能计算技术的普及，尤其是集群 系统的普及，m p i 标准如今已经成为事实意义上的消息传递并行编程标准，也是最为流行的 并行编程接口。 简而言之，m p i 标准定义了一组具有可移植性的编程接口。各个厂商或组织遵循这些标 准接口实现自己的m p i 软件包，典型的实现包括开放源码的m p i c h 、l a nm p i 以及不开放源 码的i n t e lm p i 。而对于程序员来说，设计好的应用程序并行算法，调用这些接口，链接相 应平台上的m p i 库，就可以实现基于消息传递的并行计算。也正是由于m p i 提供了统一的 接口，该标准受到各种并行平台的广泛支持，这也使得m p i 程序具有良好的可移植性。目 前，w p l 支持多种编程语言，包括f r o t r a n7 7 ，f r o t r a n 9 0 以及c c + + ；同时，m p l 支持多 种操作系统，包括大多数的类u n i x 系统以及w i n d o w s 系统：m p i 还支持多核( m u l t i c o r e ) ， 对称处理机、集群( c l u s t e r ) 等各种硬件平台。 3 2 典型的w pl 实现 胛i 是一个标准。它不属于任何一个厂商，不依赖于某个操作系统，也不是一种并行编 程语言。不同的厂商和组织遵循着这个标准推出各自的实现，而不同的实现也会有其不同 的特点。 m p i c h 是影响最大、用户最多的m p i 实现。它是由美国的a r g o n n e 国家实验室开发的开 1 2 内蒙古大学硕f 二学位论文 放源码的m p i 软件包。它与m p i 标准同步发展，方便易用。目前可以下载的最新的m p i c h 软件包为m p i c h1 2 7 p i 和m p i c h2 - 1 0 5 p 4 ，分别遵循m p i - i 2 和m p i - 2 两个版本的m p i 标准。 m p i c h 的特点在于1 ： - 开放源码。 - 与m p i 标准同步发展。 - 支持多程序多数据( m u l t i p l ep r o g r a mm u l t i p l ed a t a ，m p m d ) 编程和异构集群系 统。 - 支持c c + + 、f o r t r a n7 7 和f o r t r a n9 0 的绑定；对f o r t r a n 的支持提供了头文件 m p i f h 和模块两种方式。 一 支持类u n i x 和w i n d o w sn t 平台。 - 支持环境非常广泛，包括多核、s m p 、集群和大规模并行计算系统。 除此之外，m p i c h 软