sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИsibsutis-665Research ArticleСтатьиСтруктурно-ориентированный метод оптимизации алгоритмов коллективных обменов в распределённых вычислительных системах*)Topology-aware method for optimizing collective communication operations in distributed computer systemsКурносовМ. Г.M. Kurnosovnoemail@neicon.ruСибирский государственный университет телекоммуникаций и информатикиRussian Federation201016012023025465Copyright © Курносов М.Г., 20232023Курносов М.Г.Курносов М.Г.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/665

Предлагается метод оптимизации алгоритмов реализации коллективных обменов информацией между ветвями параллельных программ в распределённых вычислительных системах (ВС). Метод поясняется на примере создания алгоритмов трансляционно-циклических обменов (ТЦО, All-to-all Broadcast), учитывающих иерархическую структуру распределённых ВС. Показана эффективность разработанных алгоритмов ТЦО в сравнении с существовавшими версиями. Накладные расходы на оптимизацию незначительны и компенсируются сокращением времени реализации ТЦО предложенными алгоритмами.

Interconnection networks of modern distributed computer systems are now hierarchical. In such systems communication time between processor cores depends on a placement of processors in a system. For example, in large-scale SMP computer clusters first two levels are formed by switches of two-stage fat tree and a third level is presented by a shared memory of computer nodes. In this paper, we describe a dynamic optimization method for collective communication operations on hierarchical computer clusters. Our approach exploits knowledge of the L-level hierarchy and is based on a mapping of intensively communicating processes into the same computer node. Performance results on multicore SMP computer clusters with In?niBand and Gigabit Ethernet networks indicate that the Allgather algorithms based on our approach outperform the original Allgather algorithms.

операции коллективных обменов информациейпараллельное программированиераспределённые вычислительные системыcollective communication operationsparallel programmingdistributed computer systemsReferencesХорошевский В.Г. Архитектура вычислительных систем. - М.: МГТУ им. Н.Э. Баумана, 2008. - 520 с.Хорошевский В.Г. Архитектура вычислительных систем. - М.: МГТУ им. Н.Э. Баумана, 2008. - 520 с.Евреинов Э.В., Хорошевский В.Г. Однородные вычислительные системы. - Новосибирск: Наука, 1978. - 320 с.Евреинов Э.В., Хорошевский В.Г. Однородные вычислительные системы. - Новосибирск: Наука, 1978. - 320 с.Rabenseifner R. Automatic MPI Counter Profiling // Proceedings of the 42nd Cray User Group. - Noorwijk, The Netherlands, 2000. - 19 pp.Rabenseifner R. Automatic MPI Counter Profiling // Proceedings of the 42nd Cray User Group. - Noorwijk, The Netherlands, 2000. - 19 pp.Han D., Jones T.. MPI Profiling // Technical Report UCRL-MI-209658 - Lawrence Livermore National Laboratory, USA, 2004. - 15 pp.Han D., Jones T.. MPI Profiling // Technical Report UCRL-MI-209658 - Lawrence Livermore National Laboratory, USA, 2004. - 15 pp.Thakur R., Rabenseifner R., and Gropp W. Optimization of collective communication operations in MPICH // Int. Journal of High Performance Computing Applications. - 2005. - Vol. 19, No. 1. - P. 49-66.Thakur R., Rabenseifner R., and Gropp W. Optimization of collective communication operations in MPICH // Int. Journal of High Performance Computing Applications. - 2005. - Vol. 19, No. 1. - P. 49-66.Balaji P., Buntinas D., Goodell D., Gropp W., Kumar S., Lusk E., Thakur R. and Traff J. L. MPI on a Million Processors // Proc. of the PVM/MPI - Berlin: Springer-Verlag, 2009 .- P. 20-30.Balaji P., Buntinas D., Goodell D., Gropp W., Kumar S., Lusk E., Thakur R. and Traff J. L. MPI on a Million Processors // Proc. of the PVM/MPI - Berlin: Springer-Verlag, 2009 .- P. 20-30.Khoroshevsky V., Kurnosov M. Mapping Parallel Programs into Hierarchical Distributed Computer Systems // Proc. of "Software and Data Technologies". − Sofia: INSTICC, 2009. − Vol. 2 .− P. 123-128.Khoroshevsky V., Kurnosov M. Mapping Parallel Programs into Hierarchical Distributed Computer Systems // Proc. of "Software and Data Technologies". − Sofia: INSTICC, 2009. − Vol. 2 .− P. 123-128.Bruck J., Ho C.-T., Kipnis S., Upfal E. and Weathersby D. Efficient algorithms for all-to-all communications in multiport message-passing systems // IEEE Transactions on Parallel and Distributed Systems. - 1997. - Vol. 8 (11). - P. 1143-1156.Bruck J., Ho C.-T., Kipnis S., Upfal E. and Weathersby D. Efficient algorithms for all-to-all communications in multiport message-passing systems // IEEE Transactions on Parallel and Distributed Systems. - 1997. - Vol. 8 (11). - P. 1143-1156.Karypis G. and Kumar V. A Fast and Highly Quality Multilevel Scheme for Partitioning Irregular Graphs // SIAM Journal on Scientific Computing. - 1999. - Vol. 20, No. 1, P. 359-392.Karypis G. and Kumar V. A Fast and Highly Quality Multilevel Scheme for Partitioning Irregular Graphs // SIAM Journal on Scientific Computing. - 1999. - Vol. 20, No. 1, P. 359-392.Schloegel K., G. Karypis, V. Kumar. Graph partitioning for high-performance scientific simulations // Sourcebook of parallel computing. - San Franciso: Morgan Kaufmann Publish, 2003. - P. 491-541.Schloegel K., G. Karypis, V. Kumar. Graph partitioning for high-performance scientific simulations // Sourcebook of parallel computing. - San Franciso: Morgan Kaufmann Publish, 2003. - P. 491-541.Курносов М.Г. Алгоритмы вложения параллельных программ в иерархические распределённые вычислительные системы // Вестник СибГУТИ. − 2009. − № 2 (6). − С. 20-45.Курносов М.Г. Алгоритмы вложения параллельных программ в иерархические распределённые вычислительные системы // Вестник СибГУТИ. − 2009. − № 2 (6). − С. 20-45.

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