sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИsibsutis-623Research ArticleСтатьиАлгоритмы вложения параллельных программ в иерархические распределенные вычислительные системыAlgorithms for mapping parallel programs onto hierarchical distributed computer systemsКурносовМ.KurnosovM. G.mkurnosov@gmail.comСибирский государственный университет телекоммуникаций и информатикиRussian Federation200916012023022045Copyright © Курносов М.G., 20232023Курносов М.Kurnosov M.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/623

Рассматривается задача оптимального вложения в иерархические распределенные вычислительные системы (ВС) параллельных программ с целью минимизации времени их выполнения. Предложены эвристические алгоритмы решения задачи. Эффективность алгоритмов подтверждена результатами численных и натурных экспериментов по вложению тестовых MPI-программ из пакетов NAS Parallel Benchmarks и High-Performance Linpack в действующие вычислительные кластеры. Приводится описание созданного программного средства оптимизации вложения MPI-программ в вычислительные SMP-кластеры.

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.

вложение параллельных программвычислительные кластерыраспределенные вычислительные системыMPIReferencesХорошевский В. Г. Архитектура вычислительных систем. - М. : МГТУ им. Н. Э. Баумана, 2008. - 520 с.Хорошевский В. Г. Архитектура вычислительных систем. - М. : МГТУ им. Н. Э. Баумана, 2008. - 520 с.Евреинов Э. В., Хорошевский В. Г. Однородные вычислительные системы - Новосибирск : Наука. Сибирское отд-е, 1978. - 319 с.Евреинов Э. В., Хорошевский В. Г. Однородные вычислительные системы - Новосибирск : Наука. Сибирское отд-е, 1978. - 319 с.Евреинов Э. В., Косарев Ю. Г. Однородные универсальные вычислительные системы высокой производительности. - Новосибирск: Наука. Сибирское отд-е, 1966. - 308 с.Евреинов Э. В., Косарев Ю. Г. Однородные универсальные вычислительные системы высокой производительности. - Новосибирск: Наука. Сибирское отд-е, 1966. - 308 с.Bokhari S. H. On the mapping problem // IEEE Transactions on Computers. - 1981. - Vol. 30, № 3. - P. 207 - 214.Bokhari S. H. On the mapping problem // IEEE Transactions on Computers. - 1981. - Vol. 30, № 3. - P. 207 - 214.Agarwal T. Topology-aware task mapping for reducing communication contention on large pa-rallel machines // Parallel and Distributed Processing Symposium. - 2006. - P. 10Agarwal T. Topology-aware task mapping for reducing communication contention on large pa-rallel machines // Parallel and Distributed Processing Symposium. - 2006. - P. 10Тарков, М.С. Вложение структур параллельных программ в структуры живучих распределенных вычислительных систем // Автометрия. - 2003. - Том 39, № 3. - С. 84 - 96.Тарков, М.С. Вложение структур параллельных программ в структуры живучих распределенных вычислительных систем // Автометрия. - 2003. - Том 39, № 3. - С. 84 - 96.Lee C., Bic L. On the mapping problem using simulated annealing // Proceedings of Computers and Communications. - 1989. - P. 40 - 44.Lee C., Bic L. On the mapping problem using simulated annealing // Proceedings of Computers and Communications. - 1989. - P. 40 - 44.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.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.Ucar B. Task assignment in heterogeneous computing systems // Journal of Parallel and Distri-buted Computing. - 2006. - Vol. 66, № 1. - P. 32 - 46.Ucar B. Task assignment in heterogeneous computing systems // Journal of Parallel and Distri-buted Computing. - 2006. - Vol. 66, № 1. - P. 32 - 46.Yu H., Chung I. H., Moreira J. Topology Mapping for Blue Gene/L Supercomputer // Proceed-ings of ACM/IEEE Conference Supercomputing. - 2006. - P. 52.Yu H., Chung I. H., Moreira J. Topology Mapping for Blue Gene/L Supercomputer // Proceed-ings of ACM/IEEE Conference Supercomputing. - 2006. - P. 52.Монахов О. Г., Монахова Э. А. Параллельные системы с распределенной памятью: управление ресурсами и заданиями. - Новосибирск : Изд-во ИВМиМГ СО РАН, 2001. - 168 с.Монахов О. Г., Монахова Э. А. Параллельные системы с распределенной памятью: управление ресурсами и заданиями. - Новосибирск : Изд-во ИВМиМГ СО РАН, 2001. - 168 с.Cho S. Y., Park K. H. Dynamic task assignment in heterogeneous linear array networks for me-tacomputing // Heterogeneous Computing Workshop. - 1994. - P. 66 - 71.Cho S. Y., Park K. H. Dynamic task assignment in heterogeneous linear array networks for me-tacomputing // Heterogeneous Computing Workshop. - 1994. - P. 66 - 71.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.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.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.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.Jose A. An approach to mapping parallel programs on hypercube multiprocessors // Proceed-ings of Workshop Parallel and Distributed Processing. - 1999. - P. 221 - 225.Jose A. An approach to mapping parallel programs on hypercube multiprocessors // Proceed-ings of Workshop Parallel and Distributed Processing. - 1999. - P. 221 - 225.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.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.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.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.Bouvry P. Mapping and load balancing on distributed memory systems // Proceedings of Mi-croprocessing. - Budapest, 1994.Bouvry P. Mapping and load balancing on distributed memory systems // Proceedings of Mi-croprocessing. - Budapest, 1994.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.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.Chen S., Eshaghian M. A fast recursive mapping algorithm // Concurrency: Practice and Expe-rience. - 1995. - Vol. 7, № 5. - P. 391 - 409.Chen S., Eshaghian M. A fast recursive mapping algorithm // Concurrency: Practice and Expe-rience. - 1995. - Vol. 7, № 5. - P. 391 - 409.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.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.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.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.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).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).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.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.Hockney R. The communication challenge for MPP: Intel Paragon and Meiko CS-2 / R. Hockney. - Parallel Computing. - 1994. - Vol. 20, № 3. - P. 389 - 398.Hockney R. The communication challenge for MPP: Intel Paragon and Meiko CS-2 / R. Hockney. - Parallel Computing. - 1994. - Vol. 20, № 3. - P. 389 - 398.Garey M., Johnson D., Stockmeyer L. Some simplified NP-complete graph problems. - Theoretical Computer Science. - 1976. - Vol. 1. - P. 237 - 267.Garey M., Johnson D., Stockmeyer L. Some simplified NP-complete graph problems. - Theoretical Computer Science. - 1976. - Vol. 1. - P. 237 - 267.Bui T. N., Moon B. R. Genetic algorithm and graph partition // IEEE Transactions on Computers. - 1996. - Vol. 45, № 7. - P. 841 - 855.Bui T. N., Moon B. R. Genetic algorithm and graph partition // IEEE Transactions on Computers. - 1996. - Vol. 45, № 7. - P. 841 - 855.Hendrickson B., Leland R. A multilevel algorithm for partitioning graphs // Proc. of ACM/IEEE conference on Supercomputing. - San Diego : IEEE Press, 1995.Hendrickson B., Leland R. A multilevel algorithm for partitioning graphs // Proc. of ACM/IEEE conference on Supercomputing. - San Diego : IEEE Press, 1995.Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs // Journal of Parallel and Distributed computing. - 1998. - Vol. 48. - P. 96 - 129.Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs // Journal of Parallel and Distributed computing. - 1998. - Vol. 48. - P. 96 - 129.Karypis G., Kumar V. Analysis of multilevel graph partitioning // Proc. of ACM/IEEE conference on Supercomputing. - San Diego: IEEE Press, 1995.Karypis G., Kumar V. Analysis of multilevel graph partitioning // Proc. of ACM/IEEE conference on Supercomputing. - San Diego: IEEE Press, 1995.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.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.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.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.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.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.Ахо А. В., Хопкрофт В. Д., Ульман Дж. Д. Структуры данных и алгоритмы; пер. с англ. под ред. А. А. Минько. - Издательский дом "Вильямс", 2001. - 384 с.Ахо А. В., Хопкрофт В. Д., Ульман Дж. Д. Структуры данных и алгоритмы; пер. с англ. под ред. А. А. Минько. - Издательский дом "Вильямс", 2001. - 384 с.Кормен Т. Х. [и др]. Алгоритмы: построение и анализ, 2-е издание; пер. с англ. под ред. И. В. Красикова. - М.: Издательский дом "Вильямс", 2005. - 1296 с.Кормен Т. Х. [и др]. Алгоритмы: построение и анализ, 2-е издание; пер. с англ. под ред. И. В. Красикова. - М.: Издательский дом "Вильямс", 2005. - 1296 с.Fiduccia C. M., Mattheyses R. M. A linear-time heuristic for improving network partitions // Proc. of conference "Design Automation". - 1982. - P. 175 - 181Fiduccia C. M., Mattheyses R. M. A linear-time heuristic for improving network partitions // Proc. of conference "Design Automation". - 1982. - P. 175 - 181

The authors declare that there are no conflicts of interest present.