Сеть бабочек

Сеть -бабочка — это метод объединения нескольких компьютеров в высокоскоростную сеть. Эту форму многоступенчатой сети топологии можно использовать для соединения различных узлов в многопроцессорной системе. Сеть межсоединений для системы с общей памятью многопроцессорной должна иметь низкую задержку и высокую пропускную способность в отличие от других сетевых систем, таких как локальные сети (LAN) или Интернет. ^{[ нужна ссылка ]} по трем причинам:

Сообщения относительно короткие, поскольку большинство сообщений представляют собой запросы и ответы протокола когерентности без данных.

Сообщения генерируются часто, поскольку при каждом промахе чтения или записи генерируются сообщения для каждого узла в системе для обеспечения согласованности. процессора Промахи чтения/записи происходят, когда запрошенные данные отсутствуют в кэше и должны быть извлечены либо из памяти, либо из кэша другого процессора.

Сообщения генерируются часто, поэтому процессорам сложно скрыть задержку связи.

Компоненты

Основными компонентами межсетевой сети являются: ^{[ нужна ссылка ]}

Процессорные узлы, которые состоят из одного или нескольких процессоров вместе с их кэшами , памятью и средствами связи.
Коммутационные узлы ( Маршрутизатор ), которые соединяют средства связи различных процессорных узлов в системе. В многоступенчатых топологиях узлы коммутации более высокого уровня подключаются к узлам коммутации более низкого уровня, как показано на рисунке 1, где узлы коммутации ранга 0 подключаются к узлам процессора напрямую, а узлы коммутации ранга 1 подключаются к узлам коммутации ранга 0.
Ссылки, представляющие собой физические провода между двумя коммутационными узлами. Они могут быть однонаправленными или двунаправленными.

Эти многокаскадные сети имеют более низкую стоимость, чем перекрестная сеть , но вызывают меньшую конкуренцию, чем шина . Отношение коммутационных узлов к процессорным узлам больше, чем в сети-бабочке. Такая топология , где отношение узлов коммутации к узлам процессора больше единицы, называется непрямой топологией. ^[1]

Сеть получила свое название от связей между узлами в двух соседних рядах (как показано на рисунке 1), которые напоминают бабочку . Объединение верхних и нижних рангов в один создает сеть обернутых бабочек. ^[1] На рисунке 1, если узлы ранга 3 соединяются обратно с соответствующими узлами ранга 0, то это становится обернутой сетью-бабочкой.

BBN Butterfly , массивный параллельный компьютер, созданный Болтом, Беранеком и Ньюманом в 1980-х годах, использовал межсетевую сеть типа «бабочка». ^[2] Позже, в 1990 году, компании Cray Research машина Cray C90 использовала сеть «бабочка» для связи между своими 16 процессорами и 1024 банками памяти. ^[3]

Построение сети бабочек

Для сети-бабочки с p процессорными узлами должно быть p(log ₂ p + 1) коммутационных узлов. На рисунке 1 показана сеть с 8 процессорными узлами, что подразумевает 32 узла коммутации. Он представляет каждый узел как N (ранг, номер столбца). Например, узел в столбце 6 ранга 1 представлен как (1,6), а узел в столбце 2 ранга 0 представлен как (0,2). ^[1]

Для любого 'i' больше нуля узел коммутации N(i,j) подключается к N(i-1,j) и N(i-1,m), где m - инвертированный бит на i ^й расположение Дж. Например, рассмотрим узел N(1,6): i равно 1, а j равно 6, поэтому m получается путем инвертирования i ^й немного 6.

Переменная	Двоичное представление	Десятичное представление
дж	110	6
м	010	2

В результате узлы, подключенные к N(1,6), имеют вид:

Н(я,j)	Н(я-1,дж)	Н(я-1,м)
(1,6)	(0,6)	(0,2)

Таким образом, N(0,6), N(1,6), N(0,2), N(1,2) образуют узор бабочки. На рисунке присутствует несколько паттернов бабочек, поэтому эта сеть называется сетью бабочек.

Сетевая маршрутизация «бабочка»

В обернутой сети-бабочке (что означает, что ранг 0 объединяется с рангом 3) сообщение отправляется от процессора 5 к процессору 2. ^[1] На рисунке 2 это показано путем репликации процессорных узлов ранга ниже 3. Пакет, передаваемый по каналу, имеет вид:

Заголовок	Полезная нагрузка	Трейлер

Заголовок . содержит назначение сообщения, то есть процессор 2 (010 в двоичном формате) — Полезная нагрузка это сообщение, M и трейлер содержит контрольную сумму . Следовательно, фактическое сообщение, передаваемое процессором 5, имеет вид:

010	М	контрольная сумма

При достижении узла коммутации один из двух выходных каналов выбирается на основе старшего бита адреса назначения. Если этот бит равен нулю, выбрано левое соединение. Если этот бит равен единице, выбрана правильная ссылка. Впоследствии этот бит удаляется из адреса назначения в пакете, передаваемом по выбранному каналу. Это показано на рисунке 2.

Вышеуказанный пакет достигает N(0,5). Из заголовка пакета он удаляет самый левый бит, чтобы определить направление. Поскольку это ноль, выбирается левое звено N(0,5) (которое соединяется с N(1,1)). Новый заголовок — «10».
Новый пакет достигает N(1,1). Из заголовка пакета он удаляет самый левый бит, чтобы определить направление. Поскольку это одно, выбирается правое звено N(1,1) (которое соединяется с N(2,3)). Новый заголовок имеет значение «0».
Новый пакет достигает N(2,3). Из заголовка пакета он удаляет самый левый бит, чтобы определить направление. Поскольку это ноль, выбирается левое звено N(2,3) (которое соединяется с N(3,2)). Поле заголовка пусто.
Процессор 2 получает пакет, который теперь содержит только полезную нагрузку «М» и контрольную сумму.

Параметры сети «Бабочка»

Несколько параметров помогают оценить топологию сети. Ниже приведены наиболее важные из них, имеющие отношение к проектированию крупномасштабных многопроцессорных систем, и дается объяснение того, как они рассчитываются для сети-бабочки с 8 процессорными узлами, как показано на рисунке 1. ^{[ нужна ссылка ]}

Полоса пропускания пополам : максимальная пропускная способность, необходимая для поддержания связи между всеми узлами сети. Это можно интерпретировать как минимальное количество связей, которые необходимо разорвать, чтобы разделить систему на две равные части. Например, сеть-бабочка из 8 узлов может быть разделена на две, разрезав 4 звена, пересекающихся посередине. Таким образом, полоса пропускания пополам этой конкретной системы равна 4. Это показатель узкого места полосы пропускания , которое ограничивает общую связь.
Диаметр : наихудшая задержка (между двумя узлами), возможная в системе. Его можно рассчитать с точки зрения сетевых переходов, то есть количества каналов, по которым сообщение должно пройти, чтобы достичь узла назначения. В сети-бабочке из 8 узлов кажется, что N(0,0) и N(3,7) находятся дальше всего, но при осмотре становится очевидным, что из-за симметричной природы сети переход от любого узла ранга 0 для любого узла ранга 3 требуется всего 3 перехода. Следовательно, диаметр этой системы равен 3.
Ссылки : общее количество ссылок, необходимых для построения всей сетевой структуры. Это показатель общей стоимости и сложности реализации. Для примера сети, показанной на рисунке 1, требуется всего 48 каналов (по 16 каналов между рангом 0 и 1, рангом 1 и 2, рангом 2 и 3).
Степень : сложность каждого маршрутизатора в сети. Это равно количеству входных/выходных каналов, подключенных к каждому коммутационному узлу. Узлы коммутации сети «бабочка» имеют 2 входных канала и 2 выходных канала, следовательно, это сеть 4-го уровня.

Сравнение с другими сетевыми топологиями

В этом разделе сеть-бабочка сравнивается с линейного массива, кольца, двумерной сетки и гиперкуба . сетями ^[4] Линейный массив можно рассматривать как топологию одномерной сетки. Соответствующие параметры сведены в таблицу ^{[ нужна ссылка ]} («p» представляет количество процессорных узлов).

Параметры сети
Топология	Диаметр	Полоса пропускания пополам	Ссылки	Степень
Линейный массив	р-1	1	р-1	2
Кольцо	п/2	2	п	2
2-D сетка	2( √ p - 1)	√ p	2 √ p ( √ p - 1)	4
Гиперкуб	журнал ₂ (п)	п/2	log ₂ (p) × (p/2)	журнал ₂ (п)
Бабочка	журнал ₂ (п)	2^h, h = количество узлов в одном слое	log ₂ (п) × 2п	4

Преимущества

Сети-бабочки имеют меньший диаметр, чем другие топологии, такие как линейный массив, кольцо и двумерная сетка. Это означает, что в сети «бабочка» сообщение, отправленное с одного процессора, достигнет места назначения за меньшее количество сетевых переходов.
Сети-бабочки имеют более высокую пропускную способность пополам, чем другие топологии. Это означает, что в сети-бабочке необходимо разорвать большее количество ссылок, чтобы предотвратить глобальную связь.
У него больший компьютерный диапазон.

Недостатки

Сети-бабочки более сложны и дорогостоящи, чем другие топологии, из-за большего количества каналов, необходимых для поддержания сети.

Разница между гиперкубом и бабочкой заключается в их реализации. Сеть «Бабочка» имеет симметричную структуру, в которой все процессорные узлы между двумя рангами равноудалены друг от друга, тогда как гиперкуб больше подходит для многопроцессорной системы, которая требует неравных расстояний между ее узлами. Если посмотреть на количество необходимых каналов, может показаться, что гиперкуб дешевле и проще по сравнению с сетью-бабочкой, но по мере того, как количество процессорных узлов превышает 16, стоимость маршрутизатора и сложность (представленная по степени) сети-бабочки становятся ниже. чем гиперкуб, поскольку его степень не зависит от количества узлов.

В заключение следует отметить, что ни одна топология сети не является лучшей для всех сценариев. Решение принимается на основе таких факторов, как количество процессорных узлов в системе, требования к задержке полосы пропускания, стоимость и масштабируемость .

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д Лейтон, Ф. Томсон (1992). Введение в параллельные алгоритмы и архитектуры: массивы, деревья, гиперкубы . Издательство Морган Кауфманн. ISBN 1-55860-117-1 .
^ Т., ЛеБлан; М., Скотт; К., Браун (1 января 1988 г.). Крупномасштабное параллельное программирование: опыт работы с параллельным процессором BBN Butterfly (отчет). Проект «Бабочка». hdl : 1802/15082 .
^ Джадхав, Сунита С. (2009). Передовая компьютерная архитектура и вычисления . Технические публикации. стр. Раздел 3–22. ISBN 9788184315721 .
^ М. Арджоманд, Х. Сарбази-Азад, «Оценка производительности встроенной сети Butterfly для MPSoC», Международная конференция по проектированию SoC , стр. 1–296-1-299, 2008 г.

[:0-1] Jump up to: ^а ^б ^с ^д Лейтон, Ф. Томсон (1992). Введение в параллельные алгоритмы и архитектуры: массивы, деревья, гиперкубы . Издательство Морган Кауфманн. ISBN 1-55860-117-1 .

[2] Т., ЛеБлан; М., Скотт; К., Браун (1 января 1988 г.). Крупномасштабное параллельное программирование: опыт работы с параллельным процессором BBN Butterfly (отчет). Проект «Бабочка». hdl : 1802/15082 .

[3] Джадхав, Сунита С. (2009). Передовая компьютерная архитектура и вычисления . Технические публикации. стр. Раздел 3–22. ISBN 9788184315721 .

[4] М. Арджоманд, Х. Сарбази-Азад, «Оценка производительности встроенной сети Butterfly для MPSoC», Международная конференция по проектированию SoC , стр. 1–296-1-299, 2008 г.

[1]

[2]

[3]

[4]