Algorithms for mapping parallel programs onto hierarchical distributed computer systems
Abstract
In most cases modern distributed computer systems (computer clusters and MPP systems) have hierarchical organization and non-uniform communication channels between elementary machines (computer nodes, processors or processor cores). Execution time of parallel programs significantly depends on how they map to computer system (on what elementary machines parallel processes are assigned and what channels for inter-process communications are used). The general problem of mapping a parallel program into a distributed computer system is a well known NP-hard problem and several heuristics have been proposed to approximate its optimal solution. In this paper an algorithm for mapping parallel programs into hierarchical distributed computer systems based on task graph partitioning is proposed. The software tool for mapping MPI applications into multicore computer clusters is considered. The quality of this algorithm with the NAS Parallel Benchmarks is evaluated.
About the Author
M. G. Kurnosov
Сибирский государственный университет телекоммуникаций и информатики
Russian Federation
Russian Federation
References
1. Хорошевский В. Г. Архитектура вычислительных систем. - М. : МГТУ им. Н. Э. Баумана, 2008. - 520 с.
2. Евреинов Э. В., Хорошевский В. Г. Однородные вычислительные системы - Новосибирск : Наука. Сибирское отд-е, 1978. - 319 с.
3. Евреинов Э. В., Косарев Ю. Г. Однородные универсальные вычислительные системы высокой производительности. - Новосибирск: Наука. Сибирское отд-е, 1966. - 308 с.
4. Bokhari S. H. On the mapping problem // IEEE Transactions on Computers. - 1981. - Vol. 30, № 3. - P. 207 - 214.
5. Agarwal T. Topology-aware task mapping for reducing communication contention on large pa-rallel machines // Parallel and Distributed Processing Symposium. - 2006. - P. 10
6. Тарков, М.С. Вложение структур параллельных программ в структуры живучих распределенных вычислительных систем // Автометрия. - 2003. - Том 39, № 3. - С. 84 - 96.
7. Lee C., Bic L. On the mapping problem using simulated annealing // Proceedings of Computers and Communications. - 1989. - P. 40 - 44.
8. Tarkov M. S., Mun Y., Choi J., Choi H.-I. Mapping parallel programs onto distributed comput-er systems with faulty elements // Lecture Notes in Computer Science: Computational Science. - 2001. - P. 148 - 157.
9. Ucar B. Task assignment in heterogeneous computing systems // Journal of Parallel and Distri-buted Computing. - 2006. - Vol. 66, № 1. - P. 32 - 46.
10. Yu H., Chung I. H., Moreira J. Topology Mapping for Blue Gene/L Supercomputer // Proceed-ings of ACM/IEEE Conference Supercomputing. - 2006. - P. 52.
11. Монахов О. Г., Монахова Э. А. Параллельные системы с распределенной памятью: управление ресурсами и заданиями. - Новосибирск : Изд-во ИВМиМГ СО РАН, 2001. - 168 с.
12. Cho S. Y., Park K. H. Dynamic task assignment in heterogeneous linear array networks for me-tacomputing // Heterogeneous Computing Workshop. - 1994. - P. 66 - 71.
13. Ercal F., Ramanujan J., Sadayappan P. Task allocation onto a hypercube by recursive mincut bipartitioning // Journal of Parallel and Distributed Computing. - 1990. - Vol. 10, № 1, - P. 35 - 44.
14. Jacob J. C., Lee S.-Y. Task Spreading and Shrinking on Multiprocessor Systems and Networks of Workstations // IEEE Transactions on Parallel and Distributed Systems. - 1999. - Vol. 10, № 10. - P. 1082 - 1101.
15. Jose A. An approach to mapping parallel programs on hypercube multiprocessors // Proceed-ings of Workshop Parallel and Distributed Processing. - 1999. - P. 221 - 225.
16. Kalinowski T. Solving the mapping problem with a genetic algorithm on the MasPar-1 // Proceedings of the First International Conference on Massively Parallel Computing Systems. - 1994. - P. 370 - 374.
17. Ahmad I., Kafil M. A Parallel Algorithm for Optimal Task Assignment in Distributed Systems // Proceedings of the 1997 Advances in Parallel and Distributed Computing Conference. - 1997. - P. 284.
18. Bouvry P. Mapping and load balancing on distributed memory systems // Proceedings of Mi-croprocessing. - Budapest, 1994.
19. Chen Hu. MPIPP: An Automatic Profileguided Parallel Process Placement Toolset for SMP Clusters and Multiclusters // Proceedings of the 20th annual international conference on Super-computing. - 2006. - P. 353 - 360.
20. Chen S., Eshaghian M. A fast recursive mapping algorithm // Concurrency: Practice and Expe-rience. - 1995. - Vol. 7, № 5. - P. 391 - 409.
21. Coli M., Palazzari P. Global execution time minimization by allocating tasks in parallel systems // Proceedings of the 3rd Euromicro Workshop on Parallel and Distributed Processing. - 1995. - P. 91.
22. G. Bhanot et al. Optimizing task layout on the Blue Gene/L supercomputer // IBM Journal of Research and Development. - 2005. - Vol. 49, № 2. - P. 489 - 500.
23. Hluchy L., Dobrovodsky M., Dobrucky M. Static Mapping Methods for Processor Networks [Электронный ресурс] // CiteSeer.IST, 2008. - Режим доступа: http://citeseer.ist.psu.edu/472693.html (дата обращения: 29.04.2009).
24. Salcedo-Sanz S., Hu Y., Yao X. Hybrid meta-heuristics algorithms for task assignment in heterogeneous computing systems // Computers and Operations Research. - 2006. - Vol. 33, № 3. - P. 820 - 835.
25. Hockney R. The communication challenge for MPP: Intel Paragon and Meiko CS-2 / R. Hockney. - Parallel Computing. - 1994. - Vol. 20, № 3. - P. 389 - 398.
26. Garey M., Johnson D., Stockmeyer L. Some simplified NP-complete graph problems. - Theoretical Computer Science. - 1976. - Vol. 1. - P. 237 - 267.
27. Bui T. N., Moon B. R. Genetic algorithm and graph partition // IEEE Transactions on Computers. - 1996. - Vol. 45, № 7. - P. 841 - 855.
28. Hendrickson B., Leland R. A multilevel algorithm for partitioning graphs // Proc. of ACM/IEEE conference on Supercomputing. - San Diego : IEEE Press, 1995.
29. Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs // Journal of Parallel and Distributed computing. - 1998. - Vol. 48. - P. 96 - 129.
30. Karypis G., Kumar V. Analysis of multilevel graph partitioning // Proc. of ACM/IEEE conference on Supercomputing. - San Diego: IEEE Press, 1995.
31. Karypis G., Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs // Journal on Scientific computing. - 1998. - Vol. 20, № 1. - P. 359 - 392.
32. Khan M. S., Li K. F. Fast graph partitioning algorithms // Proc. of Int. IEEE conference "Communications, Computers, and Signal Processing". - Victoria: IEEE Press, 1995. - P. 337 - 342.
33. Schloegel K., Karypis G., Kumar V. Graph partitioning for high-performance scientific simulations // Sourcebook of parallel computing. - San Franciso: Morgan Kaufmann Publish, 2003. - P. 491 - 541.
34. Ахо А. В., Хопкрофт В. Д., Ульман Дж. Д. Структуры данных и алгоритмы; пер. с англ. под ред. А. А. Минько. - Издательский дом "Вильямс", 2001. - 384 с.
35. Кормен Т. Х. [и др]. Алгоритмы: построение и анализ, 2-е издание; пер. с англ. под ред. И. В. Красикова. - М.: Издательский дом "Вильямс", 2005. - 1296 с.
36. Fiduccia C. M., Mattheyses R. M. A linear-time heuristic for improving network partitions // Proc. of conference "Design Automation". - 1982. - P. 175 - 181
Review
For citations:
Kurnosov M.G. Algorithms for mapping parallel programs onto hierarchical distributed computer systems. The Herald of the Siberian State University of Telecommunications and Information Science. 2009;(2):20-45. (In Russ.)
Views:
158
Email this article 