Эвристические алгоритмы отображения параллельных MPI-программ на мультикластерные вычислительные и GRID-системы

Авторы

  • М.Г. Курносов
  • А.А. Пазников

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

отображение параллельных программ
пространственно-распределенные вычислительные системы
GRID-системы
параллельные вычисления
MPI

Аннотация

На основе методов разбиения графов предложен метод и эвристические алгоритмы отображения параллельных программ на распределенные вычислительные системы с иерархической структурой. Оптимизация достигается за счет распределения интенсивно обменивающихся ветвей параллельной программы по процессорным ядрам, связанным быстрыми каналами связи. В методе учитываются все иерархические уровни коммуникационной сети вычислительной системы. Приводятся результаты экспериментов по отображению MPI-программ из пакетов SPEC MPI и NAS Parallel Benchmarks на пространственно-распределенную мультикластерную вычислительную систему. Работа выполнена при поддержке РФФИ (гранты 11-07-00105, 12-07-31016, 10-07-00157, 12-07-31016), Минобрнауки РФ в рамках реализации Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы (грант 2012-1.1-12-000-1005-018) и Совета по грантам Президента РФ для поддержки ведущих научных школ (грант НШ-2175.2012.9).

Новые вычислительные технологии

Загрузки

Опубликован

2013-11-14

Выпуск

Том 14 (2013): Выпуск 1.

Раздел

Раздел 2. Программирование

Авторы

М.Г. Курносов

Институт физики полупроводников имени А.В. Ржанова СО РАН
пр. Академика Лаврентьева, 13, 630090, Новосибирск
• научный сотрудник, доцент

А.А. Пазников

Институт физики полупроводников имени А.В. Ржанова СО РАН
пр. Академика Лаврентьева, 13, 630090, Новосибирск
• инженер-программист, аспирант

Библиографические ссылки

  1. Хорошевский В.Г. Распределенные вычислительные системы с программируемой структурой // Вестник СибГУТИ. 2010. 10, № 2. 3-41.
  2. Gabriel E., Resch M., Rühle R. Implementing MPI with optimized algorithms for metacomputing // Proc. of the Third MPI Developer’s and User’s Conference. Atlanta, 1999. 31-41.
  3. Fernandez E., Heymann E., Senar M.A. Supporting efficient execution of MPI applications across multiple sites // Proc. of Euro-Par’2006. Berlin: Springer, 2006. 383-392.
  4. Takano R., Matsuda M., Kudoh T., Kodama Y., Okazaki F., Ishikawa Y., Yoshizawa Y. High performance relay mechanism for MPI communication libraries run on multiple private IP address clusters // Proc. of 8th IEEE International Symposium on Cluster Computing and the Grid (CCGRID 2008). Lyon, 2008. 401-408.
  5. Saito H., Taura K. Locality-aware connection management and rank assignment for wide-area MPI // Proc. of the 7th IEEE International Symposium on Cluster Computing and the Grid (CCGRID 2007). Rio de Janeiro, 2007. 249-256.
  6. Imamura T., Tsujita Y., Koide H., Takemiya H. An architecture of Stampi: MPI library on a cluster of parallel computers // Proc. of the 7th European PVM/MPI’2000. Berlin: Springer, 2000. 200-207.
  7. Malyshkin N.V., Roux B., Fougere D., Malyshkin V.E. The NumGRID metacomputing system // Bulletin of the Novosibirsk Computing Center, Computer Science Series. Issue 21. Novosibirsk, 2004. 57-68.
  8. Филамофитский М.П. Система поддержки метакомпьютерных расчетов X-Com: архитектура и технология работы // Вычислительные методы и программирование. 2004. 5, № 1. 123-137.
  9. Anderson D.P. Boinc: a system for public-resource computing and storage // 5th IEEE/ACM International Workshop on Grid Computing. Washington: IEEE Press, 2004. 4-10.
  10. Хорошевский В.Г., Курносов М.Г. Алгоритмы распределения ветвей параллельных программ по процессорным ядрам вычислительных систем // Автометрия. 2008. 44, № 2. 56-67.
  11. Broquedis F., Clet-Ortega J., Moreaud S., Furmento N., Goglin B., 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). Pisa, 2010. 180-186.
  12. Mercier G., Clet-Ortega J. Towards an efficient process placement policy for MPI applications in multicore environments // Proc. of the 16th European PVM/MPI Users» Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface. Berlin: Springer, 2009. 104-115.
  13. Pellegrini F. Distillating knowledge about Scotch // Combinatorial Scientific Computing, Dagstuhl Seminar Proc. Series. Dagstuhl, 2009. N 09061.
  14. Yu H., Chung I.-H., Moreira J. Topology mapping for Blue Gene/L supercomputer // Proc. of SC’06. New York: ACM, 2006. N 116.
  15. Bhanot G. Optimizing task layout on the Blue Gene/L supercomputer // IBM Journal of Research and Development. 2005. 49, N 2. 489-500.
  16. Balaji P., Gupta R., Vishnu A., 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 (presented at the International Supercomputing Conference (ISC)). 2011. 26. 247-256.
  17. Bhatele A., Kale L.V., Kumar S. Dynamic topology aware load balancing algorithms for molecular dynamics applications // Proc. of the 2009 ACM International Conference on Supercomputing (ICS’09). Berlin: Springer, 2009. 110-116.
  18. Hoefler T., Snir M. Generic topology mapping strategies for large-scale parallel architectures // Proc. of the 2011 ACM International Conference on Supercomputing (ICS’11). Tucson, 2011. 75-85.
  19. Traff J.L. Implementing the MPI process topology mechanism // Proc. of the ACM/IEEE Conference on Supercomputing. Los Alamitos, 2002. 1-14.
  20. Hendrickson B., Leland R. A multilevel algorithm for partitioning graphs // Proc. of ACM/IEEE conference on Supercomputing. San Diego : ACM Press, 1995. 626-657.
  21. Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs // Journal of Parallel and Distributed computing. 1998. 48. 96-129.
  22. Fiduccia C.M., Mattheyses R.M. A linear-time heuristic for improving network partitions // Proc. of Conference on Design Automation. New York: IEEE Press, 1982. 175-181.
  23. 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 N UCB/EECS-2006-183. Berkeley, 2006.
  24. Abou-Rjeili A., Karypis G. Multilevel algorithms for partitioning power-law graphs // IEEE International Parallel &; Distributed Processing Symposium (IPDPS). Rhodes Island: IEEE, Press, 2006. 1-17.