Open AccessAn approximate algorithm for choosing the optimal subset of nodes in the Angara interconnect with failures
Author(s) -
А.В. Мукосей,
Alexander Semenov
Publication year - 2017
Publication title -
vyčislitelʹnye metody i programmirovanie
Language(s) - English
Resource type - Journals
eISSN - 1726-3522
pISSN - 0507-5386
DOI - 10.26089/nummet.v18r105
Subject(s) - interconnection , node (physics) , torus , computer science , topology (electrical circuits) , cluster (spacecraft) , algorithm , computer network , mathematics , engineering , combinatorics , geometry , structural engineering
В Научно-исследовательском центре электронной вычислительной техники (НИЦЭВТ) разрабатывается высокоскоростная коммуникационная сеть Ангара с топологией "многомерный тор". При эксплуатации вычислительного кластера с сетью Ангара в условиях наличия занятых и отказавших узлов возникает задачапоиска оптимального подмножества узлов сети для покрытия заданного числа узлов так, чтобы весь сетевой трафик лежал внутри этого подмножества узлов. В настоящей статье представлен приближенный полиномиальный алгоритм решения такой задачи. The Angara high-speed interconnect with multidimensional torus topology is under development in Scientific Research Center for Electronic Computer Technology. During the utilization of the Angara interconnect in cluster systems, there exist busy and failed nodes. Thus, there is a problem of finding an optimal cluster node subset such that the network traffic belongs to this node subset and the node subset size is not less than a given size. The paper presents an approximate algorithm for solving this problem.