Font Size: a A A

Research On Efficient Multicast Algorithms Of Interconnection Networks

Posted on:2003-05-20Degree:DoctorType:Dissertation
Country:ChinaCandidate:J P SongFull Text:PDF
GTID:1118360185496971Subject:Computer system architecture
Abstract/Summary:PDF Full Text Request
A crucial component of a massively parallel computer (MPC) is the interconnection network which links all of the nodes of the computer together. Communication between the hundreds or thousands of processing nodes relies on the network. Multicast is one of the most fundamental communication pattern. Both unicast and broadcast are special cases of multicast. Multicast/broadcast has been defined in the MPI (Message Passing Interface) standard as an instrumental operation in implementing collective communication operations. Thus, the research on efficient multicast algorithms is critical to the performance enhancement of MPC's.Most existing MPC's support only unicast communication in hardware. In these environments, multicast must be implemented in software by sending multiple unicast messages. In this dissertation, a general software multicast model is presented, which indicates the direction of the study for contention-free software multicast. Based on the model, three minimum-time, contention-free multicast algorithms are proposed in cube-connected cycle networks, hexagonal networks and honeycomb networks, respectively.Including hardware support for multicast communication may reduce the communication latency considerably. A tree-based hardware multicast algorithm is proposed in wormhole-routed 2D mesh networks. By using the handshaking protocol between two adjacent nodes to control the lengths of all branches in a multicast tree, the algorithm can be proved to be deadlock-free. Since the multicast algorithm uses XY routing, which is the most common routing algorithm for unicast messages in mesh networks, it is more suitable for the actual network systems. Moreover, the algorithm can be applied to arbitrary long messages. Simulation results show that the proposed algorithm provides a very promising performance.The spanning tree-based multicast algorithms usually don't make full use of all channels in the network. By constructing multiple spanning trees, two deadlock-free multicast algorithms are presented in 2D mesh and k-ary n-cube networks, respectively. Both of the two algorithms make full use of all channels and can be applied to arbitrary long messages with no virtual channels. Simulation results demonstrate that both of the two algorithms outperform the best single tree approach significantly.In applications requiring high reliability, communication algorithm must be able to continue to function in the presence of faults. By constructing a single pseudo-cycle...
Keywords/Search Tags:Interconnection network, wormhole routing, multicast communication, deadlock-freedom, fault-tolerance
PDF Full Text Request
Related items