Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре (стр. 2 из 4)

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.