Арбитр волнового фронта

Арбитр волнового фронта — это схема, используемая для принятия решений, которые параллельно управляют перемычкой коммутационной матрицы высокой мощности. ^[1] Он был коммерциализирован в наборах микросхем TT1 и TTx, разработанных Abrizio и проданных PMC-Sierra .

Контекст

Перемычка — это центральная часть коммутационной матрицы, которая соединяет входы с выходами. Набор решений о том, какие входы подключены к каким выходам, должен приниматься каждый арбитражный период. В приложениях с высокоскоростной коммутацией ячеек или коммутацией пакетов период арбитража очень короткий. Зачастую в секунду происходят миллионы или миллиарды арбитражных периодов.

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

Описание алгоритма

Арбитр волнового фронта — это особый тип арбитра, оптимизированный для высокоскоростной работы. Для одноадресного коммутатора алгоритм следующий:

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

Преимущество использования

К преимуществам данного вида расчета относятся:

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

Варианты

Существует множество вариантов этого метода, включая:

Рандомизация или перетасовка порядка рассмотрения строк и столбцов. Для достижения справедливости обычно необходима своего рода перетасовка.
Многоадресные варианты этого метода, в которых один вход может быть подключен к нескольким выходам за один или несколько проходов.

Ссылки

^ Геленбе, Э.; Багчи, К.; Зобрист, Г. (1999). Проектирование сетевых систем . Тейлор и Фрэнсис. п. 6. ISBN 978-90-5699-635-2 . Проверено 13 сентября 2018 г.

Описание алгоритма в Стэнфордском классе

[Gelenbe_Bagchi_Zobrist_1999_p._6-1] Геленбе, Э.; Багчи, К.; Зобрист, Г. (1999). Проектирование сетевых систем . Тейлор и Фрэнсис. п. 6. ISBN 978-90-5699-635-2 . Проверено 13 сентября 2018 г.

[1]