Читайте также:
|
1. Задана ВС с N вычислительных модулей, нумеруемых как {0,1,…,N-1}. Предполагается, что мощность множества удовлетворяет потребность в количестве ВМ для решения поставленной задачи предполагаемым методом.
2. Количество нитей W. Множество нитей Т.
3. Вычислим матрицу расстояний между вычислительными модулями.
Минимальное расстояние между двумя ВМ равно 1, максимальное – N-2.
4. Для определения показателя близости ВМ определим сумму столбцов матрицы R.
j=1,2,…,N.
При j=1 показатель близости наилучший.
5. Упорядочим St(j) в порядке возрастания
6. Построим диаграмму ранних сроков окончания выполнения операторов с указанием связей между операторами, с учетов времени передачи между операторами. Образуем множества несвязных между собой пучков нитей { 
}; S={0,1,…,q}.
7. Среди множеств { 
} найдем множество { 
}, имеющее нить 
с максимальным количеством элементов в множестве 
(таблице связей к-й нити). Предположим таблица связей имеет 
элементов.
Примечание: таких множеств нитей может быть несколько, и тогда выбирается любое из них.
8. Составим из связей между нитями множества { 
} массив MS и обнулим все его элементы.
9. Если степень i-й вершины вычислительной сети есть 
, то сравниваем и .
10. Если 
, то нить размещается в узле i, и переходим к шагу 12, иначе следующий шаг.
11. Если 
то образуется комплексный узел, в котором один вычислитель основной, остальные являются передающими звеньями.
12. Определим с какой нитью из множества {Pz} связана нить 
. Пусть это будет нить 
=(max ∩Tj), TjϵT.
13. Нить занимает узел jm вычислительной сети на минимально возможном расстоянии от узла i.
14. Образуем последовательность входящих и исходящих связей i-ой нити с , S1,S2,…,Sd (1) из множества MS.
15. Пусть связь Sm,где mϵ{1,2,..d}, в нити связывает оператор 
с оператором 
нити .Тогда,
если связь входящая, то если sT(γ) ≥ fT(α) + r(i,jm)*ρA,
то переходим на шаг 17,
иначе Pγ=Pγ+ r(i,jm)*ρA.
Если связь исходящая, то если Sm =0, то
Pα=Pα+ r(i,jm)*ρA,
иначе если sT(γ) <fT(α), то
sT(γ) = fT(α).
16. Если Sm - входящая связь, то все операторы в нити , начиная с оператора сдвинуты по оси времени вправо на величину r(i,j)* ρA. Иначе, аналогично в нити сдвинуты все операторы, начиная с .
17. Связь Sm=1 в массиве связей всех нитей MS.
18. Из последовательности (1) берем следующую связь для рассмотрения, пусть m=m+1 и обозначим эту связь Sm. Если m≤d, то перейти к шагу 15, иначе шаг 19.
19. TSk= TSk|Tjm, если TSk≠0, то переходим к шагу 12, иначе шаг 20.
20. Уменьшим количество нерассмотренных нитей на 1, то есть W=W-1.
Если W=0, то переходим к п.17, иначе выбираем из оставшихся нитей множества {Pz} нить с максимальным числом связей. Пусть эта нить и переходим к шагу 12.
21. Исключить из рассмотрения множества { } и переномеровать множество { }; S={0,1,…,q-1}. Если { } 0, то перейти к шагу 7, иначе шаг 22.
22. Конец алгоритма.
Дата добавления: 2015-11-14; просмотров: 74 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Распределение нитей на структуре типа циркулянта | | | ПРИЛОЖЕНИЕ 4.1 Матрица следования 1 страница |