Сеть бабочек - Butterfly network
Сеть бабочки представляет собой метод , чтобы связать множество компьютеров в высокоскоростной сети. Эта форма топологии многоступенчатой взаимосвязанной сети может использоваться для соединения различных узлов в многопроцессорной системе. Сеть межсоединений для многопроцессорной системы с общей памятью должна иметь низкую задержку и высокую пропускную способность в отличие от других сетевых систем, таких как локальные сети (LAN) или Интернет, по трем причинам:
- Сообщения относительно короткие, поскольку большинство сообщений представляют собой запросы протокола согласования и ответы без данных.
- Сообщения генерируются часто, потому что каждый промах при чтении или записи генерирует сообщения для каждого узла в системе для обеспечения согласованности. Промахи чтения / записи возникают, когда запрошенные данные отсутствуют в кэше процессора и должны быть получены либо из памяти, либо из кеша другого процессора.
- Сообщения генерируются часто, поэтому процессорам трудно скрыть задержку связи.
Составные части
Основными компонентами межсетевой сети являются:
- Узлы процессоров, которые состоят из одного или нескольких процессоров вместе с их кешами , памятью и средствами связи.
- Коммутационные узлы ( маршрутизатор ), которые соединяют коммуникационные средства различных узлов процессора в системе. В многоступенчатых топологиях узлы коммутации более высокого уровня подключаются к узлам коммутации более низкого уровня, как показано на рисунке 1, где коммутационные узлы ранга 0 подключаются к узлам процессора напрямую, а коммутационные узлы ранга 1 подключаются к узлам коммутации ранга 0.
- Ссылки, которые представляют собой физические провода между двумя узлами коммутации. Они могут быть однонаправленными или двунаправленными.
Эти многоступенчатые сети имеют меньшую стоимость, чем поперечная балка , но имеют меньшую конкуренцию, чем шина . Соотношение коммутирующих узлов и процессорных узлов больше, чем в сети типа «бабочка». Такая топология , в которой соотношение узлов коммутации к узлам процессора больше единицы, называется непрямой топологией.
Сеть получила свое название от соединений между узлами в двух соседних рядах (как показано на рисунке 1), которые напоминают бабочку . Объединение верхних и нижних рангов в один ранг создает сеть Wrapped Butterfly. На рисунке 1, если узлы ранга 3 снова подключаются к соответствующим узлам ранга 0, тогда это становится обернутой сетью «бабочка».
BBN Butterfly , массивный параллельный компьютер, построенный Болтом, Беранеком и Ньюманом в 1980-х годах, использовал межкомпонентную сеть типа «бабочка». Позже, в 1990 году, машина Cray C90 от Cray Research использовала сеть «бабочка» для связи между своими 16 процессорами и 1024 банками памяти.
Строительство сети бабочек
Для сети типа «бабочка» с p узлов процессора должно быть p (log 2 p + 1) узлов коммутации. На рисунке 1 показана сеть с 8 процессорами, что подразумевает 32 узла коммутации. Он представляет каждый узел как N (ранг, номер столбца). Например, узел в столбце 6 ранга 1 представлен как (1,6), а узел в столбце 2 ранга 0 представлен как (0,2).
Для любого '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) образуют узор бабочки. На рисунке существует несколько паттернов бабочек, поэтому эта сеть называется сетью бабочек.
Сетевая маршрутизация бабочки
В обернутой сети «бабочка» (что означает, что ранг 0 объединяется с рангом 3), сообщение отправляется от процессора 5 к процессору 2. На рисунке 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.
- 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-х ступенчатая сеть.
Сравнение с другими сетевыми топологиями
В этом разделе сравнивается сеть «бабочка» с сетями линейных массивов, кольцами, двумерными сетками и гиперкубами . Обратите внимание, что линейный массив можно рассматривать как топологию одномерной сетки. Соответствующие параметры собраны в таблице («p» обозначает количество узлов процессора).
| Топология | Диаметр | Пропускная способность бисекции | Ссылки | Степень |
|---|---|---|---|---|
| Линейный массив | п-1 | 1 | п-1 | 2 |
| Звенеть | p / 2 | 2 | п | 2 |
| 2-мерная сетка | 2 ( √ p - 1) | √ p | 2 √ p ( √ p - 1) | 4 |
| Гиперкуб | журнал 2 (р) | p / 2 | журнал 2 (p) × (p / 2) | журнал 2 (р) |
| Бабочка | журнал 2 (р) | p / 2 | журнал 2 (п) × 2п | 4 |
Преимущества
- Сети типа «бабочка» имеют меньший диаметр, чем другие топологии, такие как линейный массив, кольцо и двумерная сетка. Это означает, что в сети «бабочка» сообщение, отправленное от одного процессора, достигнет пункта назначения за меньшее количество сетевых переходов.
- Сети типа «бабочка» имеют более высокую пропускную способность, чем другие топологии. Это означает, что в сети «бабочка» необходимо разорвать большее количество ссылок, чтобы предотвратить глобальную коммуникацию.
- Имеет больший компьютерный диапазон.
Недостатки
- Сети типа «бабочка» сложнее и дороже, чем другие топологии, из-за большего количества каналов, необходимых для поддержки сети.
Разница между гиперкубом и бабочкой заключается в их реализации. Сеть Butterfly имеет симметричную структуру, в которой все процессорные узлы между двумя рангами равноудалены друг от друга, тогда как гиперкуб больше подходит для многопроцессорной системы, которая требует неравных расстояний между своими узлами. Глядя на количество требуемых каналов, может показаться, что гиперкуб дешевле и проще по сравнению с сетью типа бабочка, но по мере того, как количество процессорных узлов превышает 16, стоимость и сложность маршрутизатора (выраженная степенью) сети бабочки становится ниже. чем гиперкуб, потому что его степень не зависит от количества узлов.
В заключение следует отметить, что ни одна топология единой сети не подходит для всех сценариев. Решение принимается на основе таких факторов, как количество процессорных узлов в системе, требования к полосе пропускания и задержки, стоимость и масштабируемость .
Смотрите также
Источники
- Ян, Солихин (октябрь 2009 г.). Основы параллельной компьютерной архитектуры: многокристальные и многоядерные системы . ООО "Солихин Паблишинг энд Консалтинг". ISBN 978-0-9841630-0-7 .