Автоматика и телемеханика, № 10, 2014
Безопасность, живучесть, надежность,
техническая диагностика
( 2014 г. В.С. ПОДЛАЗОВ, д-р техн. наук (podlazov@ipu.ru) (Институт проблем управления им. В.А. Трапезникова РАН, Москва)
НОВЫЙ ВИД НЕБЛОКИРУЕМОЙ СЕТИ
Сравниваются характеристики сложенных перестраиваемых и небло-кируемых сетей Клоза, полученные имитационным моделированием. Рассматриваются новые виды неблокируемых сетей - обобщённая и остаточная обобщённая сети Клоза. Сравниваются характеристики всех этих сетей.
1. Введение
Многокаскадная сеть Клоза широко применяется для построения параллельных многопроцессорных вычислительных систем (МВС) [1]. На рис. 1 показана базовая сеть Клоза [2] на R портов, в которой используются однонаправленные коммутаторы с симплексными портами. Сеть имеет три каскада полных коммутаторов r х m, m х r (1-й и 3-й каскады) и r х r (2-й каскад - хребет), полностью задается параметрами m, r (R = mr) и является перестраиваемой при m = r и неблокируемой при m ^ 2r — 1.
Многокаскадная сеть Клоза с t = 2k + 1 каскадами строится рекурсивно в предположении, что второй каскад состоит из m сетей Клоза с 2k — 1 каскадами.
Перестраиваемая сеть Клоза имеет отдельное бесконфликтное расписание для любой перестановки данных между входными и выходными портами, которое в общем случае неизвестно, и требуется выполнение отдельной процедуры для построения такого расписания. Сеть имеет Rt = rk+1 портов при использовании коммутаторов r х r (с r входными и r выходными портами) в каждом каскаде. Сложность коммутатора r х r будем обозначать как Обычно для оценок считается, что ^ = r2 точек коммутации Перестраивае-
-t о -t kv. j--n(k+1)/(k+2)
мая сеть, состоящая из t каскадов, имеет сложность = trkN = tR\ точек коммутации, которая определяет энергопотребление сети. Построение расписания для перестраиваемой сети занимает много больше времени, чем передача пакета данных, поэтому на практике оно не используется, а используется самомаршрутизация с равномерным рандомизированным распределением пакетов по каналам первых k каскадов.
Если базовый коммутатор перестраиваемой сети Клоза имеет размеры 2 х 2 (r = 2), то образуется перестраиваемая сеть Бенеша, которая за
г х т г х г т х г
Рис. 1. Базовая трехкаскадная сеть Клоза.
г х г г х г
Рис. 2. Сложенная двухкаскадная перестраиваемая сеть Клоза - СПСК2(Й2,г).
счет d-кратного мультиплицирования коммутаторов и использования соответствующего алгоритма динамической самомаршрутизации может быть (см. [3]) превращена в неблокируемую сеть. Однако такая сеть мало пригодна для практических применений из-за сравнительно большой глубины сети 2 log2 N каскадов) и, как следствие, большого времени установления соединения и большого расхода кабелей. Современные тенденции требуют построения системных сетей с малой глубиной за счет использования коммутаторных сверхбольших интегральных схем (СБИС) максимально больших размеров. Так, МВС Black Widow [1]строится на основе перестраиваемой сети Клоза, в которой используется самая большая известная авторам СБИС полного коммутатора YARC 64 х 64.
На практике перестраиваемая сеть Клоза используется в виде сложенной сети, в которой одноименные коммутаторы i-го и (t — i + 1)-го каскадов выполняются в виде одного каскада из r коммутаторов (r/2) х (r/2) с r дуплексными портами, а в качестве коммутаторов центрального каскада (хребта) используются r/2 коммутаторов r х r c r дуплексными портами. В этом случае число каскадов t определяется как t = к + 1, а сеть обозначается СПС^^^г). Сложность каскадных и хребтовых коммутаторов одинакова и составляет ^ = r2. В этой сети число портов Rt = r*(1/2)i-1 и сложность St = N(2t — 1)(1/2)t-1 rt-1 = (2t — 1)(1/2)t—1 rt+1. На рис. 2 представлена сложенная двухкаскадная перестраиваемая сеть Клоза СПСК2^2,г). В ней удельная (на одного абонента) сложность ö2 составляет ö2 = S2/R2 = 3r. В многокаскадном случае öt = St/Rt = (2t — 1)r.
Рандомизированная самомаршрутизация пакетов и в такой сети не исключает возникновение конфликтов и, как следствие, потерю пропускной способности и увеличение задержек передачи.
К2 - г-
1 1 1 1
ч2г г/
... К2 = г2, Я2 = бг3, 52 = 6г
« » 1 П
г 2г г 2г
— —
Рис. 3. Сложенная двухкаскадная неблокируемая сеть Клоза- СНСК2(Й2,г).
К
2
Сеть Клоза с однонаправленными коммутаторами (рис. 1) при т ^ 2г — 1 является неблокируемой и допускает возможность прокладки нового бесконфликтного пути между любой парой свободных портов, не изменяя имеющихся путей. При т = 2г она содержит Кг = гк+1 портов и состоит из коммутаторов разного состава: г х 2г и 2г х г на к начальных и конечных каскадах и г х г в хребте.
Неблокируемая сеть Клоза также может иметь сложенный вид, в котором одноименные коммутаторы г-го и (£ — г + 1)-го каскадов выполняются в виде каскада из коммутаторов г х 2г и 2г х г с 3г дуплексными портами, а в качестве коммутаторов центрального каскада (хребта) используются коммутаторы г х г с г дуплексными портами. Сложность коммутаторов г х 2г и 2г х г обозначим через V, а сложность коммутатора г х г - через Для оценок примем V = 4г2, а ^ = г2. В сложенной сети число каскадов £ определяется как £ = к + 1. В общем случае (£ ^ 2) эта сеть обозначается СНСКг(Кг,г). В ней Кг = г* и Бг = [(V + К)2г-1 — ^г*-1 = (5 ■ 2г-1 — 4)гг+1 и 5г = Бг/К = = (5 ■ 2г-1 — 4)г. На рис. 3 представлена сложенная двухкаскадная неблокируемая сеть Клоза СНСК2(К2,г). Для нее К2 = г2, по оценке Б2 = 6г3 и ¿2 = 6г.
Такая сеть может обеспечить бесконфликтную маршрутизацию за счет динамического разрешения конфликтов. Однако до сих пор не построен алгоритм параллельной динамической самомаршрутизации в неблокируемой сети Клоза. Все это приводит к тому, что более сложная неблокируемая сеть Клоза на практике не используется, так как считается что при рандомизированной самомаршрутизации она не имеет коммутационных преимуществ перед перестраиваемой сетью.
В данной статье сравниваются нагрузочные характеристики (загрузка каналов, задержки передачи, размеры очередей) перестраиваемых и неблоки-руемых двухкаскадных сетей Клоза, полученные их имитационным моделированием в режиме выполнения произвольных перестановок пакетов между абонентами сети. Оказалось, что эти характеристики у неблокируемой сети много лучше, чем у перестраиваемой.
Кроме того, предлагается новая неблокируемая сеть - новый вид обобщённой сети Клоза [4], которая имеет меньшие задержки и большее число абонентов, чем обычная неблокируемая сеть, а по сложности эти сети оказываются достаточно близкими.
2. Имитационная модель и характеристики сетей Клоза
Характеристики сетей Клоза получались посредством имитационного моделирования для перестановочного трафика, при котором пакет каждого источника входит в состав произвольной перестановки, т.е. он может передаваться одному и только одному приёмнику.
В модели все источники действуют синхронно по тактам, пытаясь передать в каждом такте все пакеты, которые еще не переданы и для которых есть свободные по расписанию каналы. Если несколько источников адресуются к одному и тому же каналу (конфликт), то пакет передает только один из них, а остальные задерживают пакет в очереди к нему до следующего такта. При переполнении очереди новые пакеты сбрасываются. После каждого такта все источники заново генерируют по одному пакету, которые в совокупности образуют новую случайную (произвольную) перестановку. Для каждого канала используется отдельная очередь размера nR2r, где n ^ 1 - параметр модели.
Работа сети характеризуется тремя параметрами - средней загрузкой сети р, средней задержкой пакетов т и средним размером максимальной очереди в источнике q. В модели измерения продолжаются K тактов. При этом измеряется суммарное число Г сгенерированных пакетов и суммарное число £ переданных пакетов, сумма их задержек передачи T и сумма максимальных размеров очередей в каждом такте Q. Сетевые характеристики определяются по формулам р = Г/£, т = T/K и q = Q/K.
Моделирование проводилось для двухкаскадных сложенных сетей Клоза, так как их свойства являются определяющими и для многокаскадных сетей. Моделирование проводилось в предположении, что все маршруты проходят через хребет, т.е. в наихудшем случае. Перестраиваемые и неблокируемые сети показали совершенно разные свойства.
Сначала рассмотрим характеристики сложенной перестраиваемой сети СПСК2(Л2,г) (рис.2), приведённые в табл. 1. В ней переменная U2 задает число коммутаторов, а переменная W2 - число кабелей. Отметим, что удельная сложность этой сети оценивается величиной ¿2 = 3r. Основное свойство перестраиваемой сети, выявленное при моделировании, - это ее неустойчивость. Она проявляется в том, что загрузка сети оказывается неполной (р < 1), а задержки передачи и длйны очередей растут пропорционально числу тактов K и параметру n, который определяет максимальный размер очереди.
Неустойчивость выявлена на ряде рассмотренных алгоритмов самомаршрутизации, различающихся способом выбора выходного канала в каскадном коммутаторе. Рассмотрено 4 способа: случайный, по источнику, по каскадным коммутаторам, по коммутаторам и по источнику. В первом номер выходного канала out для каждого источника в каждом каскадном коммутаторе на пути к хребту задается как случайное число, равномерно распределенное на [0, r — 1], т.е. out=random(r). Во втором способе номер выходного канала out для источника i (0 ^ i ^ r — 1) в каждом коммутаторе принимается равным его номеру в данном коммутаторе, т.е. out = i. В третьем способе номер выходного канала out для некоторого источника принимается равным сумме номеров выходного и входного каскадных коммутаторов, т.е. out = (d+
Таблица 1. Характеристики СПСК2(Д2,г)
г 4 8 12 16 24 32 48 64
г? 1-2 Ко - — 8 32 72 128 288 512 1152 2048
коммутаторы 4x4 8x8 12x12 16x16 24x24 32x32 48x48 64x64
U2=r + % 6 12 18 24 36 48 72 96
Wo = 4 = Й2 8 32 72 128 288 512 1152 2048
Случайная маршрутизация: out=random(r)
Р2(1) 0,89 0,68 0,71 0,71 0,66 0,7 0,68 0,68
То >4,5 >11,8 >17,1 >22,4 >36,1 >45,8 >69,9 >93,3
42 >7,6 >31,3 >69 >124 >283 >499 >1125
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.