Многоуровневые алгоритмы отображения параллельных МР1-программ на вычислительные кластеры

Многоуровневые алгоритмы отображения параллельных МР1-программ на вычислительные кластеры

Автор: Пазников Алексей Александрович, Курносов Михаил Георгиевич, Куприянов Михаил Степанович

Журнал: Проблемы информатики @problem-info

Рубрика: Системная информатика

Статья в выпуске: 1 (26), 2015 года.

Бесплатный доступ

В работе рассматривается задача отображения параллельных MPI-программ на иерархические кластерные вычислительные системы (ВС). Требуется по заданному информационному графу программы распределить ее процессы по процессорным ядрам системы с целью минимизации накладных расходов на межмашинные обмены. Для приближенного решения за¬дачи предложены алгоритмы, основанные на эвристических методах разбиения взвешенных графов. Оптимизация достигается за счет распределения интенсивно обменивающихся ветвей параллельной программы по процессорным ядрам, связанным быстрыми каналами связи. В алгоритмах учитываются все иерархические уровни коммуникационной сети ВС. Приводятся результаты экспериментов по отображению MPI-программ из пакетов SPEC MPI и NAS Parallel Benchmarks в пространственно-распределенную мультикластерную вычислительную систему.

Еще

Отображение параллельных программ, распределенные вычисли¬тельные системы, кластерные вычислительные системы

Короткий адрес: https://sciup.org/14320268

IDR: 14320268

Список литературы Многоуровневые алгоритмы отображения параллельных МР1-программ на вычислительные кластеры

  • ХОРОШЕВСКИЙ В. Г. Распределенные вычислительные системы с программируемой структурой//Вестник СибГУТИ. 2010. № 2 (10). Р. 3-41.
  • GABRIEL Е., RESCH XL. RUHLE R. Implementing MPI with optimized algorithms for metacomputing//In Proc. of the third MPI Developer's and User's Conference. 1999. P. 31-41.
  • SAITO H., TAURA K. Localitv-aware Connection Management and Rank Assignment for Wide-area MPI//In Proc. of the 7th IEEE International Symposium on Cluster Computing and the Grid (CCGRID 2007). 2007. P. 249-256.
  • IMAMURA Т., TSUJITA Y., KOIDE H., TAKEMIYA H. An Architecture of Stampi: MPI Library on a cluster of parallel Computers//In Proc. of the 7th European PVM/MPI'2000. 2000. V. 1908. P. 200-207.
  • MALYSHKIN N. V., Roux В., FOUGERE D., MALYSHKIN V. E. The NumGRID metacomputing system//In Bulletin of the Novosibirsk Computing Center, series Computer Science. 2004. N 21. P. 57-68.
  • ФИЛАМОФИТСКИЙ М.П. Система поддержки метакомпьютерных расчетов X-COM: архитектура и технология работы//Вычислительные методы и программирование. 2004. Т. 5. Р. 123¬137.'
  • ANDERSON D. P. Boinc: A system for public-resource computing and storage//5th IEEE/ACM International Workshop on Grid Computing. 2004. P. 4-10.
  • ХОРОШЕВСКИЙ В.Г., КУРНОСОВ М.Г. Алгоритмы распределения ветвей параллельных программ по процессорным ядрам вычислительных систем//Автометрия. 2008. № 2 (44). С. 56-67.
  • BROQUEDIS F., CLET-ORTEGA J., MOREAUD S., FURMENTO N., GOGLIN В., 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). 2010. P. 180-186.
  • MERCIER G., CLET-ORTEGA J. Towards an Efficient Process Placement Policy for MPI Applications in Multicore Environments//Proceedings of the 16th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface. 2009. V. 5759. P. 104-115.
  • Yu H., CHUNG I.-H., MOREIRA J. Topology mapping for Blue Gene/L supercomputer//In Proc. of SC'06. 2006. N. 116. P. 1-52.
  • BHANOT G. Optimizing task layout on the Blue Gene/L supercomputer//IBM Journal of Research and Developmen. 2005. V. 49, N 2. P. 489-500.
  • BALAJI P., GUPTA R., VISHNU R., 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. 2011. V. 26. P. 247-256.
  • BHATELE A., GUPTA G.R., KALE L.V., CHUNG I.H. Automated mapping of regular communication graphs on mesh interconnects//2010 International Conference on High Performance Computing. 2010. P. 1-10.
  • BHATELE A., KALE L. V. Heuristic-Based Techniques for Mapping Irregular Communication Graphs to Mesh Topologies//13th IEEE International Conference on High Performance Computing and Communication. 2011. P. 765-771.
  • JEANNOT E., MERCIER G. Near-optimal placement of MPI processes on hierarchical NUMA architectures//Proceedings of the 16th international Euro-Par conference on Parallel processing: Part II. 2010. V. 6272. P. 199-210.
  • BHATELE A., KALE L. V., KUMAR S. Dynamic topology aware load balancing algorithms for molecular dynamics applications//In Proc. of the 2009 ACM International Conference on Supercomputing (ICS'09). 2009. P. 110-116.
  • LIFFLANDER J., MILLER P., VENKATARAMAN R. ET AL. Mapping Dense LU Factorization on Multicore Supercomputer Nodes//Parallel and Distributed Processing Symposium (IPDPS), 2012 IEEE 26th International. 2012. P. 596-606.
  • TRAPP J.L. Implementing the MPI Process Topology Mechanism//Proceedings of the ACM/IEEE conference on Supercomputing. 2002. P. 1-14.
  • KARLSSON C., DAVIES Т., CHEN Z. Optimizing Process-to-Core Mappings for Application Level Multi-dimensional MPI Communications//Proceedings of the 2012 IEEE International Conference on Cluster Computing. 2012. P. 486-494.
  • HOEPLER Т., RABENSEIPNER R., RITZDORP H. ET AL. The scalable process topology interface of MPI 2.2//Concurr. Comput.: Pract. Exper. 2011. V. 23, N 4. P. 293-310.
  • RASHTI M. J., GREEN J., BALAJI P. ET AL. Multi-core and network aware MPI topology functions//Proceedings of the 18th European MPI Users' Group conference on Recent advances in the message passing interface. 2011. V. 6960. P. 50-60.
  • HOEPLER Т., SNIR M. Generic Topology Mapping Strategies for Large-scale Parallel Architectures//In Proc. of the 2011 ACM International Conference on Supercomputing (ICS'll). 2011. P. 75-85.
  • ZHANG J., ZHAI J., CHEN W., ZHENG W. Process Mapping for MPI Collective Communications//Proceedings of the 15th International Euro-Par Conference on Parallel Processing. 2009. V. 5704. P. 81-92.
  • BHATELE A., GAMBLIN Т., LANGER S.H. ET AL. Mapping applications with collectives over sub-communicators on torus networks//SC '12 Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. 2012. P. 1-11.
  • HENDRICKSON В., LELAND R. A multilevel algorithm for partitioning graphs//Proc. of ACM/IEEE conference on Supercomputing. -San Diego: IEEE Press. 1995. P. 1-28.
  • KARYPIS G., KUMAR V. Multilevel k-wav partitioning scheme for irregular graphs//Journal of Parallel and Distributed computing. 1998. V. 48(1). P. 96-129.
  • FLDUCCLA I. MATTHEYSES R. M. A linear-time heuristic for improving network partitions//Proc. of conference "Design Automation". 1982. P. 175-181.
  • 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 No. UCB/EECS-2006-183. 2006. P. 1-54.
  • PELLEGRINI F. Distillating knowledge about Scotch//Combinatorial Scientific Computing, Dagstuhl Seminar Proceedings series. 2009. N 09061. P. 1-12.
  • ABOU-RJEILI A., KARYPISG. Multilevel Algorithms for Partitioning Power-Law Graphs//IEEE International Parallel k, Distributed Processing Symposium (IPDPS). 2006. P. 1-15.
  • FERNANDEZ E., HEYMANN E., SENAR M.A. Supporting efficient execution of MPI applications across multiple sites//In Proc. of Euro-Par'2006. 2006. V. 4128. P. 383-392.
  • TAKANO R., MATSUDA XL. KUDOH Т., KODAMA Y, OKAZAKI F., ISHIKAWA Y, YOSHIZAWA Y. High performance relay mechanism for MPI communication libraries run on multiple private IP address clusters//In Proc. of 8th IEEE international symposium on cluster computing and the grid (CCGRID 2008). 2008. P. 401-408.
  • MERCIER G., JEANNOT E. Improving MPI applications performance on multicore clusters with rank reordering//Proceedings of the 18th European MPI Users' Group conference on Recent advances in the message passing interface. 2011. V. 6960. P. 39-49.
  • SUBRAMONI H., POTLURI S., KANDALLA К. ET AL. Design of a scalable InfiniBand topology service to enable network-topologv-aware placement of processes//Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. 2012. P. 1-12.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp