第205页共7页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第205页共7页一个基于一般通信模式的多到一全局归约操作算法熊玉庆中国科学院计算技术研究所，100080北京摘要给出了一般逻辑拓扑结构定义，提出了一个基于一般通信模式的多到一全局归约操作算法，该算法建立在一般逻辑拓扑结构上。逻辑拓扑结构是决定在分布并行计算中消息如何传递的机制。由于一般逻辑拓扑结构的抽象性，该算法实际上提供了一个多到一全局归约操作实现算法框架。当给定一个具体的逻辑拓扑结构，该框架可给出基于特殊通信模式的多到一全局归约操作算法。这为设计多到一全局归约操作算法提供了一个新方法。关键词并行计算多到一全局归约操作逻辑拓扑结构多到一全局归约操作是将参与并行计算的多个进程中的数据进行加或求最大，最小等操作，并将操作后的数据留在其中一个进程中。它在并行计算中广泛使用[1]。很多关于它们的算法被提出，这些算法大部分是基于特殊的通信模式。本文首先给出通信模式的一般形式定义，即一般逻辑拓扑结构定义。逻辑拓扑结构是决定在分布并行计算中消息如何传递的机制[2]。在此基础上提出一个基于一般通信模式的多到一全局归约操作算法，该算法建立在一般逻辑拓扑结构上。由于一般逻辑拓扑结构的抽象性，该算法实际上提供了一个多到一全局归约操作实现算法框架。当给定一个具体的逻辑拓扑结构，根据该框架可得到基于特殊通信模式的多到一归约操作算法。这为设计多到一全局归约操作算法提供了一个新方法。1一般逻辑拓扑结构定义及其基本性质定义1设P={p0,p1,...,pn−1}，n≥2，为进程集合，T={0,1,...,m−1}为时间步集合，其中，1≤m≤n。Ω={α0,α1,...,αl}是P的一个划分，其中0
,¿这是2-树逻辑拓扑结构，如图2所示。0001t图1Γ树图22-树逻辑拓扑结构定理1在一般逻辑拓扑结构TOP中，对任意的非根进程p，存在唯一的进程q使得在α0α1α2α3α4第207页共7页第206页共7页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第207页共7页某时间步i有¿p,i,q>∈TOP。p称作q的前驱，q称作p的后继。证设p∈α，α∈Ω，由于p是非根进程，...
