Курсовая работа: Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре
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.