Просмотр статьи


Номер журнала: 2009.2

Заголовок статьи: Алгоритмы вложения параллельных программ в иерархические распределённые вычислительные системы

Резюме

Рассматривается задача оптимального вложения в иерархические распределённые вычислительные системы (ВС) параллельных программ с целью минимизации времени их выполнения. Предложены эвристические алгоритмы решения задачи. Эффективность алгоритмов подтверждена результатами численных и натурных экспериментов по вложению тестовых 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 parallel 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 com-puter systems with faulty elements // Lecture Notes in Computer Science: Computational Sci-ence. – 2001. – P. 148 – 157.
9. Ucar B. Task assignment in heterogeneous computing systems // Journal of Parallel and Dis-tributed 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 metacomputing // 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 // Pro-ceedings 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 Ex-perience. – 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 het-erogeneous 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. Hock-ney. – Parallel Computing. – 1994. – Vol. 20, № 3. – P. 389 – 398.
26. Garey M., Johnson D., Stockmeyer L. Some simplified NP-complete graph problems. – Theo-retical Computer Science. – 1976. – Vol. 1. – P. 237 – 267.
27. Bui T. N., Moon B. R. Genetic algorithm and graph partition // IEEE Transactions on Com-puters. – 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 confer-ence 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 “Com-munications, Computers, and Signal Processing”. – Victoria: IEEE Press, 1995. – P. 337 – 342.
33. Schloegel K., Karypis G., Kumar V. Graph partitioning for high-performance scientific simula-tions // 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.

Ключевые слова

вложение параллельных программ, MPI, вычислительные кластеры, распределённые вычислительные системы.

Скачать полный текст