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

РАСЧЕТНО-ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Курсового проекта на тему

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

по дисциплине

«Вычислительные системы»

Реферат

РПЗ 30 с., 4 табл., 16 рис., 6 источников, 7 прил.

ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ, НИТИ, ЦИРКУЛЯНТА, ПРОГРАММНЫЙ МОДУЛЬ, ОБЩАЯ ПАМЯТЬ.

Объектом проектирования является вычислительная система.

Цель работы - спроектировать вычислительную систему (ВС) с оптимальным временем решения задачи в узлах ВС.

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

Материалы по курсовой работе представлены в виде расчетно-пояснительной записки.

Оглавление

Введение

1.Теоретическая часть

1.1Понятие о современных вычислительных системах

1.2 Структура ВС типа «Циркулянт»

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

3. Распределение операторов по ВМ вычислительной системы с распределенной памятью для информационно-логической граф-схемы

3.1 Построение матрицы следования ИЛГ

3.2 Определение ранних сроков окончания выполнения операторов

3.3 Распределение нитей на структуре типа циркулянта

Заключение

Список используемой литературы

Приложение

Перечень сокращений, условных обозначений, символов, единиц и терминов

процессор вычислительный алгоритм модуль

ВС - вычислительная система,

ВМ - вычислительный модуль (вычислитель),

ИЛГ - информационно-логическая граф-схема,

ИГ - информационная граф-схема,

КС - компьютерная система,

МПС - многопроцессорная система,

ЭВМ - электронно-вычислительная машина.

Введение

Многопроцессорные системы с каждым годом всё шире используются крупными компаниями и научными учреждениями для обработки и хранения больших массивов данных. Так, вычислительные кластеры применяются преимущественно для решения сложных инженерных и научных задач: расчёт параметров конструкции ракеты-носителя для обеспечения заданных параметров надёжности; прогнозирование развития биологических и химических реакций, разработка лекарства против рака и пр.

В последние годы многопроцессорные системы стали входить и в жизнь массового пользователя: современные программы (например, трёхмерные игры) предъявляют высокие требования к скорости обработки данных (видеоданных), для чего целесообразно использовать несколько процессоров или процессорных ядер, работающих параллельно. Итак, современный персональный компьютер представляет собой простейшую разновидность многопроцессорной системы.

Для эффективного использования многопроцессорных систем необходимо:

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

.        использовать специальные алгоритмы (планировщики), которые позволят распределить операторы параллельных алгоритмов по процессорам ВС наиболее оптимальным образом.

Планировщик - часть основного алгоритма, служащая для обеспечения эффективного выполнения основного алгоритма на конкретной ВС.

При этом алгоритмы-планировщики могут использовать различные критерии оптимизации:

         минимизация времени выполнения задачи;

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

         обеспечение максимальной эффективности использования процессоров ВС;

         прочие.

Сложность разработки планировщика связана с некоторыми сложностями:

         анализ большого количества условий;

         рассмотрение множества различных ситуаций, которые возникают при распределении операторов по нитям и нитей по процессорам ВС;

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

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

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

1.Теоретическая часть

1.1    Понятие о современных вычислительных системах

Параллельные вычислительные системы (ВС) являются одними из самых перспективных направлений увеличения производительности вычислительных средств. При решении задач распараллеливания существует два подхода:

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

2.      Имеется класс задач, для решения которых необходимо спроектировать параллельную вычислительную систему, минимизирующую время решения поставленной задачи, при минимальных затратах на её проектирование.

При создании параллельных вычислительных систем учитываются различные аспекты их эксплуатации, такие как множественность решаемых задач, частоту их решения, требования к времени решения и т.д., что приводит к различным структурным схемам построения таких систем. Перечислим их в порядке возрастания сложности:

·   однородные многомашинные вычислительные комплексы (ОМВК), которые представляют собой сеть однотипных ЭВМ;

·        неоднородные многомашинные вычислительные комплексы (НМВК), которые представляют собой сеть разнотипных ЭВМ;

·        однородные многопроцессорные вычислительные системы (ОМВС), которые представляют собой ЭВМ с однотипными процессорами и общим полем оперативной памяти или без него;

·        неоднородные многопроцессорные вычислительные системы (НМВС), которые представляют собой системы с разнотипными процессорами и общим полем оперативной памяти или без него.

Система, представленная множеством описаний W={K,A}, где K - описание конструкций ВС, А - описание алгоритма работы множества вычислительных модулей, называется вычислительной. Описание К составляет множества значений {M,S}, где М - множество базовых вычислительных устройств {mi}, i=0, ... , N-1, где под базовыми вычислительными устройствами понимаются ЭВМ, процессоры, блоки памяти, внешние устройства. S - сеть связей между множествами элементов базиса.

В конструкцию К должны быть заложены следующие принципы:

а) параллелизм при обработке информации, т.е. организация вычислений одновременно на множестве вычислительных модулей М с организацией в случае необходимости обмена данными через сеть S;

б) адаптация конфигурации сети S к решаемой задаче. Алгоритм А обеспечивает наряду с требуемой обработкой управление одновременной работой определённым множеством ВМ и необходимым обменом данными между ними.

Сеть S должна обеспечивать в каждый момент времени требуемый обмен данными между вычислительными модулями. Наиболее подходящей для этой цели является сеть по полному графу, т.е. связь каждого вычислительного модуля с каждым. Построение такой сети для большого количества вычислительных модулей, содержащихся в современных ВС, является сложной и дорогостоящей процедурой. В связи с чем, разрабатываются различные типы и конфигурации сетей, в которых обеспечиваются связи в зависимости от различных требований. Очевидно, что в таких сетях, как правило, возникает необходимость транзитной передачи информации с помощью вычислительных модулей, попадающих в контур передачи информации. Такие передачи, естественно, требуют дополнительных затрат времени, в связи с чем возникает задача минимизации этих затрат c помощью выбора конструкций тех или иных разновидностей сетей с учетом структуры решаемых задач. Вследствие этого проблему выбора графа межмодульных связей необходимо рассматривать в нескольких аспектах:

·        минимизация времени выполнения межмодульных обменов;

·        максимизация числа одновременно выполняемых обменов;

·        максимальная сохранность связности при выходах из строя ВМ и линий.

1.2 Структура ВС типа «Циркулянт»

В настоящее время в индустрии ВС получили широкое распространение коммутационные структуры (КС) типа циркулянтных. Эти структуры традиционно представляются D_n-графами.

Циркулянтой называется D_n-граф, представляемый в виде множества , где N - число вершин в графе, вершины нумеруются от 0 до N-1,  - множество образующих чисел таких, что , а для чисел  наибольший общий делитель, равен 1, n - число образующих чисел. Вершина i соединяется ребрами с вершинами .

Если граф коммутационной структуры имеет равные степени вершин, то КС называется симметричной, и несимметричной - в противном случае.

Циркулянта относится к классу симметричных КС. Пример циркулянты, представленной в виде двумерной матрицы или хордового кольца показан на рисунке 1 для {7,1,3}.

Рисунок 1 - Пример циркулянты {7,1,3}, изображенной в виде двумерной матрицы (а) и хордового кольца (б)

Для выполнения работы задана циркулянта {49, 1, 3, 4, 5, 7}.

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

Вершина - оператор ИЛГ заданной задачи.

Вес вершины (P) - время расчета вершины на i-ом процессоре.

Степень вершины (Vi) - количество узлов, находящиеся от i-ой вершины на минимальном расстоянии.

Коэффициент передачи (pA) - время передачи между узлами ВС.

Комплексный узел - транзитный узел ВС.

Время старта вершины (sT) - время старта расчета вершины в существующем разбиении вершин между процессорами.

Время финиша вершины (fT) - время финиша расчета вершины в существующем разбиении вершин между процессорами.

Нить - набор из одной или нескольких вершин, которые последовательно рассчитываются на одном процессоре.

Множество нитей (Т) - совокупность всех нитей заданного ИЛГ.

Пучок нитей ({Pz}) - множество связанных между собой нитей.

Таблица связей к-ой нити (TSk) - совокупность нитей, связанных с k-ой нитью (имеет Sk элементов).

Массив связей (MS) - упорядоченное множество связей всех нитей одного пучка.

3.Распределение операторов по ВМ вычислительной системы с распределенной памятью для информационно-логической граф-схемы

При построении плана распределения операторов по ВМ вычислительной системы с распределённой памятью для информационной граф-схемы возникают определённые трудности, связанные с передачей информации через транзитные ВМ. Сущность метода заключается в том, что на первом этапе создаются нити без учёта обмена информацией между ВМ. Затем при построении нитей в моменты обмена данными длины нитей корректируются на время обмена информацией в данной точке. Вначале получаем модифицированные веса вершин в виде pm,j=pj+qj,i ,где pj - вес j-й вершины, qj,i - вес дуги, исходящей из j-й вершины. При использовании транзитных ВМ модифицированный вес возрастает на qj,i(n-1), где n - количество используемых транзитных процессоров.

Структура ВС с общей памятью. Применяется в многопроцессорных системах и не используется в многомашинных системах.

Коммуникационная сеть вырождается в общую шину. Дополнительно к преимуществу структуры общей шины данная структура обладает тем достоинством, что обмен информацией между процессорами не требует дополнительных операций, а осуществляется благодаря доступу процессора к памяти.

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

Рисунок 2 - Вычислительная система с общей памятью

Рисунок 3 - Граф-схема параллельного алгоритма (чёрным - веса вершин, синим - веса дуг)

3.1 Построение матрицы следования ИЛГ

Основным инструментом анализа граф-схем алгоритмов служит матрица следования, а также различные её модификации. Матрица следования - это транспонированная матрица смежности. Использование матрицы следования вместо матриц смежности объясняется удобством размещения и анализа граф-схем.

Для удобства присвоим постоянный идентификатор - Si i{1, 2. …, n}.Матрица S - квадратная - количество строк и столбцов совпадает с количеством вершин граф-cхемы. В матрице S i - ой вершине графа G ставятся в соответствие i - ые столбец и строка этой матрицы. Если существует связь по управлению: , то элемент матрицы равен (i,j) = j.n, при j → i образуется (i,j) = 1. Остальные элементы матрицы S равны 0.

Для заданной матрицы Si размера m отражения весов вершин вводится понятие расширенной матрицы следования SRi: прибавляется дополнительно k столбцов с номерами m+1, …, m+k, где k - размерность вектора весов вершин граф - схемы.

Построим расширенные матрицы следования для граф - схемы с рисунка 3. (см. таблицу 1 в приложении 4.1).

Построим матрицу следования с указанием весов дуг и вершин (SDR) для данного ИЛГ (см. таблицу 2 в приложении 4.2).

3.2 Определение ранних сроков окончания выполнения операторов

При исследовании граф-схем алгоритмов одними из основных характеристик являются ранние сроки окончания выполнения операторов. Имея эти величины, можно построить планы выполнения операторов с учётом распределения операторов по ВМ. На основе граф-схемы алгоритма можно определить:

) Частичную упорядоченность выполнения алгоритма.

) Веса операторов pj, j = 1, …, m (обычно - времена выполнения процедур).

Началом отсчёта времени решения задачи является начало выполнения операторов, являющихся входами в алгоритм. Тк - это путь максимальной длины в граф-схеме (максимальное время, за которое может быть решена данная задача).

Ранний срок окончания выполнения оператора - это время на оси отсчёта времени, равное t1, j = , j = 1 . . .m, где - время начала выполнения j-ого оператора, p_j - время выполнения j-ого оператора, полученное при минимальном времени решения задачи Т=Тк.

По алгоритму, приведенному в Приложении 2, определим ранние сроки окончания выполнения операторов и построим диаграмму (рисунок 4).

Каждая строка диаграммы может служить нитью для загрузки в процессор. Таким образом получим 9 нитей: ={2, 5, 6, 15, 26, 34, 46}={1, 7, 27, 35, 45}={3, 8, 16, 22, 31, 36, 47, 44}={4, 9, 17, 28, 37, 48}={10, 19, 29, 38, 43}={11, 20, 18, 42}={12, 21, 30, 24, 41}

T8={13, 23, 32, 40}

T9={14, 25, 33, 39, 49}ак как рассматривается ВС с общей памятью, обмена данными через каналы связи между процессорами нет, и количество нитей меньше, чем число процессоров, поэтому распределение нитей между ВМ может осуществляться, например, следующим образом: первая нить загружается в первый ВМ, вторая - во второй и т. д.

Учёт времён передачи информации осуществляется, используя следующие соотношения: для развёртки- p_,j=q_i,j+p_j, где j=- номера операторов, образующих развёртку; для свёртки- p_j= q_j,i +p_j где j=- номера операторов, образующих cвёртку. С помощью матрицы следования с указанными весами дуг и вершин модифицированные веса вершин можно вычислить следующим образом: если в i-й строке найдено одно число, то вес i-й вершины модифицируется к виду: р_i:=p_i+q_ji;если в i-й строке найдено несколько чисел, то веса вершин модифицируются к виду р_j:=p_j+q_i,j, j={}, где j - номера столбцов, в которых найдены числа,q_i,j- множество весов дуг, принадлежащихi-й строке.

В таблице 3 приведены ранние сроки окончания выполнения операторов.

Таблица 3- Ранние сроки окончания выполнения операторов

Рисунок 4 - Диаграмма ранних сроков окончания выполнения операторов

Паузы, возникшие по окончанию 12, 15, 20, 21, 22 единиц времени, обусловлены синхронизацией вычислений, определяемой структурой рассматриваемой граф-схемы. Общее время выполнения алгоритма составляет 26 условных единиц времени.

Этот способ графического представления плана выполнения алгоритма на ВС позволяет в максимальной степени компактно распределить параллельные операторы по узлам ВС. Это позволяет обеспечить экономию времени при выполнении задач. Как видим, при таком раскладе наиболее продолжительный по времени последовательный путь в ИЛГ незначительно выдаётся за пределы компактного распределения интервалов работы операторов основного тела ИЛГ.

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

Рисунок 5 - Временная диаграмма при срабатывании дуги 5.1

Рисунок 6 - Временная диаграмма при срабатывании дуги 5.2

Рисунок 7 - Временная диаграмма при срабатывании дуги 5.3

Рисунок 8 - Временная диаграмма при срабатывании дуги 5.4

Рисунок 9 - Временная диаграмма при срабатывании дуги 5.5 и 10.1

Рисунок 10 - Временная диаграмма при срабатывании дуги 5.5 и 10.2

Рисунок 11 - Временная диаграмма при срабатывании дуги 5.6

Рисунок 12 - Временная диаграмма при срабатывании дуги 5.7

Рисунок 13 - Временная диаграмма при срабатывании дуги 5.8

Рисунок 14 - Временная диаграмма при срабатывании дуги 5.9

Как видно из рисунка 14, максимальное число нитей для данного алгоритма равно 7. Полная временна диаграмма свидетельствует о наличии 9 таких нитей.

3.3 Распределение нитей на структуре типа циркулянта

В задании в качестве исходных данных для архитектуры ВС дана информация о циркулянте {49, 1, 3, 4, 5, 7}. Эта циркулянта представлена на рисунке 15.

Рисунок 15 - Схематическое представление циркулянты {49, 1, 3, 4, 5, 7}

Для показанной на рисунке 15 циркулянты строится матрица дистанций (см. таблицу 3 в приложении 5.1), в которой расстояния указываются в минимальном числе промежуточных связей между соответствующими вычислительными модулями. Минимальная сумма расстояний от любого ВМ циркулянты до других ВМ равна 116 ед. То есть эта сумма является постоянной величиной, не зависящей от номера ВМ в циркулянте. Таким образом, отдать предпочтение каким-либо конкретным ВМ в составе циркулянтной ВС не представляется возможным. Тем не менее, очевидно, что ВМ для размещения 9 нитей должны быть выбраны среди всего множества ВМ циркулянтной ВС так, чтобы расстояния между ВМ внутри группы были минимальны.

Таким образом, первую нить можно разместить в любом ВМ (например, в 0-ом), а последующие нити - на минимально возможном расстоянии от первой. Так, расстояние от нитей 2 и 3, размещённых соответственно на 48 и 1 ВМ составит единицу от первой нити, размещённой на нулевой ВМ. Аналогично на единичном расстоянии от первой нити будут находиться 4 и 5 нити, размещённые на ВМ 3 и 46 соответственно. 6 и 7 нити целесообразно разместить на 4 и 45 ВМ соответственно, тогда как 8 и 9 нити разместятся на 5 и 44 ВМ. Таким образом, нити с 2 по 9 находятся на минимальном (единичном) расстоянии от первой нити. Расстояние между ними также минимально возможным в силу конструктивным особенностей ВС типа циркулянта {49, 1, 3, 4, 5, 7}. На рисунке 16 представлено распределение нитей по ВМ ВС структуры циркулянта {49, 1, 3, 4, 5, 7} (см. также таблицу 4 в приложении 5.2).

Рисунок 16 - Распределение нитей по вычислительным модулям ВС структуры циркулянта {49, 1, 3, 4, 5, 7}

Заключение

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

Так, в процессе проектирования были решены задачи:

         нахождение ранних сроков окончания выполнения операторов;

         построение нитей решения задачи в соответствии с заданной граф-схемой;

         распределение нитей по ВС, с учетом времени передачи между операторами и между процессорами.

Результаты работы показали корректность алгоритма распределения программных модулей по узлам ВС и оптимальность его выходных данных. Данный алгоритм применим для различных топологий ВС и для неограниченного количества операторов, что позволяет решать многие классы существующих сложных вычислительных задач. На основании проведённых проектировочных исследований можно утверждать, что алгоритм распределения программных модулей по узлам ВС является универсальным.

Список используемой литературы

.       Руденко Ю.М., Волкова Е.А. Вычислительные системы. Москва, НИИ РЛ МГТУ им. Н.Э.Баумана, 2010.

.       Корнеев В.В. Параллельные вычислительные системы, Издательство НГТУ, 2009.

.       Хорошевский В.Г. Архитектура вычислительных систем, МГТУ им. Н.Э. Баумана, 2014.

4.     Руденко Ю.М. Новый подход к изображению схем алгоритмов для вычислительных систем. Информатика и системы управления в ХХ1 веке. Сборник трудов №7 молодых учёных, аспирантов, и студентов - М,: МГТУ им. Н.Э. Баумана, 2012. 167-181 с.

.       Руденко Ю.М. Построение плана выполнения параллельных алгоритмов на базе граф-схем. Аэрокосмические технологии. Научные материалы МНТК - 2009.Реутов - Москва 2009. 179-181с.

.       Руденко Ю.М. Учёт зависимостей программных модулей по данным и последовательностям их выполнения при параллельных вычислениях. Известия высших учебных заведений. Поволжский регион. Технические науки. № 3 (11), 2009. 67-75 с.

1.   Приложение 1

Алгоритм построения нитей

1.      Просматриваем матрицу SDR по строкам сверху вниз. Если просмотрены все строки, то - конец алгоритма.

2.      Если в i-й строке найдено одно число, то вес i-й вершины модифицируется к виду: р_i:=p_i+q_j,i . Если в i-й строке найдено несколько чисел, то веса вершин модифицируются следующим образом: р_j:=p_j+q_i,j ,j={}, где ,j - множество столбцов, в которых найдены числа,q_i,j- множество весов дуг, принадлежащихi-й строке .

3.      Используя модифицированные веса, с помощью алгоритма 6.1.1 вычисляем ранние сроки окончания выполнения операторов.

4.      Вычисленные ранние сроки окончания выполнения операторов служат основой для построения диаграммы загрузки ВМ. Каждая строка диаграммы может служить нитью для загрузки в процессор.

Приложение 2

Алгоритм вычисления ранних сроков окончания выполнения операторов

. Вычислим t_1,j:=0, где j :=1,…,RS. RS - размер матрицы следования

2. Просматриваются строки матрицы S сверху вниз, выбирается первая необработанная строка матрицы, и осуществляется переход к следующему шагу, если обработаны все строки, то - конец алгоритма.

. Если выбрана j-я строка, не содержащая единичных элементов, то вычисляем t_1,j:= p_j , где p_j - вес j-го оператора и переходим на шаг 5.

. Если j-я строка содержит единичные элементы, то вычисляется

t_1,j:= + p_j,

где max , берётся по множеству времён t_1,j, где j_q- номера элементов j-й строки, равных единице. Если в множестве  есть нулевые элементы, то выполняется шаг 6, иначе выполняется шаг 5.

5. Обработанная j-я строка исключается из рассмотрения. Осуществляется переход на шаг 3.

. Выбираем столбец j:=j_q и переходим на шаг 3.

Примечание: пункт 6 алгоритма 6.1.1 используется для нетреугольной матрицы S

Приложение 3

Алгоритм распределения программных модулей по узлам Вычислительной сети.

1.   Задана ВС с N вычислительных модулей, нумеруемых как {0,1,…,N-1}. Предполагается, что мощность множества удовлетворяет потребность в количестве ВМ для решения поставленной задачи предполагаемым методом.

2.      Количество нитей W. Множество нитей Т.

.        Вычислим матрицу расстояний между вычислительными модулями.

Минимальное расстояние между двумя ВМ равно 1, максимальное - N-2.

.     Для определения показателя близости ВМ определим сумму столбцов матрицы R.

j=1,2,…,N.
При j=1 показатель близости наилучший.

5.      Упорядочим St(j) в порядке возрастания

6.      Построим диаграмму ранних сроков окончания выполнения операторов с указанием связей между операторами, с учетов времени передачи между операторами. Образуем множества несвязных между собой пучков нитей {}; S={0,1,…,q}.

.        Среди множеств {} найдем множество {}, имеющее нить  с максимальным количеством элементов в множестве (таблице связей к-й нити). Предположим таблица связей имеет элементов.

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

8.      Составим из связей между нитями множества {} массив MS и обнулим все его элементы.

.        Если степень i-й вершины вычислительной сети есть , то сравниваем  и .

.        Если , то нить размещается в узле i, и переходим к шагу 12, иначе следующий шаг.

.        Если то образуется комплексный узел, в котором один вычислитель основной, остальные являются передающими звеньями.

12.    Определим с какой нитью из множества {Pz} связана нить . Пусть это будет нить =(max∩Tj), TjϵT.

.        Нить  занимает узел j_m вычислительной сети на минимально возможном расстоянии от узла i.

.        Образуем последовательность входящих и исходящих связей i-ой нити с , S₁,S₂,…,S_d (1) из множества MS.

.        Пусть связь S_m ,где mϵ{1,2,..d}, в нити  связывает оператор  с оператором  нити.Тогда,

.        если связь входящая, то если sT(γ) ≥ fT(α) + r(i,j_m)*ρA,

  то переходим на шаг 17,

иначе Pγ=Pγ+ r(i,j_m)*ρA.

Если связь исходящая, то если S_m =0, то

Pα=Pα+ r(i,j_m)*ρA,

иначе если sT(γ) <fT(α), то

sT(γ) = fT(α).

17.    Если S_m - входящая связь, то все операторы в нити , начиная с оператора  сдвинуты по оси времени вправо на величину r(i,j)* ρA. Иначе, аналогично в нити  сдвинуты все операторы, начиная с.

.        Связь S_m=1 в массиве связей всех нитей MS.

.        Из последовательности (1) берем следующую связь для рассмотрения, пусть m=m+1 и обозначим эту связь S_m. Если m≤d, то перейти к шагу 15, иначе шаг 19.

20.    TS_k= TS_k|T_jm, если TS_k≠0, то переходим к шагу 12, иначе шаг 20.

.        Уменьшим количество нерассмотренных нитей на 1, то есть W=W-1.

Если W=0, то переходим к п.17, иначе выбираем из оставшихся нитей множества {P_z} нить с максимальным числом связей. Пусть эта нить  и переходим к шагу 12.

.        Исключить из рассмотрения множества {} и переномеровать множество {}; S={0,1,…,q-1}. Если {}0, то перейти к шагу 7, иначе шаг 22.

.        Конец алгоритма.

Приложение 4

Матрица следования

Таблица 1 - Расширенная матрица следования

Расширенная матрица следования с указанием весов дуг и вершин

Таблица 2 - Расширенная матрица следования с указанием весов дуг и вершин (SDR) данного ИЛГ