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

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

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @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   |   DOI: 10.14529/cmse220302

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

  • 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).
Еще
Статья научная