Heuristic algorithms of mapping MPI-programs onto multicluster computer and GRID systems

Authors

  • M.G. Kurnosov
  • A.A. Paznikov

Keywords:

parallel programs mapping
geographically-distributed computer systems
GRID-systems
parallel computing
MPI PDF (in Russian) (3.00MB) PDF. zip (in Russian) (2.83MB)

Abstract

On the basis of graph partitioning, a method and heuristic algorithms of mapping the parallel programs onto distributed computer systems with hierarchical structure are proposed. The optimization is achieved due to mapping intensively interacting parallel processes onto processor cores connected by rapid network channels. All hierarchical levels of the communication network is taken into account by the proposed method. Some results of mapping the MPI-programs taken from the benchmark suites SPEC MPI and NAS Parallel Benchmarks onto a geographically-distributed multicluster computer system are discussed. The work was supported by Russian Foundation for Basic Research (projects 11-07-00105, 12-07-31016, 10-07-00157, and 12-07-31016), by Ministry of Education and Science of the Russian Federation in the framework of the Federal Program «Scientific and science-education personnel of innovative Russia» for 2009-2013 (project 2012-1.1-12-000-1005-018), and by Council for grants of the Russian Federation President for the support of leading scientific schools (project SS-2175.2012.9).

New computational technologies

Downloads

Published

2013-11-14

Issue

Vol. 14 (2013): Issue 1.

Section

Section 2. Programming

Author Biographies

M.G. Kurnosov

Institute of Semiconductor Physics of SB RAS (ISP SB RAS)
• Researcher, Docent

A.A. Paznikov

Institute of Semiconductor Physics of SB RAS (ISP SB RAS)
• Software Engineer, Graduate Student

References

  1. Хорошевский В.Г. Распределенные вычислительные системы с программируемой структурой // Вестник СибГУТИ. 2010. 10, № 2. 3-41.
  2. Gabriel E., Resch M., Rühle R. Implementing MPI with optimized algorithms for metacomputing // Proc. of the Third MPI Developer’s and User’s Conference. Atlanta, 1999. 31-41.
  3. Fernandez E., Heymann E., Senar M.A. Supporting efficient execution of MPI applications across multiple sites // Proc. of Euro-Par’2006. Berlin: Springer, 2006. 383-392.
  4. Takano R., Matsuda M., Kudoh T., Kodama Y., Okazaki F., Ishikawa Y., Yoshizawa Y. High performance relay mechanism for MPI communication libraries run on multiple private IP address clusters // Proc. of 8th IEEE International Symposium on Cluster Computing and the Grid (CCGRID 2008). Lyon, 2008. 401-408.
  5. Saito H., Taura K. Locality-aware connection management and rank assignment for wide-area MPI // Proc. of the 7th IEEE International Symposium on Cluster Computing and the Grid (CCGRID 2007). Rio de Janeiro, 2007. 249-256.
  6. Imamura T., Tsujita Y., Koide H., Takemiya H. An architecture of Stampi: MPI library on a cluster of parallel computers // Proc. of the 7th European PVM/MPI’2000. Berlin: Springer, 2000. 200-207.
  7. Malyshkin N.V., Roux B., Fougere D., Malyshkin V.E. The NumGRID metacomputing system // Bulletin of the Novosibirsk Computing Center, Computer Science Series. Issue 21. Novosibirsk, 2004. 57-68.
  8. Филамофитский М.П. Система поддержки метакомпьютерных расчетов X-Com: архитектура и технология работы // Вычислительные методы и программирование. 2004. 5, № 1. 123-137.
  9. Anderson D.P. Boinc: a system for public-resource computing and storage // 5th IEEE/ACM International Workshop on Grid Computing. Washington: IEEE Press, 2004. 4-10.
  10. Хорошевский В.Г., Курносов М.Г. Алгоритмы распределения ветвей параллельных программ по процессорным ядрам вычислительных систем // Автометрия. 2008. 44, № 2. 56-67.
  11. Broquedis F., Clet-Ortega J., Moreaud S., Furmento N., Goglin B., Mercier G., Thibault S., Namyst R. Hwloc: a generic framework for managing hardware affinities in HPC applications // Int. Conference on Parallel, Distributed and Network-Based Processing (PDP2010). Pisa, 2010. 180-186.
  12. Mercier G., Clet-Ortega J. Towards an efficient process placement policy for MPI applications in multicore environments // Proc. of the 16th European PVM/MPI Users» Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface. Berlin: Springer, 2009. 104-115.
  13. Pellegrini F. Distillating knowledge about Scotch // Combinatorial Scientific Computing, Dagstuhl Seminar Proc. Series. Dagstuhl, 2009. N 09061.
  14. Yu H., Chung I.-H., Moreira J. Topology mapping for Blue Gene/L supercomputer // Proc. of SC’06. New York: ACM, 2006. N 116.
  15. Bhanot G. Optimizing task layout on the Blue Gene/L supercomputer // IBM Journal of Research and Development. 2005. 49, N 2. 489-500.
  16. Balaji P., Gupta R., Vishnu A., Beckman P. Mapping communication layouts to network hardware characteristics on massive-scale Blue Gene systems // Special edition of the Springer Journal of Computer Science on Research and Development (presented at the International Supercomputing Conference (ISC)). 2011. 26. 247-256.
  17. Bhatele A., Kale L.V., Kumar S. Dynamic topology aware load balancing algorithms for molecular dynamics applications // Proc. of the 2009 ACM International Conference on Supercomputing (ICS’09). Berlin: Springer, 2009. 110-116.
  18. Hoefler T., Snir M. Generic topology mapping strategies for large-scale parallel architectures // Proc. of the 2011 ACM International Conference on Supercomputing (ICS’11). Tucson, 2011. 75-85.
  19. Traff J.L. Implementing the MPI process topology mechanism // Proc. of the ACM/IEEE Conference on Supercomputing. Los Alamitos, 2002. 1-14.
  20. Hendrickson B., Leland R. A multilevel algorithm for partitioning graphs // Proc. of ACM/IEEE conference on Supercomputing. San Diego : ACM Press, 1995. 626-657.
  21. Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs // Journal of Parallel and Distributed computing. 1998. 48. 96-129.
  22. Fiduccia C.M., Mattheyses R.M. A linear-time heuristic for improving network partitions // Proc. of Conference on Design Automation. New York: IEEE Press, 1982. 175-181.
  23. Asanovic K. et al. The landscape of parallel computing research: a view from Berkeley // Electrical Engineering and Computer Sciences, University of California, Berkeley. Technical Report N UCB/EECS-2006-183. Berkeley, 2006.
  24. Abou-Rjeili A., Karypis G. Multilevel algorithms for partitioning power-law graphs // IEEE International Parallel &; Distributed Processing Symposium (IPDPS). Rhodes Island: IEEE, Press, 2006. 1-17.