Сообщения генерируются часто, поскольку при каждом промахе чтения или записи генерируются сообщения для каждого узла в системе для обеспечения согласованности. Промахи чтения/записи происходят, когда запрошенные данные отсутствуют в кэше процессора и должны быть извлечены либо из памяти, либо из кэша другого процессора.
Сообщения генерируются часто, поэтому процессорам сложно скрыть задержку связи.
Процессорные узлы, которые состоят из одного или нескольких процессоров вместе с их кэшами , памятью и средствами связи.
Коммутационные узлы ( Маршрутизатор ), которые соединяют средства связи различных процессорных узлов в системе. В многоступенчатых топологиях узлы коммутации более высокого уровня подключаются к узлам коммутации более низкого уровня, как показано на рисунке 1, где узлы коммутации ранга 0 подключаются к узлам процессора напрямую, а узлы коммутации ранга 1 подключаются к узлам коммутации ранга 0.
Ссылки, представляющие собой физические провода между двумя коммутационными узлами. Они могут быть однонаправленными или двунаправленными.
Эти многокаскадные сети имеют более низкую стоимость, чем перекрестная сеть , но вызывают меньшую конкуренцию, чем шина . Отношение коммутационных узлов к процессорным узлам больше, чем в сети-бабочке. Такая топология , где отношение узлов коммутации к узлам процессора больше единицы, называется косвенной топологией. [1]
Сеть получила свое название от связей между узлами в двух соседних рядах (как показано на рисунке 1), которые напоминают бабочку . Объединение верхних и нижних рангов в один создает сеть обернутых бабочек. [1] На рисунке 1, если узлы ранга 3 соединяются обратно с соответствующими узлами ранга 0, то это становится обернутой сетью-бабочкой.
Для сети-бабочки с p процессорными узлами должно быть p(log 2 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.
В результате узлы, подключенные к N(1,6), имеют вид:
Таким образом, N(0,6), N(1,6), N(0,2), N(1,2) образуют узор бабочки. На рисунке присутствует несколько паттернов бабочек, поэтому эта сеть называется сетью бабочек.
Сетевая маршрутизация «бабочка»
Рисунок 2. Сетевая маршрутизация типа «бабочка».
В обернутой сети-бабочке (что означает, что ранг 0 объединяется с рангом 3) сообщение отправляется от процессора 5 к процессору 2. [1] На рисунке 2 это показано путем репликации узлов процессора ниже ранга 3. Передаваемый пакет по ссылке имеет форму:
Заголовок содержит назначение сообщения, то есть процессор 2 (010 в двоичном формате) . Полезная нагрузка — это сообщение, M и трейлер содержит контрольную сумму . Следовательно, фактическое сообщение, передаваемое процессором 5, имеет вид:
При достижении узла коммутации один из двух выходных каналов выбирается на основе старшего бита адреса назначения. Если этот бит равен нулю, выбрано левое соединение. Если этот бит равен единице, выбрана правильная ссылка. Впоследствии этот бит удаляется из адреса назначения в пакете, передаваемом по выбранному каналу. Это показано на рисунке 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» обозначает количество процессорных узлов).
Преимущества
Сети-бабочки имеют меньший диаметр, чем другие топологии, такие как линейный массив, кольцо и двумерная сетка. Это означает, что в сети «бабочка» сообщение, отправленное с одного процессора, достигнет места назначения за меньшее количество сетевых переходов.
Сети-бабочки имеют более высокую пропускную способность пополам, чем другие топологии. Это означает, что в сети-бабочке необходимо разорвать большее количество ссылок, чтобы предотвратить глобальную связь.
У него больший компьютерный диапазон.
Недостатки
Сети-бабочки более сложны и дорогостоящи, чем другие топологии, из-за большего количества каналов, необходимых для поддержания сети.
Разница между гиперкубом и бабочкой заключается в их реализации. Сеть «Бабочка» имеет симметричную структуру, в которой все процессорные узлы между двумя рангами равноудалены друг от друга, тогда как гиперкуб больше подходит для многопроцессорной системы, которая требует неравных расстояний между ее узлами. Если посмотреть на количество требуемых каналов, может показаться, что гиперкуб дешевле и проще по сравнению с сетью-бабочкой, но по мере того, как количество процессорных узлов превышает 16, стоимость маршрутизатора и сложность (представленная по степени) сети-бабочки становятся ниже. чем гиперкуб, поскольку его степень не зависит от количества узлов.
В заключение следует отметить, что ни одна топология сети не является лучшей для всех сценариев. Решение принимается на основе таких факторов, как количество процессорных узлов в системе, требования к задержке полосы пропускания, стоимость и масштабируемость .
^ abcd Лейтон, Ф. Томсон (1992). Введение в параллельные алгоритмы и архитектуры: массивы, деревья, гиперкубы . Издательство Морган Кауфманн. ISBN 1-55860-117-1.
^ Т., ЛеБлан; М., Скотт; К., Браун (1 января 1988 г.). Крупномасштабное параллельное программирование: опыт работы с параллельным процессором BBN Butterfly (отчет). Проект «Бабочка». hdl : 1802/15082.
^ Джадхав, Сунита С. (2009). Передовая компьютерная архитектура и вычисления . Технические публикации. стр. Раздел 3–22. ISBN9788184315721.
^ М. Арджоманд, Х. Сарбази-Азад, «Оценка производительности встроенной сети Butterfly для MPSoC», Международная конференция по проектированию SoC , стр. 1–296-1-299, 2008 г.
