Научные статьи \ Философия. Психология

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

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

Автор: Хабирова Эльвира Радмировна, Сальников Алексей Николаевич

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Статья в выпуске: 3 т.11, 2022 года.

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

Топологическая структура коммуникационных сетей суперкомпьютерных систем при увеличении размера и сложности суперкомпьютеров соответственно усложняется. Для ее описания существует множество методов, однако такие описания являются громоздкими, что усложняет манипулирование ими. В статье предложен подход к описанию коммуникационной среды суперкомпьютера, когда коммуникационная сеть описывается как конструктор, где элементами конструктора являются типовые топологические структуры, часто встречающиеся в различных вычислительных системах. С этой целью разработан язык описания топологической структуры, основанный на операции произведения подграфов. Язык идейно схож в своих принципах с языками NetML и OMNeT++. Отдельное внимание в работе уделяется исключениям в регулярности сетей реальных суперкомпьютеров; с целью добавления возможности описания данного факта в язык внесены специальные конструкции. Для поддержки работы с языком описания разработана библиотека на языке программирования Си и специальная оболочка над ней написанная на языке Python3, которая затем может использоваться для визуализации описываемых языком графов. Выразительная мощность языка была продемонстрирована на описании вычислительных кластеров: Tianhe-2A, AI Bridging Cloud Infrastructure и Ломоносов-2. Метод был проверен и сравнен с GraphViz DOT показано многократное сокращение необходимых объема записи для некоторых крупных систем из Top500.

Еще

Вычислительный кластер, топология компьютерной сети, языки описания графов, произведения подграфов

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

IDR: 147238563   |   УДК: 19.175.3,   |   DOI: 10.14529/cmse220302

Topological structure of computing clusters description method based on operations of subgraphs multiplication

Topological structure of communication networks in supercomputers with grow in size and complexity of installation, respectively becomes more difficult. There are many methods to describe it, but such descriptions are cumbersome, which makes them difficult to manipulate. The article proposes an approach to describing the communication environment of a supercomputer, when the communication network is described as a constructor. The elements of the constructor are typical topological structures often found in various computing systems. For this purpose, a language for describing the topological structure has been developed. It based on the operation products of subgraphs. The language is ideologically similar in its principles to the NetML and OMNeT++ languages. Special attention is paid to exceptions in the regularity of networks of real supercomputers; in order to add the possibility of describing this fact, special constructions have been introduced into the language. A library has been developed in the C programming language with purpose to facilitate work with the language intoduced in this article. Also a special wrapper over C library has been written in Python3, which then can be used to visualize graphs described by the language. The expressive power of language has been demonstrated in the description computing clusters: Tianhe-2A, AI Bridging Cloud Infrastructure and Lomonosov-2. The method has been tested and compared with GraphViz DOT it is showed multiple reductions in the Record volume required to save topology for some of the major Top500 systems.

Еще

Список литературы Метод описания топологической структуры вычислительных кластеров, основанный на операциях произведений подграфов

  • June 2022 | ТОР500 Supercomputer Sites. URL: https://top500.org/lists/top500/ 2022/06/ (дата обращения: 21.08.2022).
  • Воеводин В.В., Воеводин В.В. Параллельные вычисления. БХВ-Петербург, 2002. 608 с.
  • Leiserson С.Е. Fat-trees: Universal networks for hardware-efficient supercomputing // IEEE Transactions on Computers. 1985. Vol. 34, no. 10. P. 892-901. DOI: 10.1109/TC. 1985. 6312192.
  • Ohring S.R., Ibel М., Das S.K., Kumar M.J. On generalized fat trees // Proceedings of IPPS ’95, The 9th International Parallel Processing Symposium, Santa Barbara, California, USA, April 25-28, 1995. IEEE, 1995. P. 37-44. DOI: 10.1109/IPPS. 1995.395911.
  • Kim J., Dally W.J., Scott S., Abts D. Technology-Driven, Highly-Scalable Dragonfly Topology // 35th International Symposium on Computer Architecture (ISCA 2008), Beijing, China, June 21-25, 2008. IEEE, 2008. P. 77-88. DOI: 10.1109/ISCA.2008.19.
  • Kim J., Dally W.J., Abts D. Flattened Butterfly: A Cost-Efficient Topology for High-Radix Networks // 34th International Symposium on Computer Architecture (ISCA 2007), San Diego, California, USA, June 9-13, 2007. ACM, 2007. P. 126-137. DOI: 10.1145/1250662. 1250679.
  • Petrini F., Kerbyson D.J., Pakin S. The Case of the Missing Supercomputer Performance: Achieving Optimal Performance on the 8,192 Processors of ASCI Q // Proceedings of the ACM/IEEE SC2003 Conference on High Performance Networking and Computing, Phoenix, AZ, USA, November 15-21, 2003, CD-Rom. 2003. P. 55-55. DOI: 10. 1145/ 1048935.1050204.
  • Zheng G., Wilmarth T., Jagadishprasad P., Kale L. Simulation-Based Performance Prediction for Large Parallel Machines // International Journal of Parallel Programming. 2005. Vol. 33, no. 2-3. P. 183-207. DOI: 10.1007/sl0766-005-3582-6.
  • Liu N., Carothers C., Cope J., et al. Model and Simulation of Exascale Communication Networks // Journal of Simulation. 2012. Vol. 6, no. 4. P. 227-236. DOI: 10.1057/j os. 2012.4.
  • Parsonage E., Nguyen H.X., Bowden R., et al. Generalized graph products for network design and analysis // Proceedings of the 19th annual IEEE International Conference on Network Protocols, ICNP 2011, Vancouver, BC, Canada, October 17-20, 2011. IEEE, 2011. P. 79-88. DOI: 10.1109/ICNP. 2011.6089084.
  • Roughan M., Tuke S.J. Unravelling Graph-Exchange File Formats // CoRR. 2015. Vol. abs/1503.02781. arXiv: 1503.02781. URL: http://arxiv.org/abs/1503.02781.
  • Siek J., Lee L.-Q., Lumsdaine A. The Boost Graph Library: User Guide and Reference Manual. 2002. 346 p.
  • Ellson J., Gansner E.R., Koutsofios E., et al. Graphviz - Open Source Graph Drawing Tools // Graph Drawing, 9th International Symposium, GD 2001 Vienna, Austria, September 23-26, 2001, Revised Papers. Vol. 2265 / ed. by P. Mutzel, M. Jiinger, S. Leipert. Springer, 2001. P. 483-484. Lecture Notes in Computer Science. DOI: 10.1007/3-540-45848-4_57.
  • Batagelj V., Mrvar A. Pajek - Program for Large Network Analysis. 1999.
  • Tamassia R. Handbook of Graph Drawing and Visualization. 1st. Chapman & Hall/CRC, 2016.
  • Himsolt M. GML: A portable Graph File Format. 2010. URL: http://www.fim.uni-passau.de/fileadmin/files/lehrstuhl/brandenburg/projekte/gml/gml-technical-report.pdf.
  • Holt R.C., Schiirr A., Sim S.E., Winter A. GXL: A graph-based standard exchange format for reengineering // Science of Computer Programming. 2006. Vol. 60, no. 2. P. 149-170. DOI: 10.1016/j . scico. 2005.10.003.
  • Batagelj V., Mrvar A. Towards NetML Networks Markup Language // International Social Network Conference, London. 1995.
  • Kumar A.R.A., Rao S.V., Goswami D. NS3 Simulator for a Study of Data Center Networks // IEEE 12th International Symposium on Parallel and Distributed Computing, ISPDC 2013, Bucharest, Romania, June 27-30, 2013. IEEE, 2013. P. 224-231. DOI: 10. 1109/ISPDC.2013.37.
  • Choudhury N., Mehta Y., Wilmarth T.L., et al. Scaling an Optimistic Parallel Simulation of Large-Scale Interconnection Networks // Proceedings of the 37th Winter Simulation Conference, Orlando, FL, USA, December 4-7, 2005. IEEE, 2005. P. 591-600. DOI: 10 . 1109/WSC.2005.1574299.
  • Lantz B., Heller B., McKeown N. A Network in a Laptop: Rapid Prototyping for Software-Defined Networks // Proceedings of the 9th ACM Workshop on Hot Topics in Networks. HotNets 2010, Monterey, CA, USA, October 20-21, 2010. ACM, 2010. Article 19. DOI: 10.1145/1868447.1868466.
  • Navaridas J., Pascual J.A., Erickson A., et al. INRFlow: An interconnection networks research flow-level simulation framework // Journal of Parallel and Distributed Computing. 2019. Vol. 130. P. 140-152. DOI: 10.1016/j .jpdc.2019.03.013.
  • Varga A. The OMNET++ discrete event simulation system // Proc. ESM’2001. 2001. Vol.
  • Varga A., Hornig R. An Overview of the OMNeT++ Simulation Environment // Proceedings of the 1st International Conference on Simulation Tools and Techniques for Communications, Networks and Systems & Workshops, SimuTools 2008, Marseille, France, March 3-7, 2008. ICST/ACM, 2008. Article 60. DOI: 10.5555/1416222.1416290.
  • Sabidussi G. Graph multiplication // Mathematische Zeitschrift. 1959. Vol. 72, no. 1. P. 446-457. DOI: 10.1007/bf01162967.
  • Weichsel P. The Kronecker Product of Graphs // Proceedings of The American Mathematical Society - PROC AMER MATH SOC. 1962. Vol. 13. DOI: 10.2307/2033769.
  • Geller D., Stahl S. The chromatic number and other functions of the lexicographic product // Journal of Combinatorial Theory, Series B. 1975. Vol. 19, no. 1. P. 87-95. DOI: 10.1016/0095-8956(75)90076-3.
  • Godsil C., McKay B. A new graph product and its spectrum // Bulletin of The Australian Mathematical Society - BULL AUST MATH SOC. 1978. Vol. 18. DOI: 10.1017/ S0004972700007760.
  • Кнут Д. Искусство программирования, том 4, А. Комбинаторные алгоритмы, часть 1. Вильямс, 2013.
  • Chen D., Eisley N.A., Heidelberger Р., et al. The IBM Blue Gene/Q Interconnection Network and Message Unit / / Conference on High Performance Computing Networking, Storage and Analysis, SC 2011, Seattle, WA, USA, November 12-18, 2011. ACM, 2011. Article 26. DOI: 10.1145/2063384.2063419.
  • Bray Т. The JavaScript Object Notation (JSON) Data Interchange Format: RFC / RFC Editor. 2017. No. 8259. URL: https://www.rfc-editor.org/rfc/rfc8259.txt.
  • IEEE Standard for Information Technology-Portable Operating System Interface (POSIX(R)) Base Specifications, Issue 7 // IEEE Std 1003.1-2017 (Revision of IEEE Std 1003.1-2008). 2018. P. 1-3951. DOI: 10.1109/IEEESTD.2018.8277153.
  • Stunkel C.B., Graham R.L., Shainer G., et al. The high-speed networks of the Summit and Sierra supercomputers // IBM J. Res. Dev. 2020. Vol. 64, no. 3/4. 3:1-3:10. DOI: 10.1147/JRD.2020.2967330.
  • Liao X.-K., Pang Z.-B., Wang K.-F., et al. High Performance Interconnect Network for Tianhe System // Journal of Computer Science and Technology. 2015. Vol. 30, no. 2. P. 259-272. DOI: 10.1007/sll390-015-1520-7.
  • Takizawa S. Al Bridging Cloud Infrastructure (ABCI) and its Communication Performance. 2019. URL: http://mug.mvapich.cse.ohio-state.edu/mug/19/ 7th Annual MVAPICH User Group Meeting.
  • Voevodin V., Antonov A., Nikitenko D., et al. Supercomputer Lomonosov-2: Large Scale, Deep Monitoring and Fine Analytics for the User Community // Supercomputing Frontiers and Innovations. 2019. Vol. 6, no. 2. P. 4-11. DOI: 10.14529/jsfИ90201.
  • PARALLEL.RU. Суперкомпьютер “ЛОМОНОСОВ-2” | PARALLEL.RU - Информационно-аналитический центр по параллельным вычислениям. URL: https : //parallel.ru/cluster/lomonosov2.html (дата обращения: 15.05.2020).
Еще
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp