Рассматривается метод изменения топологии 2-шаговой системной сети «сплющенная бабочка» (Flattened Butterfly), обеспечивающий уменьшение размеров составляющих ее коммутаторов и, как следствие, уменьшение схемной сложности и энергопотребления при сохранении числа абонентов (процессоров), диаметра сети и коммутационных свойств. При сохранении размеров коммутаторов предлагаемый метод позволяет существенно увеличить число абонентов при сохранении диаметра сети.
P P
P P P P P P
S
S P P
S
S P P
P P P
P Рис.1. Исходная сеть FB2 при k=4 (N=16 и m=7). В результате мы приходим к следующей постановке задачи для сети FB2, как сети с наименьшим диаметром. Практически не изменяя число абонентов сети N, число каналов R и диаметр D требуется уменьшить сложность S и энергопотребление W сети за счет изменения ее топологии, при котором имеет место уменьшение числа портов отдельных коммутаторов.
Возможность такой постановки задачи открывает разработка [3, 4] сетей с прямыми каналами, имеющих топологию квазиполных графов и орграфов, которые позволяют эффективно заменять в топологии сети полный граф c числом узлов N=k на квазиполный граф с числом узлов N*=k*(k*–1)/+1 (где – число независимых прямых каналов между любыми двумя узлами) или квазиполный орграф с N*=(k*)2 (только с одним прямым каналом =1). В случае N=N* это приводит к уменьшению степени узлов от k до k* (m)1/2. При схемной реализации степень узла задает число его портов.
Обоснованность такой постановки подтверждается тем, что сеть с топологией квазиполного графа или орграфа является неблокируемой при самомаршрутизации пакетов каждым источником. Это означает, что она равномощна сети с топологией полного графа на произвольных перестановках пакетов и близка к ней на случайном равномерном трафике между абонентами [5]. Последний вид трафика и имеет место между коммутаторами в FB2.
Дело в том, что сеть FBn наследует коммутационные свойства сети n-каскадная k-ичная бабочка. Поэтому сеть FBn не является ни неблокируемой ни даже перестраиваемой и имеет только один путь между любыми двумя процессорами. Для преодоления этого недостатка приходится использовать специальные алгоритмы маршрутизации, которые и приводят к равномерной рандомизации трафика между коммутаторами. Эти алгоритмы снижают пропускную способность сети до двух раз или аналогично повышают ее эффективный диаметр (реальные задержки передачи) [1]. 2. Квазиполные графы и орграфы
Квазиполный граф QFG(M*,k*,*) – это однородный двудольный граф, каждую долю
которого составляют M* узлов степени k*. Значение k* выбирается минимальным, при котором
любые два узла в одной доле связаны * ≤ k* прямыми путями длины 2 через разные узлы в
другой доле. Если такой граф существует, то его параметры связаны соотношением M*=k*(k*–
1)/*+1. На рис. 2 представлена сеть с топологией квазиполного графа QFG(
Рис. 2. Сеть с топологией квазиполного графа QFG(
Квазиполные графы изоморфны симметричным блок-схемам, исследуемым в комбинаторике [3, 4]. Их построение сводится к построению соответствующих блок-схем, и осуществляется обычно комбинаторными методами, которые являются NP-сложными по k*.
При схемной реализации узлы одной доли – это абоненты с k* дуплексными портами, а
узлы другой доли – это полные коммутаторы k*×k* с k* дуплексными портами. Таблицей
инцидентности квазиполного графа является симметричная блок-схема B(M*,k*,*), которая
представлена в табл. 1 для графа QFG(
Эта таблица задает схему межсоединений узлов разных долей в сети. Первая колонка в ней задает коммутаторы, а строки – подсоединенных к ним абонентов, задаваемых номерами в ячейках.
Нахождение прямого пути между любыми двумя абонентами сводится к нахождению номеров выходных портов абонентов и коммутаторов, однозначно задающих этот путь. А S1 P1
S2 P2
S3 P3
S5 P5
S6 P6
S7
P7 S4 P4 прокладка прямого канала – это просто передача короткого пакета-зонда по выбранному пути с подтверждением его приема.
Таблица 1. Межсоединения в QFG(
B(
QFG(
Квазиполный орграф определяется только при *=1 и для направленных дуг. Квазиполный орграф QFDG(M*,k*) – это однородный двудольный граф, каждую долю которого составляют M* узлов степени k*. Значение k* выбирается минимальным, при котором любые два узла в одной доле связаны прямыми путями длины 2 через разные узлы в другой доле. Таблица 2. Таблица межсоединений в квазиполном орграфе по рис. 3 Дуги от абонентов Дуги к абонентам Рис. 4. Квазиполный орграф QFDG(9, 3), полученный из 2-мерного 3-ичного обобщенного гиперкуба. Таблица 3. Таблица межсоединений в квазиполном орграфе по рис. « Дуги от абонентов Дуги к абонентам 3. Предлагаемое решение
Сначала рассмотрим вариант изменения топологии для сети FB2, сложность и энергопотребление которой составляет величины S=3bN3/2 и W=3cN3/2. Для этого расширим FB2, заменив в ней полный граф на квазиполный граф или орграф, в котором расширенные коммутаторы FB2 являются абонентами (рис. 5). Расширенную сеть FB2 будем обозначать как ЕB2.
1 1 1 2 3 1 2 3 1 2 3 7 7 P P P P
P P 4. Сплющивание обобщенной сети
Обобщенными мы называем сложенные многокаскадные сети, в которых межкаскадные соединения имеют топологию квазиполного графа или орграфа [9]. В частности, 2-каскадная обобщенная сеть получается из квазиполного графа или орграфа по рис. 2–4 заменой каждого абонента на дуплексный коммутатор k*×k* (коммутатор ВВ), каждого узла другой доли – на коммутатор k*×k* (коммутатор хребта), а ребра – на дуплексные каналы для графа или пары симплексных каналов для орграфа. Такая сеть объединяет N*=k*[k*(k*–1)/+1] абонентов, если она получена из квазиполного графа, и N*=(k*)3 абонентов, если она получена из квазиполного орграфа.
При сплющивании 2-каскадной обобщенной сети одноименные коммутаторы ВВ и хребта объединяются в один расширенный коммутатор с m*=2k*–1 дуплексными портами. Такая сплющенная сеть состоит из M*=N*/k* расширенных коммутаторов, любые два из которых связаны 2(k*–1) парами симплексных каналов, использует R*=2M*(k*–1) таких пар каналов и имеет диаметр D*=3. Обозначим такую сплющенную обобщенную сеть как FG2.
При использовании топологии квазиполного орграфа сложность сети FG2 задается выражением S*=4b(k*)4=4b(N*)4/3. FG2, как и сеть FB2, не является перестраиваемой и имеет только один путь между любыми двумя абонентами. Отношение сложностей FB2 и FG2 при N N* задается выражением S/S*=3bN1/6/4. т.е. таким же соотношением как и для FB2 и EB2 в предыдущем параграфе. Число сетевых портов составного коммутатора в FB2 задается величиной r=k–1=N1/2–1, а в FG2 – величиной r*=2(k*–1)=2(N1/3–1).
Энергопотребление сетей FB2 и FG2 при одинаковом числе абонентов N=1024N*=1000 имеем k=32, k*=10 и W/W* 2,5. При этом В сети FB2 используется R=k(k–1)=992 дуплексных каналов (1984 симплексных каналов). В сети FG2 используется R*=2(k*)2(k*–1)=1800 пар симплексных каналов, т.е. почти в два раза больше, чем в сетях FB2 и EB2. При этом каждый составной коммутатор в FB2 имеет r=31 сетевых портов, а в FG2 – только r*=20 сетевых портов.
В табл. 4 сравниваются характеристики сетей FB2 и FG2 при одинаковых размерах расширенных коммутаторов. Видно, что FG2 имеет в несколько раз большее число абонентов при меньшей удельной схемной сложности.
Таблица 4. Сравнительные характеристики сетей FB2 и FG2 для квазиполного орграфа (K=1024) FB2 m k N M R/N S/N FG2 m* k* N* M* R*/N* S*/N* FB2 16 K/4 16 0,94 48b
31 FG2 11 1,3K 121 1,82 44b FB2 24 0,56K 24 0,96 72b
47 FG2 16 4K 256 1,88 64b FB2 32 K 32 0,97 96b
63
FG2 22 10,4K 484 1,81 88b В случае использования топологии квазиполного графа в сети появляется возможность иметь несколько прямых каналов через разные вторичные коммутаторы. Для этого в абоненты одного расширенного коммутатора должны связываться с друг другом только через другие расширенные коммутаторы. При этом s=3bk2. В частности, для FB2 с N=1024 в FG2 c *=2 можно выбрать k*=13 и получить M*=79, N*=1027 и W*=c3M*132. Поэтому W/W* 2,4 и R*=2M*(k*–1)=1896 пар симплексных каналов, т.е. R*1,91R. Здесь опять в FB2 r=31, а в FG2 только r*=24.
В табл. 5 сравниваются характеристики сетей FB2 и FG2 при одинаковых размерах расширенных коммутаторов. Видно, что FG2 имеет в несколько раз большее число абонентов, в полтора раза меньшую удельную сложность и повышенную канальную отказоустойчивость и/или пропускную способность. Таблица 5. Сравнительные характеристики сетей FB2 и FG2 для топологии квазиполного графа (K=1024) 5. Заключение
Предложена модификация сети FB2 в расширенную сеть EFB2, которая состоит в замене топологии полного графа на топологию квазиполного графа или орграфа, осуществляемая за счет введения промежуточного слоя малых коммутаторов. Она может осуществляться без изменения числа абонентов (процессоров), диаметра сети и числа используемых каналов, и обеспечивать более чем трехкратное снижение энергопотребления сети. Эта модификация позволяет многократно увеличить число абонентов при использовании коммутаторов одинакового размера без увеличения удельного энергопотребления.
Предложена новая сплющенная сеть FG2, полученная из 2-каскадной обобщенной сети, имеющая характеристики сети EFB2. Накладными расходами при этом является двукратное увеличение удельного числа проводов.
Рассмотрен отдельный вариант сети FG2, полученный сплющиванием нового вида неблокируемой сети – сеть FN2. Она является неблокируемой сетью и имеет примерно равное удельное энергопотребление и меньшие задержки передачи. Сеть FN2 требует дальнейшего исследования. Литература 1. Kim J., Dally W. J., and Abts D. Flattened Butterfly: A Cost-Efficiently Topology for High-Radix Networks // URL: http://www.cs.berkeley.edu/~kubitron/courses/cs258
S08/handouts/papers/ISCA_FBFLY.pdf. 2. Корж А.А. Инновационная платформа А-Class для создания мультипетафлопсных систем // Международная суперкомпьютерная конференция «Научный сервис в сети Интернет: многообразие суперкомпьютерных миров». Новороссийск. 2014. Пленарный доклад. Устное сообщение. 3. Каравай М.Ф., Подлазов В.С. Метод инвариантного расширения системных сетей многопроцессорных вычислительных систем. Идеальная системная сеть. // АиТ. 2010. № 10. С. 166–176. Topology reserves of flattened system networks Viktor Podlazov and Michail Karavay Keywords: Supercomputer interconnect, Flattened butterfly, Flattened system area networks, Hardware complexity, Power consuming, Number of network nodes A method of modification the topology of double-hop system network type of Flattened Batterfly is considered. The method ensures diminution of component commutator sizes and as a consequence of that feature decrease in hardware complexity and power consuming, preserving number of network nodes (processors), network diameter and functional characteristics. In case of retain the original component commutator size the method gives a possibility to enhance number of network nodes dramatically with preservation of network diameter