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



              

Временные оценки на информационных графах - часть 6


Ф = 10 и т.д.

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

 \begin{align*} \varphi^{(T)} (\theta_1, \theta_2)= \min_{\tau_1 \dts \tau_m}\text{Ф} (\tau_1 \dts \tau_m, \theta_1, \theta_2) \notag \end{align*}

назовём минимальной загрузкой отрезка [?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] выполнялось соотношение

 \begin{align*} \varphi^{(T)}(\theta_1, \theta_2) \le n ( \theta_2 - \theta_1) \notag \end{align*}

(7.1)

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

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

 \begin{align*} \max_{t\in[0,T]}F(\tau_1 \dts \tau_m\,t)\le n. \end{align*}

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

[0, T]

 \begin{align*} \varphi^{(T)}(\theta_1, \theta_2)\le \text{Ф} (\tau_1 \dts \tau_m, \theta_1, \theta_2) \int_{\theta_1}^{\theta_2} F(\tau_1 \dts \tau_m,t)dt \le n ( \theta_2 - \theta_1) \end{align*}

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

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

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

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

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

 \begin{align*} n\ge \frac{\varphi^{(T)}(\theta_1, \theta_2)}{\theta_2 - \theta_1} \notag \end{align*}

(7.2)

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

[0, T] т.е.

 \begin{align*} n\ge \max_{[\theta_1, \theta_2] \subset [0, T]}\frac{\varphi^{(T)}(\theta_1, \theta_2)}{\theta_2 - \theta_1} \notag \end{align*}

(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.


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