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

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

Прежде чем перейти к рассмотрению алгоритма, введем ряд дополнитель­ных обозначений. Определим индикаторную функцию 5такую, чтс, ес­

ли в очереди Q₁в данный момент времени имеется хотя бы один пакет, и 5 (Qi) = 0, если очередь Q₁пуста. Через условимся обозначать операции чтения содержимого регистра и записи значения в регистр.

Граф-схема разработанного алгоритма коммутации пакетов изображена на рис. 2.4.

Алгоритм работает циклически, пока выполняется условие наличия пакетов хотя бы в одной очереди:(вершина 3). Циклическая часть алгоритма

включает входную параллельную секциюцентральный

последовательный участок (вершины 9 и 10), выходную параллельную секцию (вершиныфинальный последовательный участок (вершины 13 и

14). /-я ветвь входной параллельной секции описывает процесс передачи пакетов из очереди Q_iв i-й столбец МРі включает 5 шагов: 1) считывание пакета

из очереди (оператор 4.i); 2) определение строки МР, в которую должен быть за­писан этот пакет согласно реализуемому алгоритму маршрутизации (оператор 5.i); 3) проверка занятости регистра, выбранного для записи пакета (условие 6.i);

4) перенос пакета из очереди с выбранный регистр, если этот регистр свободен, обнуление веса соответствующей вершины графа совместности (оператор 7.i);

5) сдвиг очереди (оператор 8.i).

Рисунок 2.4.

На центральном последовательном участке осуществляется построение графа совместности Γ_kна ранее определенном носителе F_k(вершина 9), выделя­ется клика Γk, имеющая максимальный суммарный вес вершин (вершина 10), и тем самым выбирается множество пакетов Fkдля выдачи на выходы КУ. Отме­тим, что формирование графа Γ_kпроисходит автоматически на основе уже полу­ченного распределения пакетов по регистрам МР. По сути, это фиктивная опера­ция, не требующая дополнительного времени на выполнение. Выбор клики в со­ответствии с вершиной 10 алгоритма производится путем построчно­параллельного анализа состояния МР (т.е. фактически вершина 10 является па­раллельной секцией, включающей nветвей). В каждой строке выбирается пакет, вершина которого в графе Γ_kимеет максимальный вес среди пакетов, отображен­ных на ту же строку. Этот процесс требует O (n) временных единиц при последо­вательной реализации и O (1) временных единиц в случае параллельного вычис­ления максимума. При использовании пирамидальной схемы нахождения макси­мума, процесс займет O (log n) единиц времени. Поскольку строки матрицы реги­стров рассматриваются параллельно, весь процесс выделения клики потребует O (1) единиц времени в лучшем случае (параллельная схема) и O (n) - в худшем случае (последовательная схема). Следует подчеркнуть, что решение задачи вы­деления клики, отвечающей условию (2.2), за столь малое время достигается бла­годаря специальному виду рассматриваемых графов, отображенных на матрич­ную структуру.

Следом за вершинами 9 и 10 алгоритма выполняется выходная параллель­ная секция. Ее i-я ветвь описывает процесс выдачи пакета из i-й строки МР на вы­ход O_i (i = 1, n) и включает два шага: 1) выбор регистра B_jj, в котором находится подлежащий выдаче пакет c_j(оператор 11. i); 2) выдачу пакета c_jна выход O_iи обнуление регистра B_j(оператор 12.

выдать на текущем шаге (оператор 13), и выполняется переход к очередному цик­лу ретрансляции пакетов (оператор 14). Отметим, что все пакеты обрабатываются в вершине 13 одновременно.

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

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

Исходное состояние МР в начале работы алгоритма (k = 0) условно принято таким, как показано на рис. 2.5,а. Дальнейшее изменение состояния матрицы при k = 1,2,...,8 отображено на рис. 2.5,6-и, соответственно. Очередное множество за­гружаемых в МР пакетов на каждом шаге определяется случайным образом так, чтобы проиллюстрировать возможные варианты ретрансляции пакетов. Выделяе­мые на каждом шаге клики графа совместности показаны пунктиром; входящие в них вершины закрашены.

Рисунок 2.5. Иллюстрация работы алгоритма коммутации пакетов

Анализируя рис. 2.5, можно увидеть, что на некоторых шагах в матрице ре­гистров оказывается более nпакетов. Это объясняется тем, что не все ранее за­груженные пакеты удается выдать за 1 цикл ретрансляции, при этом в следующем цикле в МР подгружаются новые пакеты (реализуется конвейерный режим обра­ботки).

2.5.