Сеть бабочек

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Май 2017 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Рисунок 1: Сеть Butterfly для 8 процессоров

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

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

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

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

Компоненты [ править ]

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

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

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

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

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

Строительство сети бабочек [ править ]

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

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

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

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

N (i, j)	N (i-1, j)	N (i-1, м)
(1,6)	(0,6)	(0,2)

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

Сетевая маршрутизация бабочки [ править ]

Рисунок 2: Сетевая маршрутизация Butterfly

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

Заголовок

Полезная нагрузка

Трейлер

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

010

M

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

При достижении коммутационного узла один из двух выходных каналов выбирается на основе самого старшего бита адреса назначения. Если этот бит равен нулю, выбирается левая ссылка. Если этот бит равен единице, выбрана правая ссылка. Впоследствии этот бит удаляется из адреса назначения в пакете, передаваемом по выбранному каналу. Это показано на рисунке 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 получает пакет, который теперь содержит только полезную нагрузку «M» и контрольную сумму.

Сетевые параметры бабочки [ править ]

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

Bisection Bandwidth : максимальная пропускная способность, необходимая для поддержания связи между всеми узлами в сети. Это можно интерпретировать как минимальное количество ссылок, которые необходимо разорвать, чтобы разделить систему на две равные части. Например, 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 степенями свободы.

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

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

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

Преимущества [ править ]

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

Недостатки [ править ]

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

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

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

См. Также [ править ]

Параллельные вычисления
Топология сети
Ячеистая сеть

Источники [ править ]

Ян, Солихин (октябрь 2009 г.). Основы параллельной компьютерной архитектуры: многокристальные и многоядерные системы . ООО "Солихин Паблишинг энд Консалтинг". ISBN 978-0-9841630-0-7.

Ссылки [ править ]

^ Solihin 2009 , стр. 371-372.
^ Solihin 2009 , стр. 373-374.
^ a b c d Лейтон, Ф. Томсон (1992). Введение в параллельные алгоритмы и архитектуры: массивы, деревья, гиперкубы . Издательство Морган Кауфманн. ISBN 1-55860-117-1.
^ Т., ЛеБлан; М., Скотт; К., Браун (1988-01-01). «Крупномасштабное параллельное программирование: опыт работы с параллельным процессором BBN Butterfly». ЛВП : 1802/15082 . Cite journal requires |journal= (help)
^ Jadhav, Sunitha S (2009). Продвинутая компьютерная архитектура и вычисления . Технические публикации. С. Раздел 3–22. ISBN 9788184315721.
^ Solihin 2009 , стр. 377-378.
^ М. Арджоманд, Х. Сарбази-Азад, «Оценка производительности сети Butterfly на кристалле для MPSoC», Международная конференция по проектированию SoC , стр. 1–296-1-299, 2008 г.
^ Solihin 2009 , стр. 379-380.

[FOOTNOTESolihin2009371–372-1] Solihin 2009 , стр. 371-372.

[FOOTNOTESolihin2009373–374-2] Solihin 2009 , стр. 373-374.

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

[4] Т., ЛеБлан; М., Скотт; К., Браун (1988-01-01). «Крупномасштабное параллельное программирование: опыт работы с параллельным процессором BBN Butterfly». ЛВП : 1802/15082 . Cite journal requires |journal= (help)

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

[FOOTNOTESolihin2009377–378-6] Solihin 2009 , стр. 377-378.

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

[FOOTNOTESolihin2009379–380-8] Solihin 2009 , стр. 379-380.

[1],