В АО «НИЦЭВТ» разрабатывается высокоскоростная коммуникационная сеть Ангара с топологией «многомерный тор». При реальном использовании суперкомпьютера с сетью Ангара в условиях наличия занятых и отказавших узлов возникает задача нахождения оптимального подмножества узлов сети для покрытия заданного числа узлов так, чтобы весь сетевой трафик лежал только внутри этого подмножества узлов. В данной работе представлен приближенный полиномиальный алгоритм решения такой задачи. Ключевые слова: Отказоустойчивость, коммуникационные сети, многомерный тор, связность, детерминированная маршрутизация, маршрутизация с порядком направлений.
agora.guru.ru/pavt 2. Определения
В данном разделе вводятся некоторые формальные определения, которые в дальнейшем будут использоваться в статье. 1) mod dj, ..., un) для любого индекса 1 \leq j \leq
Рассмотрим коммуникационную сеть с топологией многомерный тор. Множество всех узлов сети обозначим N , размерности тора обозначим (d1, d2, ..., dn), а общее число узлов рамках тороидальной топологии будем называть узлы u = (u1, u2, ..., un) и u\~ = (u1, ..., (uj \pm
, ..., 0) \in \scrD , b\igtranleup i < \bigtranleup j, если i < j. 3. Маршрутизация в сети Ангара 3.1. Правило порядка направлений с использование битов направлений Среди алгоритмов маршрутизации для многомерных торов можно выделить класс алгоритмов, соблюдающих правило порядка направлений: маршрут между любой парой узлов включает движения в направлениях в определенном, заранее заданном, порядке. Эти алгоритмы обладают свойством отсутствия взаимных блокировок между кольцами нескольких измерений тора при любом количестве одновременных запросов на передачу данных по сети.
Во введенных обозначениях правило порядка направлений будет формулироваться следующим образом: Dj- 1 \leq Dj, j = 2, N , где N — длина пути.
Чтобы задать путь, удовлетворяющий правилу порядка направлений, необходимо
задать стартовую вершину и количество шагов в каждом из направлений, т.е. набор
u0, s\delta (
В сети Ангара реализована маршрутизация с использованием битов направлений,
которая вносит некоторые ограничения на маршрутизацию с правилом порядка направлений.
Аналогично правилу порядка направлений для задания пути, соответствующему
маршрутизации с использованием битов направлений, необходимо задать стартовую вершину и
количество шагов в выбранных направлениях, то есть следующий набор: u0, s\delta (
Метод First Step/Last Step [6] используется в сети Ангара как механизм обхода отказавших узлов. Он расширяет маршрутизацию с использованием битов направлений путем добавления первого и последнего нестандартного шага.
Путь с использованием первого и последнего нестандартного шага будет записываться следующим образом: u0, DF S, Pdirbit, DLS, где u0 — стартовый узел, DF S — первое положительное нестандартное направление, DLS — последнее отрицательное нестандартное направление. При этом набор направлений DF S, Ddirbit, DLS удовлетворяет правилу порядка направлений.
Таким образом, для однозначного задания пути в сети Ангара необходимо задать набор DF S, Pdirbit, DLS. 4. Постановка задачи
Во время работы разделяемого вычислительного кластера необходимо при любом состоянии системы уметь предоставлять требуемое число узлов, которые должны быть маршрутизируемы между собой и не иметь транзитного трафика вне этого набора узлов, если это возможно. Состояние системы определяется набором отказавших линков и/или узлов и наличием занятых узлов. Занятый или отказавший узел можно интерпретировать как узел, у которого линки сломаны во всех направлениях.
Обозначим множество сломанных линков F \subet s\crE .
Так как физический канал связи между двумя узлами v и u представляет собой линки от узла v к узлу u и наоборот, то разумно предположить, что при неисправности одного из линков — второй так же неисправен. Таким образом, множество F будет включать в себя отказавшие каналы связи попарно.
Во введенных определениях задача будет формулироваться следующим образом. Пусть задан тор 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).
При построении маршрута между двумя узлами ограничение на принятие решения
о следующем шаге вносит предыстория пути. Рассмотрим движение по некоторому пути
в торе в направлениях: \bigtranleup d\elta (
Поэтому для описания вычислительного узла ui в графе построим множество U i вершин, которые будут характеризовать предысторию путей, которые проходят через вычислительный узел ui: 1. U DiFSj , j = 1, .., n — вершины, в которые возможно попасть, совершив первый нестандартный положительный шаг из соседнего узла в направлении DF Sj ; 2. U DiLSj , j = n + 1, .., 2n — вершины, в которые возможно попасть, совершив последний нестандартный отрицательный шаг из соседнего узла в направлении DF Sj ; 3. U Didirbitj , Ddirbitj \in Ddirbit — всевозможные наборы направлений, удовлетворяющие правилу с использованием битов направлений, за исключением набора с отсутствием agora.guru.ru/pavt 5.2. Алгоритм выбора подмножеств узлов равномерным расширением Рассмотрим переборный алгоритм решения задачи выбора оптимального подмножества Ts2 = O(| N | log2(| N | )). Рис. 2. Схема работы приближенного алгоритма равномерного расширения на примере двухмерного тора.
M \prime можно пройти поиском вширь по графу G(V, E) и графу GT (V, E), полученному из графа G(E, V ) путем обращения связей (стартовая вершина теперь будет Uejnd, а конечная — Ubiegin). Таким образом, для каждой вершины ui из M \prime можно получить множество узлов uj, для которых существует путь в одну сторону и обратно.
Сложность третьего этапа в наихудшем случае можно оценить случаем, когда во всех расширениях прямоугольника присутствовали сломанные линки, а значит для всех узлов множества M пришлось выполнить поиск в ширь по графу G(V, E) и графу GT (V, E) – Ts3 = O(2(A + B)| M | 2| N | ).
Алгоритм равномерного расширения можно оценить как Texpan = Ts1 + Ts2 + Ts3 = | + | N | log2| N | + 2(A + B)| M | 2| N | ) = O((A + B)| M | 2| N | ), где A = 3n + 2n + 1 иO(B(2=n +2n13)n|M+| 1N.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 \subet N . Требуется найти оптимальную таблицу маршрутизации для узлов множества M и вычислить загруженность каждого линка всех таких узлов M .
Допустим, что число путей между двумя узлами ограничено некоторым числом Npaths, тогда существует Np(a|Mth|-s 1)\ast| M| различных таблиц маршрутизаций. Даже при небольшом числе узлов сети и различных вариантов путей число различных таблиц маршрутизации очень велико, и требуется специальный алгоритм для создания таблиц маршрутизации.
Предложен следующий алгоритм построения таблицы маршрутизации. Предположим, что все линки узлов множества M имеют нулевую загруженность. Для каждого узла u маршрутизируемого множества M в графе G(V, E) запускается алгоритм поиска вширь. После окончания поиска из каждого узла множества M необходимо подняться по построенному дереву обратно вверх к узлу u, увеличивая при этом загруженность Gu,D проходимых линков сети. Эвристически выяснено, что сбалансированная таблица маршрутизации получается, если в качестве следующего узла для запуска поиска вширь выбирать максимально удаленным от узла u. Вторая эвристика, введенная для получения более равномерной загрузки линков, заключается в сортировке вершин на каждом новом слое поиска вширь по возрастанию загруженности линков, соответствующих вершинам. l Сортировку слоев в алгоритме можно оценить как O(\sum (| Vi| log2| Vi| )) = i=1 l = O(\sum (| 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 таких, что \foral i, ki \leq di, которые характеризуют прямоугольную область. Эта область является одним из решений задачи. Для всех таких решений ищется система с минимальным диаметром. Дополнительно рассчитывается загруженность линков при помощи алгоритма построения таблиц маршрутизации в подразделе 5.3, а также количество транзитных узлов.
Алгоритм факторизации решения задачи в сети без отказов используется в данный момент в системном ПО на кластере с сетью Ангара. 6. Исследование
Исследование качества разработанного приближенного алгоритма выбора оптимального подмножества узлов в сети с отказами можно провести следующим образом. Сначала с помощью сравнения результатов работы разработанного алгоритма с алгоритмом выбора узлов в сети без отказов проводится оценка качества нового алгоритма в том случае, для которого известен другой алгоритм решения задачи. Затем проводится исследование результатов работы нового алгоритма в сети с отказами в зависимости от размера искомой системы и количества сломанных линков.
Исследование разработанного алгоритма проводилось на равносторонних трехмерных торах: 5x5x5, 7x7x7 и 9x9x9.
На рисунке 3 представлены характеристики систем, полученных с помощью алгоритма выбора подмножества узлов в сети без отказов (алгоритм факторизации) и алгоритма равномерного расширения в зависимости от размера сети и размера искомой системы. По 250 . к и -р200 а х е и ен150 ч а н з ео100 н т ю л со50 б А 0 100 .-ки 8900 ар 70 .х 60 ни 50 м 40 еи 30 не 20 иж 10 тс 0 о ,д 0 % 25 50 75 100 125 150
Число сломанных линков диаметер ср. загр. транз. уз. (a) Размер искомой системы 57 175
В данной работе описан полиномиальный алгоритм построения маршрутизируемого подмножества узлов заданного размера в сети с отказами и проведено предварительное исследование.
Алгоритм показал результаты, близкие к результатам алгоритма поиска маршрутизируемых систем в сети без занятых или отказавших узлов. Предварительное исследование результатов работы алгоритма показало, что требуется доработка алгоритма для улучшения качества результатов и увеличения скорости его работы.
В будущих работах планируется оптимизировать алгоритм и выполнить более подробное исследование. Литература 1. Корж А.А., Макагон Д.В., Жабин И.А., Сыромятников Е.Л. Отечественная коммуникационная сеть 3D-тор с поддержкой глобально адресуемой памяти для суперкомпьютеров транспетафлопсного уровня производительности // Параллельные вычислительные технологии (ПаВТ’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. Approximate algorithm for choosing the best subset of nodes in the «Angara» interconnect with failures
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 trafic 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.