<<
>>

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

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

Целью диспетчеризации является выбор подмножеств пакетов для выда­чи в каждом такте работы КУ таким образом, чтобы сократить среднее время пе­редачи одного пакета.

Формализуем определение порядка выдачи пакетов из матрицы регистров.

Обозначим через Fkмножество пакетов, находящихся в матрице Bна k-м такте ретрансляции, k = 0,1,2,.... На множествеопределим функцию Sk, та­кую, что, если регистр Bjсодержит некоторый пакет cqв k-м такте

ретрансляции,если регистр Bjсвободен. Таким образом:

36

На рис. 2.2 дана графическая иллюстрация определения функции Sk. Здесь квадратами показаны отдельные регистры (регистровые ячейки) МР, а вложенные

Рисунок 2.2. Определение функции Skдля заданного распределения пакетов множества Fkв матрице регистров

На множестве пакетов Fkопределим отношение совместности

такое, что

37

Еслито пакеты cqи crбудем считать совместными (такие пакеты

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

Через отношение αkможно определить также отношение несовместности

Введем в рассмотрение граф совместности. Вершины этого

графа соответствуют пакетам множества Fk, а ребра - отображают их совмест­ность. Взвесим вершины графа Γ kнеотрицательными целыми числамиВес

τqвершины cqбудем определять временем, которое пакет cqпровел в матрице регистров, выраженным в числе тактов работы КУ. Сразу после записи пакета cq в МР полагаем τ = 0.

q

На рис. 2.3 в качестве примера показан взвешенный граф совместности Γk для случая, представленного на рис. 2.2 (значения весов выбраны условно и ука­заны внутри вершин).

Выделим в графе Γ kкликутакую, что:

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

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

Учет весов вершин при выделении кли­ки Γkпозволяет реализовать относительный приоритет при выборе пакетов для выдачи, ограничивая время пребывания пакетов в матрице регистров и позволяя реализовать диспетчеризацию пакетов с учетом времени их обработки.

Рисунок 2.3. Взвешенный граф совместности Γkдля случая рис. 2.2

Для графа Γ k, изображенного на рис. 2.3, выделяется клика Γkс носителем (пунктирная линия на рис. 2.3). Для этой клики Сумма весов остальных трех клик, имеющихся в данном графе, равна

1, 1 и 0.

Учитывая введенное формализованное представление, один такт (цикл) ре­трансляции пакетов при использовании ПКП-метода можно описать приведенным ниже псевдокодом. Далее для удобства через clи B(μ(cl)) условимся обозначать соответственно пакет, находящийся в голове очереди Ql, и регистр матрицы B, выбранный для записи этого пакета согласно реализуемому алгоритму маршрути­зации.

НАЧАЛО ПРОЦЕДУРЫ «Цикл ретрансляции пакетов»

ПРИНЯТЬ k = 0

ВЫПОЛНЯТЬ ПОКА хотя бы одна очередь Q1не пуста

СЧИТАТЬ пакеты из не пустых очередей [Ql}

ОПРЕДЕЛИТЬ множество регистров {b (μ( cl

ПЕРЕПИСАТЬ в матрицу Bвсе пакеты {cr}, для которых

КОНЕЦ ВЫПОЛНЯТЬ ПОКА

КОНЕЦ ПРОЦЕДУРЫ «Цикл ретрансляции пакетов»

Рассматривая приведенный выше псевдокод с привязкой к структурной мо­дели КУ (см. рис. 2.1), уточним функции элементов данной модели. Передача в МР считанных из очередей пакетовобеспечивается коммутирующими эле­ментами Rx, R2,..., Rn. Проверка условия /и блокировка передачи

пакетов в МР (HOL blocking) осуществляется коммутирующими элементами Kx,K2,...,Knи клапанами Gx,G2,...,Gn. Формирование клики Γ'обеспечивается за счет матричной организации КУ, при которой совместные пакеты автоматиче­ски попадают в разные строки МР, а учет весов вершин с целью выбора множе­ства Fс максимальным суммарным весом вершин реализуется правилами φx2,...,φn, определяющими работу коммутирующих элементов Lx,L2,.,Ln.

2.4.

<< | >>
Источник: Мохаммед Ажмаль Джамиль Абдо. МЕТОД, АЛГОРИТМ И УСТРОЙСТВО КОММУТАЦИИ С ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ В МАТРИЧНЫХ МУЛЬТИПРОЦЕССОРАХ. Диссертация на соискание ученой степени кандидата технических наук. КУРСК - 2019. 2019

Еще по теме Определение порядка выдачи пакетов из матрицы регистров:

  1. Оценка эффективности использования матрицы регистров коммутационного устройства
  2. 3.7. Оценка средней загрузки матрицы регистров
  3. Общие особенности разработанного метода коммутации пакетов
  4. 4. Материальная ответственность в административном порядке и ее субъекты.
  5. Структурная модель устройства коммутации с параллельно­конвейерной диспетчеризацией пакетов
  6. Тема: РАССМОТРЕНИЕ ДЕЛ В ПОРЯДКЕ УПРОЩЕН­НОГО ПРОИЗВОДСТВА. ПРИКАЗНОЕ ПРОИЗВОДСТВО В АРБИТРАЖНОМ ПРОЦЕССЕ
  7. МЕТОД И АЛГОРИТМ КОММУТАЦИИ С ПАРАЛЛЕЛЬНО­КОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ. СТРУКТУРНАЯ МОДЕЛЬ КОММУТАЦИОННОГО УСТРОЙСТВА
  8. Оценка быстродействия коммутационного устройства при использовании параллельно-конвейерной диспетчеризации пакетов
  9. Алгоритм коммутации с параллельно-конвейерной диспетчеризацией пакетов
  10. ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК КОММУТАЦИОННОГО УСТРОЙСТВА С ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ
  11. Тема: ПРОИЗВОДСТВО ПО ПЕРЕСМОТРУ СУДЕБНЫХ АКТОВ В ПОРЯДКЕ НАДЗОРА. ПРОИЗВОДСТВО ПО ПЕ­РЕСМОТРУ СУДЕБНЫХ АКТОВ ПО НОВЫМ И ВНОВЬ ОТКРЫВШИМСЯ ОБСТОЯТЕЛЬСТВАМ
  12. Структура и формат передаваемых пакетов
  13. Оценка полного времени прохождения пакетов через коммутационное устройство
  14. МЕТОДЫ И УСТРОЙСТВА КОММУТАЦИИ ПАКЕТОВ В МАТРИЧНЫХ МУЛЬТИПРОЦЕССОРАХ
  15. Определение текучести
  16. Определение насыпной плотности
  17. СТРУКТУРНО-ФУНКЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ КОММУТАЦИОННОГО УСТРОЙСТВА С ПАРАЛЛЕЛЬНО­КОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ
  18. Определение твердости
  19. Определение гранулометрического состава
  20. 2.3.5 Определение твердости