Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt Приближенный алгоритм выбора оптимального подмножества узлов в коммуникационной сети Ангара с отказами А. В. Мукосей, А. С. Семенов, Д. В. Макагон АО «НИЦЭВТ» В АО «НИЦЭВТ» разрабатывается высокоскоростная коммуникационная сеть Ангара с топологией «многомерный тор». При реальном использовании супер- компьютера с сетью Ангара в условиях наличия занятых и отказавших узлов возникает задача нахождения оптимального подмножества узлов сети для по- крытия заданного числа узлов так, чтобы весь сетевой трафик лежал только внутри этого подмножества узлов. В данной работе представлен приближенный полиномиальный алгоритм решения такой задачи. Ключевые слова: Отказоустойчивость, коммуникационные сети, многомерный тор, связность, детерминированная маршрутизация, маршрутизация с порядком на- правлений. 1. Введение В АО «НИЦЭВТ» разрабатывается высокоскоростная коммуникационная сеть Анга- ра [1, 2] с топологией «многомерный тор». В маршрутизаторе сети реализована бездед- локовая, адаптивная маршрутизация, основанная на правилах «пузырька» (Bubble flow control, [4]) и «порядка направлений» (Direction ordered routing, DOR, [5, 6]) с использо- ванием битов направлений [6]. Благодаря алгоритму First Step/Last Step «нестандартного первого и последнего шага» [6] аппаратно поддерживается обход отказавших узлов или линков. Эффективность этого метода по поддержанию связности в сети с отказами была показана в статье [3]. Применяемая маршрутизация позволяет избежать взаимных блоки- ровок из-за циклических зависимостей пакетов в кольцах и между кольцами нескольких измерений, а также гарантирует сохранение порядка передачи пакетов между любыми дву- мя адресатами. Для эффективного использования узлов системы, необходимо уметь оптимально вы- делять ресурсы в зависимости от состояния кластера. Состояние кластера изменяется по- стоянно по различным причинам: занятость отдельных узлов и неисправность оборудова- ния. Необходимо уметь за небольшое время принимать решения по выделению требуемого числа узлов. В данной статье предложен приближенный алгоритм выбора оптимального подмножества узлов в коммуникационной сети Ангара с отказами. Авторам статьи подоб- ные алгоритмы для сетей с топологией «многомерный тор» и используемыми в сети Ангара методами маршрутизации в литературе неизвестны. Статья организована следующим образом. В разделе 2 приводятся необходимые фор- мальные определения. В разделе 3 описывается маршрутизация в сети Ангара. В разделе 4 представлена постановка задачи. В разделе 5 рассматриваются алгоритмы решения постав- ленной задачи: вспомогательный алгоритм определения существования маршрутов из каж- дого узла множества в другой каждый узел этого множества, алгоритм выбора множеств узлов равномерным расширением, приближенный алгоритм расчета оптимальных таблиц маршрутизации для заданного множества узлов, также в этом разделе описан используе- мый в настоящее время в сети Ангара алгоритм выбора требуемого множества узлов без учета занятых или отказавших узлов. Исследование разработанных алгоритмов проводится в разделе 6. 257 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt 2. Определения В данном разделе вводятся некоторые формальные определения, которые в дальнейшем будут использоваться в статье. Рассмотрим коммуникационную сеть с топологией многомерный тор. Множество всех узлов сети обозначим N , размерности тора обозначим (d1 , d2 , ..., dn ), а общее число узлов — | N | . Каждый узел u имеет координаты (u1 , u2 , ..., un ), где 0 \leq ui < di . Соседними в рамках тороидальной топологии будем называть узлы u = (u1 , u2 , ..., un ) и u \~ = (u1 , ..., (uj \pm 1) mod dj , ..., un ) для любого индекса 1 \leq j \leq n. Легко заметить, что каждый узел имеет 2n соседей (в случае dj > 2). Будем считать, что каждый из этих соседей находится в одном из направлений от узла u. Множество направлений обозначим \scrD и пронумеруем их числами 1, 2n: \scrD = \{ \bigtriangleup j \} j=1,2n . Направления с номерами 1, ..., n будем называть положительными: u \~ = (u1 , ..., (uj + 1) mod dj , ..., un ), \bigtriangleup j = (0, ..., \underbrace{} 1\underbrace{} , ..., 0) \in \scrD , позиция j где 1 \leq j \leq n. Направления с номерами n + 1, ..., 2n будем называть отрицательными: \~ = (u1 , ..., (uj - n - 1) mod dj - n , ..., un ), u \bigtriangleup j = (0, ..., \underbrace{} - 1 \underbrace{} , ..., 0) \in \scrD , позиция j - n где n + 1 \leq j \leq 2n. В такой формулировке выражение «узел u находится в направлении D от узла v записывается как u = v + D». На множестве направлений \scrD введем порядок в соответствии с указанной нумерацией: \bigtriangleup i < \bigtriangleup j , если i < j. Определение 1. Каналом связи (линком) будем называть пару (u, D), где u \in N , D \in \scrD . Множество всех каналов связи обозначим \scrE = N \times \scrD . Определение 2. Путем \scrP , соединяющим два узла сети: u0 и un , назовем последователь- ность вида u0 , D1 , u1 , D2 , ..., DN , uN , где ui — узел сети, Di — направления, связывающее узел ui - 1 с узлом ui , N — длина пути. При этом u1 , ..., un - 1 — транзитные узлы. Так как транзитные узлы могут быть получены из соответствующих переходов, то их можно опустить, тогда подобный путь будет записываться в виде: u0 , D1 , D2 , ..., Dn . Определение 3. Подмножество M множества узлов N назовем маршрутизируемым, если для любых двух узлов u, v множества M существует путь \scrP из u в v такой, что транзитные узлы этого пути принадлежат M . Определение 4. Таблицей маршрутизации \scrR маршрутизируемого множества M назовем некоторый набор путей таких, что для любых двух узлов u, v множества M в \scrR существует единственный путь из u в v такой, что транзитные узлы этого пути принадлежат M . Определение 5. Диаметром маршрутизируемого множества M с таблицей маршрутиза- ции \scrR назовем максимальную длину пути из набора путей \scrR . Определение 6. Пусть для некоторого маршрутизируемого множества M \subset N построена таблица маршрутизации \scrR . Загруженностью G(u,D) канала связи маршрутизируемого мно- жества M будем называть количество путей, которым принадлежит данный канал связи: G(u,D) = | \{ \scrP ij | (u, D) \in \scrP ij , \scrP ij \in \scrR \} | . 258 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt 3. Маршрутизация в сети Ангара 3.1. Правило порядка направлений с использование битов направлений Среди алгоритмов маршрутизации для многомерных торов можно выделить класс ал- горитмов, соблюдающих правило порядка направлений: маршрут между любой парой узлов включает движения в направлениях в определенном, заранее заданном, порядке. Эти алго- ритмы обладают свойством отсутствия взаимных блокировок между кольцами нескольких измерений тора при любом количестве одновременных запросов на передачу данных по сети. Во введенных обозначениях правило порядка направлений будет формулироваться сле- дующим образом: Dj - 1 \leq Dj , j = 2, N , где N — длина пути. Чтобы задать путь, удовлетворяющий правилу порядка направлений, необходимо за- дать стартовую вершину и количество шагов в каждом из направлений, т.е. набор u0 , s\delta (1) , s\delta (2) , ..., s\delta (i) , где u0 \in N — стартовый узел, s\delta (1) , s\delta (2) , ..., s\delta (i) > 0 — количество шагов в направлениях \bigtriangleup \delta (1) , \bigtriangleup \delta (2) , ..., \bigtriangleup \delta (i) таких, что \bigtriangleup \delta (j) < \bigtriangleup \delta (j+1) , j = 1, i - 1. В сети Ангара реализована маршрутизация с использованием битов направлений, ко- торая вносит некоторые ограничения на маршрутизацию с правилом порядка направлений. Аналогично правилу порядка направлений для задания пути, соответствующему маршру- тизации с использованием битов направлений, необходимо задать стартовую вершину и ко- личество шагов в выбранных направлениях, то есть следующий набор: u0 , s\delta (1) , s\delta (2) , ..., s\delta (i) , где u0 \in N – стартовый узел, s\delta (1) , s\delta (2) , ..., s\delta (i) > 0 – количество шагов в направлени- ях \bigtriangleup \delta (1) , \bigtriangleup \delta (2) , ..., \bigtriangleup \delta (i) . При этом в наборе направлений \bigtriangleup \delta (1) , \bigtriangleup \delta (2) , ..., \bigtriangleup \delta (i) нет направле- ний с противоположными знаками и \bigtriangleup \delta (j) < \bigtriangleup \delta (j+1) , j = 1, i - 1. Обозначим такой набор направлений как Ddirbit . Путь, соответствующий маршрутизации с использованием битов направлений, обозначим Pdirbit . 3.2. First Step/Last Step Метод First Step/Last Step [6] используется в сети Ангара как механизм обхода отка- завших узлов. Он расширяет маршрутизацию с использованием битов направлений путем добавления первого и последнего нестандартного шага. Путь с использованием первого и последнего нестандартного шага будет записываться следующим образом: u0 , DF S , Pdirbit , DLS , где u0 — стартовый узел, DF S — первое поло- жительное нестандартное направление, DLS — последнее отрицательное нестандартное на- правление. При этом набор направлений DF S , Ddirbit , DLS удовлетворяет правилу порядка направлений. Таким образом, для однозначного задания пути в сети Ангара необходимо задать набор DF S , Pdirbit , DLS . 4. Постановка задачи Во время работы разделяемого вычислительного кластера необходимо при любом со- стоянии системы уметь предоставлять требуемое число узлов, которые должны быть марш- рутизируемы между собой и не иметь транзитного трафика вне этого набора узлов, если это возможно. Состояние системы определяется набором отказавших линков и/или узлов и наличием занятых узлов. Занятый или отказавший узел можно интерпретировать как узел, у которого линки сломаны во всех направлениях. Обозначим множество сломанных линков F \subset \scrE . Так как физический канал связи между двумя узлами v и u представляет собой линки от узла v к узлу u и наоборот, то разумно предположить, что при неисправности одного из линков — второй так же неисправен. Таким образом, множество F будет включать в себя 259 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt отказавшие каналы связи попарно. Во введенных определениях задача будет формулироваться следующим образом. Пусть задан тор c размерностями (d1 , ..., dn ) и набором отказавших линков F . Требуется построить алгоритм нахождения маршрутизируемого множества M такого, что m \leq | M | , где m — требуемое число узлов. Так как различных систем M может быть несколько, необходим критерий выбора опти- мального маршрутизируемого множества. В работе рассматривались следующие критерии: 1. Минимальный диаметр; 2. Наименьшая средняя загрузка линков; 3. Наименьшее число транзитных узлов. Первый критерий возникает из-за того, что в сети с минимальным диаметром задержка на передачу данных будет наименьшей. Второй критерий следует из стремления получить равномерно загруженную систему. Третий критерий — из необходимости эффективно ис- пользовать аппаратные ресурсы вычислительного кластера. 5. Алгоритмы решения задачи Для решения поставленной задачи разработано несколько алгоритмов. Основной ал- горитм выбора множеств узлов равномерным расширением (см. подраздел 5.2) приведен после используемого им вспомогательного алгоритма проверки множества на маршрутизи- руемость (см. подраздел 5.1). В алгоритме равномерного расширения строится набор мно- жеств требуемого размера, после чего требуется выбрать оптимальное множество. Прибли- женный алгоритм расчета критериев оптимальности и выбора множества, которое является решением задачи, приведен в подразделе 5.3. Для оценки качества предложенного алгоритма в подразделе 5.4 приведен используе- мый в настоящее время в сети Ангара алгоритм выбора требуемого множества узлов без учета занятых или отказавших узлов. 5.1. Алгоритм определения маршрутизируемости множества Сведем задачу определения маршрутизируемости множества к поиску пути в некотором ориентированном графе G(V, E). При построении маршрута между двумя узлами ограничение на принятие решения о следующем шаге вносит предыстория пути. Рассмотрим движение по некоторому пути в торе в направлениях: \bigtriangleup \delta (1) , ..., \bigtriangleup \delta (i) . Этот путь можно продолжить только в таком на- правлении \bigtriangleup \delta (i+1) , что набор направлений \bigtriangleup \delta (0) , ..., \bigtriangleup \delta (i) , \bigtriangleup \delta (i+1) удовлетворяет правилу с использованием битов направлений или \bigtriangleup \delta (i) \leq \bigtriangleup \delta (i+1) в случае, если \bigtriangleup \delta (i+1) является последним нестандартным шагом. Поэтому для описания вычислительного узла ui в графе построим множество U i вер- шин, которые будут характеризовать предысторию путей, которые проходят через вычис- лительный узел ui : i 1. UD , j = 1, .., n — вершины, в которые возможно попасть, совершив первый нестан- F Sj дартный положительный шаг из соседнего узла в направлении DF Sj ; 2. UDi , j = n + 1, .., 2n — вершины, в которые возможно попасть, совершив последний LSj нестандартный отрицательный шаг из соседнего узла в направлении DF Sj ; i 3. UD , Ddirbitj \in Ddirbit — всевозможные наборы направлений, удовлетворяющие dirbitj правилу с использованием битов направлений, за исключением набора с отсутствием 260 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt движения. В эти вершины возможно попасть, совершив движение по соответствую- щему набору направлений; i 4. Ubegin — вершина, из которой начинается движение. i 5. Uend — вершина, в которой заканчивается движение. Посчитать количество вершин UD i можно следующим образом. Закодируем набор dirbitj n-мерным числом, где на j-ом месте стоит - 1 в случае движения в направлении \bigtriangleup j +n , +1 в случае движения в направлении \bigtriangleup j и 0 — в случае отсутствия движения в j-том измерении тора. Всего таких наборов 3n - 1. Таким образом, 3 - 1 i n U i = (\cup nj=1 UD i FS ) \cup (\cup 2n i i i j=n+1 UDLS ) \cup (\cup j=1 UDdirbit ) \cup Ubegin \cup Uend , j j i i n n | U | = n + n + 3 - 1 + 2 = 3 + 2n + 1, | N | V = \cup i=1 U i , | V | = | N | \ast | U i | = | N | \ast (3n + 2n + 1) = A| N | . Соединим вершины в графе следующим образом. i 1. Рассмотрим вершину Ubegin , соответствующую узлу ui , из которой начинается движе- ние. Первым шагом в пути из узла ui может быть: \bullet движение в направлении первого нестандартного положительного шага DF Sk в j вершину UD FS , соответствующую узлу uj = ui + DF Sk , k j \bullet движение в любом направлении \bigtriangleup k в вершину U\bigtriangleup k , соответствующую узлу uj = i u + \bigtriangleup k , i \bullet в вершину Uend для завершения движения. i 2. Рассмотрим вершины UD , соответствующие узлу ui . Из этих вершин возможно FS l j движение в вершины U\bigtriangleup k , соответствующие узлам uj = ui + \bigtriangleup k в направлениях \bigtriangleup k таких, что DF Sl < \bigtriangleup k . i 3. Рассмотрим вершины U\bigtriangleup , соответствующие узлу ui , через который проходят \delta (0) ,...,\bigtriangleup \delta (l) пути с направлениями \bigtriangleup \delta (0) , ..., \bigtriangleup \delta (l) . Из этих вершин возможно движение: j \bullet в вершины U\bigtriangleup \delta (0) ,...,\bigtriangleup \delta (l) ,\bigtriangleup \delta (l+1) , соответствующие узлам uj = ui + \bigtriangleup \delta (l+1) в на- правлениях \bigtriangleup \delta (l+1) таких, что \bigtriangleup \delta (0) , ..., \bigtriangleup \delta (l) , \bigtriangleup \delta (l+1) удовлетворяет правилу с ис- пользованием битов направлений, j \bullet в вершины UD F Sk , соответствующие узлам uj = ui + DF Sk в направлениях DF Sk таких, что \bigtriangleup \delta (0) , ..., \bigtriangleup \delta (l) , DF Sk удовлетворяет правилу порядка направлений, i \bullet в вершину Uend для завершения движения. 4. Рассмотрим вершины UDi , соответствующие узлу ui , через который проходят пути с LSk последними нестандартными отрицательными направлениями DLSk . Из этих вершин возможно движение только в вершину Uend i для завершения движения. На рисунке 1 изображены все вершины графа, соответствующие узлу ui в двухмерной топологии сети. Узлы ua , ub , uc , ud — соседние узлы к узлу ui . Пунктиром обведены вершины графа, которые соответствуют одному узлу сети. На рисунке изображенны только ребра, входящие в вершины графа, которые относятся к узлу ui . . Основной алгоритм 261 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt +x ua b a U FS x U begin Ua U a U a U a +y FS x y x  x y b U FS y b U begin d i u u U i FS y U i y U i  x y i U b x U begin U i ub x U dx b U  yx i U FS x U i y  x i U end U b y U d begin U i x U i LS x U b x  y i i i i U LS y U  x y U  x y U y U b x  y c U c y  x U c x U c x U c x  y U c x  y U begin U FS c x U c y uc Рис. 1. Часть графа на двухмерной топологии. Посчитаем, сколько ребер графа приходится на один набор U i вершин. В первом случае i вершины Ubegin имеют n + 2n + 1 ребер. Во втором случае для каждого DF Sj существует \sum n 2 2n - j вариантов, итого получим (2n - j) = 2n \ast n - (1+n)n 2 = 3n 2 - n ребер. В третьем j=1 i n случае для каждой вершины U\bigtriangleup \delta (0),...,\bigtriangleup \delta j из 3 - 1 вершин будет не больше, чем 2n соседей. В четвертом случае — n ребер. 2 Просуммировав все, получим n+2n+1+ 3n 2 - n +(3n - 1)2n+n = 2n3n +1.5n2 +1.5n+1 = B — оценку числа ребер на каждый узел тора ui . Таким образом, общее количество ребер в графе | E| = O(B| N | ). Утверждение 1. Из узла ui \in N в узел uj \in N существует путь \scrP тогда и только тогда, i j когда в графе G(V, E) существует путь из вершины Ubegin в вершину Uend . Доказательство 1. Для доказательства приведем взаимнооднозначное соответствие меж- ду множеством путей в сети и множеством путей в графе G. Рассмотрим путь: P = ui , DF S , \bigtriangleup \delta (1) , ..., \bigtriangleup \delta (1) , ..., \bigtriangleup \delta (i) , ..., \bigtriangleup \delta (i) , DLS = v j \underbrace{} \underbrace{} \underbrace{} \underbrace{} s\delta (1) >0 s\delta (i) >0 Построим соответствующий путь в графе G: i - 1 \sum \sum i s\delta (j)+2 s\delta (j)+2 i 2+s j j , UF1 S , U\bigtriangleup 2 \delta (1) j=1 j=1 Ubegin \delta (1) , ..., U \bigtriangleup \delta (1) , ..., U \bigtriangleup \delta (1) ,...,\bigtriangleup \delta (i) , ..., U \bigtriangleup \delta (1) ,...,\bigtriangleup \delta (i) , ULS , Uend \underbrace{} \underbrace{} \underbrace{} \underbrace{} s\delta (1) s\delta (i) Аналогичным образом по данному пути в графе G можно построить путь в сети, удовлетво- ряющий правилам маршрутизации. Это соответствие показывает, что существование пути j в сети из ui в uj равносильно существованию пути в графе G из Ubegin i в Uend .\blacksquare Таким образом, задача определения маршрутизируемости множества M \subset N сводится к определению связности множества вершин в графе G, соответствующих узлам множества 262 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt i M . Для этого можно применить метод поиска вширь: для каждой из вершин Ubegin опре- j делим множество достижимых из нее вершин вида Uend . При этом соответствующие узлы j i j i u будут достижимы из u , а u , u и транзитные узлы будут принадлежать M . Алгоритм поиска вширь имеет сложность T = O(V + E) = O(A| M | + B| M | ) = O((A + B)| M | ). Так как алгоритм нужно выполнить для всех M вершин, то T = O((A + B)| M | 2 ). 5.2. Алгоритм выбора подмножеств узлов равномерным расширением Рассмотрим переборный алгоритм решения задачи выбора оптимального подмножества \bigl( m \bigr) узлов в сети с отказами. Всего вариантов расположения m узлов в сети: N nodes . Для проверки маршрутизируемости для каждого набора узлов требуется m 2 операций. Даже \bigl( m \bigr) 2 для небольших систем N nodes \ast m очень велико, эта функция растет очень быстро, поэтому переборный алгоритм не может быть применен на практике. В качесте решения задачи предлагается приближенный алгоритм решения задачи по- линомиальной сложности. Идея алгоритма заключается в том, что из каждого узла тора происходит попытка построить k-мерный прямоугольник поочередным (равномерным) рас- ширением в разные стороны. Ниже алгоритм будет называться алгоритмом равномерного расширения. На вход алгоритму подается размер искомой системы m. Алгоритм состоит из трех этапов: на первом из каждого узла сети производится расширение во все стороны с добав- лением только тех узлов, у которых нет отказавших линков. На втором этапе проводится сортировка полученных систем и удаление одинаковых. На третьем этапе производится расширение получившихся систем с добавлением отказавших линков. Рассмотрим алгоритм подробнее. На первом этапе алгоритм выделяет прямоугольни- ки без сломанных линков. Такие прямоугольники хороши тем, что не требуют проверки множества на маршрутизируемость. Для каждого узла ui сети строится многомерный пря- моугольник следующим образом. Каждый прямоугольник можно задать двумя узлами в противоположных углах: P a и N a. Первоначальный прямоугольник состоит из одной вер- шины: P a = N a = ui . Затем происходят попытки увеличения прямоугольника в каждом направлении по очереди с проверкой, что в захваченной области нет сломанных линков. Расширение прямоугольника происходит путем перемещения одного из его углов в выбран- ном направлении — P a в случае расширения в положительном направлении, N a в случае отрицательного. После каждого расширения происходит проверка числа захваченных уз- лов, если это число больше m, то первый этап завершается. Также первый этап завершается, если отсутствуют направления, в которые можно расширить прямоугольник. На рисунке 2 представлена схема работы первого этапа алгоритма для двухмерного случая. Оценим сложность первого этапа алгоритма. За все время обхода нужно проверить O(2n| M | + | M | ) = O((2n + 1)| M | ) узлов и линков. Этот алгоритм нужно применить ко всем узлам множества N . Получаем следующую оценку сложности: Ts1 = O((2n + 1)| M | | N | ). Для того, чтобы сократить дальнейшую работу, на втором этапе происходит удале- ние одинаковых построенных прямоугольников при помощи предварительной сортиров- ки. Если на втором этапе находятся прямоугольники нужного размера, алгоритм закан- чивается. Так как каждый прямоугольник задается с помощью двух узлов сети, то его можно описать набором 2n чисел. Таким образом, чтобы сравнить все прямоугольники, необходимо O(| N | log2 (| N | )) сравнений. Таким образом, оценка сложности второго этапа Ts2 = O(| N | log2 (| N | )). На третьем этапе происходят попытки расширить полученные прямоугольники в сторо- ны со сломанными линками, на каждом шаге проверяется маршрутизируемость результи- рующего множества узлов. Заметим, чтобы проверить маршрутизируемость нового множе- ства M \prime \prime , которое получится из M путем расширения в выбранном направлении, необходи- мо проверить маршрутизируемость добавленных узлов M \prime со всеми узлами M \prime \prime . Это можно сделать с помощью построенного графа G(V, E). Для этого из каждой вершины множества 263 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt Рис. 2. Схема работы приближенного алгоритма равномерного расширения на примере двухмер- ного тора. M \prime можно пройти поиском вширь по графу G(V, E) и графу GT (V, E), полученному из гра- j фа G(E, V ) путем обращения связей (стартовая вершина теперь будет Uend , а конечная — i i \prime Ubegin ). Таким образом, для каждой вершины u из M можно получить множество узлов uj , для которых существует путь в одну сторону и обратно. Сложность третьего этапа в наихудшем случае можно оценить случаем, когда во всех расширениях прямоугольника присутствовали сломанные линки, а значит для всех узлов множества M пришлось выполнить поиск в ширь по графу G(V, E) и графу GT (V, E) – Ts3 = O(2(A + B)| M | 2 | N | ). Алгоритм равномерного расширения можно оценить как Texpan = Ts1 + Ts2 + Ts3 = O((2n + 1)| M | | N | + | N | log2 | N | + 2(A + B)| M | 2 | N | ) = O((A + B)| M | 2 | N | ), где A = 3n + 2n + 1 и B = 2n3n + 1.5n2 + 1.5n + 1, A + B = (2n + 1)3n + 1.5n2 + 3.5n + 2. Значение констант A и B довольно велико, для сети размерностью n = 4 значение выражения A + B = 769. Однако A + B \leq | N | , поэтому предложенный алгоритм является полиномиальным. В результате работы алгоритма получается набор маршрутизируемых множеств разме- ра больше или равного m. Затем необходимо выбрать оптимальное множество. Для этого необходимо вычислить значение характеристик: диаметра, средней загрузки линков и число транзитных узлов системы и выбрать наилучшее множество путем сортировки сначала по диаметру, затем по средней загруженности и затем по числу транзитных узлов (см. крите- рии выбора в разделе 4 постановки задачи). Алгоритм вычисления средней загруженности линков системы путем построения таблиц маршрутизации представлен в следующем под- разделе. 5.3. Алгоритм построения таблиц маршрутизации Пусть имеется маршрутизируемое множество M \subset N . Требуется найти оптимальную таблицу маршрутизации для узлов множества M и вычислить загруженность каждого лин- ка всех таких узлов M . Допустим, что число путей между двумя узлами ограничено некоторым числом Npaths , (| M | - 1)\ast | M | тогда существует Npaths различных таблиц маршрутизаций. Даже при небольшом числе узлов сети и различных вариантов путей число различных таблиц маршрутизации очень велико, и требуется специальный алгоритм для создания таблиц маршрутизации. Предложен следующий алгоритм построения таблицы маршрутизации. Предположим, что все линки узлов множества M имеют нулевую загруженность. Для каждого узла u 264 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt маршрутизируемого множества M в графе G(V, E) запускается алгоритм поиска вширь. После окончания поиска из каждого узла множества M необходимо подняться по построен- ному дереву обратно вверх к узлу u, увеличивая при этом загруженность Gu,D проходимых линков сети. Эвристически выяснено, что сбалансированная таблица маршрутизации полу- чается, если в качестве следующего узла для запуска поиска вширь выбирать максимально удаленным от узла u. Вторая эвристика, введенная для получения более равномерной за- грузки линков, заключается в сортировке вершин на каждом новом слое поиска вширь по возрастанию загруженности линков, соответствующих вершинам. \sum l Сортировку слоев в алгоритме можно оценить как O( (| Vi | log2 | Vi | )) = i=1 \sum l = O( (| Vi | log2 | V | )) = O(| V | log2 | V | ), где l — число слоев в алгоритме, Vi — множество i=1 вершин на каждом слое. Сложность одного прохода этого алгоритма можно оценить как сумму трех слагаемых: T1 = O((A + B)| M | 2 ) для поиска вширь в графе G(V, E), T2 = O(| V | log2 | V | ) — сортировка узлов на каждом шаге поиска, T3 = O(Lmax | M | ) — вычисление загруженности линков. В худшем случае таблицы маршрутизации нужно построить для каждой системы, по- строенной алгоритмом равномерного расширения из каждого узла сети. Поэтому итоговая сложность постройки таблиц маршрутизации для всех систем составляет TR = | N | \ast (T1 + T2 + T3 ) = O((A + B)| M | 2 | N | ). Заметим, что алгоритм построения таблиц маршрутизации имеет такую же сложность, как и алгоритм равномерного расширения. 5.4. Алгоритм решения задачи в сети без отказов Для того, чтобы оценивать качество работы разработанного приближенного алгоритма равномерного расширения, проводилось сравнение с алгоритмом решения задачи выбора оптимального маршрутизируемого множества в сети без отказов, работающего по принципу факторизации. Алгоритм выбора оптимального множества узлов в сети без отказов устроен следующим образом. Для системы размера m строятся всевозможные разложения чисел m, m+1, ..., | N | на n натуральных множителей k1 , ..., kn таких, что \forall i, ki \leq di , которые характеризуют прямоугольную область. Эта область является одним из решений задачи. Для всех таких решений ищется система с минимальным диаметром. Дополнительно рассчитывается загру- женность линков при помощи алгоритма построения таблиц маршрутизации в подразделе 5.3, а также количество транзитных узлов. Алгоритм факторизации решения задачи в сети без отказов используется в данный момент в системном ПО на кластере с сетью Ангара. 6. Исследование Исследование качества разработанного приближенного алгоритма выбора оптимально- го подмножества узлов в сети с отказами можно провести следующим образом. Сначала с помощью сравнения результатов работы разработанного алгоритма с алгоритмом выбо- ра узлов в сети без отказов проводится оценка качества нового алгоритма в том случае, для которого известен другой алгоритм решения задачи. Затем проводится исследование результатов работы нового алгоритма в сети с отказами в зависимости от размера искомой системы и количества сломанных линков. Исследование разработанного алгоритма проводилось на равносторонних трехмерных торах: 5x5x5, 7x7x7 и 9x9x9. На рисунке 3 представлены характеристики систем, полученных с помощью алгорит- ма выбора подмножества узлов в сети без отказов (алгоритм факторизации) и алгоритма равномерного расширения в зависимости от размера сети и размера искомой системы. По 265 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt диаметру и средней загруженности линка на алгоритме равномерного расширения полу- чены значения, немного уступающии алгоритму факторизации, а число транзитных узлов для алгоритма равномерного расширения значительно лучше. Так как алгоритм равномер- ного расширения более общий по сравнению с алгоритмом факторизации, то полученные незначительные ухудшения характеристик являются допустимыми. 70 300 диаметер, Факторизация диаметер, Факторизация 60 диаметер, Расширение диаметер, Расширение транз.уз, Факторизация 250 транз.уз, Факторизация транз.уз., Расширение транз.уз., Расширение Абсолютное значение хар-ик. Абсолютное значение хар-ик. 50 ср. загр., Факторизация ср. загр., Факторизация ср. загр., Расширение 200 ср. загр., Расширение 40 150 30 100 20 50 10 0 0 20 30 40 50 60 70 80 90 100 57 107 157 207 257 Размер искомой системы Размер искомой системы (a) Топология сети 5х5х5 (b) Топология сети 7х7х7 800 диаметер, Факторизация 700 диаметер, Расширение транз.уз, Факторизация 600 транз.уз., Расширение Абсолютное значение хар-ик. ср. загр., Факторизация ср. загр., Расширение 500 400 300 200 100 0 121 171 221 271 321 371 421 471 521 571 Размер искомой системы (c) Топология сети 9х9х9 Рис. 3. Значение характеристик решения задачи в зависимости от размера искомой системы. Исследование алгоритма равномерного расширения проводилось в сети с топологией 7х7х7 (число узлов Nnodes = 343) с отказами. Сломанные линки выбирались случайным об- разом. Число сломанных линков изменялось в диапазоне 5, 10, 15, ..., 195. Размеры искомых систем (параметр m) выбирались 16 Nnodes , 26 Nnodes , ..., 56 Nnodes . На рисунке 4 представлено значение отношения (c - cmin )/(cmax - cmin ) (в процентах), характеризующее достижение какой-то характеристикой ее минимального значения, где c, cmin и cmax — выбранное, минимально и максимально полученное значение алгоритмом равномерного расширения одной из рассматриваемых характеристик c (диаметр, количе- ство транзитных узлов и средняя загруженность линков). По графикам можно видеть, что выбранный результат минимизирует рассматриваемые характеристики во многих случа- ях. Приближение к максимальным значениям в некоторых случаях объясняется тем, при отборе решений происходит сортировка сначала по диаметру, затем по значениям средней загруженности линков и затем по количеству транзитных узлов. Таким образом, выбрав все системы с минимальным диаметром, возможно получить не минимальное число транзитных узлов. Для искомой системы из 228 узлов все три характеристики хорошо минимизируют- 266 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt 100 100 90 90 %, достижение мин. хар-ик. %, достижение мин. хар-ик. 80 80 70 70 60 60 50 50 40 40 30 30 20 20 10 10 0 0 0 25 50 75 100 125 150 175 0 10 20 30 40 50 60 70 80 90 100 Число сломанных линков Число сломанных линков диаметер ср. загр. транз. уз. диаметер ср. загр. транз. уз. (a) Размер искомой системы 57 (b) Размер искомой системы 114 100 100 90 90 %, достижение мин. хар-ик. %, достижение мин. хар-ик. 80 80 70 70 60 60 50 50 40 40 30 30 20 20 10 10 0 0 0 10 20 30 40 50 0 5 10 15 20 25 30 35 40 45 Число сломанных линков Число сломанных линков диаметер ср. загр. транз. уз. диаметер ср. загр. транз. уз. (c) Размер искомой системы 171 (d) Размер искомой системы 228 Рис. 4. Оценка приближения значений характеристик (диаметра системы, средней загруженности линка и количества транзитных узлов) к наилучшим известным значениям в зависимости от числа сломанных линков для сети с топологией 7х7х7 и разных размеров искомой системы. ся из-за небольшого общего количества найденных решений, что связано с отсутствием связности искомой системы при случайных отказах. Время выполнения алгоритма на системе размера 5х5х5 составило 0.01 с — 0.1 с в зави- симости от числа сломанных линков и размера искомой системы. Данное время приемлемо при выборе свободных узлов во время запуска задачи. На системах размера 7x7x7 и 9х9х9 время выполнения довольно велико: 0.7 c — 3 c и 7 с — 30 с соответственно. Планируется несколько путей решения этой проблемы. Во-первых, алгоритм можно оптимизировать в нескольких направлениях, например, нет необходимости искать все системы в малозагру- женной сети; также возможно применение различных эвристик для сокращения перебора. Во-вторых, реализацию алгоритма можно оптимизировать и распараллелить с использова- нием технологии OpenMP. Заключение В данной работе описан полиномиальный алгоритм построения маршрутизируемого подмножества узлов заданного размера в сети с отказами и проведено предварительное исследование. Алгоритм показал результаты, близкие к результатам алгоритма поиска маршрутизи- руемых систем в сети без занятых или отказавших узлов. Предварительное исследование результатов работы алгоритма показало, что требуется доработка алгоритма для улучше- ния качества результатов и увеличения скорости его работы. В будущих работах планируется оптимизировать алгоритм и выполнить более подроб- ное исследование. Литература 1. Корж А.А., Макагон Д.В., Жабин И.А., Сыромятников Е.Л. Отечественная коммуникационная сеть 3D-тор с поддержкой глобально адресуемой памяти для 267 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt суперкомпьютеров транспетафлопсного уровня производительности // Параллельные вычислительные технологии (ПаВТ’2010): Труды международной конференции (Уфа, 29 марта 2 апреля 2010 г.). Челябинск: Издательский центр ЮУрГУ, 2010. С. 227–237. 2. Жабин И., Макагон Д., Симонов А. и др. Кристалл для Ангары // Суперкомпьютеры. — 2013. — Т. зима-2013. — С. 46–49. 3. Пожилов И.А., Семенов А.С., Макагон Д.В. Алгоритм определения связности сети с топологией "многомерный тор"с отказами для детерминированной маршрутизации // Программная инженерия. — 2015. — № 3. — С. 13–19. 4. 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,"// Parallel Processing, 1999. Proceedings. 1999 International Conference on , vol., no., pp.58,67, 1999. 5. Adiga N.R., Blumrich M., Chen D. et al. Blue Gene/L torus interconnection network // IBM Journal of Research and Development. 2005. — Vol. 49, no. 2.3. — P. 265–276. 6. Scott S.L., et al. The Cray T3E Network: Adaptive Routing in a High // Performance 3D Torus. — 1996. 268 Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016) agora.guru.ru/pavt Approximate algorithm for choosing the best subset of nodes in the «Angara» interconnect with failures A.V. Mukosey, A.S. Semenov, D.V. Makagon JSC «NICEVT» (Moscow) JSC NICEVT develops the Angara high-speed interconnect with multi-dimensional torus topology. In actual use of the "Angara"interconnect in the conditions of employment and the availability of the failed nodes arises the problem of finding an optimal nodes subset to cover a given number of nodes thus all network traffic is lying within the subset of nodes. This paper presents an approximation algorithm for solving this problem. Keywords: Fault tolerance, communication networks, multidimensional torus, connectivity, deterministic routing, direction ordered routing. References 1. Korzh A.A., Makagon D.V., Zhabin I.A., Syromyatnikov E.L. Otechestvennaya kommunikatsionnaya set’ 3D-tor s podderzhkoy global’no adresuyemoy pamyati dlya superkomp’yuterov transpetaflopsnogo urovnya proizvoditel’nosti [Russian 3D-torus Interconnect with Support of Global Address Space Memory]. Parallelnye vychislitelnye tekhnologii (PaVT’2010): Trudy mezhdunarodnoj nauchnoj konferentsii (Ufa, 29 marta – 2 aprelya 2010) [Parallel Computational Technologies (PCT’2010): Proceedings of the International Scientific Conference (Ufa, Russia, March, 29 – April, 2, 2010)]. Chelyabinsk, Publishing of the South Ural State University, 2010. P. 527–237. 2. Zhabin, I.A. Kristall dlya Angary [Angara Chip] / I.A. Zhabin, D.V. Makagon, A.S. Simonov // Superkomp’yutery [Supercomputers]. —Winter-2013. — P. 46–49. 3. Pozhilov I.A., Semenov A.S., Makagon D.V. Algoritm opredeleniya svyaznosti seti s topologiyey "mnogomernyy tor"s otkazami dlya determinirovannoy marshrutizatsii [Connectivity problem solution for direction ordered deterministic routing in nD torus]. // Software Engineering. — 2015. — № 3. — С. 13–19. 4. 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,"// Parallel Processing, 1999. Proceedings. 1999 International Conference on , vol., no., pp.58,67, 1999. 5. Adiga N.R., Blumrich M., Chen D. et al. Blue Gene/L torus interconnection network // IBM Journal of Research and Development. 2005. — Vol. 49, no. 2.3. — P. 265–276. 6. Scott S.L., et al. The Cray T3E Network: Adaptive Routing in a High // Performance 3D Torus. — 1996. 269