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

А Арбитр волнового фронта представляет собой схему, используемую для принятия решений, которые параллельно управляют перекладиной коммутационной матрицы высокой емкости.[1] Он был коммерциализирован в наборах микросхем TT1 и TTx, разработанных Абрицио и продано ЧВК-Сьерра.

Контекст

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

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

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

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

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

Польза от использования

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

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

Варианты

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

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

Рекомендации

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