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

1、一个基于一般通信模式的多到一全局归约操作算法熊玉庆中国科学院计算技术研究所，100080 北京摘要 给出了一般逻辑拓扑结构定义，提出了一个基于一般通信模式的多到一全局归约操作算法，该算法建立在一般逻辑拓扑结构上。逻辑拓扑结构是决定在分布并行计算中消息如何传递的机制。由于一般逻辑拓扑结构的抽象性，该算法实际上提供了一个多到一全局归约操作实现算法框架。当给定一个具体的逻辑拓扑结构，该框架可给出基于特殊通信模式的多到一全局归约操作算法。这为设计多到一全局归约操作算法提供了一个新方法。关键词 并行计算 多到一全局归约操作 逻辑拓扑结构多到一全局归约操作是将参与并行计算的多个进程中的数据进行加或求最大，

2、最小等操作，并将操作后的数据留在其中一个进程中。它在并行计算中广泛使用1。很多关于它们的算法被提出，这些算法大部分是基于特殊的通信模式。本文首先给出通信模式的一般形式定义，即一GHIKLMNOP般逻辑拓扑结构定义。逻辑拓扑结构是决定在分布并行计算中消息如何传递的机制2。在此基础上提出一个基于一般通信模式的多到一全局归约操作算法，该算法建立在一般逻辑拓扑结构上。由于一般逻辑拓扑结构的抽象性，该算法实际上提供了一个多到一全局归约操作实现算法框架。当给定一个具体的逻辑拓扑结构，根据该框架可得到基于特殊通信模式的多到一归约操作算法。这为设计多到一全局归约操作算法提供了一个新方法。1 一般逻辑拓扑结构定

3、义及其基本性质 定义1 设，为进程集合，为时间步集合，其中，。是的一个划分，其中，称为根进程。是一棵有向加权树，它的节点集合为，根节点为，权值集合为，方向是从叶节点到根。对任意非叶节点，设其入度为，存在一个从条进入该节点有向边到的映射，称为的关联映射。有下列性质： 最小的权为； 在每一条从叶节点到根节点的路径上，边的权值严格递增； 进入任意非叶节点的有向边中，权相等的边的数目不大于； 对任意非叶节点，如果有条边进入使得对其中任意边，有 ，则这条边的权值是连续的，即它们的权值可表示为 ,。其中，权最大（即）的有向边称作 进程的终止边； 每个非叶节点中的所有进程的终止边的权相等； 每个非根非叶节点

4、的射入边的最大权值（即终止边的权）与从该节点射出边的权值 是连续的。即，如果射入边的最大权值为，则射出边的权值为,。后继函数定义为：当且仅当，是从到的有向边，且，的权为，否则，。定义2 设进程集合为，时间步集合为，。为后继函数。一般逻辑拓扑结构定义为：。 例如，设进程集合为，时间步集合为，的划分为，进程为根进程。树如图1所示，各节点的关联映射为：，,。由定义1，后继函数为, , ,，在其他情况下，的值为。由和定义2，可得下列逻辑拓扑结构： 这是2-树逻辑拓扑结构，如图2所示。 0 0 0 1t图 1 树图 2 2-树逻辑拓扑结构 定理1 在一般逻辑拓扑结构中，对任意的非根进程，存在唯一的进程使

5、得在某时间步有。称作的前驱，称作的后继。证 设，由于是非根进程，不是树的根。这样，在树中存在唯一节点使得有一条从到的有向边。由定义1，存在唯一的使得。再由定义1，有，是树中边的权。从而，。由上面，可得下面推论。推论1 根进程没有后继。定理2 对任意的非根进程，在与之间，唯一地有进程，时间步使得，。证 设，。由于是非根进程，因而在树中，是不根。由图论可知，在树中存在唯一的一条从到的路径。设该路径为。由定义1，在分别有进程，使得, , , ,，其中， 分别是的关联映射。再由定义1，我们有，其中，是树中边的权。由定义2，可得定理成立。3 基于一般通信模式的多到一全局归约操作算法设归约操作运算为，满足

6、结合律和交换律，即，和。为运算的操作数。每个操作数称为运算结果的因子。如是的因子。设SEND和RECV是一对点到点通信原语。在SEND(msg, ), msg是要发送的消息，表示接受该消息的进程。在RECV(recv_msg, ), recv_msg表示存放要接受的消息，表示发送该消息的进程，当是any_source时，表明调用进程将接受由任意进程发来的消息。建立在一般逻辑拓扑结构上的多到一全局归约操作算法描述如下。假设调用进程为。Reduce (msg, ) /* 进程调用该算法 */ IF 存在使得 THEN 设是最小的这样的。 ； label: WHILE 存在使得 DO RECV(re

7、cv_msg, any_source); /* 由定理1，任意进程的后继是唯一的，因此，使用any_source能正确接到消息。 */ msg msg recv_msg ; END-OF-WHILE; ; ; /* 由树的性质 */ IF 存在使得 THEN goto label /* End of IF */ IF THEN SEND (msg, ); /* 由树的性质，可知存在，使得 */ /* End of Reduce */定理 3 上面算法不产生死锁。证 如果算法产生死锁，则在进程集中存在, 使得等待接受发送消息，等待接受发送消息, , and 等待接受发送消息。由算法可知，必存在时

8、间步使得, , 。因此，中的进程都有后继，由推论1，都不是根进程。由定理2，存在一进程，在中有进程，在时间步，使得, , , 。这样，有二个不同的后继和 (如果)或和 (如果), 这与定理1相矛盾。定理4 算法执行后，根进程中的数据为各进程中的数据经运算后的结果。证 由定理2及算法可知，每个非根进程都把数据作为运算结果的一个因子传到根进程。再由的结合律和交换律，可得到定理成立。4 基于特殊通信模式的全局多到一归约算法设计上述算法是基于一般通信模式的多到一全局归约操作算法，是建立在一般逻辑拓扑结构之上的。由于一般逻辑拓扑结构的抽象性，它实际上是一个框架，当给定一个具体的逻辑拓扑结构，它可实现基于

9、该特殊逻辑拓扑结构的多到一全局归约操作算法。下面用二个例子说明。4.1 基于1-环逻辑拓扑结构的多到一全局归约操作算法设计设进程集合，时间步集合，上的1-环逻辑拓扑结构为，其中，为根进程。图2表示一个时的1-环逻辑拓扑结构。图2 1-环逻辑拓扑结构 在1-环逻辑拓扑结构中，除外，其他进程都有唯一的前驱进程，除外，其他进程都有唯一后继。由前面的算法，我们可得下面的基于1-环逻辑拓扑结构的多到一全局归约操作算法。假设为调用进程。Reduc_1-ring (msg); IF THEN RECV (recv_msg, any_source); msgmsgrecv_msg; IF THEN SEND

10、(msg, ) /* 假设, */ /* end of Reduc_1-ring */4.2 基于2-树逻辑拓扑结构的全局多到一归约算法设计设进程集，时间步集，上的2-树逻辑拓扑结构为，其中，是根进程，和是使，和位于到之间的整数。图1表示时的2-树逻辑拓扑结构。假设算法调用进程为，。当时，算法中的是使或或的最大值。当时，算法中的是使或的最大值。当，将该式变形为，由拓扑结构可知，的前驱下标为（时）和（时），后继下标为。同理，可知当时，的前驱下标为（时）和（时），后继下标为。当时，与3互质，因为是使的最大值。的前驱下标为（时）和（时），如果，则为根，由推论1，它没有后继；如果，则或，由，它的后继下

11、标为；如果，设，则,，由拓扑结构可知，的后继下标为。这样，由第4节的算法，我们有下面多到一全局归约操作算法。Reduce_2-tree (msg); CASE OF : IF THEN FOR (;) IF THEN RECV (recv_msg, any_source); msgmsgrecv_msg; IF THEN RECV (recv_msg, any_source); msgmsgrecv_msg; /* end of FOR */ /* end of IF */ SEND (msg, ); : IF THEN FOR IF THEN RECV (recv_msg, any_sour

12、ce); msg msg recv_msg; IF THEN RECV (recv_msg, any_source); msg msg recv_msg; /* end of FOR */ /* end of IF */ SEND (msg, ); : FOR IF THEN RECV (recv_msg, any_source); msg msg recv_msg; IF THEN RECV (recv_msg, any_source); msg msg recv_msg; /* end of FOR */ IF THEN SEND (msg, ) IF THEN SEND (msg, ) /* , */ /* end of CASE */ /* end of ELSE */ /* end of Reduce_2-tree */致谢 本文工作完成于中科院软件所并行软件研究开发中心，并得到该中心孙家昶研究员