Communication Problems Of Several Classes Of Regular Interconnection Networks

The performance of a parallel computing system heavily depends on theeffectiveness of the underlying interconnection network. Interconnection networksprovide an effective mechanism of exchanging data between processors (nodes) inparallel computing systems. The network topology determines how well the nodes canwork cooperatively. As a result, interconnection networks have received considerableattention from the parallel computing community. When a parallel algorithm isexecuted on an interconnection network, it is necessary to exchange data between nodes.The interprocessor communication time may be substantial relative to the time neededexclusively for computations, so it is important to exchange data between nodes asefficiently as possible.Hypercube-like networks are a promising class of network topologies. Themajority of communication problems on these interconnection networks, however, hasnot been well solved, which makes it difficult to develop various efficient parallelalgorithms for these interconnection networks, so that, up to date, these networks appearto be lack of practical utility. This paper addresses the communication strategies on twokinds of hypercube-like networks. The major contributions are listed below.First, for one class of hypercube-like networks---locally twisted cube, the singlenode broadcast problem is addressed. The single node broadcast is a basiccommunication problem, which requires that a message be sent from a given node to allother nodes. A broadcast algorithm is proposed, which can execute the single nodebroadcast task in O (N log N)time, where N=2~nis the number of nodes inn-dimensional locally twisted cubes. The broadcast algorithm turns out to be optimal interms of the number of time steps. To the best of our knowledge, this is the first time tostudy this problem.Second, for another class of hypercube-like networks, the independent spanningtrees (ISTs) problem is dealt with. Fault-tolerant broadcasting and secure messagedistribution are important issues for numerous applications in interconnection networks.It is a common idea to design multiple ISTs as a broadcasting scheme or a distributionprotocol for receiving high levels of fault-tolerance and security. An algorithm forgenerating n ISTs of n-dimensional crossed cube is proposed, which runs in timeO (N log N), where N=2nis the number of the nodes in n-dimensional crossed cube. This algorithm can be parallelized to run in O (log N)time. The algorithm is optimal inthe sense that the number of ISTs obtained attains the maximum.