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

Анатолий Викторович Мукосей, Александр Сергеевич Семенов

Аннотация


В данной работе рассматривается высокоскоростная вычислительная сеть с топологией многомерный тор. Работа посвящена оптимизации фрагментации, возникающей в результате последовательного выделения вычислительных узлов в многоузловой системе при заданном требовании о том, что сетевой трафик разных пользовательских заданий не должен пересекаться. В данной работе на основе идей из задачи о многомерной упаковке контейнера предложен метод поиска узлов с оценкой фрагментированности системы. Для такой оценки введено понятие прямоугольников максимального размера, которые возможно вписать в систему после размещения очередного пользовательского задания. Каждое множество узлов, подходящее для размещения задания, оценивается предложенной функцией, учитывающей размер и количество найденных прямоугольников максимального размера. Исследование разработанного метода проводилось с помощью симулятора работы вычислительной системы. Рассмотрен набор различных вычислительных систем с трехмерными и четырехмерными топологиями, размер минимальной системы — 32 вычислительных узла, максимальной — 144 узла. Для каждой системы задана синтетическая очередь заданий, параметры которой приближены к реально возможной. В качестве критерия качества метода выбора узлов рассматривается средняя утилизация ресурсов вычислительной системы и среднее время ожидания заданий в очереди. Исследование показало, что увеличение утилизации ресурсов для предложенного метода выбора узлов составило в среднем 11% по сравнению с базовым методом, а среднее значение времени нахождения задания в очереди сокращенно на 45,3%.


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


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

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

PDF

Литература


Lan Z., Tang W., Wang J., Yang X., Zhou Z., Zheng X. Balancing job Performance with System Performance via Locality-aware Scheduling on Torus-connected Systems. 2014 IEEE International Conference on Cluster Computing (CLUSTER) (Madrid, Spain, September 22–26, 2014). 2014. pp. 140–148. DOI: 10.1109/CLUSTER.2014.6968751.

IBM Redbooks Publication: IBM System Blue Gene Solution: Blue Gene/Q system administration. 2013. 282 p.

Tang W., Lan Z., Desai N., Buettner D., Yu Y. Reducing Fragmentation on Torus-Connected Supercomputers. Proceedings of the 2011 IEEE International Parallel Distributed Processing Symposium (IPDPS’11) (Anchorage, Alaska, USA, May 16–20, 2011), 2011. pp. 828–839. DOI: 10.1109/IPDPS.2011.82.

Cray Document: Managing System Software for Cray XE and Cray XT Systems. 2010.

Agarkov A.A., Ismagilov T.F., Makagon D.V. Performance Evaluation of the Angara Interconnect. Supercomputernie dni v Rossii: Trudy meghdunarodnoj konferentsii (Moscva, 26–27 sentyabra 2016) [Russian Supercomputing Days: Proceedings of the International Scintific Conference (Moscow, Russia, September 26–27, 2016)]. Moscow, Publishing House of Moscow State University, 2016. pp. 626–639. (in Russian)

Simonov A.S., Makagon D.V., Zhabin I.A., Shcherbak A.N., Syromyatnikov E.L., Polyakov D.A. The First Generation of Angara High-Speed Interconnect. Naukoemkie technologii [Science Technologies]. 2014. vol. 15, no. 1. pp. 21–28. (in Russian)

Puente V., Beivide R., Gregorio J.A., Prellezo J.M., Duato J., Izu C. Adaptive Bubble Router: a Design to Improve Performance in Torus Networks. Proceedings of the International Conference Parallel Processing (Wakamatsu, Japan, September 21–24, 1999), 1999. pp. 58–67. DOI: 10.1109/ICPP.1999.797388.

Adiga N.R., Blumrich M., Chen D.. Blue Gene/L Torus Interconnection Network. IBM Journal of Research and Development. 2005. vol. 49, no. 2. pp. 265–276. DOI: 10.1147/rd.492.0265.

Scott S.L., et al. The Cray T3E Network: Adaptive Routing in a High. Performance 3D Torus. 1996.

Pozhilov I.A., Semenov A.S., Makagon D.V., Connectivity Problem Solution for Direction Ordered Deterministic Routing in nD Torus. Programmnaya inzheneriya [Software Engineering]. 2015. no. 3. pp. 13–19. (in Russian)

Kagirov R.R. Multiple Knapsack Problem: New Solving Methods. Vestnik SibGAU [Vestnik of the Reshetnev Siberian State Aerospace University]. 2007. no. 3. pp. 16–20. (in Russian)

Gonçalves J. F., Resende M.G.C. A Parallel Multi-population Based Random-key Genetic Algorithm for a Container Loading Problem. Computers & Operations Research. February 2012. vol. 39, no. 2. pp. 179--190. DOI: 10.1016/j.cor.2011.03.009.

Mukosey A.V., Semenov A.S. An Approximate Algorithm for Choosing the Optimal Subset of Nodes in the Angara Interconnect with Failures. Vyichislitelnyie metodyi i programmirovanie [Numerical methods and Programming]. 2017. vol. 18. pp. 53–64. (in Russian)

Baranov A.V., Kiselev E.A., Lyakhovets D.S. The quasi scheduler for utilization of multiprocessing computing system's idle resources under control of the management system of the parallel jobs. Vestnik Yuzhno-Ural'skogo Gosudarstvennogo Universiteta. Seriya "Vychislitelnaya Matematika i Informatika" [Bulletin of South Ural State University. Series: Computational Mathematics and Software Engineering]. 2014. vol. 3, no. 4. pp. 75–84. DOI: 10.14529/cmse140405. (in Russian)

Polezhaev P.N. Simulator of computer cluster and its management system used for research of job scheduling algorithms. Vestnik Yuzhno-Ural'skogo Gosudarstvennogo Universiteta. Seriya "Matematicheskoe Modelirovanie i Programmirovanie" [Bulletin of South Ural State University. Series: Mathematical Modeling, Programming & Computer Software]. 2010. vol. 6. pp. 79–90. (in Russian)




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