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

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

Аннотация


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

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


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

Полный текст:

PDF

Литература


June 2022 | TOP500 Supercomputer Sites. URL: https://top500.org/lists/top500/2022/06/ (accessed: 21.08.2022).

Voevodin V.V., Voevodin V.V. Parallel Computing. BHV-Petersburg, 2002. 608 p.

Leiserson C.E. 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 M., 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., Kalé 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/s10766-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/jos.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. Jünger, 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.unipassau.de/fileadmin/files/lehrstuhl/brandenburg/projekte/gml/gml-technicalreport.pdf.

Holt R.C., Schürr 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. 9.

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.

Knuth D.E. The Art of Computer Programming: Volume 4A: Combinatorial Algorithms: Part 1. Addison-Wesley Professional, 2014. P. 27–28.

Chen D., Eisley N.A., Heidelberger P., 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 T. 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. P. 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/s11390-015-1520-7.

Takizawa S. AI 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/jsfi190201.

PARALLEL.RU. Supercomputer "Lomonosov-2" | PARALLEL.RU – Information and analytical center for parallel computing on the internet. URL: https://parallel.ru/cluster/lomonosov2.html (accessed: 15.05.2020).




DOI: http://dx.doi.org/10.14529/cmse220302