一个基于一般通信模式的多到一全局归约操作算法

205一个基于一般通信模式的多到一全局归约操作算法熊玉庆中国科学院计算技术研究所，100080北京摘要给出了一般逻辑拓扑结构定义，提出了一个基于一般通信模式的多到一全局归约操作算法，该算法建立在一般逻辑拓扑结构上。逻辑拓扑结构是决定在分布并行计算中消息如何传递的机制。由于一般逻辑拓扑结构的抽象性，该算法实际上提供了一个多到一全局归约操作实现算法框架。当给定一个具体的逻辑拓扑结构，该框架可给出基于特殊通信模式的多到一全局归约操作算法。这为设计多到一全局归约操作算法提供了一个新方法。关键词并行计算多到一全局归约操作逻辑拓扑结构多到一全局归约操作是将参与并行计算的多个进程中的数据进行加或求最大，最小等操作，并将操作后的数据留在其中一个进程中。它在并行计算中广泛使用[1]。很多关于它们的算法被提出，这些算法大部分是基于特殊的通信模式。本文首先给出通信模式的一般形式定义，即一般逻辑拓扑结构定义。逻辑拓扑结构是决定在分布并行计算中消息如何传递的机制[2]。在此基础上提出一个基于一般通信模式的多到一全局归约操作算法，该算法建立在一般逻辑拓扑结构上。由于一般逻辑拓扑结构的抽象性，该算法实际上提供了一个多到一全局归约操作实现算法框架。当给定一个具体的逻辑拓扑结构，根据该框架可得到基于特殊通信模式的多到一归约操作算法。这为设计多到一全局归约操作算法提供了一个新方法。1一般逻辑拓扑结构定义及其基本性质定义1设},...,,{110npppP，2n，为进程集合，}1,...,1,0{mT为时间步集合，其中，nm1。},...,,{10l是P的一个划分，其中l0，}{00p，0p称为根进程。是一棵有向加权树，它的节点集合为，根节点为0，权值集合为T，方向是从叶节点到根。对任意非叶节点，设其入度为d，d||，存在一个从d条进入该节点有向边到的映射f，f称为的关联映射。有下列性质：⑴最小的权为0t；⑵在每一条从叶节点到根节点的路径上，边的权值严格递增；⑶进入任意非叶节点的有向边中，权相等的边的数目不大于||；⑷对任意非叶节点，p，如果有'd条边进入使得对其中任意边e，有pef)(，则这'd条边的权值是连续的，即它们的权值可表示为1,...,1,'diii,'0dmi。其中，权最大（即1'di）的有向边称作进程p的终止边；⑸每个非叶节点中的所有进程的终止边的权相等；⑹每个非根非叶节点的射入边的最大权值（即终止边的权）与从该节点射出边的权值是连续的。即，如果射入边的最大权值为i，则射出边的权值为1i,10mi。后继函数}{2:PTSP定义为：ppiS,),(当且仅当，,p，e是从到的有向边，且pef)(，e的权为i，否则，),(iS。206定义2设进程集合为},...,,{110npppP，时间步集合为}1,...,2,1{mT，nm1。S为后继函数。一般逻辑拓扑结构TOP定义为：),()}},({}{{iSiSiTOP。例如，设进程集合为},,,,,,,{76543210ppppppppP，时间步集合为}1,0{T，P的划分为},,,,{43210，}{00p，},{631pp，},{212pp，},{543pp，}{74p，进程0p为根进程。树如图1所示，各节点的关联映射为：002)(0pf，001)(0pf，313)(1pf,614)(1pf。由定义1，后继函数S为02)0,(pS,33)0,(pS,64)0,(pS,01)1,(pS，在其他情况下，S的值为。由S和定义2，可得下列逻辑拓扑结构：,,0,,,0,,,0,,,0,,,0,{6735340201ppppppppppTOP},1,,,1,0603pppp这是2-树逻辑拓扑结构，如图2所示。0001t图1树图22-树逻辑拓扑结构定理1在一般逻辑拓扑结构TOP中，对任意的非根进程p，存在唯一的进程q使得在某时间步i有TOPqip,,。p称作q的前驱，q称作p的后继。证设p，，由于p是非根进程，不是树的根。这样，在树中存在唯一节点使得有一条从到的有向边e。由定义1，存在唯一的q使得qef)(。01234207再由定义1，有qiS),(，i是树中边e的权。从而，TOPqip,,。由上面，可得下面推论。推论1根进程没有后继。定理2对任意的非根进程p，在p与0p之间，唯一地有进程kqqq,...,,21，时间步121,...,kiii使得TOPqip11,,，TOPqiq221,,，…，TOPpiqkn01,,。证设p，。由于p是非根进程，因而在树中，是不根。由图论可知，在树中存在唯一的一条从到0的路径。设该路径为012211...kneee。由定义1，在021,,...,,k分别有进程0121,,...,,pqqqk，使得11)(1qef,22)(2qef,…,kkqefk)(,01)(0pefn，其中，021,...,,ffffk分别是021,,...,,n的关联映射。再由定义1，我们有11),(qiS，221),(qiS，…，kkkqiS),(1，01),(piSkk，其中，121,...,,kiii是树中边121,...,,keee的权。由定义2，可得定理成立。3基于一般通信模式的多到一全局归约操作算法设归约操作运算为，满足结合律和交换律，即)()(kjikjiaaaaaa，和ijjiaaaa。kjiaaa,,为运算的操作数。每个操作数称为运算结果的因子。如kjiaaa,,是kjiaaa的因子。设SEND和RECV是一对点到点通信原语。在SEND(msg,q),msg是要发送的消息，q表示接受该消息的进程。在RECV(recv_msg,q),recv_msg表示存放要接受的消息，q表示发送该消息的进程，当q是any_source时，表明调用进程将接受由任意进程发来的消息。建立在一般逻辑拓扑结构上的多到一全局归约操作算法描述如下。假设调用进程为p。Reduce(msg,TOP)/*进程p调用该算法*/{IF存在q使得TOPpiq,,THEN{设k是最小的这样的i。ki；label:WHILE存在q使得TOPpiq,,DORECV(recv_msg,any_source);/*由定理1，任意进程的后继是唯一的，因此，使用any_source能正确接到消息。*/msgmsgrecv_msg},,{piqTOPTOP;END-OF-WHILE;1kk;ki;/*由树的性质⑷*/IF存在q使得TOPpiq,,THENgotolabel208}/*EndofIF*/IF0ppTHENSEND(msg,r);/*由树的性质⑸，⑹，可知存在r，使得TOPrip,,*/}/*EndofReduce*/定理3上面算法不产生死锁。证如果算法产生死锁，则在进程集P中存在mqqq,...,,21,2m使得2q等待接受1q发送消息，3q等待接受2q发送消息,…,and1q等待接受mq发送消息。由算法可知，必存在时间步121,...,,miii使得TOPqiq211,,,TOPqiq322,,,…,TOPqiqmm11,,。因此，},...,,{21mqqq中的进程都有后继，由推论1，都不是根进程0p。由定理2，存在一进程},...,,{21miqqqq，在},...,{21mqqqP中有进程lrrr,...,,21，0l，在时间步121,...,,ljjj，使得TOPrjqi11,,,TOPrjr221,,,…,TOPpjrll01,,。这样，iq有二个不同的后继1r和1iq(如果mi)或1r和1q(如果mi),这与定理1相矛盾。定理4算法执行后，根进程中的数据为各进程中的数据经运算后的结果。证由定理2及算法可知，每个非根进程都把数据作为运算结果的一个因子传到根进程。再由的结合律和交换律，可得到定理成立。4基于特殊通信模式的全局多到一归约算法设计上述算法是基于一般通信模式的多到一全局归约操作算法，是建立在一般逻辑拓扑结构之上的。由于一般逻辑拓扑结构的抽象性，它实际上是一个框架，当给定一个具体的逻辑拓扑结构，它可实现基于该特殊逻辑拓扑结构的多到一全局归约操作算法。下面用二个例子说明。4.1基于1-环逻辑拓扑结构的多到一全局归约操作算法设计设进程集合},...,,{110npppP，时间步集合}2,...,1,0{nT，P上的1-环逻辑拓扑结构为},1,,...,,1,,,0,{013221pnpppppTOPnnnn，其中，0p为根进程。图2表示一个8n时的1-环逻辑拓扑结构。图21-环逻辑拓扑结构在1-环逻辑拓扑结构中，除1np外，其他进程都有唯一的前驱进程，除0p外，其他进程都有唯一后继。由前面的算法，我们可得下面的基于1-环逻辑拓扑结构的多到一全局归约操作算法。假设p为调用进程。Reduc_1-ring(msg);{209IF1nppTHEN{RECV(recv_msg,any_source);msgmsgrecv_msg;}IF0ppTHENSEND(msg,ip)/*假设1ipp,20ni*/}/*endofReduc_1-ring*/4.2基于2-树逻辑拓扑结构的全局多到一归约算法设计设进程集},...,,{110npppP，时间步集}1,...,1,0{mT，P上的2-树逻辑拓扑结构为},,,,,{11113323333kkkkiiiiiipippipTOP，其中，0p是根进程，i和k是使ki13，iik331和iik3231位于0到1n之间的整数。图1表示8n时的2-树逻辑拓扑结构。假设算法调用进程为hp，10nh。当0h时，算法中的u是使uuvh331或uuvh3231或vhu13的最大值。当0h时，算法中的u是使13nu或132nu的最大值。当uuvh331，将该式变形为)33(311iuiuivh，ui0，由拓扑结构TOP可知，hp的前驱下标为iiuiuiv3)33(311（1n时）和iiuiuiv32)33(311（1n时），后继下标为vu13。同理，可知当uuvh3231时，hp的前驱下标为iiuiuiv3)323(311（1n时）和iiuiuiv32)323(311（1n时），后继下标为vu13。当vhu13时，v与3互质，因为u是使vhu13的最大值。hp的前驱下标为iuv331（1n时）和iuv3231（1n时），如果0v，则hp为根，由推论1，它没有后继；如果30v，则111130333uuuuvh或11113203323uuuuvh，由TOP，它的后继下标为0；如果v3，设srv3，30s，则srvhuuu121333,2,1s，由拓扑结构TOP可知，hp的后继下标为ru23。这样，由第4节的算法，我们有下面多到一全局归约操作算法。Reduce_2-tree(msg);{CASEhpOFuuvp331:IF0uTHENFOR(1j;uj;1j){IF13)33(3111)1(nvjju