Оценка эффективности использования матрицы регистров коммутационного устройства

Конвейеризация обработки пакетов разработанным КУ приводит к тому, что в МР могут одновременно находиться больше nпакетов. Это обеспечивает повышение средней загрузки матрицы регистров и, как следствие, способствует увеличению его пропускной способности.

Оценим, насколько повышается загрузка матрицы регистров при введении параллельно-конвейерной диспетчеризации.

Будем рассматривать предельное значение загрузки МР. Первоначально предположим, что в матрицу регистров нельзя записывать новые пакеты, пока в ней имеются загруженные ранее не обработанные пакеты (подобный режим реа­лизован в параллельно-последовательном КУ [2]). Поскольку за один цикл (такт) ретрансляции в матрицу регистров может быть записано не более nпакетов, при этом следующее множество пакетов записывается только после освобождения МР, предельная загрузка МР при указанных условиях составит

Выведем выражение для вычисления предельной загрузки МР при исполь­зовании ПКП-метода, используя известные формулы сумм [4].

Очевидно, что загрузка матрицы станет предельной, если за каждый такт ретрансляции из нее будет выдаваться наименьшее возможное число пакетов (что составляет 1 пакет в такте 0, 2 пакета в такте 1, 3 пакета в такте 2 и т.д., nпакетов в тактах n -1, n, n +1, n + 2,...), а записываться - наибольшее возможное их число (что составляет nпакетов), причем такой режим будет иметь место неограниченно долго. Указанные условия обеспечиваются, если первые nпакетов будут записаны в одну (любую) строку МР, например, в i-ю, i∈{1,2,..., n}. Не нарушая общности рассуждений, можно считать i = x. Поскольку может быть выдан лишь один пакет (из n-го столбца), ко второму такту в матрице их останется n -x.

Второе множество из nпакетов должно быть записано в любую из остав­шихся свободных строк, например, в j-ю строку, j∈{1,2,..., n}, j ≠ i.

Третье множество из nпакетов будет записано в любую из оставшихся сво­бодных строк, например, в l-ю строку, l∈{1,2,..., n}, l ∉{i, j}. Исключением бу­дут пакеты c_nи c_n-1. Пакет c_n-1при этом может быть записан в любую строку, кроме j-й. Пакет c_nможно загрузить в любую строку. Аналогично описанному считаем, что пакеты c_nи c_n-1записываются в l-ю строку вместе с остальными па­кетами третьего множества. В результате в матрице регистров будет (2n- 3) + n = 3n -3 пакетов. Из них в данном такте может быть выдано лишь 3 пакета (из регистров R _n-2), R_j( _n-1) и R_ln). Таким образом, к четвертому такту ре­трансляции в МР останется 3n- 6 пакетов. Не нарушая общности, можно считать l = 3.

Дальнейшее заполнение матрицы регистров пакетами и выдача пакетов на выходы происходит аналогичным способом, пока не будет заполнена последняя свободная строка матрицы. В результате в матрице регистров окажется пакетов, из числа которых можно вы­дать nпакетов (по одному из каждой строки МР). После их выдачи в матрице

Несложно убедиться, что- предельное число пакетов, которые мо­

гут быть размещены в матрице регистров, и что дальнейшая перезапись пакетов в МР не будет приводить к росту ее загрузки.

Описанный выше порядок заполнения МР пакетами схематично поясняется на рис. 2.6. Здесь пакеты, которые будут выданы в текущем такте ретрансляции, отображены закрашенными кружками.

Исходя из всего сказанного, получим выражение для оценки предельной за­грузки МР при использовании ПКП-метода:

Несложно доказать, чтоДействительно, рассмотрим рис. 2.6

(такт n). Предположим, что в такте n +1 в матрице регистров окажется n + 2 паке­тов. Однако это возможно лишь тогда, когда в матрицу будет записано nпакетов, а выдано n -1 пакетов. Выдача n -1 пакетов, в свою очередь, возможна лишь при наличии одной пустой строки. Получили противоречие.

На рис. 2.7 представлены графики зависимости предельной загрузки МР от числа входов/выходов КУ nпри отсутствии конвейеризации (ПП-коммутация) и при использовании разработанного ПКП-метода, полученные по формулам (2.3) и (2.4) соответственно. Из приведенных графиков видно, что с ростом числа вхо­

дов/выходов КУ загрузка МР при отсутствии конвейеризации асимптотически стремится к нулю, а в случае ПКП-метода приближается к 0.5.

Рисунок 2.6. Иллюстрация порядка заполнения МР при определении ее предельной загрузки

Следует отметить, что выведенные зависимости соответствуют идеальному случаю, когда загрузка пакетов из входных очередей в матрицу регистров осу­ществляется без ограничений, и поэтому представляют собой верхние границы. В реальных условиях, из-за того, что вероятность блокировки передачи пакета в МР отлична от нуля, средняя загрузка матрицы будет значительно ниже (см. подраз­дел 3.7).

Рисунок 2.7. Графики зависимости предельной загрузки МР от числа входов/выходов КУ при отсутствии конвейеризации (ПП-коммутация) и при использовании ПКП-метода

2.6.