DOI: https://doi.org/10.26089/NumMet.v17r330

Анализ и оптимизация алгоритма параллельных цепочек для реализации корневой редукции на распределенных вычислительных системах

Авторы

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

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

корневая редукция
модель передачи сообщений
MPI
параллельное программирование
распределенные вычислительные системы

Аннотация

В модели параллельных вычислений LogP построено аналитическое выражение времени выполнения алгоритма k параллельных цепочек для реализации корневой редукции на распределенных вычислительных системах (ВС). По построенной функциональной зависимости найдено оптимальное значение числа k параллельных цепочек, при котором алгоритм характеризуется минимальным в модели LogP временем выполнения. На основе этого создан алгоритм с оптимальным числом параллельных цепочек. Для сокращения времени ожидания корневым процессом результатов частичных редукций разработан алгоритм с адаптивным числом параллельных цепочек. Зависимость времени выполнения созданных алгоритмов от числа процессов имеет порядок роста Ο(sqrt{P}), что эффективнее по сравнению с линейным Ω(P) временем выполнения исходного алгоритма. Алгоритмы реализованы в стандарте MPI и исследованы на вычислительных кластерах с сетями связи стандарта InfiniBand QDR.

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

Загрузки

Опубликован

2016-08-06

Выпуск

Том 17 (2016): Выпуск 3.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

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

Сибирский государственный университет телекоммуникаций и информатики,
Центр параллельных вычислительных технологий
ул. Кирова, 86, 630102, Новосибирск
• директор

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

  1. V. G. Khoroshevsky, “Distributed Programmable Structure Computer Systems,” Vestn. Sib. Gos. Univ. Telekommun. Inform. 10 (2), 3-41 (2010).
  2. T. Hoefler and D. Moor, “Energy, Memory, and Runtime Tradeoffs for Implementing Collective Communication Operations,” J. Supercomput. Frontiers Innovations 1 (2), 58-75 (2014).
  3. P. Balaji, D. Buntinas, D. Goodell, et al., “MPI on Millions of Cores,” Parallel Process. Lett. 21 (1), 45-60 (2011).
  4. R. Alverson, D. Roweth, and L. Kaplan, “The Gemini System Interconnect,” in Proc. 18th IEEE Symposium on High Performance Interconnects, Mountain View, USA, August 18-20, 2010 (IEEE Press, Washington, DC, 2010), pp. 83-87.
  5. D. Chen, N. A. Eisley, P. Heidelberger, et al., “The IBM Blue Gene/Q Interconnection Network and Message Unit,” in Proc. 2011 Int. Conf. for High Performance Computing, Networking, Storage and Analysis, Seattle, USA, November 12-18, 2011 (ACM Press, New York, 2011),
    doi 10.1145/2063384.2063419
  6. V. K. Levin, B. N. Chetverushkin, G. S. Elizarov, et al., “Communication Fabric MVS-Express,” Inform. Tekhnol. Vychisl. Sistemy, No. 1, 10-24 (2014).
  7. R. Thakur, R. Rabenseifner, and W. Gropp, “Optimization of Collective Communication Operations in MPICH,” Int. J. High Perform. Comput. Appl. 19 (1), 49-66 (2005).
  8. M. G. Kurnosov, “Algorithms of Transmission-Cyclical Information Exchanges in the Hierarchical Distributed Computing Systems,” Vestn. Komp’yut. Inform. Tekhnol., No. 5, 27-34 (2011).
  9. T. Ma, G. Bosilca, A. Bouteiller, and J. J. Dongarra, “Kernel-Assisted and Topology-Aware MPI Collective Communications on Multiсore/Many-сore Platforms,” J. Parallel Distrib. Comput. 73 (7), 1000-1010 (2013).
  10. G. Fagg, J. Pješivac-Grbović, G. Bosilca, et al., “Flexible Collective Communication Tuning Architecture Applied to Open MPI,” in Proc. of EuroPVM/MPI, Bonn, Germany, September 17-20, 2006 (Forschungszentrum, Julich, 2006), pp. 1-10.
  11. J. Pješivac-Grbović, T. Angskun, G. Bosilca, et al., “Performance Analysis of MPI Collective Operations,” Cluster Comput. 10 (2), 127-143 (2007).
  12. D. Culler, R. Karp, D. Patterson, et al., “LogP: Towards a Realistic Model of Parallel Computation,” ACM SIGPLAN Notices 28 (7), 1-12 (1993).
  13. T. Worsch, R. Reussner, and W. Augustin, “On Benchmarking Collective MPI Operations,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2002), Vol. 2474, pp. 271-279.
  14. M. G. Kurnosov, “MPIPerf: A Toolkit for Benchmarking MPI Libraries,” Vestn. Lobachevskii Univ. Nizhni Novgorod, No. 5/2, 385-391 (2012).