h-RELATION PERSONALIZED COMMUNICATION STRATEGY

Maciej Paszyński

doi:10.7494/csci.2010.11.0.81

Authors

Maciej Paszyński AGH University of Science and Technology

DOI:

https://doi.org/10.7494/csci.2010.11.0.81

Keywords:

scheduling, concurrent point-to-point communications

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.

Downloads

Download data is not yet available.

Author Biography

Maciej Paszyński, AGH University of Science and Technology

Department of Computer Science

References

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.

Bader D. A., Helman D. R., J´aJ´a J.: Practical Parallel Algorithms for Personalized Communication and Integer Sorting. ACM Journal of Experimental Algorithmics, vol. 1, 1996, pp. 1–42.

Biggs N. L.: Discrete Mathematics. Oxford University Press, 1985.

Cormen T. H., Leiserson C. E., Rivest R. L.: Introduction to Algorithms. MIT Press, 1999.

Goldman A., Trystram D.: Algorithms for the Message Exchange Problem. Proc. of the International Conference on Parallel Computing in Electrical Engineering, Poland, 1998.

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.

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.

Johnsson S. L., Ho. C.-T.: Optimal Broadcasting and Personalized Communication in Hypercubes. IEEE Transactions on Computers, vol. 38, 1989, pp. 1249–1268.

Kapoor A., Rizzi R.: Edge Coloring Bipartite Graphs. Technical Report DIT-02-040, University of Trento, 1999.

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.

Mathur K. K., Johnsson S. L.: All-to-All Communication Algorithms for Distributed BLAS Technical Report 07-93, Harvard University, 1993.

Mathur K. K., Johnsson S. L.: Communication Primitives for Unstructured Finite Element Simulations on Data Parallel Architectures. Technical Report 23-92, Harvard University, 1992.

Risinger L. D., Marathe M. V., Panconesi A.: Edge Coloring Algorithms for Scheduling in ASCI: Survey and Experimental Results. Technical Report LAURNo-97-2341, Los Alamos National Laboratory, 1997.

Rizzi R.: Finding 1-Factors in Bipartite Regular Graphs and Edge-Coloring Bipartite Graphs. SIAM J. Discrete Math., vol. 15, 2002, pp. 283–288.

Skiena S.: Coloring Bipartite Graphs. [in:] Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addison-Wesley, 1990.

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.

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.

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.

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.