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

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

Условимся различать среднее время ретрансляции пакета через МР, факти­ческое время прохождения пакета через МР.

Определение 2.1.Под средним временем ретрансляции пакета через МР бу­дем понимать отношение времени прохождения через МР некоторого множества пакетов к мощности этого множества.

Определение 2.2.Под фактическим временем прохождения пакета через МР условимся понимать минимально возможное время последовательного физиче­ского прохождения пакета с выхода соответствующей очереди через МР на тре­буемый выход КУ. Это время соответствует одному такту (циклу) ретрансляции.

Отметим, что среднее время ретрансляции пакета через МР может быть меньше такта ретрансляции вследствие распараллеливания обработки множества пакетов в матрице. Например, множество из 5 пакетов может быть передано за 3 такта и на один пакет, таким образом, придется 0.6 такта ретрансляции. Фактиче­ское же время прохождения пакета через МР, очевидно, не может быть меньше такта ретрансляции. Однако оно может быть больше такта ретрансляции, что обу­словлено ожиданием выдачи пакета согласно заданной дисциплине обслужива­ния.

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

Предположим, что интенсивность входящих потоков пакетов такова, что в каждой очереди всегда находится хотя бы один пакет. Тогда для передачи nпаке­тов, находящихся в головных регистрах очередей Q_x,Q₂,...,Q_n, при последова­тельной организации КУ потребуется

51 тактов ретрансляции. Очевидно, что среднее время ретрансляции одного пакета t₀ при чисто последовательной обработке не зависит от параметров устройства и входных потоков пакетов, и равно t.

При тех же условиях время ретрансляции nпакетов через МР при ПП- коммутации (без конвейеризации) составит [2]:

где- вероятность того, что nпакетов разместятся в МР так, что хотя бы в од­ной из строк окажется lпакетов, а в остальных строках будет не более lпакетов.

Значение суммы в формуле (2.5) фактически дает наиболее вероятное число пакетов, размещенных в одной строке МР. Оно и определяет число тактов ре­трансляции, требуемых для выдачи nпакетов. Из этой формулы нетрудно полу­чить среднее время ретрансляции одного пакета через МР при ПП-коммутации согласно определению 2.1:

Предполагая, что все возможные способы размещения пакетов в матрице регистров равновероятны, можно получить выражение для вычисления вероятно­сти

где Q_n- число всевозможных способов размещения nпакетов в матрице; Q_n^l- число способов размещения nпакетов в матрице таким образом, что хотя бы в одной из строк окажется lпакетов, а в остальных строках будет не более lпаке­тов.

Поскольку любой пакет записывается в любую строку МР независимо от оставшихся n -1 пакетов:

52

что соответствует общему числу размещений из nэлементов по nсо всеми воз­можными повторениями [23].

Выражение для вычисления Q¹_nможно получить путем анализа всевозмож­ных вариантов расположения пакетов в МР с повторениями в одноименных стро­ках не более чем по lраз, причем таким образом, что хотя бы в одной из строк имеется ровно lпакетов:

где p- дополнительный параметр, обозначающий число строк в текущей подмат­рице регистров (первоначальнцелая часть числа

- число бесповторных сочетаний из xэлементов по у- число бес-

повторных размещений из xэлементов по у; χ(a) - дополнительная функция: χ(a) = a, если a > 0; χ(a) = 1 иначе.

Покажем справедливость формулы (2.9).

Случай l = 0 очевиден. При l = 1 оставшиеся nпакетов размещаются в pне­занятых строках текущей подматрицы МР (p ≥ n) по одному без повторений, что, очевидно, составляет Aⁿ_pспособов. При l = nмножество из nоставшихся пакетов записывается в одну строку МР, а поскольку таких строк осталось p, получаем p способов размещения.

Проанализируем возможные способы размещения пакетов в МР при

Ясно, что в множестве из nпакетов можно выделить не более

53 подмножеств по lпакетов в каждомПри этом останется подмноже­ство, содержащепакетов, которые могут быть размещены в сво­

бодных строках произвольным образом.

этом должны размещаться не более чем по l -1 в одной строке). Все эти комби­нации являются альтернативными, поэтому суммируются.

В подмножество S₁войдут lиз nпакетов, поступивших в любые столбцы МР, что составляет C¹_nкомбинаций. В подмножество S₂будут включены lиз n -1пакетов, поступивших в любые оставшиеся столбцы МР, что составляет комбинаций. Продолжая аналогично, увидим, что в подмножествовойдут lиз пакетов, поступивших в любые оставшиеся столбцы МР, что со­ставляетомбинаций. Указанные сочетания являются независимыми и по­

этому их числа перемножаются с учетом текущего числа подмножеств пакетов вариантов. Распределение подмножеств среди pсвободных строк матрицы регистров осуществляет­ся C¹_pспособами, без учета порядка выбора строк, что исключает повторяющиеся комбинации.

Внутренняя сумма в формуле (2.9) отражает возможные варианты размеще­ния n - ilпакетов, не включенных в подмножества S₁,S₂,...,S_i.

этой суммызадает наибольшее число таких пакетов в строке.

Очевидно, что это значение не может быть больше l -x, так как иначе можно бы­ло бы сформировать еще одно подмножество из lпакетов S_i+x. Рекуррентное вы­числение значенияпо формуле (2.9) позволяет определить число вари­

антов размещения оставшихся n - ilпакетов в свободных p - iстроках МР не бо­лее чем по rпакетов в одной строке. Поскольку эти способы размещения для раз­ных значений rвзаимоисключающие, осуществляется суммирование их числа. Функция χ( a) позволяет избежать влияния нулевых значений внутренней суммы при miисключая тем самым некорректное обнуление слагаемых

внешней суммы выражения (2.9).

Для оценки времени ретрансляции пакетов при использовании ПКП-метода формула (2.5) в общем случае оказывается не пригодной, так как в некоторых столбцах матрицы регистров может оказаться более одного пакета (см., например, рис. 2.5, д-и). Учитывая сказанное, время прохождения пакетов через МР при ПКП-коммутации составит:

тактов ретрансляции, где- среднее число пакетов, которые в

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

предыдущих тактах и всё ещё находящихся в матрице регистров (из оценки пре­дельной загрузки МР следует, что- вероятность того, что nпа­

кетов располагаются в МР так, что хотя бы в одной из строк окажется ровно lпа­кетов, а в остальных строках будет не более lпакетов.

Следует отметить, что пакеты, которые будут записаны в МР в следующих тактах, никак не повлияют на время T₂, рассчитанное для k-го такта. Действитель­но, если новый пакет будет записан в пустую строку матрицы, то он будет выдан

одновременно с уже имеющимися пакетами. Если же этот пакет будет переписан в непустую строку, то соответствующая ему вершина графа совместности полу­чит нулевой вес и не будет включена в клику Γkсогласно правилу (2.2). Таким образом, вновь поступающие в МР пакеты можно не рассматривать при оценке времени ретрансляции.

Из формулы (2.10) согласно определению 2.1 несложно получить среднее время ретрансляции пакета через МР в ПКП-устройстве:

Вывод формулы для расчета вероятностиможно выполнить аналогично выводу выраженияучитывая возможное присутствие в столбцах нескольких пакетов одновременно.

Считая все возможные способы размещения пакетов в МР равновероятны­ми, получим:

где Q-- число всевозможных способов размещения nпакетов в матрице;

- число способов размещения nпакетов в матрице таким образом, что хотя бы в одной из строк будет точно lпакетов, а в остальных строках - не более lпа­кетов.

Для определения Q-можно использовать следующую очевидную формулу:

Эта формула отражает все способы размещения пакетов в МР, возможные при за­данных значениях iи n. Она учитывает ситуации, когда при некоторых значениях nпакеты невозможно разместить в матрице так, чтобы хотя бы в одной строке было ровно iпакетов, а в остальных - не более iпакетов (в таких случаях Подобные случаи обсуждаются ниже при выводе выражения для

Чтобы вывести выражение для вычислениявыполним анализ всевоз­можных вариантов размещения пакетов в МР с повторениями в одноименных строках не более чем по lраз, причем таким образом, что хотя бы в одной из строк имеется ровно lпакетов. Будем учитывать, что в одном и том же столбце матрицы может быть несколько пакетов. При выводе воспользуемся известными упрощающими соотношениями [4, 23].

Случай l = 1, очевидно, возможен только при n = n. Пакеты разных строк в этом случае могут быть расположены в любых столбцах МР, поэтому:

Случай l = 2 имеет место лишь тогда, когда n +1 ≤ n ≤ 2n. Действительно, при n 2nнеизбежно появление строки, содержащей 3 пакета. Пакеты различных строк (которых в каждой строке 1 или 2) могут быть размещены в произвольных столбцах матрицы, таким обра­зом:

где- число пакетов, находящихся в i-й строкепричем спра­

ведливо следующее условие полноты:

Случай l = 3 возможен, если только n + 2 ≤ n ≤ 3n. В самом деле, при n 3nнеизбежно наличие стро­ки, содержащей 4 пакета. Пакеты разных строк (которых в каждой строке 1, 2 или 3) могут быть размещены в любых столбцах МР, поэтому:

57

Продолжая аналогичным образом, видим, что общий случай возможен, если имеет место следующее неравенство:

Пакеты различных строк (которых в каждой строке теперь 1, 2, ..., либо l) могут быть размещены в произвольных столбцах МР. Таким образом:

іричем из условия максимума загрузки МР следует, что:

Учитывая, что формулу (2.14) можно свести к видуоконча­

тельно придем к следующему выражению:

Перемножение в формуле (2.21) выполняется по всем комбинациям из n значений u_ι∈{1,2,..., l}, при которых остается верным условие полноты (2.16). При l > x подобное вычисление становится весьма трудоемким из-за необходимо­сти перебора большого числа комбинаций значений u_i∈{1,2,..., l}, поэтому целе­сообразно перейти к рекуррентному представлению формулы (2.21), взяв за осно­ву выражение (2.9):

58 где параметр pобозначает число строк текущей подматрицы МР, которое умень­шается по мере реализации вычисления (изначально считается p ? n); дополни­тельная функция ζ определяется следующим образом:

Использование функции ζ позволяет заранее исключить ветви дерева рекуррент­ных вычислений, в которых будут нарушены условия (2.16), (2.18). Например, при p ? n = 4, n = 5 и l = 2 пакеты невозможно разместить в МР так, чтобы не оста­лось пустых строк (нарушается условие (2.18)).

Покажем справедливость формулы (2.22).

Первоначально рассмотрим терминальные случаи. Условие (p +1 -1 >n) v (pl n.

На рис. 2.8 изображены графики зависимости величин t_xи t₂от n, получен­ные с использованием формул (2.6) и (2.11). Единицей измерения величин t_x, t₂ является такт ретрансляции длительностью t. Тот факт, что для ретрансляции па­кета через МР требуется время, меньшее t, связан с эффектом ускорения вслед­ствие параллельной обработки множества пакетов (см. определение 2.1). Так, например, при n = 5 даже при отсутствии конвейеризации пакет проходит через матрицу регистров в среднем теоретически за 0.457281временных единиц. При

этом для ретрансляции n = 5пакетов требуется 5 ·0.45728t = 2.2864tвременных единиц, что примерно в 2.187 раза быстрее, чем при чисто последовательной об­работке пакетов. Быстродействие КУ при этом теоретически составляет примерно 2.187 пакета/такт ретрансляции. В случае ПКП-коммутации при n = 5каждому пакету необходимо в среднем 0.322151временных единиц для прохождения через МР. Для ретрансляции n = 5 пакетов требуется 5 · 0.322151 ≈ 1.61tвременных еди­ниц, что примерно в 3.1 раза быстрее, чем при последовательной обработке. Быстродействие КУ при этом теоретически равно примерно 3.104 пакета/такт ре­трансляции.

На рис. 2.9 представлены графики зависимости величин V₁и V₂от n, полу­ченные исходя из значений t₁и t₂.

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

Из рис. 2.8 и 2.9 видно, что введение параллельно-конвейерной диспетчери­зации пакетов обеспечивает скоростные преимущества при любых значениях n. Так, например (см. рис. 2.8), при n = 5 пакет проходит через матрицу регистров в среднем за 0.457281временных единиц при ПП-коммутации и примерно за 0.322151временных единиц при ПКП-коммутации. Быстродействие КУ при этом повышается (см. рис. 2.9) с 2.187 до 3.104 пакетов/такт ретрансляции, т.е. при­мерно в 1.419 раза. При n = 10 согласно рис. 2.8 имеем соответственно 0.274871 без конвейеризации и 0.186601для ПКП-метода, при этом быстродействие КУ увеличивается (см. рис. 2.9) с 3.638 до 5.359 пакетов/такт ретрансляции, т.е. при­мерно в 1.473 раза. При n = 15 (см. рис. 2.8) имеем 0.20221tдля ПП-коммутации и 0.134211для ПКП-метода соответственно, а быстродействие КУ согласно рис. 2.9 возрастает с 4.945 до 7.451 пакетов/такт ретрансляции, т.е. примерно в 1.507 раза.

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

На рис. 2.10 представлен график зависимости отношенияот n. Соглас­

но этому графику минимальное преимущество от использования конвейеризации составляет 12.5% (при n = 2). Отметим, однако, что случаи n < 5 являются не ти­пичными для мультипроцессоров рассматриваемого класса и поэтому практиче­ски не значимы. В практически значимых случаях (n ≥ 5) согласно рис. 2.10 ПКП- метод ускоряет прохождение пакетов через МР более чем на 41%. Так, при n = 5 (что соответствует системам с двумерной матричной топологией) ускорение со-

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

ниц (см. подраздел 3.6).

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

Выводы

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

бор клики графа совместности при наличии нескольких равнозначных вариантов обеспечивает балансирование загрузки очередей при высокой интенсивности по­токов пакетов.

2. Режим коммутации пакетов с параллельно-конвейерной диспетчериза­цией позволяет увеличить предельную загрузку матрицы регистров, что способ­ствует повышению эффективности использования матрицы регистров и пропуск­ной способности коммутационного устройства.

3. Использование параллельно-конвейерной диспетчеризации с учетом времени обработки пакетов обеспечивает ускорение прохождения пакетов через матрицу регистров теоретически более чем на 41% по сравнению с параллельно­последовательной коммутацией пакетов для всех практически значимых случаев.

3.