Управление потоком через червоточину , также называемое переключением через червоточину или маршрутизацией через червоточину , представляет собой систему простого управления потоком в компьютерных сетях на основе известных фиксированных ссылок. Это подмножество методов управления потоком, называемых управлением потоком через флит-буфер . [1] : Глава 13.2.1
Коммутация — более подходящий термин, чем маршрутизация, поскольку «маршрутизация» определяет маршрут или путь, по которому можно достичь пункта назначения. [2] [3] Метод червоточины не определяет маршрут к пункту назначения, а решает, когда пакет будет передан маршрутизатору.
Коммутация через червоточины широко используется в мультикомпьютерах из-за ее низкой задержки и небольших требований к узлам. [3] : 376
Маршрутизация через червоточину поддерживает очень низкую задержку , высокую скорость и гарантированную доставку пакетов, подходящую для связи в реальном времени . [4]
В системе управления потоком данных с использованием червоточины каждый пакет разбивается на небольшие фрагменты, называемые флитами (единицами управления потоком или цифрами управления потоком).
Обычно первые flits, называемые заголовочными flits, содержат информацию о маршруте этого пакета (например, адрес назначения) и устанавливают поведение маршрутизации для всех последующих flits, связанных с пакетом. За заголовочными flits следуют ноль или более body flits, которые содержат фактическую полезную нагрузку данных. Некоторые финальные flits, называемые хвостовыми flits, выполняют некоторую бухгалтерию для закрытия соединения между двумя узлами.
В коммутации червоточин каждый буфер либо простаивает, либо выделяется для одного пакета. Заголовочный Flit может быть перенаправлен в буфер, если этот буфер простаивает. Это выделяет буфер пакету. Тело или концевой Flit могут быть перенаправлены в буфер, если этот буфер выделен его пакету и не заполнен. Последний Flit освобождает буфер. Если заголовок Flit заблокирован в сети, буфер заполняется, и после заполнения больше Flit не может быть отправлен: этот эффект называется «обратным давлением» и может распространяться обратно к источнику.
Название «червоточина» играет на способе отправки пакетов по ссылкам: адрес настолько короткий, что его можно перевести до того, как прибудет само сообщение. Это позволяет маршрутизатору быстро настроить маршрутизацию фактического сообщения, а затем «откланяться» от остальной части разговора. Поскольку пакет передается flit за flit, он может занимать несколько буферов flit на своем пути, создавая образ, похожий на червя.
Такое поведение очень похоже на сквозное переключение [5] , обычно называемое «виртуальным сквозным переключением», основное отличие состоит в том, что сквозное управление потоком выделяет буферы и полосу пропускания канала на уровне пакетов, тогда как управление потоком через червоточину делает это на уровне пакетов.
В случае циклической зависимости это обратное давление может привести к тупиковой ситуации.
Во многих отношениях технология червоточины очень похожа на пересылку ATM или MPLS , за исключением того, что ячейку не нужно ставить в очередь .
Одной из особенностей управления потоком через червоточину является реализация виртуальных каналов:
Виртуальный канал содержит состояние, необходимое для координации обработки flits пакета по каналу. Как минимум, это состояние определяет выходной канал текущего узла для следующего перехода маршрута и состояние виртуального канала (простой, ожидание ресурсов или активный). Виртуальный канал может также включать указатели на flits пакета, которые буферизуются на текущем узле, и количество буферов flit, доступных на следующем узле. [1] : 237
Рассмотрим сеть 2x2 на рисунке справа с 3 пакетами для отправки: розовый, состоящий из 4 флитов, 'UVWX', от C до D; синий, состоящий из 4 флитов 'abcd', от A до F; и зеленый, состоящий из 4 флитов 'ijkl', от E до H. Мы предполагаем, что маршрутизация была вычислена, как на рисунке, и подразумевает конфликт буфера в нижнем левом маршрутизаторе. Пропускная способность составляет один флит за единицу времени.
Сначала рассмотрим розовый поток: в момент времени 1 флит «U» отправляется в первый буфер; в момент времени 2 флит «U» проходит через следующий буфер (предполагая, что вычисление маршрута не занимает времени), а флит «V» отправляется в первый буфер и т. д.
Синий и зеленый потоки требуют пошагового представления:
Методы червоточин в основном используются в многопроцессорных системах, в частности, гиперкубах . В компьютере-гиперкубе каждый ЦП присоединен к нескольким соседям по фиксированной схеме, что сокращает количество переходов от одного ЦП к другому. Каждому ЦП присваивается номер (обычно всего от 8 до 16 бит ), который является его сетевым адресом, и пакеты на ЦП отправляются с этим номером в заголовке. Когда пакет поступает на промежуточный маршрутизатор для пересылки, маршрутизатор проверяет заголовок (очень быстро), устанавливает канал к следующему маршрутизатору, а затем выходит из разговора. Это заметно сокращает задержку по сравнению с коммутацией с промежуточным хранением , которая ждет весь пакет перед пересылкой. Совсем недавно управление потоком червоточин нашло свое применение в системах на кристалле (NOC), одной из разновидностей которых являются многоядерные процессоры. Здесь многие ядра процессора или, на более низком уровне, даже функциональные блоки могут быть соединены в сеть на одном корпусе IC . Поскольку задержки в проводах и многие другие немасштабируемые ограничения на связанные элементы обработки становятся доминирующим фактором при проектировании, инженеры стремятся упростить организованные сети взаимосвязей, в которых важную роль играют методы управления потоками.
Технологии IEEE 1355 и SpaceWire используют червоточины.
Расширением управления потоком через червоточину является управление потоком через виртуальный канал , где несколько виртуальных каналов могут быть мультиплексированы через один физический канал. Каждый однонаправленный виртуальный канал реализуется независимо управляемой парой буферов (flit). Затем различные пакеты могут совместно использовать физический канал на основе flit-by-flit. Первоначально виртуальные каналы были введены для того, чтобы избежать проблемы взаимоблокировки, но их также можно использовать для уменьшения блокировки червоточины, улучшения задержки и пропускной способности сети. Блокировка червоточины происходит, когда пакет захватывает канал, тем самым не давая другим пакетам использовать канал и заставляя их останавливаться. Предположим, что пакет P0 захватил канал между двумя маршрутизаторами. При отсутствии виртуальных каналов пакет P1, прибывший позже, будет заблокирован до тех пор, пока передача P0 не будет завершена. Если реализованы виртуальные каналы, возможны следующие улучшения:
Использование виртуальных каналов для уменьшения блокировки червоточин имеет много общего с использованием виртуальной очереди вывода для уменьшения блокировки начала очереди .
В одном и том же пакете с червоточиной-коммутацией может использоваться смесь исходной маршрутизации и логической маршрутизации. Значение первого байта пакета Myrinet или SpaceWire является адресом пакета. Каждый коммутатор SpaceWire использует адрес для принятия решения о маршрутизации пакета. [7]
При маршрутизации от источника отправитель пакета выбирает, как пакет будет маршрутизирован через коммутатор.
Если первый байт входящего пакета SpaceWire находится в диапазоне от 1 до 31, он указывает на соответствующий порт от 1 до 31 коммутатора SpaceWire. Затем коммутатор SpaceWire отбрасывает этот символ маршрутизации и отправляет остаток пакета через этот порт. Это открывает следующий байт исходного пакета следующему коммутатору SpaceWire. Отправитель пакета может выбрать использование исходной маршрутизации , чтобы явно указать полный путь через сеть к конечному пункту назначения таким образом. [7]
При логической маршрутизации коммутатор Spacewire сам решает, как маршрутизировать пакет.
Если адрес (первый байт) входящего пакета SpaceWire находится в диапазоне от 32 до 255, коммутатор SpaceWire использует это значение в качестве индекса во внутренней таблице маршрутизации, которая указывает, на какой порт(ы) отправлять пакет и следует ли удалить или сохранить этот первый байт. [7]
Адрес 0 используется для прямой связи с коммутатором и может использоваться для установки записей таблицы маршрутизации для этого коммутатора. [7]