Переключение червоточины

Управление потоком червоточины , также называемое переключением червоточины или маршрутизацией червоточины , представляет собой систему простого управления потоком в компьютерных сетях , основанную на известных фиксированных каналах. Это подмножество методов управления потоком, называемое Flit-Buffer Flow Control. ^[1]^{: Глава 13.2.1}

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

Коммутация «червоточина» широко используется в мультикомпьютерах из-за низкой задержки и небольших требований на узлах. ^[3]^: 376

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

Принцип механизма

При управлении потоком червоточины каждый пакет разбивается на небольшие части, называемые флитами (единицы управления потоком или цифры управления потоком).

Обычно первые флеты, называемые флитами заголовка, содержат информацию о маршруте этого пакета (например, адрес назначения) и устанавливают поведение маршрутизации для всех последующих флитов, связанных с пакетом. За сменами заголовка следует ноль или более смен тела, которые содержат фактическую полезную нагрузку данных. Некоторые заключительные этапы, называемые хвостовыми, выполняют некоторую бухгалтерию, чтобы закрыть соединение между двумя узлами.

При коммутации червоточины каждый буфер либо простаивает, либо выделяется для одного пакета. Смещение заголовка может быть перенаправлено в буфер, если этот буфер свободен. Это выделяет буфер для пакета. Флит тела или трейлера может быть перенаправлен в буфер, если этот буфер выделен для его пакета и не заполнен. Последняя операция освобождает буфер. Если флит-заголовок заблокирован в сети, буфер заполняется, и после заполнения флит-файлы больше не могут быть отправлены: этот эффект называется «обратным давлением» и может быть распространен обратно к источнику.

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

Это поведение очень похоже на сквозное переключение . ^[5] обычно называемое «виртуальным сквозным соединением», основное отличие которого состоит в том, что сквозное управление потоком распределяет буферы и полосу пропускания канала на уровне пакетов, тогда как управление потоком «червоточины» делает это на уровне flit.

В случае циклической зависимости это противодавление может привести к тупику.

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

Особенностью управления потоком червоточин является реализация виртуальных каналов:

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

Пример

Анимация переключения червоточины с тремя потоками. — Три потока в сети 2x2 с использованием коммутации «червоточина»

Рассмотрим сеть 2x2 на рисунке справа, в которой необходимо отправить 3 пакета: розовый, состоящий из 4 флитов, «UVWX», от C до D; синий, состоящий из 4 крыльев abcd, от A до F; и зеленый, состоящий из 4 флитов «ijkl», от E до H. Мы предполагаем, что маршрутизация была рассчитана, как показано на рисунке, и подразумевает конфликт буфера в нижнем левом маршрутизаторе. Пропускная способность составляет один флит в единицу времени.

Во-первых, рассмотрим розовый поток: в момент 1 сигнал «U» отправляется в первый буфер; в момент времени 2 сообщение «U» проходит через следующий буфер (при условии, что вычисление маршрута не занимает много времени), а сообщение «V» отправляется в первый буфер и так далее.

Синий и зеленый потоки требуют пошагового представления:

Время 1: И синий, и зеленый потоки посылают свои первые сигналы «i» и «a».
Время 2: «i» может перейти в следующий буфер. Но буфер выделен для пакета от его первой до последней передачи, поэтому пересылка 'a' не может быть перенаправлена. Это начало эффекта противодавления . Флит «j» может заменить флейт «i». Флит 'b' может быть отправлен.
Время 3: Зеленый пакет горит. Синий флит «c» не может быть перенаправлен (буфер занят флитами «b» и «a»): этот эффект обратного давления достигает источника пакета.
Тайм 4: Как и в тайме 3.
Время 5: Зеленый пакет больше не использует нижний буфер. Синий пакет разблокирован и может быть перенаправлен (при условии, что «разблокированная» информация может быть перенаправлена в нулевое время)
Время 6-10: Синий пакет проходит через сеть.

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

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

Использование

Методы червоточин в основном используются в многопроцессорных системах, особенно в гиперкубах . В компьютере-гиперкубе каждый процессор подключен к нескольким соседям по фиксированной схеме, что уменьшает количество переходов от одного процессора к другому. Каждому ЦП присваивается номер (обычно от 8 до 16 бит ), который является его сетевым адресом, и пакеты ЦП отправляются с этим номером в заголовке. Когда пакет поступает на промежуточный маршрутизатор для пересылки, маршрутизатор проверяет заголовок (очень быстро), устанавливает канал до следующего маршрутизатора, а затем прекращает диалог. Это заметно снижает задержку (задержку) по сравнению с коммутацией с промежуточным хранением, при которой перед пересылкой ожидает весь пакет. Совсем недавно управление потоком червоточин нашло свое применение в системах Network On Chip (NOC), одной из разновидностей которых являются многоядерные процессоры. Здесь множество процессорных ядер или, на более низком уровне, даже функциональные блоки могут быть объединены в сеть на одном корпусе микросхемы . Поскольку задержки в проводах и многие другие немасштабируемые ограничения на связанные элементы обработки становятся доминирующим фактором при проектировании, инженеры стремятся упростить организованные сети межсоединений, в которых методы управления потоками играют важную роль.

Технологии IEEE 1355 и SpaceWire используют червоточину.

Виртуальные каналы

Расширением управления потоком червоточины является виртуальных каналов управление потоком , при котором несколько виртуальных каналов могут быть мультиплексированы в один физический канал. Каждый однонаправленный виртуальный канал реализуется независимо управляемой парой (flit) буферов. Затем различные пакеты могут совместно использовать физический канал на индивидуальной основе. Виртуальные каналы изначально были введены, чтобы избежать проблемы тупиковой ситуации, но их также можно использовать для уменьшения блокировки червоточин, улучшения задержки и пропускной способности сети. Блокировка «червоточины» происходит, когда пакет захватывает канал, что предотвращает использование канала другими пакетами и приводит к их остановке. Предположим, пакет P0 захватил канал между двумя маршрутизаторами. При отсутствии виртуальных каналов пакет P1, пришедший позже, будет заблокирован до тех пор, пока не будет завершена передача P0. В случае реализации виртуальных каналов возможны следующие улучшения:

По прибытии P1 физический канал может быть мультиплексирован между ними поэтапно, так что оба пакета передаются с половинной скоростью (в зависимости от схемы арбитража).
Если P0 является полноразмерным пакетом, тогда как P1 представляет собой лишь небольшой управляющий пакет размером в несколько флитов, то эта схема позволяет P1 проходить через оба маршрутизатора, в то время как P0 замедляется на короткое время, соответствующее передаче нескольких пакетов. Это уменьшает задержку для P1.
Предположим, что P0 временно заблокирован в нисходящем направлении от текущего маршрутизатора. Пропускная способность увеличивается за счет того, что P1 может работать на полной скорости физического канала. Без виртуальных каналов P0 занимал бы канал, фактически не используя доступную полосу пропускания (поскольку она блокируется). ^[6]

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

Маршрутизация

В одном и том же пакете, коммутируемом через червоточину, может использоваться сочетание маршрутизации от источника и логической маршрутизации. Значение первого байта пакета Myrinet или SpaceWire является адресом пакета. Каждый коммутатор SpaceWire использует адрес, чтобы решить, как маршрутизировать пакет. ^[7]

Исходная маршрутизация

При маршрутизации от источника отправитель пакета выбирает способ маршрутизации пакета через коммутатор.

Если первый байт входящего пакета SpaceWire находится в диапазоне от 1 до 31, он указывает соответствующий порт от 1 до 31 коммутатора Spacewire. Затем коммутатор SpaceWire отбрасывает этот символ маршрутизации и отправляет остальную часть пакета через этот порт. Это предоставляет следующий байт исходного пакета следующему коммутатору SpaceWire. Отправитель пакета может выбрать использование исходной маршрутизации , чтобы таким образом явно указать полный путь через сеть к конечному пункту назначения. ^[7]

Логическая маршрутизация

При логической маршрутизации коммутатор Spacewire сам решает, как маршрутизировать пакет.

Если адрес (первый байт) входящего пакета SpaceWire находится в диапазоне от 32 до 255, Коммутатор SpaceWire использует это значение в качестве индекса во внутренней таблице маршрутизации, который указывает, на какой порт(ы) отправить пакет и следует ли удалить или сохранить этот первый байт. ^[7]

Адрес 0 используется для прямой связи с коммутатором и может использоваться для установки записей таблицы маршрутизации для этого коммутатора. ^[7]

См. также

Ссылки

^ Перейти обратно: ^а ^б Уильям Джеймс Далли; Брайан Таулз (2004). «13.2.1». Принципы и практика сетей межсетевого взаимодействия . Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-200751-4 .
^ Джон Л. Хеннесси и Дэвид А. Паттерсон (2006). «Приложение Е.5». Компьютерная архитектура: количественный подход (Четвертое изд.). Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-370490-0 .
^ Перейти обратно: ^а ^б Мохапатра, Прасант (1998), «Методы маршрутизации червоточины для многокомпьютерных систем с прямым подключением» (PDF) , ACM Computing Surveys , 30 (3): 374–410, CiteSeerX 10.1.1.11.9098 , doi : 10.1145/292469.292472 , S2CID 78 50481
^ Шарад Сундаресан; Риккардо Беттати. «Управление распределенными соединениями для связи в реальном времени через сети, маршрутизируемые через червоточину» . 1997.
^ Стефан Хаас. «Стандарт IEEE 1355: разработки, характеристики и применение в физике высоких энергий» . 1998. с. 59.
^ Павел Тврдик. «Почему маршрутизация червоточин является важным методом переключения»
^ Перейти обратно: ^а ^б ^с ^д доктор Барри М. Кук; Пол Уокер. «Ethernet через SpaceWire — проблемы с программным обеспечением» . ^{[ постоянная мертвая ссылка ]} 2007. п. 2.

[Dally_and_Towles-1] Перейти обратно: ^а ^б Уильям Джеймс Далли; Брайан Таулз (2004). «13.2.1». Принципы и практика сетей межсетевого взаимодействия . Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-200751-4 .

[2] Джон Л. Хеннесси и Дэвид А. Паттерсон (2006). «Приложение Е.5». Компьютерная архитектура: количественный подход (Четвертое изд.). Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-370490-0 .

[Mohapatra-3] Перейти обратно: ^а ^б Мохапатра, Прасант (1998), «Методы маршрутизации червоточины для многокомпьютерных систем с прямым подключением» (PDF) , ACM Computing Surveys , 30 (3): 374–410, CiteSeerX 10.1.1.11.9098 , doi : 10.1145/292469.292472 , S2CID 78 50481

[4] Шарад Сундаресан; Риккардо Беттати. «Управление распределенными соединениями для связи в реальном времени через сети, маршрутизируемые через червоточину» . 1997.

[5] Стефан Хаас. «Стандарт IEEE 1355: разработки, характеристики и применение в физике высоких энергий» . 1998. с. 59.

[6] Павел Тврдик. «Почему маршрутизация червоточин является важным методом переключения»

[Cook-Walker-7] Перейти обратно: ^а ^б ^с ^д доктор Барри М. Кук; Пол Уокер. «Ethernet через SpaceWire — проблемы с программным обеспечением» . ^{[ постоянная мертвая ссылка ]} 2007. п. 2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]