Введение
Арбитр Wavefront — это схема, используемая для принятия решений, управляющих кросс-барной матрицей высокопроизводительной коммутационной ткани параллельно. Он был коммерциализирован в чипсетах TT1 и TTx, разработанных Abrizio и продаваемых компанией PMC Sierra.
Контекст
Поперечная шина — центральная часть коммутационной матрицы поперечной шины, соединяющая входы с выходами. В каждый период арбитража необходимо принимать решения о том, какие входы соединяются с какими выходами. В высокоскоростных приложениях коммутации ячеек или пакетов период арбитража очень короткий, и часто исчисляется миллионами или миллиардами периодов в секунду. Арбитр — это схема, определяющая, какие из многочисленных переключателей поперечной шины должны быть замкнуты. Скорость является ключевым критерием проектирования арбитра в некоторых приложениях.
Описание алгоритма
Арбитр фронта волны – это особый тип арбитра, оптимизированный для высокоскоростной работы. Для одноадресного (unicast) коммутатора алгоритм следующий: решение начинается в одной точке матрицы x y, представляющей физические коммутаторы, например, в верхнем левом углу. На основе запросов принимается решение о закрытии этого коммутатора, соединяющего соответствующие вход и выход. Результат этого решения затем распространяется вправо по оси матрицы, представляющей вход, и вниз по оси матрицы, представляющей выход. Результаты первого вычисления затем позволяют выполнить следующее вычисление в точке справа и в точке ниже, и решение о закрытии коммутатора принимается в каждой из этих двух точек. Результаты этих двух последующих вычислений затем распространяются в точки ниже и справа от них. Эти результаты затем позволяют принимать решения в следующих трех точках, расположенных справа и ниже. Эти результаты снова распространяются вправо и вниз. В случае, если вычисление не начиналось в верхнем левом углу, результаты замыкаются, переходя с правой границы к первому левому столбцу и с нижней границы к верхнему ряду. Вычисление продолжается до тех пор, пока не будут приняты все решения.
The decision starts at a single point in the x y matrix which represents the physical switches, for example the upper left hand corner. Based on the requests, a decision is made whether to close that switch, connecting the corresponding input and output. The result of this decision is then fed to the right along the matrix axis representing the input, and down along the matrix axis representing the output. The results of the first computation then enable the next computation at the point to the right and at the point below and switch closing decision is made at each of those two points. The results of these subsequent two calculations then are then fed to the points below and to the right of them. These results then enable the decisions at the next three points which are to the right and below. These results are again fed to the right and below. In the case where the calculation did not start in the upper left hand corner, the results wrap around the right back to the first left column and around the bottom to the top row. The calculation continues until all of the decisions have been made.