Title :
Fast gossiping in square meshes/tori with bounded-size packets
Author :
Lau, Francis C M ; Zhang, Shi-Heng
Author_Institution :
Dept. of Comput. Sci., Hong Kong Univ., China
fDate :
4/1/2002 12:00:00 AM
Abstract :
Gossiping is a communication problem in which each node has a unique message (token) to be transmitted to every other node. The nodes exchange their tokens by means of packets. A solution to the problem is judged by how many rounds of packet sending are required. In this paper, we consider a version of the problem in which small-sized packets (each carrying exactly one token) are used, the links (edges) of the network are half-duplex (only one packet can flow through a link at a time), and the nodes are all-port (a node´s incident edges can all be active at the same time). This is also known as the H* model. We study the model on a 2D square mesh and on a 2D square torus. An improved, asymptotically optimal algorithm for the mesh and an optimal algorithm for the torus are presented
Keywords :
broadcasting; multiprocessor interconnection networks; packet switching; protocols; H* model; active incident edges; all-port nodes; all-to-all broadcasting; asymptotically optimal algorithm; bounded-size packets; collective communication; communication nodes; communication optimization; gossiping; half-duplex all-port model; half-duplex network links; interconnection networks; network edges; packet-sending rounds; parallel algorithms; scheduling; square mesh; square torus; token exchange; total exchange; unique message transmission;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
