一个基于一般通信模式的多到一全局归约操作算法熊玉庆中国科学院计算技术讨论所，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
