H-Relation Personalized Communication Strategy

Abstract

This paper considers the communication patterns arising from the partition of geometricaldomain into sub-domains, when data is exchanged between processors assigned to adjacentsub-domains. It presents the algorithm constructing bipartite graphs covering the graphrepresentation of the partitioned domain, as well as the scheduling algorithm utilizing thecoloring of the bipartite graphs. Specifically, when the communication pattern arises from thepartition of a 2D geometric area, the planar graph representation of the domain is partitionedinto not more than two bipartite graphs and a third graph with maximum vertex valency 2,by means of the presented algorithm. In the general case, the algorithm finds h−1 or fewerbipartite graphs, where h is the maximum number of neighbors. Finally, the task of messagescheduling is reduced to a set of independent scheduling problems over the bipartite graphs.The algorithms are supported by a theoretical discussion on their correctness and efficiency.

Keywords

• scheduling; concurrent point-to-point communications