Оценка быстродействия коммутационного устройства при использовании параллельно-конвейерной диспетчеризации пакетов
Скоростные характеристики КУ определяются временем прохождения (ретрансляции) пакетов через МР и не зависят от организации входной части, поскольку обработка пакетов в разных входных буферах осуществляется независимо.
Таким образом, для определения быстродействия КУ достаточно оценить среднее время ретрансляции пакета через матрицу регистров и найти обратную ему величину. Нижнюю границу указанного времени можно оценить аналитически, рассматривая всевозможные варианты распределения пакетов в МР.
Условимся различать среднее время ретрансляции пакета через МР, фактическое время прохождения пакета через МР.
Определение 2.1.Под средним временем ретрансляции пакета через МР будем понимать отношение времени прохождения через МР некоторого множества пакетов к мощности этого множества.
Определение 2.2.Под фактическим временем прохождения пакета через МР условимся понимать минимально возможное время последовательного физического прохождения пакета с выхода соответствующей очереди через МР на требуемый выход КУ. Это время соответствует одному такту (циклу) ретрансляции.
Отметим, что среднее время ретрансляции пакета через МР может быть меньше такта ретрансляции вследствие распараллеливания обработки множества пакетов в матрице. Например, множество из 5 пакетов может быть передано за 3 такта и на один пакет, таким образом, придется 0.6 такта ретрансляции. Фактическое же время прохождения пакета через МР, очевидно, не может быть меньше такта ретрансляции. Однако оно может быть больше такта ретрансляции, что обусловлено ожиданием выдачи пакета согласно заданной дисциплине обслуживания.
Обозначим через tдлительность такта (цикла) ретрансляции КУ. В эту длительность войдут фазы загрузки пакетов из входных буферов в МР, анализа способа расположения пакетов в матрице и выдачи на выходы КУ выбранных пакетов. Каждой из этих трех фаз соответствует один микротакт длительностью который является минимальным временным интервалом функционирования устройства.
Предположим, что интенсивность входящих потоков пакетов такова, что в каждой очереди всегда находится хотя бы один пакет. Тогда для передачи nпакетов, находящихся в головных регистрах очередей Qx,Q2,...,Qn, при последовательной организации КУ потребуется
51 тактов ретрансляции. Очевидно, что среднее время ретрансляции одного пакета t0 при чисто последовательной обработке не зависит от параметров устройства и входных потоков пакетов, и равно t.
При тех же условиях время ретрансляции nпакетов через МР при ПП- коммутации (без конвейеризации) составит [2]:
где- вероятность того, что nпакетов разместятся в МР так, что хотя бы в одной из строк окажется lпакетов, а в остальных строках будет не более lпакетов.
Значение суммы в формуле (2.5) фактически дает наиболее вероятное число пакетов, размещенных в одной строке МР. Оно и определяет число тактов ретрансляции, требуемых для выдачи nпакетов. Из этой формулы нетрудно получить среднее время ретрансляции одного пакета через МР при ПП-коммутации согласно определению 2.1:
Предполагая, что все возможные способы размещения пакетов в матрице регистров равновероятны, можно получить выражение для вычисления вероятности
где Qn- число всевозможных способов размещения nпакетов в матрице; Qnl- число способов размещения nпакетов в матрице таким образом, что хотя бы в одной из строк окажется lпакетов, а в остальных строках будет не более lпакетов.
Поскольку любой пакет записывается в любую строку МР независимо от оставшихся n -1 пакетов:
52
что соответствует общему числу размещений из nэлементов по nсо всеми возможными повторениями [23].
Выражение для вычисления Q1nможно получить путем анализа всевозможных вариантов расположения пакетов в МР с повторениями в одноименных строках не более чем по lраз, причем таким образом, что хотя бы в одной из строк имеется ровно lпакетов:
где p- дополнительный параметр, обозначающий число строк в текущей подматрице регистров (первоначальнцелая часть числа
- число бесповторных сочетаний из xэлементов по у- число бес-
повторных размещений из xэлементов по у; χ(a) - дополнительная функция: χ(a) = a, если a > 0; χ(a) = 1 иначе.
Покажем справедливость формулы (2.9).
Случай l = 0 очевиден. При l = 1 оставшиеся nпакетов размещаются в pнезанятых строках текущей подматрицы МР (p ≥ n) по одному без повторений, что, очевидно, составляет Anpспособов. При l = nмножество из nоставшихся пакетов записывается в одну строку МР, а поскольку таких строк осталось p, получаем p способов размещения.
Проанализируем возможные способы размещения пакетов в МР при
Ясно, что в множестве из nпакетов можно выделить не более
53 подмножеств по lпакетов в каждомПри этом останется подмножество
, содержаще
пакетов, которые могут быть размещены в сво
бодных строках произвольным образом.
Необходимо учесть, что возможны комбинации размещения пакетов, содержащие одно подмножество S1, два подмножества S1, S2, и наконец

этом должны размещаться не более чем по l -1 в одной строке). Все эти комбинации являются альтернативными, поэтому суммируются.
В подмножество S1войдут lиз nпакетов, поступивших в любые столбцы МР, что составляет C1nкомбинаций. В подмножество S2будут включены lиз n -1пакетов, поступивших в любые оставшиеся столбцы МР, что составляет комбинаций. Продолжая аналогично, увидим, что в подмножество
войдут lиз
пакетов, поступивших в любые оставшиеся столбцы МР, что составляет
омбинаций. Указанные сочетания являются независимыми и по
этому их числа перемножаются с учетом текущего числа подмножеств пакетов вариантов. Распределение подмножеств
среди pсвободных строк матрицы регистров осуществляется C1pспособами, без учета порядка выбора строк, что исключает повторяющиеся комбинации.
Внутренняя сумма в формуле (2.9) отражает возможные варианты размещения n - ilпакетов, не включенных в подмножества S1,S2,...,Si.
Верхний пределэтой суммызадает наибольшее число таких пакетов в строке.
Очевидно, что это значение не может быть больше l -x, так как иначе можно было бы сформировать еще одно подмножество из lпакетов Si+x. Рекуррентное вычисление значенияпо формуле (2.9) позволяет определить число вари
антов размещения оставшихся n - ilпакетов в свободных p - iстроках МР не более чем по rпакетов в одной строке. Поскольку эти способы размещения для разных значений rвзаимоисключающие, осуществляется суммирование их числа. Функция χ( a) позволяет избежать влияния нулевых значений внутренней суммы при miисключая тем самым некорректное обнуление слагаемых
внешней суммы выражения (2.9).
Для оценки времени ретрансляции пакетов при использовании ПКП-метода формула (2.5) в общем случае оказывается не пригодной, так как в некоторых столбцах матрицы регистров может оказаться более одного пакета (см., например, рис. 2.5, д-и). Учитывая сказанное, время прохождения пакетов через МР при ПКП-коммутации составит:
тактов ретрансляции, где- среднее число пакетов, которые в
данном такте удается переписать из входных очередей в матрицу с учётом занятости некоторых ее регистров- среднее число пакетов, не выданных в
предыдущих тактах и всё ещё находящихся в матрице регистров (из оценки предельной загрузки МР следует, что- вероятность того, что nпа
кетов располагаются в МР так, что хотя бы в одной из строк окажется ровно lпакетов, а в остальных строках будет не более lпакетов.
Следует отметить, что пакеты, которые будут записаны в МР в следующих тактах, никак не повлияют на время T2, рассчитанное для 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 подобное вычисление становится весьма трудоемким из-за необходимости перебора большого числа комбинаций значений ui∈{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 изображены графики зависимости величин txи t2от n, полученные с использованием формул (2.6) и (2.11). Единицей измерения величин tx, t2 является такт ретрансляции длительностью 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 представлены графики зависимости величин V1и V2от n, полученные исходя из значений t1и t2.
Рисунок 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 (что соответствует системам с двумерной матричной топологией) ускорение со-
Следует подчеркнуть, что все полученные в данном разделе оценки (t1, t2, V1, V2) представляют собой теоретические границы, поскольку вычисляются в идеализированных условиях. Одним из таких условий является допущение о равной вероятности всех способов размещения пакетов в матрице регистров. Гарантировать равновероятное распределение пакетов в МР при случайном независимом выборе строк матрицы при загрузке пакетов невозможно. В связи с этим реальные значения величин t1, t2,будут несколько ниже теоретических гра
ниц (см. подраздел 3.6).
Ускорение прохождения пакетов через матрицу регистров КУ и повышение загрузки МР должны также приводить к повышению пропускной способности устройства, однако теоретическая оценка эффекта затруднительна из-за необходимости учета множества параметров входящих потоков пакетов, которые имеют случайный характер. В связи с этим оценку полного времени ретрансляции пакета и пропускной способности КУ при использовании ПКП-метода выполним на основе имитационного моделирования.
Выводы
1. Разработанный метод коммутации пакетов отличается одновременной загрузкой множества пакетов во внутренний буфер из входных очередей без ожидания выдачи всех ранее принятых пакетов и способен обеспечить параллельную и независимую обработку пакетов во входном и выходном трактах коммутационного устройства. При этом формализация представления множества пакетов, находящихся во внутреннем буфере в каждом такте работы коммутационного устройства, в виде взвешенного графа совместности, отражающего возможность одновременной выдачи пакетов на выходы с учетом времени пребывания пакетов в матрице регистров, с последующим выделением клики этого графа, имеющей наибольший вес, позволяет минимизировать время ожидания пакета и, следовательно, повысить быстродействие коммутационного устройства. Случайный вы-
бор клики графа совместности при наличии нескольких равнозначных вариантов обеспечивает балансирование загрузки очередей при высокой интенсивности потоков пакетов.
2. Режим коммутации пакетов с параллельно-конвейерной диспетчеризацией позволяет увеличить предельную загрузку матрицы регистров, что способствует повышению эффективности использования матрицы регистров и пропускной способности коммутационного устройства.
3. Использование параллельно-конвейерной диспетчеризации с учетом времени обработки пакетов обеспечивает ускорение прохождения пакетов через матрицу регистров теоретически более чем на 41% по сравнению с параллельнопоследовательной коммутацией пакетов для всех практически значимых случаев.
3.
Еще по теме Оценка быстродействия коммутационного устройства при использовании параллельно-конвейерной диспетчеризации пакетов:
- ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК КОММУТАЦИОННОГО УСТРОЙСТВА С ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ
- МЕТОД И АЛГОРИТМ КОММУТАЦИИ С ПАРАЛЛЕЛЬНОКОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ. СТРУКТУРНАЯ МОДЕЛЬ КОММУТАЦИОННОГО УСТРОЙСТВА
- СТРУКТУРНО-ФУНКЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ КОММУТАЦИОННОГО УСТРОЙСТВА С ПАРАЛЛЕЛЬНОКОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ
- Алгоритм коммутации с параллельно-конвейерной диспетчеризацией пакетов
- Мохаммед Ажмаль Джамиль Абдо. МЕТОД, АЛГОРИТМ И УСТРОЙСТВО КОММУТАЦИИ С ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ В МАТРИЧНЫХ МУЛЬТИПРОЦЕССОРАХ. Диссертация на соискание ученой степени кандидата технических наук. КУРСК - 2019, 2019
- Оценка эффективности использования матрицы регистров коммутационного устройства
- Структурная модель устройства коммутации с параллельноконвейерной диспетчеризацией пакетов
- Оценка полного времени прохождения пакетов через коммутационное устройство
- Исследование быстродействия коммутационного устройства
- Оценка аппаратной сложности коммутационного устройства
- Методика исследования характеристик коммутационного устройства
- Исследование пропускной способности коммутационного устройства
- Структурная организация коммутационного устройства
- МЕТОДЫ И УСТРОЙСТВА КОММУТАЦИИ ПАКЕТОВ В МАТРИЧНЫХ МУЛЬТИПРОЦЕССОРАХ
- Функциональные схемы блоков коммутационного устройства
- Требования к функциональным блокам коммутационного устройства
- Особенности программной реализации имитационного моделирования коммутационного устройства