论文部分内容阅读
并行计算机的基础互连网络为处理器（结点）之间进行数据通信提供了物理基础，其拓扑结构决定了结点间通信效率，是影响并行计算机性能的主要因素之一，因而成为并行计算领域的研究热点。当在互连网络上执行并行算法时，常常需要在结点之间进行数据通信，其通信开销是算法执行时间的重要组成部分。基于互连网络的特性来研究如何高效地完成数据通信，这是一项很有意义的研究课题。类超立方体是一类重要的互连网络拓扑结构，目前，关于变形超立方体通信算法方面的研究成果还很少，相应的通信问题没有得到很好的解决，因而难以开发关于变形立方体的并行算法，同时也使得变形立方体到目前为止还缺乏实用的价值。本学位论文研究变形立方体上的通信问题，取得的主要研究成果如下：首先，对一种重要的类超立方体---局部扭曲立方体，研究了其单点广播问题。单点广播是一个基本的通信问题，需要把一组消息从一个给定的结点发送到网络中其他所有的结点。针对这一问题，本文提出了一个能够在O (N log N)时间内完成n维局部扭曲立方体上单点广播任务的算法，其中N=2n为结点数；证明了该算法在同类算法中通信时延最小。就我们所知，这还是国际上首次研究局部扭曲立方体上的单点广播问题。其次，对另一种重要的类超立方体---交叉立方体，研究了其独立生成树问题。容错通信和安全消息分发是互连网络领域的一项重要研究课题。普遍认为：设计多个独立生成树来作为广播方案或分发协议可以得到良好的容错性和安全性。本文提出了一个能够构造出n维交叉立方体中n棵独立生成树算法，其时间开销为O (N log N)，其中N=2~n为结点数。该算法可以并行化，其时间开销降为O (log N)。该算法使独立生成树的数目达到了最大，从这个意义上讲，该算法是最优的。