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

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

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

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

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

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

Преимущества данного типа расчета включают в себя:

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

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

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

• Описание алгоритма в записках занятий Стэнфорда