h-Relation personalized communication strategy

• Autorzy: Paszyński M.

Warianty tytułu

PL

Strategia komunikacji oparta na relacji h

• Języki publikacji: EN

Abstrakty

EN

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.

PL

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.

Słowa kluczowe

EN

scheduling; concurrent point-to-point communications

PL

szeregowanie; równoczesna komunikacja pomiędzy parami procesorów

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2010
• Tom: Vol. 11
• Strony: 81--98
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Paszyński M.

• Department of Computer Science, AGH University of Science and Technology, al. Mickiewicza 30, 30-059, Kraków, Poland,

Bibliografia

• [1] Bader D. A.: High-Performance Algorithms and Applications for SMP Clusters. NASA High Performance Computing and Communications Aerospace Workshop CAS 2000, Moffett Field, CA, 2000.
• [2] Bader D. A., Helman D. R., JaJa J.: Practical Parallel Algorithms for Personalized Communication and Integer Sorting. ACM Journal of Experimental Algorithmics, vol. 1, 1996, pp. 1-42.
• [3] Biggs N.L.: Discrete Mathematics. Oxford University Press, 1985.
• [4] Cormen T.H., Leiserson C.E., Rivest R.L.: Introduction to Algorithms. MIT Press, 1999.
• [5] Goldman A., Trystram D.: Algorithms for the Message Exchange Problem. Proc. of the International Conference on Parallel Computing in Electrical Engineering, Poland, 1998.
• [6] Jain R., Werth J., Browne J.C., Sasaki G.: A graph-theoretic model for scheduling problem and its application to simultaneous resource scheduling. Computer Science and Operations Research: New Developments in Their Interfaces, Penguin Press, 1992.
• [7] Johnsson S.L., Ho. C.-T.: Optimal All-to-All Personalized Communication with Minimum Span on Boolean Cubes. Technical Report 18-91, Harvard University, 1991.
• [8] Johnsson S.L., Ho. C.-T.: Optimal Broadcasting and Personalized Communication in Hypercubes. IEEE Transactions on Computers, vol. 38, 1989, pp. 1249-1268.
• [9] Kapoor A., Rizzi R.: Edge Coloring Bipartite Graphs. Technical Report DIT-02-040, University of Trento, 1999.
• [10] Marathe M.V., Panconesi A., Risinger L.D.: An experimental study of a simple, distributed edge coloring algorithm. Proc. of the 12th annual ACM symposium on Parallel Algorithms and Architectures, Bar Harbor, Maine, 2000, pp. 166-175.
• [11] Mathur K.K., Johnsson S.L.: All-to-All Communication Algorithms for Distributed BLAS Technical Report 07-93, Harvard University, 1993.
• [12] Mathur K.K., Johnsson S.L.: Communication Primitives for Unstructured Finite Element Simulations on Data Parallel Architectures. Technical Report 23-92, Harvard University, 1992.
• [13] Risinger L.D., Marathe M.V., Panconesi A.: Edge Coloring Algorithms for Scheduling in ASCI: Survey and Experimental Results. Technical Report LAUR-No-97-2341, Los Alamos National Laboratory, 1997.
• [14] Rizzi R.: Finding 1-Factors in Bipartite Regular Graphs and Edge-Coloring Bipartite Graphs. SIAM J. Discrete Math., vol. 15, 2002, pp. 283-288.
• [15] Skiena S.: Coloring Bipartite Graphs. [in:] Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addison-Wesley, 1990.
• [16] Sundar N.S., Jayasimha D.N., Panda D.K., Sadayappan P.: Hybrid Algorithms for Complete Exchange in 2D Meshes. IEEE Transactions on Parallel and Distributed Systems, vol. 12, 2001, pp. 1201-1218.
• [17] Wang J.-C., Lin T.-H., Ranka S.: Distributed Scheduling of Unstructured Collective Communication on the CM-5. Parallel Processing Letters, special issue on Partitioning and Scheduling, 1995.
• [18] Wenjie H., Xiaoling H., Ko-Wei L., Jiating S., Weifan W., Xuding Z.: Edge-Partitions of Planar Graphs and Their Game Coloring Numbers. Journal of Graph Theory, vol. 41, 2002, pp. 307-317.
• [19] Zhi-Zhong C., Xin H. Parallel complexity of partitioning a planar graph into vertex-induced forests. Discrete Applied Mathematics, vol. 69, 1996, pp. 183-198.