Fast gossiping in square meshes/tori with bounded-size packets

作     者：Lau, FCM Zhang, SH 

作者机构：Univ Hong Kong Dept Comp Sci & Informat Syst Hong Kong Hong Kong Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS》 (IEEE Trans Parallel Distrib Syst)

年 卷 期：2002年第13卷第4期

页      面：349-358页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：RGC  (HKU7028/98E) 

主　　题：gossiping all-to-all broadcast total exchange collective communication parallel algorithms interconnection networks communication optimization scheduling 

摘      要：Gossiping is the communication problem in which each node has a unique message (token) to be transmitted to every other node. The nodes exchange their tokens by packets. A solution to the problem is judged by how many rounds of packet sending it requires. In this paper, we consider the version of the problem in which small-size 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 2D square mesh and the 2D square torus. An improved, asymptotically optimal algorithm for the mesh and an optimal algorithm for the torus are presented.