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


              

Функция определяет минимально возможный объём


Ф = 10 и т.д.

Определение 9. Функцию


назовём минимальной загрузкой отрезка [?1, ?2]
[0, T].

Функция определяет минимально возможный объём работ, который при данном T и при различных допустимых значениях (расписаниях) ?1 , ... , ?m

должен быть выполнен на отрезке времени [?1, ?2]
[0, T]. Это означает, что как бы мы не планировали вычислительный процесс, который должен быть закончен к моменту времени T, т.е. какой бы набор значений ?1 , ... , ?m

мы не выбрали, объём работ, выполняемых на отрезке времени [?1, ?2], не может быть меньше значения
(T) = (?1, ?2).

Теорема 1. Для того чтобы T было наименьшим временем выполнения данного алгоритма однородной вычислительной системой, состоящей из n процессоров, либо чтобы n процессоров было достаточно для выполнения данного алгоритма за время T, необходимо, чтобы для данного отрезка времени [?1, ?2]
[0, T] выполнялось соотношение


(7.1)



Доказательство. Нетрудно видеть, что если при данном наборе ?1 , ... , ?m — сроках окончания выполнения работ, в том числе и при таком наборе, при котором обеспечивается минимальное или заданное T = max {?1

, ... , ?m}, для реализации алгоритма достаточно n процессоров, то



Отсюда, для любого отрезка времени [?1, ?2]
[0, T]


что и требовалось доказать.

Необходимость, но не достаточность условия (7.1) покажем на примере. Пусть алгоритму соответствует граф G на рис. 7.16а. Пусть T=3, и одна из возможных диаграмм выполнения алгоритма — на рис. 7.16б.


Рис. 7.16.  Пример: минимальная плотность загрузки не соответствует действительной: а — информационный граф, б — временная диаграмма загрузки

Оценим на основе (7.1) число n процессоров, достаточное для выполнения алгоритма в указанное время. Из (7.1) имеем общее соотношение


(7.2)


Для получения полной оценки надо перебрать все отрезки [?1, ?2]
[0, T] т.е.


(7.3)


Проанализируем все возможные отрезки [?1, ?2]
[0, 3] :
(3)(0, 1) =
(3)(1, 2)
(3)(2, 3) = 0,
(3)(0, 2) =
(3)(1, 3) = 3,
(3)(0, 3) = 6.

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