h-Relation personalized communication strategy

Abstract

This paper considers the communication patterns arising from the partition of geometrical domain into sub-domains, when data is exchanged between processors assigned to adjacent sub-domains. It presents the algorithm constructing bipartite graphs covering the graph representation of the partitioned domain, as well as the scheduling algorithm utilizing the coloring of the bipartite graphs. Specifically, when the communication pattern arises from the partition of a 2D geometric area, the planar graph representation of the domain is partitioned into 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 fewer bipartite graphs, where h is the maximum number of neighbors. Finally, the task of message scheduling 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.

W artykule omówiono problem szeregowania komunikacji pomiędzy procesorami przypisanymi do poddziedzin otrzymanych w wyniku podziału obszaru na podobszary, przy założeniu, że dane wymieniane są pomiędzy sąsiadującymi podobszarami. W artykule przedstawiony został algorytm tworzenia grafów dwudzielnych w oparciu o grafową reprezentację obszaru podzielonego na podobszary. Przedstawiono również algorytm szeregowania bazujący na kolorowaniu skonstruowanych grafów dwudzielnych. W szczególności, kiedy rozważamy komunikację w obrębie obszarów dwuwymiarowych, graf reprezentujący podzielony obszar dwuwymiarowy jest grafem planarnym, i rozważany algorytm zdekomponuje go na dwa grafy dwudzielne oraz trzeci graf o maksymalnej walencji wierzchołka równej 2. W ogólnym przypadku (np. gdy rozważamy obszary trójwymiarowe) przedstawiony algorytm znajdzie h - 1 lub mniej grafów dwudzielnych, gdzie h oznacza maksymalną liczbę sąsiadujących podobszarów. Zadanie szeregowania komunikatów zostało zredukowane do niezależnych zadań szeregowania na grafach dwudzielnych. Artykuł podsumowuje analiza teoretyczna poprawności i efektywności omówionych algorytmów.