Comparison of Heuristics for One-to-All and All-to-All Communications in Partial Meshes

Broadcasting (one-to-all) and gossiping (all-to-all) are two major communication paradigms that were considered from both practical and theoretical points of view. Indeed, such communication patterns frequently appear in parallel programming, and therefore are included in most of the communication libraries (e.g., MPI or PVM). Also, broadcasting and gossiping times of graphs are important parameters yielding lots of fundamental results. For most of the communication models, the corresponding decision problems are NP-complete in general. Therefore, in this paper, we consider broadcasting and gossiping heuristics. We study the performances of several heuristics applied to partial meshes, that is to connected subgraphs of the mesh. This choice of topology is motivated by the fact that a regularly connected multicomputer can be shared by many users, each of them dealing with an irregular sub-topology of the original network. The result of our comparison is that, although they were defined ..