Параллельное программирование


              

времени окончания выполнения каждой


по матрице S2) найдем R = {2, 3, 4, 6}. Составим таблицу 10. 1 времени окончания выполнения каждой работы из R каждым процессором l = 1, 2, 3. Минимальное время окончания выполнения каждой работы выделено.



Таблица 10.1. l Tl+t2l Tl+t3l Tl+t4l Tl+t6l
1 4 3 6 4
2 3 6 6 2
3 3 6 6 2


Формируем последовательность R* = {6 (4; 1, 2, 3, ?4 = 3), 3 (2; 2,3, ?2 = 2), 3( 3; 1, ?3 = 1), 2 (6; 2,3, ?6 = 2)}, где в круглых скобках указаны номер работы, список процессоров, на которых достигается минимальное время окончания ее выполнения, и число ?p

этих процессоров.

Назначим первоначально (таблица 10.2) работу 4 на процессоры 1, 2, 3, работу 2 — на процессоры 2 и 3 , работу 3 — на процессор 1.



Таблица 10.2.
1 4 (?4 = 3), 3(?3 = 1)
2 4 (?4 = 3), 2(?2 = 2)
3 4 (?4 = 3), 2(?2 = 2)


После анализа значений ?p оставим на процессоре 1 работу 3 (после чего ?4 = 2), на процессоре 2 — работу 4 (после чего ?2 = 1), на процессоре 3 — работу 2, A = \{3 - 3, 4 - 6, 2 - 3\}. Таблица распределения ? примет вид




  • B = {2, 3}. После исключения строк и столбцов, соответствующих работам 2 и 3, из матрицы S2, т.е. по сформированной матрице S3, найдем R = {5, 6}. Составим таблица 10.3 значений времени окончания выполнения каждой работы из R каждым процессором.



    Таблица 10.3. l Tl+t5l Tl+t6l
    1 5 6
    2 10 7
    3 7 4


    Из таблицы найдем R* = {5 (5; 1, ?5 = 1), 4 (6; 3, ?6 = 1)},

    Назначим работу 5 на процессор 1, работу 6 — на процессор 3, A = {5 - 5,4 - 6, 6 - 4}. Таблица распределения ? примет вид




  • B = {6}. После исключения строки и столбца, соответствующих работе 6, из матрицы следования S3, т.е. по сформированной матрице S4, найдем R =
    . Назначим процессору 3 простой в течение одной условной единицы времени. Таблица ? примет вид




  • B = {5}. После преобразования матрицы S4, т.е. по матрице S5, найдем R = {7, 8}. Из таблицы 10.4, аналогичной таблице 3, найдем R* = {9 (8;1, ?8 = 1), 7 (7; 3, ?7 = 1)} .



    Таблица 10.4. l Tl+t7l Tl+t8l
    1 9 9
    2 8 11
    3 7 10


    Назначаем работу 8 на процессор 1, работу 7 — на процессор 3. Таблица ? примет вид




  • B = {4}. После исключения строки и столбца, соответствующих работе 4, из матрицы следования S5, т.е. по сформированной при этом матрице S6, найдем R = {9}. Время окончания выполнения работы 9 на процессорах равно соответственно 10, 8, 9. Назначаем работу 9 на процессор 2. Таблица ? примет окончательный вид




  • Дополнение.

    Данный диспетчер для неоднородной ВС построен на основе обобщения рассмотренного диспетчера последовательного назначения для однородных ВС, который можно рассматривать как частный случай при k = 1.

    Он применим и в другом частном случае: когда отсутствует частичная упорядоченность работ, то есть когда надо разделить "поровну" взаимно независимые работы между n исполнителями. Наглядный пример такого распределения составляет задача о рюкзаках, рассмотренная в разделе 10.1.1.












    Содержание  Назад