（计算机系统结构专业论文）指针数组模型中数据划分技术的研究及其实现.pdf

摘要 摘要 并行编译技术是并行处理中的关键技术。随着现代体系结构的发展，并行 编译技术的相对落后大大制约了超级计算机的普及。随着基于m p p 架构的机群 系统逐渐成为超级计算的主流平台，对并行编译技术提出了更多的挑战，本文 在这方面做了些研究，以供探讨。 o p e n m p 是面向s m p 体系结构的编程标准，m p i 是面向m p p 体系结构的编程 标准。随着主流超级计算机体系结构由s m p 向m p p 过渡，m p 编程技术成为超 级计算机的主流编程规范。但是它们之间差异很大，手工转换十分困难，如能 开发出将o p e n m p 转化为m p i 的自动转化工具，则可充分利用已有的软件资 源。通过对这两种编程规范和编译技术的研究，我们在a f t 平台上开发出了将 o p e n m p 转化为经过优化的m p i 程序的自动化编译工具a f t 2 0 0 4 。 数据划分是分布主存系统中并行编译的关键技术，也是优化m p p 系统上 m p i 程序的重点和难点。通过迭代逐次求精计算数值是科学计算中一类常见的 程序。这类程序一般是借助指针数组实现对多个大小不一致的多维数组的迭代 访问，传统数据划分模式解决不了这些问题。 通过对典型数值迭代近似计算程序的分析和研究，本文提出了指针数组数 据划分模型并给出相应的划分策略，这是本文的主要贡献。在对指针数组进行 数据划分时其主要挑战是，识别跨过程的一维到多维的指针别名引用、消除数 据空间的循环变量相关性以及相邻数据空间大小不一致引起的数据对齐问题。 首先，针对模型中一维到多维的跨过程变换，本文利用上下文敏感的过程 间指针分析技术，识别出别名，从而解决模型识别中的主要难点；其次，模型 迭代体中的数据空间是循环变量相关量，不适宜通过循环展开的方式解决，针 对该问题本文提出了选取代表元的策略，从而较好地将对指针数组的讨论转化 为对代表元数组的数据划分的讨论；另外，模型中迭代体的数据空间随着划分 粒度的不同相差很大，这样当相邻数据空间进行迭代时，就需要考虑数据块之 间的对齐问题，本文提出了向最大数组对齐的策略，很好地解决了该问题。 指针数组数据划分模型与传统数据划分模式有着本质的区别，它们就好比向 量问题和标量问题，虽有共性但是我们更应该针对指针数组的独特性给出相宜 摘要 的解决策略。这种数据划分模式弥补了现有数据划分研究的不足，在惠普集群 系统上测试时取得了较好的系统效率。 在实现o r ，e n m p 到m p i 的自动转化中，我们首先给出划分的系统架构，在架 构中预留了完成各种特殊划分的接口。在i n t e l 公司资助的“t r a n s l a t i n g o p e n m pa d p l i c a t i o n si n t od i s t r i b u t e dm e m o r ys y s t e m sa p p l i c a t i o n s ”项目中，我 所开发出了t r a n s l a t i n go p e n m pt om p i ( t o m ) 自动并行编译工具a f t 2 0 0 4 。 借助此平台本文给出了一致划分和指针数组数据划分模型实现的具体策略。通 过对s p e c 2 0 0 0 中该模式的代表程序m g r i d 的改写，在复旦大学高端计算中心 的惠普集群系统上，选取3 2 个节点时取得的加速比为3 0 8 9 ，此时系统有效利 用率为9 6 5 。 【关键词】：数据划分、分布主存、并行编译、m g r i d 【中圈分类号】：t p 3 计算机技术 i i a b s t r a c t p a r a l l e l i z i n gc o m p i l a t i o nt e c h n o l o g i e sa r et h ek e yp a r to fp a r a l l e lp r o c e s s i n g b u tt h e ya r ef a rb e h i n dt h ef a s td e v e l o p m e n to ft h em o d e ma r c h i t e c t u r e ，t h e nt h e y g r e a t l yi m p e d e st h ew i d e s p r e a do fh i 曲一p e r f o r m a n c ep a r a l l e lc o m p u t i n gs y s t e m s - n o wc l u s t e rs y s t e mg r a d u a l l yb e c o m e st h em a i np l a t f o r mo fs u p e r c o m p u t e rw h i c h a r eb a s e do nm p pa r c h i t e c t u r e ，p a r a l l e l i z i n gc o m p i l a t i o nt e c h n o l o g i e sf a c e sm o r e c h a l l e n g e sw h i c hi ss t u d i e dd e e p l yi nt h i sp a p e r o p e n m pd o m i n a t e sp a r a l l e lp r o g r a m m i n gs p e c i f i c a t i o n so fs m p a r c h i t e c t u r e ， w h i l em p ii s d e s i g n e df o rm a s s i v ed i s t r i b u t e dm e m o r ya r c h i t e c t u r e w i t ht h e a r c h i t e c t u r eo ft h es u p e r c o m p u t e rc a r r i e so u tt h et r a n s i t i o nf r o ms m pt om p p , m p l w i l lb e c o m et h em a j o rp a r a l l e lp r o g r a m m i n gs p e c i f i c a t i o n so ft h es u p e r c o m p u t e r b u tt h e ya r ew i d e l yd i f f e r e n t ，i ti sv e r yd i f f i c u l tt ot r a n s l a t ef r o mo n ef o r m a tt o a n o t h e rb yh a n d i fw ec a nd e v e l o pt h ea u t o m a t i ct o o lt r a n s l a t i n go p e n m pt o m p i ( t o m ) ，w ew i l lf u l l yu t i l i z es o f t w a r er e s o u r c e sw h i c h a r eb a s e do ns m p a r c h i t e c t u r e a f t e rr e s e a r c h i n gt h et w ok i n d so fp r o g r a m m i n gs p e c i f i c a t i o n sa n dt h e c o m p i l e rt e c h n o l o g i e s ，w ed e v e l o p e dt h ea u t o m a t i ct o o l sb a s e do na f tp l a t f o r m w h i c hc a nt r a n s l a t eo p e n m pt om p i d a t ap a r t i t i o ni st h ek e yt e c h n o l o g yo fp a r a l l e lc o m p i l e rw h i c ha r eb a s e do n d i s t r i b u t e dm e m o r yp a r a l l e lc o m p u t e r s t r a d i t i o n a ld a t ap a r t i t i o nm e t h o d sa r en o t s u i t a b l et op o i n t - a r r a yp r o g r a m m i n gm o d e ，s ow ep r e s e n tan e wm o d et os o l v et h i s p r o b l e m ，n a m e dp o i n t a r r a yd a t ap a r t i t i o nm o d e i nt h em o d e ，t h em a i nc h a l l e n g e sa r er e c o g n i z i n gt h ea l i a so fp o i n tc i t i n g ， e l i m i n a t i n gt h er e l a t i v i t yb e t w e e nd a t as p a c ea n dl o o pv a r i a b l ea n dd a t aa l i g n m e n t w h i c hi sc a u s e db yd a t as p a c ev a r i a n c e i nt h ep a p e rw es o l v et h ep r o b l e mo fr e c o g n i z ea l i a sb yt h et e c h n o l o g i e so f i n t e r p r o c e d u r a lp o i n t e ra n a l y s i s a f t e ra n a l y s i n gc i t i n gi n f o r m a t i o no ft h e s ea r r a y s ， w eg i v eas u i t a b l ed a t ap a r t i t i o np o l i c yb yc h o o s i n gad e p u t a t i o nm e m b e r t h i s m o d e li sa c o m p l e m e n t a r i t y t op r e v i o u sr e s e a r c ha b o u td a t ap a r t i t i o n d a t ap a r t i t i o np o l i c i e sa r eg r e a t l yd i f f e r e n tt oe a c hp r o g r a m m i n gm o d e l s o ， 1 1 1 f i r s t l y , w eb u i l das y s t e ms o f t w a r ea r c h i t e c t u r ei nw h i c hw er e s e r v ei n t e r f a c ew h i c h i su s e dt om o u n td i f f e r e n ts p e c i a ld a t ap a r t i t i o nm o d e l i nt h ep r o j e c t “t r a n s l a t i n g o p e n m pa p p l i c a t i o n s i n t od i s t r i b u t e d m e m o r ys y s t e m sa p p l i c a t i o n s ”，w e d e v e l o p e dt h ea u t o m a t i cc o m p i l a t i o nt o o l sa f t 2 0 0 4 w ei m p l e m e n t e dt h ep o i n t e r - a r r a yd a t ap a r t i t i o nm o d e lb a s e do nt h ea f l 2 0 0 4p l a t f o r m k e y w o r d s d a t ap a r t i t i o n 、d i s t r i b u t e dm e m o r y 、p a r a l l e lc o m p i l e r 、m g r i d i v 第1 章引占 第1 章引言 高性能计算的应用推动了高性能超级计算机体系结构的不断发展。在高性 能计算中，分布主存的并行处理技术成为高性能计算机发展的方向。随着高速 网络和微处理技术的发展，由于性价比高和可扩展性好的特点，机群正逐渐成 为主流的并行计算平台。在并行处理中，各个单元协作完成一个任务，它们之 间通常需要进行数据交换，这些数据交换的时间相对于本来的开销而言构成额 外的时间开销，部分的抵消了并行计算所获得的好处。因此并行处理对软件技 术，尤其是对并行编译技术提出了较高的要求。与体系结构的发展相对应，并 行编译及其优化技术的热点也逐渐转移到分布主存系统上来。基于分布主存系 统的并行编译除了借鉴传统并行编译的些技术外，由于在存储方式上的巨大 差异还有其独特的需要解决的问题。共享存储系统的优点是，具有统一地址空 间、易于编程，然而可扩展性较差；相反，分布主存系统具有可扩展性好的优 势，却增加了编程复杂性。 消息传递( 如m p i 1 1 1 2 1 一m e s s a g ep a s s i n gi n t e r f a c e 、p ) 和共享存储( 如 o p e n m p 3 】) 是两种典型的并行编程模型。o p e n m p 是面向共享主存多机系统( s m p ) 的编程标准，m p i 是面向分布主存多机系统( m p p ) 的编程标准。通常认为，共享 存储的可编程性比消息传递要好得多。由于机群是一种典型的分布式存储系统 采用消息传递进行编程是很自然且有效的，因此消息传递系统是目前机群上主 流的并行编程环境。由于o p e n m p 和m p i 之间差异很大，手工转换很困难，对程 序员的要求极高。如能开发出将o p e n m p 转化为m p i 的自动编译工具，将极大地 方便科学计算程序的编写，同时也可充分利用现有的软件资源。 通过对o p e n m p 和m p i 这两种编程规范和编译技术的研究，我们发现在开发 将o p e n m p 程序转化为m p i 程序的自动化编译工具的过程中，关键问题是针对 某类科学计算程序建立合适的数据划分h 慎型。数据划分是分布主存系统中并 行编译的关键技术，也是优化m p p 系统上m p i 程序的重点和难点。它以数组和 包含这些数组的嵌套循环为研究对象，以提高数据局部性和挖掘计算并行性为 根本目的。传统数据划分模式是针对单个嵌套循环体的研究，不适合指针数组 的数据划分模式，本文提出了解决该类问题的划分模式，称为指针数组的数据 第】章摹f 占 划分。 本文的主要贡献是，在研究指针数组的基础上，通过分析其数据引用的特 性，选取代表元，给出指针数组模型数据划分的策略。这种数据划分模式弥补 了现有数据划分研究的不足，在复旦大学惠普机群系统上测试时取得了较好的 系统效率。借助我所的a f t 5 1 平台，在i n t e l 公司资助的“t r a n s l a t i n go p e n m p a p p l i c a t i o n si n t od i s t r i b u t e dm e m o r ys y s t e m sa p p l i c a t i o n s ”并行编译器a f f 2 0 0 4 中，实现了本文提出的指针数组模型的自动并行化。本文的部分研究成果， “指针数组数据划分的理论模型 6 】”、“一种动态分布数组的数据划分模式的 实现【7 】，己于近期分别在核心期刊上发表。 本文共分6 章。第1 章为引言，首先介绍了当前流行的现代体系结构，分 析了各自特点：在此基础上重点分析了分布主存多机系统，这是并行处理技术 发展的主流方向；然后介绍了并行编译的关键技术，指出数据划分在分布主存 系统上的核心作用；在本节的最后介绍了数据划分技术的研究现状，在此基础 上给出了本文研究的背景。第2 章为指针数组数据划分模型论述，首先在分析 大量b e n c h m a r k 的基础上给出了指针数组的数据划分模型，在分析了其数据引 用的特性后给出了解决该类问题的划分策略，先找出代表元数组，然后对代表 元数组进行划分。第3 章，首先给出在a f t 平台上实现t r a n s l a t i n go p e n m pt o m p i ( t o m ) 的软件架构，着重介绍为实现从传统的计算划分到数据划分的转 化所需的映射结构。在本节的最后给出了简单一致划分的实现算法。第4 章介 绍了指针数组数据划分模型在i n t e l 公司资助的“t r a n s l a t i n go p e n m p a p p l i c a t i o n s i n t od i s t r i b u t e d m e m o r ys y s t e m sa p p l i c a t i o n s ”并行编译器 a f y 2 0 0 4 中的实现。第5 章为测试及结果分析，将a f f 2 0 0 4 对m g r i d f 自动并 行化的输出进行测试，对自动划分的结果测试取得了理想的效果。第6 章，总 结和展望。 1 1 现代体系结构 计算机体系结构主要涉及c p u 与内存的连接方式和它的i 0 系统，体系 结构设计合理可以发挥计算机的整体优势。目前，运行超级计算、关键业务的 计算机均采用多处理机系统，其核心关键问题是并行计算。并行计算机按照存 储系统组织及编程界面的不同，可以大致分为两类：即共享存储的多处理机系 第1 章引言 统和消息传递的分布式存储多计算机系统。 互崮i 璐 互崮璐 ：ii 恻坞i ：。u 譬h 浦副萄强吲算机( b j 共享嗣髭激鲤机 图l 1 消息传递多计算机和共享存储多处理机 1 ) 共享存储系统 共享存储的并行机( s m p ) 通常也称作紧密耦合多处理机，它有一个所有 处理器都可以一致访问的全局物理内存，并且可以通过对同一存储中共享数据 的读写来提供一个简单通用的程序设计模型。用户还可以在这种系统上方便地 仿真其它程序设计模型。程序设计的方便性和系统的可移植性使得并行软件的 开发费用大为降低。然而，共享存储多处理机由于共享访问介质，使得在访问 共享存储时要面临较重的竞争和较长的延迟，相对于分布式系统而言，这些问 题会严重地损害其峰值性能和可扩展性。共享存储的多处理机如图1 1 ( b ) 所 示，其中p 表示处理器，m 表示存储器。 2 ) 分布式存储系统 分布式存储的并行机通常也叫做多计算机系统，是出多个具有本地存储模 块的相互独立的处理节点通过互连网络连接而成的。其分布存储所具有的可扩 展性使这类系统有可能获得非常高的计算性能。然而，不同节点上的进程间通 信要使用消息传递模型，即通过显式的收发原语来完成。由于程序设计者需要 认真考虑数据分配和消息通信，因而较共享存储系统上的程序设计要困难一 些。另外不同地址空间的进程迁移使得问题更加复杂化。因此，分布式存储系 统在硬件方面变得可扩展了，但软件方面的问题却更复杂了。消息传递的多计 算机如图1 1 ( a ) 所示。 在共享存储系统中，所有处理器共享主存储器，每一处理器都可咀把信息 第1 章引言 存入主存储器，或从中取出信息，处理器之间的通信通过访问共享变量来实 现。而在消息传递系统中，每个处理器都有一个只有它自己才能访问的局部存 储器，处理器之间的通信必须通过显式的消息传递来进行。从图1 1 可以看 出，在消息传递多计算机系统中，每个处理机的存储器是单独编址的；而在共 享存储多处理机系统中，所有存储器统一编址。 由于分布主存多机系统的存储器是通过互联网络连接起来的，所以这种系 统的扩展性很强，其节点数可能达到上万，因此又称为大规模并行处理系统 ( m a s s i v ep a r a l l e l p r o c e s s i n gs y s t e m ，简称m p p ) 。m p p 由于其极佳的可扩展 性，处理能力比s m p 强的多，目前已经成为超级计算机的主流方向。 图1 2d s m 系统的结构组织示意图 分布主存系统因其可扩展性而得到很好的应用，而用户为了编程的简单方 便，往往要求底层体系结构是透明的，即要求系统有统一的全局地址空间，因 而促使了分布式共享存储d s m 【8 系统( d i s t r i b u t e ds h a r e dm e m o r y ) 的出现。 图1 2 为d s m 系统的结构组织示意图。d s m 系统就是在物理上分布存储的系统 上逻辑地实现共享存储模型。d s m 系统对于程序设计者来说，隐藏了远程通信 机制，保持了共享存储系统所具有的程序设计的方便性和可移植性。系统设计 者可以通过各种各样的方法，有硬件支持全局编址( d a s h 9 1 ) 和软件支持全 局编址( o p e n m p j i a j i a ”】) 两种d s m ，即分别通过硬件支持和软件的方式实 现共享编程。对于硬件支持共享编程的系统，编译系统可以充分利用硬件所提 供的功能来提高共享编程的性能；对于硬件不支持共享编程的系统，则通过软 件的方法来构造一个共享编程环境( 如，t h r e a d m a r k ，j i a j i a 等软件d s m 系 4 第l 章引g = - 统) 。硬件d s m 提供硬件全局地址空间及硬件同步原语或硬件c a c h e - - 致 性，因而，并行编译器可以充分利用这些特性来提高目标程序的性能；而软件 d s m 的c a c h e - - 致性、同步等都完全由软件来实现，相对于硬件d s m 系统， 其系统开销更大，且可扩展性不好。 对并行编译器而言，不管是哪种d s m 系统，都存在以下需要解决的问题： ( 1 ) 局部性问题，包括c a c h e 局部性和内存局部性。由于本地访存时间 和远地访存时间的不一致，充分开发局部性可以充分利用访问本地数据的低延 迟性。 ( 2 ) 数据组织，包括数据结构的组织及数据私有共享特征的确定。数据 结构的适当组织能充分利用底层硬件的特征，而将程序中共享数据数量减少到 最小将极大地减少由于共享数据的一致性及数据传送等带来的开销，尤其是对 软件d s m 系统，这一点显得非常重要。 ( 3 ) 通信优化，包括增大消息粒度、减小通信次数、隐藏通信延迟、将通 信流水线化等等。对软件d s m 系统，软件系统本身如何选择一种有效的一致性 协议并减少通信开销是一大难点。 ( 4 ) 对不支持全局c a c h e - - 致性的d s m 系统，控制共享数据访问一致性 和提高共享数据访问效率的编译优化技术将是一个难点。 由分析知，不管是硬件支持全局共享编程还是软件支持全局共享编程，其 性能、可扩展性和适应范围都比消息传递方式差。尤其对于软件支持的全局共 享编程，这种差别更明显。所以，对于大规模的分布存储系统，尤其是c l u s t e r 系统，要提供一种高效的全局共享编程环境，是十分困难的。 1 3 并行编译技术 分布主存系统的并行编译器需要解决各局部存储器之间数据分布问题和各 处理机之间通信优化问题。基于分布主存系统的并行编译关键技术【1 1 】有：并行 编程模型、代码和数据分布、通信优化以及代码生成问题四个方面。 1 ) 并行编程模型： 基于分布主存系统的程序自动并行化方面已有大量的研究，但许多编译技 术的适用性十分有限【1 2 】。因此，为了简化编译器的任务，尤其为了减轻编译器 在代码和数据分布处理中的负担，人们通过在并行编程模型中提供适当的并行 5 第i 章引言 编程接口，把一定的处理困难转移到编程者一方。目前两种最重要的并行编程 模型是数据并行和消息传递1 1 。数据并行，即将相同的操作同时作用于不同的 数据，因此适合在s i m d 并行计算机上运行。消息传递，即各个并行执行的部分 之间通过传递消息来交换信息、协调步伐、控制执行。 数据并行编程模型的编程级别比较高，编程相对简单，但它仅适用于数据 并行问题：消息传递编程模型的编程级别相对较低，但消息传递编程模型可以 有更广泛的应用范围。表格i 1 是对数据并行和消息传递两种并行编程模式的 简单对比。 表1 1 并行编程模式对比表 对比内容数据并行消息传递 编程级别 岛 低 适用的并行机类型 s i m d s i m d m i m d 执行效率依赖于编译器和数据本身的并行性程序员负责 地址空间 堕一 多个 存储类型共享内存分布式或共享内存 通信的实现 编译器负责程序员负责 问题类数据并行类问题数据并行、任务并行类问 题 目前状况缺乏高效编译对其支持使用广泛 与并行编程模型相对应，常用的两种并行编程语言为o p e n m p 和m p i 。 o p e n m p o p e n m p 3 1 标准通过定义编译制导、库例程和环境变量规范，给程序员提供了 支持f o r t r a n 、c c + + 语言的一组功能强大的高层并行结构和一个支持增量并行 的共享存储程序设计模型，能满足很大范围的应用需求。o p e n m p 允许用户创 建、管理可移植的并行程序，其编译制导主要包括3 种类型：并行及工作共享制 导、数据环境制导和同步制导。o p e n m p 程序的并行块主要由p a r a l l e l 制导来描 述，并行块以s p m d 方式在多线程上运行。工作共享制导用于将并行区域中的任 务划分成子任务在多个线程上执行，包括f o r ，s e c t i o n s 和s i n g l e 这3 种模式。工 作共享制导可以和某个并行块绑定在一起使用，编程更加简洁。数据环境制导 用于在并行执行时控制数据的属性，主要包括t h r e a d p r i v a t e 制导和一些描述数 据区域属性的子句，如p r i v a t e ，s h a r e d ，d e f a u l t ，f i r s t p r i v a t e ，l a s t p r i v a t e ， r e d u c t i o n 和c o p y i n 子旬。同步制导主要包括m a s t e r ，b a r r i e r ，c r i t i c a l ， 第1 章引言 a t o m i c ，f l u s h 和o r d e r e d 。另外，o p e n l p 的库例程主要提供一些获取线程标识 和设置锁变量的接口函数，和环境变量一起便于对程序运行时行为进行控制。 o p e n m p 采用f o r k j o i n 并行执行模式。o p e n m p 程序首先由m a s t e r 线程执行， 直到碰到第1 个并行结构( 由p a r a l l e l $ 1 j 导构成) ，则i 妇m a s t e r 线程创建( f o r k 操作) 一 组线程，且m a s t e r 线程成为线程组的主线程。除了工作共享结构外，每个线程 都执行并行动态扩展域中的代码。而工作共享结构表明任务被划分成子任务， 线程组中的每个线程分别执行对应的子任务，所有线程在工作共享结构结束处 需要隐式同步，而且在并行结构的出口处执行合并操作( j o i n 操作1 。并行结构执 行完后，m a s t e r 线程继续执行。程序中可以说明多个并行结构，所以程序在执行 时创建和合并多次。o p e n m p 标准只规定用户直接并行的语义，它的实现本身 并不检查依赖、死锁等导致程序错误的问题，完全由用户保证采用o p e n m p 结构 的程序正确性。 m p i 消息传递是一种广泛应用的并行编程模型。为了使消息传递系统能被更多 的人使用、能在更多的机器上运行，m p i l l 】f 2 】标准便应运而生。m p i 标准定义了 用c 和f o r t r a n 编写消息传递应用程序所用到的核心库例程的语法和语义，具 有很多特点。首先，m p i 提供了一个易移植的编程接口和一个可靠的通信接口， 允许避免内存到内存的拷贝，允许通信重叠，具有良好的通信性能；其次，它可 以在异构系统中透明使用，即能在不同体系结构的处理器上运行；再者，m p i 提 供的接口与现存消息传递系统接口( 如p v m ，n x ，e x p r e s s ，p 4 等) 相差不大，却提 供了更大的灵活性，能在更多的平台上运行。m p i 是一个标准，它没有规定具体 的实现细节，这给实现该标准的厂家带来了很大的灵活性，使m p i 可扩展性更 好。m p i 提供模块化的函数调用，函数种类和个数都很多，适用于各种场合。同 时对一般的应用程序来说，通常只用到其中的1 0 几个最常用的库函数，程序本 身比用p v m 编写的程序要直观得多。 2 ) 代码和数据分布： 在分布存储系统中，无论是进行串行程序并行化还是并行程序编译，编译 器都必须首先发现并提取程序中的并行性，然后再根据发掘出的并行性对程序 中的计算和数据进行分割，形成消息传递式的结点程序，最后将这些程序分配 第1 章g i 言 到各个结点中并行执行。在这个过程中，代码和数据的分布模式直接影响通信 的开销，从而影响编译器的性能，因此代码和数据的分割决策至关重要。本文 中主要讨论代码和数据分布模式的自动化技术，其目标是在程序分析的基础 上，全盘考虑数据分割与计算分割的需要，推导出一个较优的全局分布模式， 实现在尽可能大地开发程序中并行性的同时，减少程序中通信与同步的开销。 一般来说，代码和数据的分割不能独立执行，所以必须在提高并行性和降低通 信丌销之间取一个折衷。 3 ) 通信优化： 由于消息通信开销的重要性以及在大多数分布存储系统中通信起始开销很 高，编译器必须尽量减少生成消息的大小和数量，从而减少发送和接收消息的 开销，而且还应当最大化计算与通信的重叠，避免处理机空闲，隐藏部分通信 延迟。目前常用的几种通信优化技术是，消息向量化、集合通信、冗余通信消 除、通信与计算重叠等。 4 ) 代码生成问题： 当编译器为每个处理机生成代码时，需要计算每个处理机所访问的局部存 储地址以及指定处理机访问非局部数据的发送和接收序列。因此在分布存储系 统上并行编译的代码生成阶段主要解决两个问题：一是通信生成问题，以满足 每个处理机对非局部数据的引用；二是地址计算问题，将对全局名空间的引用 映射到局部存储地址。 1 4 数据划分技术 分布主存系统中节点间一般通过消息机制进行通信，在这样的系统中计算 的速度要远高于通信传输的速度。在此环境下，平衡各个处理机的负载和减少 处理机之间的通信，成为提高系统效率的两个主要问题，良好的数据划分是解 决这两个问题的关键。数据划分的主要目的是使处理机尽量引用本机的数据， 减少处理机间的通信；其研究思路是，针对一类应用程序抽象出模型，分析模 型中的数据引用特性，据此给出模型的划分策略。所以，数据划分一般以数组 和包含这些数组的嵌套循环为主要研究对象，以提高数据局部性和挖掘计算并 行性为根本目的。 传统的数据划分研究集中在两个层次进行：一是单个多重嵌套循环内数组 第1 章引言 的划分，二是多个嵌套循环问的全局数据划分。前者针对单个嵌套循环内数据 的应用方式，寻求局部最优的数据划分。后者是针对整个程序，寻求多个嵌套 循环间的一致划分，其研究的重点是，不同循环的划分存在冲突时如何寻找一 个全局的一致划分，尽量减少划分冲突引起的数据通信开销。在传统数据划分 模式中，各种算法是基于单个嵌套循环体的分析，没有针对指针数组的研究。 1 4 1 数据划分的概念 j m a n d e r s o na n dm s l a m 4 】给出了通常条件下数据划分的定义： 一个已规范化的，深度为，的多重嵌套循环工，确定了一个z 维的多面体迭 代空间，嵌套循环的每个迭代对应该多面体空间的一个整数点，可以用迭 代向量i ：( i l i 2 ，f ) 7 来表示。一个m 维数组，确定了一个i n 维的长方体空间 a ，数组的每一个元素都可以用向量厅= “，a ，a 。) 7 来表示。类似的，一个n 维的处理机空间尸的一个节点可以用个芦；( p ，p ：，p 。) 1 来表示。如果迭代 空间( 和数组空间a 之间存在线性关系，我们用一个线性转换函数，来表示： 尹：一a ，f ( i ) = f i + f ，其中f 是线性转换矩阵，云是常数向量。 定义1 1 ：数据划分就是将m 一数组空间a 的每一个元素厅影射到n 一维处理 机空间尸的一个函数孑佰) ：a 一尸，孑陋) = d d + 占，其中d 是一个n m 的线性 转换矩阵，占是一个常数偏移向量。 定义1 2 ：计算划分就是将f 一迭代空间( 的每一个元素i 影射到n 维处理 机空间j p 的一个函数芒 ) ：一只f ( i ) = c i + 尹，其中c 是一个n x l 的线性转 换矩阵，尹是一个常数偏移向量。 所以，数据划分的问题最终归结为寻找每个嵌套循环的计算划分函数芒( i ) 和每个数组的数据划分函数厅侮) ，以最大化计算并行度和最小化通讯。 1 4 2 计算空间和数据空间的一致性 对于大多数科学计算程序来说，计算空问和数据空间4 之间是线性相关 的而且符合以下条件： 数组下标是一致产生引用( u n i f o r m l yg e n e r a t e dr e f e r e n c e s ) 1 1 4 l ，即数组下 标的引用方式在整个程序中保持一致。 迭代空间和数组空问之间的转换函数符合初等变换，也就是浣其线性转换 函数f 仃) ；盯+ 云中，f 是单位阵e 的初等变换矩阵( 只经过初等行变换 第1 章引言 或初等列变换) 。 ( 、a 符合以上条件则称之为这两个空间是完全一致的，此时考虑任何一个 空间的同时也就考虑了相对应的另外一个空间。 1 4 3 数据划分的研究现状 研究表明寻找最佳数据划分问题是一个n p 问题【1 5 】【1 6 ”l 【1 8 1 。但是，针对特 定的程序模型提出有效的数据划分方法是可行的。传统的共享存储模型上的 t i l i n 9 1 1 9 】 2 0 】【2 l 】 2 2 2 3 】f 2 4 】 2 5 1 专注于计算迭代空间的划分，以寻找最小的计算时间， 由于没有考虑数据空问的划分，故对于分布式存储模型并不可行。 对于单个嵌套多重循环，如果数组下标是一致产生引用( u n i f o r m l y g e n e r a t e dr e f e r e n c e s ) ，c h e na n ds h e u z s 】提出了一种有数组复制和无数组复制的 启发式算法，实现通讯；或者可以通过建立将迭代空间和数据空间影射到处理 机空间方程式 2 6 】 2 7 1 2 8 1 ，来求解嵌套多重循环的无数据通讯的数据划分。如果 数组下标是非一致产生引用，可以通过d c h 、d s f t 2 6 】方法将非一致产生引用 数组下标转换成一致产生引用下标。 上述算法已经较好地解决了单个嵌套循环并行化时数据划分的问题，但是 许多科学计算问题都是由多个嵌套循环组成的，循环之间往往存在数据划分冲 突，因此，对于整个计算程序来说，如何寻找一个全局最优的划分，以最大的 减少重组通讯代价成为数据划分的关键所在。l ip e i z o n 9 1 2 7 】让每个嵌套循环有 其独立的局部数据划分，根据局部划分之间数据重组的代价和计算并行所带来 的好处，从而决定最后的数据划分。l ip e i z o n g l 2 8 j 则进一步提出数组“重要 性”的概念，按数组的“重要性”来对准划分，从而保证重要数组不需要重组 或尽量少的重组。这些算法给寻求多个嵌套循环问的一致划分提供了较好的策 略，论文【“1 对此作了更详尽的论述。 1 5 指针数组数据划分模式的提出 科学计算一般采用数值计算求近似值，这些数值计算的本质是通过迭代逐 次求精计算数值；每次计算按照预定义的粒度划分进行计算，次数增加时粒度 变小。在迭代中，通过比较第i 次与第i 一1 次迭代的差值与给定的微量来确定 是否达到精度要求或者继续第i + 1 次迭代。在求值的过程中，每次迭代所需的 l o 第i 章引言 数据量是不同的，粒度越细计算所需的数据空间就越大；下次迭代的计算空间 是由当前空问加上细化后的空间组成，如下图所示： 次 数 增 长 方 向 ，、 第i 次计算所增加的空 j 罐蓬誓藿誓鋈鍪塑圈 - + 空间大小f x 方向) 图1 3 数据空间变化示意图 如图1 3 ，这种数据空间的需求可以用二维数组或者指针数组来解决。但 是由于所需计算次数是动态决定的，如果用二维数组，那么二维数组的y 方向 长度不能确定，必须假定最大值；同时x 方向必须假定为所增加空间的最大 值，这样就造成严重的空间浪费。指针数组可以很好的解决这个问题，用一个 一维数组作为存储空间，通过指针来获取所需的空间，这样既不会造成空间浪 费，同时能够保证程序简洁，如下图1 4 所示，其中1 、2 、i 分别表示数 组1 、2 、i ，指针pe t 、p 2 、pe i 分别指向这些数组的起始地址。 p 1 1 】圜 p 【2 】堰羹重羹叠 p m，重蠢羹l 国要 图1 4 数据空间的指针表示 通过对现有数据划分方式的分析和总结，我们发现它们只能对数组进行划 分，不能处理如图1 4 指针表示的数组，因此我们提出了本文的指针数组数据 1 1 划分模型。 第2 章指针数组数据划分的理论模型 第2 章指针数组数据划分的理论模型 在科学计算应用中，由于不同类型程序的行为模式区别很大，针对一类程 序的优化方法往往不能对另一类程序起作用。本文的研究对象是指针数组模 型。在科学计算程序中，指针数组是一种常见的数据结构，指针数组的每个成 员指向一个多维数组的起始地址，这样的指针数组称之为数组向量。借助数组 向量，可以实现任意多个多维数组的相似访问，这时嵌套循环体中的数组是循 环变量相关结构。传统数据划分模式是针对单个嵌套循环体提出的划分算法， 不适合指针数组模型。本文提出解决该类问题的指针数组的数据划分模式。 指针数组模型具有以下特征：研究对象为指针数组，其成员个数一般都较 大，不适合用循环展开的方式讨论；迭代计算在指针数组的指向成员之间进 行，各个成员数组具有相似的数据引用方式。针对这种模式我们应该从整体出 发，分析其数据引用的特性，通过选取代表元，提出统一的划分算法。与传统 数据划分模式相比，指针数组模型分析的是数组向量，后者考虑的对象是单个 数组，这就好比讨论数组和标量，它们有着本质的不同。 本文基于对这类程序的研究提出了指针数组的数据划分模式，这种模式弥 补了现有数据划分研究的不足。在本节的余下部分，我们首先从指针数组的典 型b e n c h m a r k 入手，通过分析该类b e n c h m a r k 的数据引用特性，提炼出指针数 组的数据划分模型，然后给出相应的划分策略。 2 1 指针数组模型 b e n c h m a r k 分析 本文研究的是多重网格的加密、变疏的迭代过程，在此基础上提出了指针 数组的数据划分模型。因此我们首先对此类程序的代表b e n c h m a r km g r i d 进行 研究分析，为下文的模型建立做些铺垫。 分析s p e c 2 0 0 0 中的m g r i d 等程序，其主要结构如下图所示： r e a l + 8 u ( n r ) ，r ( n r ) d o k = l m ，2 ，一1 j = k - 1 c a l lr p r j 3 r ( i r k ) ) ，m m ( k ) ，r ( i r u ) ) ，m m u ) 第2 章指针数组数据划分的理论模型 e n d d o d ok _ 2 l m j = k 1 c m 工z n t e r p ( u ( i r u ) ) ，m m ( j ) u ( 1 r 趵) m m i k ) ) e n d d o s u b r o u t i n er p r j 3 ( r ，m k s ，m j ) i n t e g e rm km j r e a l + 8 r ( m k m l ( ，m k ) ，s ( m j ，m j ，m j ) s u b r o u t i n e i n t e r p ( z ，m ，u ，n ) i n t e g e r m ，n r e a l + 8z ( m ，m ，m ) u ，n ，n ) 图2 1 程序结构图 如图2 1 ，该程序在多次迭代中实现网格的加密和变疏。程序中有2 个大数 组u 、r ，u 是迭代的目标数组，r 是辅助数组。它们是由不断变稀的三维数 组一维化后合并成的一维数组，图中l m 是运行时输入的参数。在函数调用处 发生参数关联时，s u b r o u t i n e 中使用下标数组i r 和维长度数组m m 实现一维 到多维的变换，其中r o r ( k ) 1 给出多维数组的起始地址，m m ( k ) 给出多维数组 的维长度。其中n r 是预先设定的常量。 用一维数组表示多个多维数组 由图2 1 可以