APPLICATION OF DOMINANT NODE CONCEPT TO COLLECTIVE COMMUNICATION IN WORMHOLE ' ROUTED NETWORKS

Abstract

Collective communication operations are being increasingly demanded in parallel computing. The implementation of collective operations depends on the characteristics of underlying network architecture, such as network topology, switching strategy and port model. The predominant switching strategy used in parallel architectures is wormhole routing. The most fundamental collective operations are broadcast and global combine. An optimal broadcast algorithm among one-port model is Recursive Doubling (RD) algorithm. The RD algorithm fails to take the advantage of multi-port architecture and requires more number of message passing steps than necessary. In this dissertation, a new approach named Extended Dominating Node (EDN) model has been simulated, which takes the advantage of multi-port architecture and requires less number of message passing steps to complete a collective operation. The simulation is carried out for broadcast and global combine operations on mesh and torus networks. Besides RD algorithm has also been implemented for both the operations. Through simulation, the EDN and RD approaches have been compared with respect to maximum communication latency. Performance results are presented that confirm the advantage of EDN approach over the RD approach.