Алгоритмы вложения параллельных программ в иерархические распределенные вычислительные системы
Аннотация
Рассматривается задача оптимального вложения в иерархические распределенные вычислительные системы (ВС) параллельных программ с целью минимизации времени их выполнения. Предложены эвристические алгоритмы решения задачи. Эффективность алгоритмов подтверждена результатами численных и натурных экспериментов по вложению тестовых MPI-программ из пакетов NAS Parallel Benchmarks и High-Performance Linpack в действующие вычислительные кластеры. Приводится описание созданного программного средства оптимизации вложения MPI-программ в вычислительные SMP-кластеры.
Список литературы
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
Рецензия
Для цитирования:
Курносов М. Алгоритмы вложения параллельных программ в иерархические распределенные вычислительные системы. Вестник СибГУТИ. 2009;(2):20-45.
For citation:
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.)
Просмотров:
155
Послать статью по эл. почте 