6. Если из вершины выходит несколько связей (развертка -вершины), то среди множества дуг J, исходящих из вершины ищем , (1), где -вес дуги, исходящей из вершины и входящей в вершину j.

7. Если условию (1) удовлетворяют несколько вершин, то выбирается первая вершина рассматриваемого множества, составляющих эти вершины. Для вершины вычисляется вес , если вершина не модифицировалась и , в противном случае. Веса вершин из множества J, исключая вершину , вычисляются как , если j-я вершина не модифицировалась и в противном случае, где -вес дуги, выходящей из вершины и входящей в вершину j. Обобщенный вес вершины определяется, как на шаге 3. Переходим к шагу 11. Если из вершины не выходит несколько связей, то выполняется следующий шаг.

8. Если вершина входит в свертку J, то обобщенный вес вершины , связанной с вершиной , вычисляется как , если обобщенный вес -й вершины не модифицировался и в противном случае. Веса остальных вершин, исключая вершину , вычисляются как , если вес вершины j не модифицировался и в противном случае. Обобщенный вес вершины вычисляется как на шаге 3. Переходим на шаг 12.

9. Вершина включается в Tk-ю нить как конец нити и исключается из рассмотрения. Tk-я нить включается в множество нитей NT.

10. Вычислим . Если , то вычисляем f: =f+1 и переходим к шагу 13, иначе положим i: =i+1 и переходим на шаг 2.

11. Вершина оформляется как элемент Tk-й нити и исключается из рассмотрения. Вершина включается в множество продолжения нити . Дуги исключаются из графа G или его компонентов. Составляется таблица (множество) связей фрагмента Tk нити в виде , где -включает номера операторов множества J, исключая оператор . Осуществляется переход на шаг 10.

12. Вершина оформляется как элемент Тк нити и исключается из рассмотрения. Вершина включается в множество продолжения нити . Дуги исключаются из графа G или его компонентов. Составляется таблица связей для фрагмента нити, где -включает номера операторов составляющих множество J, исключая оператор . Осуществляется переход на шаг 10.

13. Рассмотрим множество К компонентов графа G, образованные в результате удаления связей. Если множество , то переходим на шаг 16, иначе выполняем следующий шаг.

14. С помощью матрицы S, составленной для компонентов графа G определим множество начальных вершин .

15. Образуем множество таким образом, чтобы элементы множества предшествовали элементам множества , полученного на шаге 14. Множество Положим i: =1 и переходим на шаг 2.

16. Для графа G*, который имеет ту же конфигурацию, что и исходный граф G, но в котором изменены весы вершин с учетом весов дуг, вычислим ранние сроки окончания выполнения операторов.

17. Для каждой нити вычислим время старта нити в виде , где - ранний срок выполнения первого оператора Тк нити. Время окончания нити определяется как , где - ранний срок окончания последнего оператора Тк нити.

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

Таким образом, каждая нить характеризуется своим номером (к), временем начала нити , временем окончания нити и таблицей связей к-й нити с другими операторами, входящими в нити множества Тк.

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

1. Времена начала и конца нитей объединяются в множества где n - число нитей, полученных в предыдущем алгоритме.

2. Упорядочим множество в порядке не убывания. Элементы представляются таким образом, чтобы i-ый номер начала нити соответствовал i-му номеру конца нити.

3. Найдем такой что для соседних нитей, размещаемых на интервале [0,T], после вычислений по соотношения (1) выполняется условие, что время окончания предшествующей нити должно быть меньше или равно времени начала последующей нити.

4. Если нити, удовлетворяющие условию (1) найдены, то соответствующие и удаляются и записываются в множество в виде составной к-й нити. Объединяются множества таблиц связей в виде где I - число нитей, вошедших в составную нить.

5. Если =0, то работа алгоритма заканчивается, иначе осуществляется переход к п.3.

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

4.4 Алгоритм распределения вершин графа решаемой задачи на узлах вычислительной сети с одинаковой степенью вершин

Предполагаем, что количество узлов вычислительной сети неограниченно и множество нитей Т получено с помощью алгоритма 4.2.

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

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

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

4. Если то образуется комплексный узел, в котором один вычислитель основной, остальные являются передающими звеньями. Полагаем f: =1 и переходим к следующему шагу.

5. Определяем где Т множество нитей.

6. Если , то переход на шаг 10.

7. Нить занимает узел вычислительной сети на минимально возможном расстоянии от узла i. Все вершины из окружения нити Ti, принадлежащие множеству удаляются из узлов, соседних с узлом I, т.е.

8. В соседних узлах с узлом размещаются элементы таблицы . Если количество узлов с минимальным расстоянием недостаточно, то организуются комплексные узлы, как пункте 4.