几种互连网络上的通信问题的研究

发布时间：2018-04-18 21:26

本文选题：互连网络 + 局部扭曲立方体　；参考：《重庆大学》2012年硕士论文

【摘要】：并行计算机的基础互连网络为处理器（结点）之间进行数据通信提供了物理基础，其拓扑结构决定了结点间通信效率，是影响并行计算机性能的主要因素之一，因而成为并行计算领域的研究热点。当在互连网络上执行并行算法时，常常需要在结点之间进行数据通信，其通信开销是算法执行时间的重要组成部分。基于互连网络的特性来研究如何高效地完成数据通信，这是一项很有意义的研究课题。类超立方体是一类重要的互连网络拓扑结构，目前，关于变形超立方体通信算法方面的研究成果还很少，，相应的通信问题没有得到很好的解决，因而难以开发关于变形立方体的并行算法，同时也使得变形立方体到目前为止还缺乏实用的价值。本学位论文研究变形立方体上的通信问题，取得的主要研究成果如下：首先，对一种重要的类超立方体---局部扭曲立方体，研究了其单点广播问题。单点广播是一个基本的通信问题，需要把一组消息从一个给定的结点发送到网络中其他所有的结点。针对这一问题，本文提出了一个能够在O (N log N)时间内完成n维局部扭曲立方体上单点广播任务的算法，其中N=2n为结点数；证明了该算法在同类算法中通信时延最小。就我们所知，这还是国际上首次研究局部扭曲立方体上的单点广播问题。其次，对另一种重要的类超立方体---交叉立方体，研究了其独立生成树问题。容错通信和安全消息分发是互连网络领域的一项重要研究课题。普遍认为：设计多个独立生成树来作为广播方案或分发协议可以得到良好的容错性和安全性。本文提出了一个能够构造出n维交叉立方体中n棵独立生成树算法，其时间开销为O (N log N)，其中N=2~n为结点数。该算法可以并行化，其时间开销降为O (log N)。该算法使独立生成树的数目达到了最大，从这个意义上讲，该算法是最优的。
[Abstract]:The basic interconnection network of parallel computers provides a physical basis for data communication between processors (nodes). Its topology determines the communication efficiency between nodes and is one of the main factors that affect the performance of parallel computers.Therefore, it has become a research hotspot in the field of parallel computing.When parallel algorithms are executed on interconnection networks, data communication between nodes is often required, and the communication overhead is an important part of the algorithm execution time.It is a significant research topic to study how to accomplish data communication efficiently based on the characteristics of interconnection network.Hypercube is an important topology of interconnection network. At present, there are few researches on the algorithm of deformed hypercube communication, and the corresponding communication problems have not been solved well.Therefore, it is difficult to develop parallel algorithms for deformable cubes, and at the same time, deformable cubes still lack practical value.In this dissertation, the communication problem on the deformed cube is studied, and the main research results are as follows:Firstly, the problem of single point broadcasting for an important hypercube---locally twisted cube is studied.Single point broadcasting is a basic communication problem. It is necessary to send a set of messages from a given node to all other nodes in the network.In order to solve this problem, this paper proposes an algorithm that can complete a single point broadcast task on an n-dimensional locally twisted cube in O ~ n log N time, where N ~ (2) n is the number of nodes, and it is proved that the algorithm has the minimum communication delay among the similar algorithms.As far as we know, this is the first time in the world to study the problem of single point broadcasting on partially distorted cubes.Secondly, the problem of independent spanning tree is studied for another important hypercube-cross cube.Fault-tolerant communication and secure message distribution is an important research topic in the field of interconnection networks.It is generally believed that designing multiple independent spanning trees as broadcast schemes or distribution protocols can achieve good fault tolerance and security.In this paper, we propose an algorithm that can construct n independent spanning trees in n-dimensional cross cubes, whose time cost is O n log n, where N ~ (2 +) n is the number of nodes.The algorithm can be parallelized, and its time cost is reduced to O log N.The algorithm maximizes the number of independent spanning trees. In this sense, the algorithm is optimal.
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP338.6

【共引文献】