АЛГОРИТМ РАСПРЕДЕЛЕНИЯ НИТЕЙ ГРАФ-СХЕМЫ АЛГОРИТМА ПО УЗЛАМ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ.

- объемы передаваемой информации

l – пропускная способность магистрали.

Пусть i-я вершина связана с несколькими вершинами в графе, множество вершин назовем разверткой вершины i (J).

Условимся, что в случае такой развертке сигнал в линиях передается одновременно.

Множество J вершин, связанных с рассматриваемой – назовем сверткой вершин.

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

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

Алгоритм 20 (Построение нитей в сети G представляющей решаемую задачу)

1. В графе G выберем множество начальных вершин (В матрице S начальным вершинам соответствуют нулевые строки).

I:=1 – параметр определяющий текущий номе в множестве

V:= 1 – номер массива перебора операторов

k:=1 – номер очередной создаваемой нити.

- множество связей нити с другими нитями

f:=0 – номер очередного разрезания графа G

- множество продолжения нитей

1. Возьмем вершину

3. Вычислим обобщенный вес вершины , если вес вершины не модифицировался . Иначе: шаг 4

4. Если из вершины не выходит связь, то переходим на шаг 9. Иначе: шаг 5

1. Если из выходит 1 связь в j-ю вершину, тоесть в матрице S в строке содержится единица в i-й строке.

6. Если j-я вершина не модифицировалась . Иначе

Обобщенный вес вершины определяем как в шаге 3. Переходим к шагу 10. Иначе к следующему шагу.

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

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

Для вершины вычисляется вес. Если вершина не модифицировалась

Весами вершины множества J исключая вершину вычисляется как

Где - Обобщенный вес вершины считаем, как на шаге 3. Переходим на шаг 11.

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

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

1. Вершина включается в -ю нить и исключается из рассмотрения, а -я нить, включается в множество NT.
2. Вычислим

k++

Если , то f++, шаг 13. Иначе i++, шаг 2.

1. Вершина , оформляется, как элемент нити и исключается из рассмотрения. Вершина , включается в , дуги ( ) исключаются из графа G или его компонента. Составляется таблица связей в виде объединений множеств , где - включает номера операторов множества J, исключая .
2. Вершина оформляется, как элемент нити и исключается из рассмотрения. Вершина , включается в , дуги ( ) исключаются из графа G или его компонента. Составляется таблица связей в виде объединений множеств , где - включает номера операторов множества J, исключая . Осуществляется переход на шаг 10.
3. Рассмотрим множество «к» компонентов графа G, образованного удалением связей. Если то переходим на шаг 16, Иначе выполняем следующий шаг.
4. С помощью матрицы S составленной для компонентов графа G, определим множество начальных вершин
5. , таким образом, чтобы элементам множества предшествовали элементы множества

Переходим на шаг 2.

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

Пример

1. 
2. i:=1
3.