一个基于一般通信模式的多到一全局归约操作算法分析研究 计算机科学与技术专业VIP免费

一个基于一般通信模式的多到一全局归约操作算法摘要给出了一般逻辑拓扑结构定义，提出了一个基于一般通信模式的多到一全局归约操作算法，该算法建立在一般逻辑拓扑结构上。逻辑拓扑结构是决定在分布并行计算中消息如何传递的机制。由于一般逻辑拓扑结构的抽象性，该算法实际上提供了一个多到一全局归约操作实现算法框架。当给定一个具体的逻辑拓扑结构，该框架可给出基于特殊通信模式的多到一全局归约操作算法。这为设计多到一全局归约操作算法提供了一个新方法。关键词并行计算多到一全局归约操作逻辑拓扑结构多到一全局归约操作是将参与并行计算的多个进程中的数据进行加或求最大，最小等操作，并将操作后的数据留在其中一个进程中。它在并行计算中广泛使用[1]。很多关于它们的算法被提出，这些算法大部分是基于特殊的通信模式。本文首先给出通信模式的一般形式定义，即一般逻辑拓扑结构定义。逻辑拓扑结构是决定在分布并行计算中消息如何传递的机制[2]。在此基础上提出一个基于一般通信模式的多到一全局归约操作算法，该算法建立在一般逻辑拓扑结构上。由于一般逻辑拓扑结构的抽象性，该算法实际上提供了一个多到一全局归约操作实现算法框架。当给定一个具体的逻辑拓扑结构，根据该框架可得到基于特殊通信模式的多到一归约操作算法。这为设计多到一全局归约操作算法提供了一个新方法。1一般逻辑拓扑结构定义及其基本性质定义1设，，为进程集合，为时间步集合，其中，。是的一个划分，其中，，称为根进程。是一棵有向加权树，它的节点集合为，根节点为，权值集合为，方向是从叶节点到根。对任意非叶节点，设其入度为，，存在一个从条进入该节点有向边到的映射，称为的关联映射。有下列性质：⑴最小的权为；⑵在每一条从叶节点到根节点的路径上，边的权值严格递增；⑶进入任意非叶节点的有向边中，权相等的边的数目不大于；⑷对任意非叶节点，，如果有条边进入使得对其中任意边，有，则这条边的权值是连续的，即它们的权值可表示为,。其中，权最大（即）的有向边称作进程的终止边；⑸每个非叶节点中的所有进程的终止边的权相等；⑹每个非根非叶节点的射入边的最大权值（即终止边的权）与从该节点射出边的权值是连续的。即，如果射入边的最大权值为，则射出边的权值为,。后继函数定义为：当且仅当，，是从到的有向边，且，的权为，否则，。定义2设进程集合为，时间步集合为，。为后继函数。一般逻辑拓扑结构定义为：。例如，设进程集合为，时间步集合为，的划分为，，，，，，进程为根进程。树如图1所示，各节点的关联映射为：，，,。由定义1，后继函数为,,,，在其他情况下，的值为。由和定义2，可得下列逻辑拓扑结构：这是2-树逻辑拓扑结构，如图2所示。0001t图1树图22-树逻辑拓扑结构定理1在一般逻辑拓扑结构中，对任意的非根进程，存在唯一的进程使得在某时间步有。称作的前驱，称作的后继。证设，，由于是非根进程，不是树的根。这样，在树中存在唯一节点使得有一条从到的有向边。由定义1，存在唯一的使得。再由定义1，有，是树中边的权。从而，。由上面，可得下面推论。推论1根进程没有后继。定理2对任意的非根进程，在与之间，唯一地有进程，时间步使得，，…，。证设，。由于是非根进程，因而在树中，是不根。由图论可知，在树中存在唯一的一条从到的路径。设该路径为。由定义1，在分别有进程，使得,,…,,，其中，分别是的关联映射。再由定义1，我们有，，…，，，其中，是树中边的权。由定义2，可得定理成立。3基于一般通信模式的多到一全局归约操作算法设归约操作运算为，满足结合律和交换律，即，和。为运算的操作数。每个操作数称为运算结果的因子。如是的因子。设SEND和RECV是一对点到点通信原语。在SEND(msg,),msg是要发送的消息，表示接受该消息的进程。在RECV(recv_msg,),recv_msg表示存放要接受的消息，表示发送该消息的进程，当是any_source时，表明调用进程将接受由任意进程发来的消息。建立在一般逻辑拓扑结构上的多到一全局归约操作算法描述如下。假设调用进程为。Reduce(msg,)/*进程调用该算法*/{IF存在使得THEN{设是最小的这样的。；label...