Приближенный алгоритм выбора оптимального подмножества узлов в коммуникационной сети Ангара с отказами

Вычислительные методы и программирование: новые вычислительные технологии. 2017. Т. 18. С. 53–64.

Мукосей А. В., Семенов А. С.

В Научно-исследовательском центре электронной вычислительной техники (НИЦЭВТ) разрабатывается высокоскоростная коммуникационная сеть Ангара с топологией “многомерный тор”. При эксплуатации вычислительного кластера с сетью Ангара в условиях наличия занятых и отказавших узлов возникает задача поиска оптимального подмножества узлов сети для покрытия заданного числа узлов так, чтобы весь сетевой трафик лежал внутри этого подмножества узлов. В настоящей статье представлен приближенный полиномиальный алгоритм решения такой задачи.

Ключевые слова: связность, отказоустойчивость, fault tolerance, interconnect, torus topology, connectivity, коммуникационные сети, многомерный тор, deterministic routing, direction-order routing, детерминированная маршрутизация, порядок направлений