Fast gossiping on mesh-bus computers

A mesh-bus computer is a parallel computer in which nodes (i.e., processors) are arranged on a two-dimensional array, and nodes on each row and nodes on each column, respectively, are connected by a shared bus. The nodes communicate with each other by exchanging packets through shared buses in CREW manner. Suppose that each node initially contains a piece of information called a token. A gossiping problem is the routing problem of exchanging tokens among all nodes in the computer, which has been studied extensively as a basic communication scheme for sharing information among nodes in a parallel computer. In this paper, we propose three gossiping algorithms for mesh-bus computers assuming that each packet can carry at most ℓ tokens in a step, where ℓ is a function of the number of all nodes. It is shown that by selecting the fastest algorithm among them, for each given function ℓ, a lower bound on the gossiping time can be attained asymptotically.