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



              

Диспетчер последовательного назначения для неоднородной ВС - часть 4


по матрице 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\}. Таблица распределения ? примет вид

 \begin{array}{c|c|c} 1 & 1, 3 & T_1 = 3\\ \hline 2 & \ubox 1, 4 & T_2 = 6\\ \hline 3 & \ubox 1, 2 & T_3 = 3 \end{array}

  • 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}. Таблица распределения ? примет вид

     \begin{array}{c|c|c} 1 & 1, 3, 5 & T_1 = 5\\ \hline 2 & \ubox1, 4 & T_2 = 6\\ \hline 3 & \ubox 1, 2, 6 & T_3 = 4 \end{array}

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

    . Назначим процессору 3 простой в течение одной условной единицы времени. Таблица ? примет вид

     \begin{array}{c|c|c} 1 & 1, 3, 5, & T_1> = 5\\ \hline 2 & \ubox 1, 4 & T_2 = 6\\ \hline 3 & \ubox 1, 2, 6, \ubox1 & T_3 = 5 \end{array}

  • 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. Таблица ? примет вид

     \begin{array}{c|c|c} 1 & 1, 3, 5, 8 & T_1 = 9\\ \hline 2 & \ubox 1, 4 & T_2 = 6\\ \hline 3 & \ubox 1, 2, 6, \ubox 1, 7 & T_3 = 7 \end{array}

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

     \begin{array}{c|c|c} 1 & 1, 3, 5, 8 & T_1 = 9\\ \hline 2 & \ubox1, 4, 9 & T_2 = 8\\ \hline 3 & \ubox 1, 2, 6, \ubox 1, 7 & T_3 = 7. \end{array}

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

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

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




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