Высокая производительность ВС достигается
Проблема её программирования — это
С ориентацией на достижение максимальной производительности ВС, а также на специальное применение в составе конкретных систем, например, в составе сложных систем управления, различают две взаимно-обратные задачи параллельного программирования.
Задача 1.
Под стоимостью понимают
В однородной ВС задача 1 вырождается в задачу
Задача 2.
Представим себе программу решения задачи, которая отображает
последовательное
изложение алгоритма на машинном языке, ассемблере или
Например, программа F представляется как
F = F1(X1 , X2 ; X3 , X4 ) F2 (X2 ; X5 ) F3 (X3 ; X6 ) F4 (X1 ,
X4 ;
X7 ) F5 (X3 , X4 , X5 ; X8 ) F6 (X3 , X4 , X7 ; X9 ) F7 (X5 , X7 ;
X10) F8 (X6 , X8 , X9 , X10 ; Y),
где точкой с запятой отделены входные данные от выходных, X = {X1,
X2} —
исходные данные задачи, Y — выходные данные или результат.
Итак, мы разбили заданный алгоритм решения задачи на ряд модулей,
операторов,
работ и установили информационную взаимосвязь этих работ. Чтобы подчеркнуть
общность задач и методов распараллеливания, не ограничивающуюся применением
только для ВС, будем пользоваться термином
Для решения задач оптимального выполнения работ многими исполнителями (т.е.
процессорами ВС) нам понадобятся временные оценки выполнения как программы в
целом, так и каждого
Пусть относительно данного алгоритма и предполагаемой ВС нам известны
следующие
оценки T = {t1, t2, ... , t8}.
Тогда, чтобы отразить прохождение обрабатываемой информации и выявить
возможности
распараллеливания, представим G (рис. 7.1). Вершины соответствуют работам. Дуги отражают
частичную упорядоченность работ.
(рис 7.1) Информационный граф алгоритма
А именно, если работа $$\beta$$ использует в качестве входной
информации результат
выполнения работы $$\alpha,$$ то её выполнение не может быть начато
до того, как
закончится выполнение работы $$\alpha.$$ Такая преемственность
информации и отражена в
графе. Граф G — взвешенный, ориентированный и не содержит
контуров. (Т.к. время
выполнения алгоритма конечно, то программные циклы либо погружены внутрь работ,
либо развёрнуты.)
Например, представим себе информационный
граф, соответствующий скалярному
умножению векторов заданной длины: A = B x C способом
"пирамиды", В = {b1 , ... , b8}, C = {c1 , ... , c8}. Схема счёта показана
на рис. 7.2.
(рис 7.2) Схема счёта "пирамидой"
Примем время сложения равным единице. Время умножения пусть превышает время
сложения в четыре раза. G, соответствующий
счёту способом
"пирамиды", представлен на рис. 7.3.
(рис 7.3) Информационный граф — "пирамида"
Мы рассмотрели составление
Например, может быть целесообразным следующее разбиение программы (алгоритма) на модули (работы):
F = F1(X1; X2) if A then F2(X2; X3) else F3(X1;X4) F4(X1, X3, X4; Y).
Информационно-логический граф G — на рис. 7.4.
(рис 7.4) Информационно-логический граф
Преемственность информации (1 -> 2), а также (1
-> 3), при наличии
"жирной"
стрелки "по управлению" можно не указывать, так как частичная
упорядоченность
работ в таком случае полностью определена.
Рассмотрение информационно-логических графов сильно усложняет решение задач оптимизации параллельных вычислений. Практически ограничиваются планированием выполнения самой сложной, трудоемкой ветви алгоритма или решают её для разных ветвей отдельно, — т.е. сводят оптимизацию к рассмотрению только информационных графов.
Для формальных исследований G
представляется матрицей
следования S, или, с добавлением столбцов весов, — расширенной
матрицей следования S*. При этом, т.к. граф G не содержит контуров
(циклов), то S может быть сведена
к треугольной "правильным" выбором нумерации вершин. Ниже (рис. 7.5) приведены
матрицы S и S* для графа, представленного на
рис. 7.1, и для некоторых известных
значений весов.
(рис 7.5) Матрица следования с задающими связями
Определение 1. Назовём все связи по
информации, обусловленные исходным видом
графа G,
Определение 2. G будем называть последовательности вершин вида a1, a2 , ... , as такие, что для любой пары соседних вершин ai и ai+1 существует
дуга, исходящая из вершины ai и входящая в вершину ai+1.
Будем считать все пути в графе G допустимыми, т.е. реально
существующими
ветвями отображаемой программы.
Определение 3. G назовём
сумму весов вершин,
составляющих этот путь.
Определение 4. Tкр в информационном графе G назовём
В одном графе может быть несколько путей равной длины, являющихся критическими.
Если в графе G есть дуга, исходящая из вершины a и входящая в вершину b, т.е.
существует a -> b, а также есть дуга,
исходящая из вершины b и
входящая в вершину c, т.е. существует b
-> c, но нет задающей
связи a -> c, очевидно, что последовательный порядок
выполнения работ a и c
определяется двумя указанными задающими связями. Т.е. граф G
можно дополнить
дугой, соответствующей связи a -> c, что только
подтвердит заданную частичную
упорядоченность работ.
Определение 5. Множество связей, которые
введены направленно внутри всех пар
работ, принадлежащих одному пути в графе G и не связанных
задающими связями,
назовём
Алгоритм 1 дополнения треугольной матрицы S транзитивными связями.
S.i -й строке организуем просмотр элементов в
порядке увеличения j номеров столбцов.(i, j)=1, складываем строки i и j по операции дизъюнкции.S нетреугольная,
последовательный просмотр
её строк производится неоднократно до установления факта неизменности
окончательно полученной матрицы.)Конец алгоритма.
В представленном выше примере после введения всех
S примет вид, представленный на рисунке 7.6)рисунке 7.6
(введённые транзитивные
связи выделены курсивом).
(рис 7.6) Матрица следования с транзитивными связями
С помощью введения G. О наличии контуров
свидетельствуют
появившиеся ненулевые диагональные элементы, указывающие на связь вида a
-> a.
Например, пусть задан граф G
на рис. 7.7.
(рис 7.7) Граф алгоритма и матрица следования
После первого шага преобразования S принимает вид, показанный
на рис. 7.8.
(рис 7.8) Первый шаг обнаружения контура
После второго шага преобразования S принимает вид, показанный
на рис. 7.9.
(рис 7.9) Обнаружение контура
Т.к. на главной диагонали матрицы появились единицы, то граф G содержит циклы
(контуры). Из рисунка графа виден цикл 2 -> 6 -> 3
-> 5 ->. "Участники" цикла отмечены единицами на
главной диагонали.
Определение 6. Работы a и b будем называть S выполняется условие (a, b) = (b, a) = 0.
Определение 7. Работы {ai}, i = 1, ... , s,
образуют
Например, для графа G,
представленного на рис. 7.1, после введения транзитивных
связей, что учтено в матрице следования на рис. 7.6, можно установить
следующие
ПМВНР: {1,2}, {2,3,4}, {3,4,5}, {2,3,6}, {3,5,6,7}, {8}.
Таким образом, для каждой i = 1 , ... , m работы алгоритма,
представленного
T < Tкр, то для
каждой
работы можно найти и i -й работы позже этого срока приводит к тому, что выполнение
других
работ, следующих за данной, не может быть закончено до истечения времени T. Иначе говоря, поздний срок окончания выполнения данной работы
не
может превышать разности между значением T и максимальной из длин
путей,
в первую вершину которых входит дуга, что исходит из вершины,
соответствующей данной работе. Без задания значения T
(ограничения на
длительность вычислительного процесса) определение позднего срока
окончания выполнения работы не имеет смысла.
При T = Tкр ранние сроки окончания выполнения работ,
составляющих критические
пути, совпадают с поздними сроками окончания их выполнения.
Прежде чем рассмотреть алгоритм нахождения ранних и поздних сроков окончания
выполнения работ по S*, отметим,
что учёт
G не содержит контуров, то матрица следования S
может быть преобразована в
треугольную. Однако при построении алгоритмов решения задач распараллеливания
не представляется удобным преобразовывать матрицу следования. Поэтому будем
считать, что в общем случае матрица S не треугольная.
Алгоритм 2 нахождения ранних сроков окончания выполнения работ.
S, находим
очередную из
необработанных строк. Если все строки обработаны, выполнение алгоритма
заканчивается.j — номер найденной необработанной строки. Если j -я строка не содержит
единичных элементов, полагаем $$\tau _{1j} = t_{j}$$. Переходим к
выполнению шага 6.j -я строка содержит единичные элементы, выбираем
элементы множества $$\{ \tau _{11} , \dots , \tau _{1m}\}$$, соответствующие номерам единичных
элементов j -й строки.Если все выбранные таким образом элементы, образующие множество $$\{ \tau _{1j(\nu )}\} , \nu = 1, \dots , k_{j}$$, отличны от нуля, полагаем $$\tau _{1}j = max \tau _{1 j\nu } + t_{j}$$.
Если хотя бы один из выбранных элементов нулевой (соответствующий ранний срок ещё не найден), выполняем шаг 2.
Обработанную j -ю строку метим, чтобы исключить её повторную
обработку.
Переходим к выполнению шага 2.
Примечание. Если граф G не содержит контуров, зацикливание при этом невозможно.
Конец алгоритма.
Если матрица S треугольная, то никогда не складываются условия
для многократного
циклического обзора строк. Тогда ранние сроки окончания выполнения работ
находятся за один последовательный просмотр строк матрицы S.
Очевидно, что $$T_{кр} = max \{ \tau _{11} , \dots ,\tau _{1m}\}$$.
По матрице S* ( S — треугольная) на рис. 7.5 (граф G — на рис. 7.1) находим
$$\tau _{11} = t_{1} = 2, \tau _{12} = t_{2} = 3, \tau _{13} = \tau _{11} + t_{3}=3, \tau _{14}= \tau _{11} + t_{4} = 4,\tau _{15} = max \{ \tau _{11}, \tau _{12} + t_{5}= 7, \tau _{16} = max\{ \tau _{11},\tau _{14}\} + t_{6} = 8, \tau _{17} = max \{ \tau _{12},\tau _{14} \} + t_{7} = 6,\tau _{18} = max \{ \tau _{13}, \tau _{15}, \tau _{16}, \tau _{17}\} + t_{8} = 9; T_{кр} = 9$$.
Чтобы рассмотреть пример с нетреугольной матрицей следования, выберем граф G без контуров с "неправильно" пронумерованными
вершинами (рис. 7.10).
(рис 7.10) Информационный граф с не треугольной матрицей следования
После обработки первой строки $$\tau _{11} = 1$$. Попытка
обработать вторую строку неудачна,
т.к. $$\tau _{13}$$ и $$\tau _{14}$$ ещё не найдены. После
обработки третьей строки $$\tau _{13} = \tau _{11} + t_{3} = 3$$.
Обработка четвёртой строки даёт $$\tau _{14} = 2$$. После обработки
пятой строки $$\tau _{15} = \tau _{13} + t_{5} = 4$$. Попытка обработки шестой строки
неудачна, т.к.
не найдено значение $$\tau _{12}$$. Приступаем к следующему циклу
обзора необработанных
строк S.
Обрабатываем вторую строку: $$\tau _{12} = max \{ \tau _{13}, \tau _{14}\} +t_{2} = 6$$.
После обработки шестой строки $$\tau _{16} = \tau _{12} + t_{6} = 7.T_{кр} = 7$$.
Для удобства представления наряду с другими способами будем пользоваться
наглядными диаграммами выполнения работ при заданных значениях времени начала
или окончания их выполнения. Работы обозначаются прямоугольниками с постоянной
высотой и длиной, равной времени выполнения. Стрелки, связывающие
прямоугольники-работы, соответствуют дугам в графе G. На рис. 7.11 представлена
диаграмма выполнения работ, отраженных графом G на рис. 7.1 и
расширенной
матрицей следования на рис. 7.5 — при
(рис 7.11) Временная диаграмма выполнения работ при ранних сроках окончания
Алгоритм 3 нахождения поздних сроков окончания выполнения работ при заданном
значении Т.
S, находим
очередной из не обработанных ещё столбцов. Если все столбцы обработаны,
выполнение алгоритма заканчивается.j — номер найденного необработанного столбца. Если j -й столбец не
содержит единичных элементов, полагаем $$\tau _{2j}(T) = T$$.
Переходим к выполнению шага 6.j -й столбец содержит единичные элементы, выбираем
элементы множества $$\{ \tau _{21}(T) , \dots ,\tau _{2m}(T) \}$$, соответствующие номерам
единичных элементов j-го столбца.Если все выбранные таким образом элементы $$\{ \tau _{2j\nu }\} (T)\} \subset \{ \tau _{21}(T), \dots , \tau _{2m}(T)\} , \nu = 1 , \dots , k_{j}$$, отличны от нуля, полагаем
$$\tau _{2j} (T) = min \{ \tau _{2j\nu } (T) - t_{j\nu } \}$$.
В противном случае выполняем шаг 2.
j -й столбец метим с целью исключения его
повторной обработки.
Переходим к выполнению шага 2.Конец алгоритма.
Если матрица S — треугольная, то поздние сроки окончания
выполнения работ
находятся за один просмотр столбцов.
Для матрицы S* (матрица S — треугольная) на
рис. 7.5 и для T = 10 за один просмотр
находим
$$\tau _{28}(10) = 10, \tau _{27}(10) = \tau _{28}(10) - t_{8} = 9, \tau _{26}(10) = \tau _{28}(10)- t_{8} = 9, \tau _{25}(10) = \tau _{28}(10) - t_{8} = 9 ,\tau _{24} = min \{ \tau _{26}(10), - t_{6}, \tau _{27}(10) - t_{7}\} = 5, \tau _{23}(10) = \tau _{28}(10) - t_{8} = 9, \tau _{22}(10) = min \{ \tau _{25}(10) - t_{5},\tau _{27}(10) - t_{7} \} = 5, \tau _{21}(10) = min \{ \tau _{23}(10) - t_{3}, \tau _{24}(10) - t_{4},\tau _{25}(10) - t_{5}, \tau _{26}(10) - t_{6}\} = 3$$.
Для нетреугольной матрицы S на рис. 7.10 при T =
10 находим $$\tau _{26}(10) = \tau _{25}(10) = 10$$. Обработка четвёртого
столбца откладывается, т.к. не
найдено значение $$\tau _{22}(10)$$. По этой же причине не
обрабатывается третий столбец.
После обработки второго столбца находим $$\tau _{22}(10) = \tau _{26}(10)- t_{6} = 9$$.
Обработка первого столбца невозможна, т.к. ещё не найдено значение $$\tau _{23}(10)$$. Продолжаем циклический обзор столбцов. После обработки четвёертого столбца получаем $$\tau _{24}(10) = \tau _{22}(10) - t_{2} = 6$$. Обработка третьего столбца даёт $$\tau _{23}(10) = min \{ \tau _{22}(10) - t_{2}, \tau _{25}(10) - t_{5}\} =6$$. После обработки первого столбца находим $$\tau _{21}(10) = \tau _{23}(10) - t_{3} = 4$$.
Диаграммы выполнения работ при поздних сроках окончания, по графам на
рис. 7.1 и
7.10, при T = 10 представлены на
рис. 7.12 — (а) и (б),
соответственно.
(Стрелки, соответствующие дугам в графах, опущены в связи с их
избыточностью.)
(рис 7.12) Диаграммы выполнения работ при поздних сроках окончания: а — для графа на рис. 7.1,б — для графа на рис. 7.10
Пусть $$\tau _{j}$$ — произвольное значение момента окончания
выполнения j -й работы, j =1 , ... , m,
$$\tau _{1j} \le \tau _{j} \le \tau _{2j}(T) (\tau _{j} \in [\tau _{1j}, \tau _{2j}(T)])$$.
Меняя значения $$\{ \tau _{j}\} , j = 1 , \dots ,m$$, но соблюдая при этом
порядок следования
работ, мы получим
Определение 7. Функцию$$\begin{align*} F(\tau_1,\tau_2 \dts \tau_m,t) = \sum_{j=1}^m f(\tau_j,t), \end{align*} где \begin{align*} f(\tau_j,t)= \left\{ \begin{array}{rcl} 1 \text{ при } t \in \lfloor \tau_j - t_j,\tau_j\rfloor \\ 0 \text{ в противном случае }, \end{array} \right. \end{align*}$$ назовём плотностью загрузки, найденной для значений $$\tau _{1} , \dots ,\tau _{m}$$.
Для заданных $$\tau _{1} , \dots , \tau _{m}$$ значение функции F в каждый момент времени t совпадает с числом одновременно (параллельно) выполняющихся в
этот момент работ.
Например, по диаграмме на 7.11,
т.е. для $$\tau _{1} = \tau _{11}, \tau _{2} = \tau _{12}, \dots , \tau _{8} = \tau _{18}$$,
функция F(2, 3, 3, 4, 7, 8, 6, 9, t) имеет вид, представленный на
рис. 7.13а.
Для F(2, 4, 3, 4, 8, 9, 7, 10, t)
имеет вид, представленный на рис. 7.13б.
(рис 7.13) Графики функции: а — для ранних сроков окончания работ,,б — для некоторого допустимого расписания
Для графического представления функции F удобно пользоваться
временной диаграммой,
которая для второго случая, например, имеет вид, представленный на рисунке 7.14..
(рис 7.14) Временная диаграмма функции F
Пусть данный граф G, в котором учтены l
полных множеств ri, i = 1 , ... , l,
число работ,
образующих i -е полное множество и найдём
R = max {r1 , ... , rl}.
Тогда$$\begin{align*}
R = \max\limits_{\tau_1,\tau_2 \dts \tau_m} F(\tau_1,\ldots \tau_m, t),
\end{align*}$$
т.к. возможно и такое распределение выполняемых работ во времени, задаваемое
набором $$\tau _{1} , \dots , \tau _{m}$$, (т.е. R
работ.
Например, для графа на рис. 7.1 мы нашли ПМВНР {3,5,6,7},
включающее четыре
работы. Тогда существует F равно четырём (рис. 7.15).
(рис 7.15) Максимальное значение плотности загрузки
Таким образом, справедливо утверждение
Лемма.
Минимальное число n процессоров
одинаковой специализации и производительности (т.е. в однородной ВС), способных
выполнить данный алгоритм
за время T >= Tкр, не превышает R = max
{r1 , ... , rl }, где ri , i = 1 , ... , l,
— число работ, входящих в i -е ПМВНР, которое составлено по
G,
соответствующему этому алгоритму.
Определение 8. Функцию$$\begin{align*}
\text{Ф} (\tau_1 \dts \tau_m, \theta_1, \theta_2)= \int_{\theta_1}^{\theta_2}
F(\tau_1 \dts \tau_m,t)dt
\end{align*}$$
назовём
Функция Ф определяет объём работ (суммарное время их
выполнения) на
фиксированном отрезке их выполнения при заданном допустимом расписании.
Так, для отрезка времени $$[0, 4] \subset [0, 10]$$ на рис. 7.13а Ф = 10 ; для отрезка
времени [1, 3] на ррис. 7.13б Ф= 4 ; для
отрезка времени [2, 5] на рис. 7.15 Ф = 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*}$$
назовём минимальной
Функция определяет минимально возможный объём работ, который при
данном T и при различных допустимых значениях
(расписаниях) $$\tau _{1} , \dots , \tau _{m}$$
должен быть выполнен на отрезке времени $$[\theta _{1}, \theta _{2}]\subset [0, T]$$.
Это означает,
что как бы мы не планировали вычислительный процесс, который должен
быть
закончен к моменту времени T, т.е. какой бы набор
значений $$\tau _{1} , \dots , \tau _{m}$$
мы не выбрали, объём работ, выполняемых на отрезке времени $$[\theta _{1}, \theta _{2}]$$,
не может быть меньше значения $$\varphi ^{(T)} = (\theta _{1},\theta _{2})$$.
Теорема 1. Для того чтобы T
было наименьшим временем выполнения данного
алгоритма однородной вычислительной системой, состоящей из n
процессоров,
либо чтобы n процессоров было достаточно для выполнения данного
алгоритма за время T, необходимо, чтобы для данного отрезка
времени $$[\theta _{1}, \theta _{2}] \subset [0, T]$$ выполнялось соотношение$$\begin{align*}
\varphi^{(T)}(\theta_1, \theta_2) \le n ( \theta_2 - \theta_1) \notag
\end{align*}$$
Доказательство. Нетрудно
видеть, что если при данном наборе $$\tau _{1} , \dots , \tau _{m}$$ — сроках окончания выполнения работ, в том
числе и при таком наборе,
при котором обеспечивается минимальное или заданное $$T = max \{ \tau _{1}, \dots , \tau _{m}\}$$,
для реализации алгоритма достаточно n процессоров, то$$\begin{align*}
\max_{t\in[0,T]}F(\tau_1 \dts \tau_m\,t)\le n.
\end{align*}$$
Отсюда, для любого отрезка времени $$[\theta _{1}, \theta _{2}] \subset [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*}$$
Для получения полной оценки надо перебрать все отрезки $$[\theta _{1},\theta _{2}] \subset [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*}$$
Проанализируем все возможные отрезки $$[\theta _{1}, \theta _{2}] \subset [0,3] : \varphi ^{(3)}(0, 1) = \varphi ^{(3)}(1, 2) \varphi ^{(3)}(2, 3) = 0, \varphi ^{(3)}(0, 2) = \varphi ^{(3)}(1, 3)= 3, \varphi ^{(3)}(0, 3) = 6$$. Находим
минимальное n = 2, удовлетворяющие (7.3). Однако из рисунка
видно, что не
существует плана выполнения работ на двух процессорах за время T=3.
Минимально достаточное число процессоров здесь n = 3.
Функция $$\varphi ^{(T)}(\theta _{1}, \theta _{2})$$ минимальной
Предварительно определим функцию$$\begin{align*} \xi (x) = \left\{ \begin{array}{rcl} x \text { при } x\ge 0 \\ 0 \text { при } x< 0. \end{array} \right. \end{align*}$$
Тогда значение $$\xi (\tau _{1j} - \theta _{1})$$ характеризует
условный объём части работы j на
отрезке времени $$[\theta _{1}, \theta _{2}]$$ при условии $$\tau _{1j} - t_{j} \le \theta _{1}$$ и при максимальном
смещении времени выполнения работы j влево (рис. 7.17а).
Значение $$\xi (\theta _{2} - \tau _{2j}(T) + t_{j})$$ характеризует
аналогичный объём работы j при
максимальном смещении времени выполнения работы j вправо. Это
соответствует,
например, ситуации, изображённой на рис. 7.17б.
(рис 7.17) Нахождение минимальной плотности загрузки отрезка: все различные случаи соотношения времени выполнения работ и сроков
Если для работы j оба указанных выше значения функции $$\xi$$ отличны от нуля,
но не превышают значение tj и $$\theta _{2} - \theta _{1}$$,
то максимально разгрузить отрезок $$[\theta _{1}, \theta _{2}]$$ от работы j можно смещением
времени его выполнения в сторону,
обеспечивающую меньшее из двух указанных выше значений $$\xi$$ (рис. 7.17в).
Существуют два случая, когда работа j не может быть хотя бы
частично смещена
с отрезка $$[\theta _{1}, \theta _{2}]:$$
а) $$\theta _{1} \le \tau _{1j} - t_{j} < \tau _{2j} (T) \le \theta _{2}$$, в этом случае очевидно,
что $$t_{j} \le \theta _{2} - \theta _{1}$$
(рис. 7.17г), и объём работы j, выполняемой на отрезке,
совпадает с объёмом tj всей этой работы;
б) $$\tau _{1j} \ge \theta _{2} \Lambda \tau _{2j}(T) - t_{j} \le \theta _{1}$$, в этом случае очевидно,
что $$t_{j} \ge \theta _{2} - \theta _{1}$$
(рис. 7.17д), и объём части работы j, выполняемой на отрезке $$[\theta _{1}, \theta _{2}]$$
совпадает со значением $$\theta _{2} - \theta _{1}$$.
Приведённый ниже алгоритм объединяет все возможные указанные выше случаи.
Алгоритм 4 нахождения значения функции $$\varphi ^{(T)}(\theta _{1}, \theta _{2})$$.
1. Предполагаем, что для каждой работы j = 1, ... , m, известны
значения $$t_{j},\tau _{1j}, \tau _{2j}(T)$$. Полагаем равным нулю значение переменной $$\phi.$$
2. Организуем j = 1, ... , m.
3. Для каждой работы j полагаем
$$\varphi := \varphi + min \{ \xi (\tau _{1j} - \theta _{1}), \xi (\theta _{2} -\tau _{2j}(T) + t_{j}), t_{j} , \theta _{2} - \theta _{1}\}$$.
После перебора всех работ $$\varphi = \varphi ^{(T)}(\theta _{1},\theta _{2})$$.
Конец алгоритма.
Выше было получено соотношение (7.2) , которое можно использовать для n процессоров, необходимых
для выполнения данного алгоритма
за время, не превышающее T.
Приведём аналогичное соотношение для нижней оценки минимального времени Т.
Теорема 2. Пусть заданный алгоритм выполняется на ВС, состоящей
из n процессоров,
и T* — текущее значение оценки снизу времени выполнения
алгоритма. Пусть на
отрезке времени $$[\theta _{1}, \theta _{2}] \subset [0, T^{*}]$$
выполняется соотношение
$$\varphi ^{(T*)}(\theta _{1},\theta _{2}) - n(\theta _{2} - \theta _{1}) = d > 0$$.
Тогда минимальное время T выполнения алгоритма удовлетворяет
соотношению$$\begin{align*}
T \ge T^* + \frac{d}{n}.
\end{align*}$$
Теоремы 1 и 2 на основе анализа такой локальной характеристики параллельного алгоритма, как значение функции $$\phi$$ минимальной загрузки отрезка, предлагают способы оценки снизу ресурсов, необходимых для реализации каждого заданного алгоритма:
n процессоров при заданном ограничении на
длительность T процесса;T, необходимого для реализации
данного алгоритма при
заданном числе n процессоров.
(рис 7.18) К примеру нахождения нижней оценки числа исполнителей
Алгоритм 5.
n = 0.Организуем перебор всех отрезков $$[\theta _{1}, \theta _{2}] \subseteq [0, T]$$ в порядке$$\begin{align*} [0,1] ;\\ [0,2] ; [1,2] ;\\ [0,3] ; [1,3] ; [2,3] ;\\ . . . . . . . . . . . . . . . . . . . . . . . . . .\\ [0,T] ; [1,T] ; \ldots , [T-1,T] . \end{align*}$$
Всего таких отрезков T(T+1)/2.
n' > n, выполняем операцию n := n'.
После перебора всех отрезков
окажется найденным значение n, которое равно максимальному из
значений,
удовлетворяющих (7.2).Пример. Нахождение оценки n.
Нахождение $$\varphi ^{(4)}(\theta _{1},\theta _{2})$$ будем иллюстрировать графически, возможными временными диаграммами (рис. 7.19).
(рис 7.19) Нахождение нижней оценки числа исполнителей(рис 7.19) Окончание
В результате анализа всех отрезков находим n = max n' = 2.
Алгоритм 6.
Первоначально полагаем
$$\begin{align*} T = \max \left \{ ]\frac{1}{n}\sum_{j=1}^m t_j[,\,T_\t{кр}\right \}. \end{align*}$$
T может увеличиваться, что при данном
порядке
перебора не приведёт к усложнению алгоритма.)Для очередного анализируемого отрезка времени $$[\theta _{1},\theta _{2}]$$ находим значение
$$d = \varphi ^{(T)}(\theta _{1},\theta _{2}) - n(\theta _{2} - \theta _{1})$$
d > 0, выполняем операцию T := T + ] d/n
[.После перебора всех отрезков $$[\theta _{1}, \theta _{2}]$$ окажется
найденным окончательное
значение T — нижняя оценка минимального времени выполнения
данного алгоритма
на данной ВС.
Пример.
Произведём оценку T для графа G, рассмотренного в
предыдущем
примере, и ВС, состоящей из двух процессоров, n = 2 (рис. 7.20).
(рис 7.20) Оценка снизу минимального времени выполнения работ(рис 7.20) Окончание
Первоначально находим$$T = \max \left \{ \frac{1}{2}\cdot (2+2+1+1),T_{кр}=3\right \}=3.$$
После перебора всех отрезков, с учётом уточнения оценки времени в процессе
этого перебора, окончательно находим T = 4.
G, и для времени T, отведённого для его
выполнения, найти наименьшее
число n процессоров, составляющих однородную ВС, и план
выполнения работ на
них.
Метод точного решения задачи (метод "ветвей и границ") основан на следующей основной теореме.
Теорема. Для того чтобы значение n являлось наименьшим числом процессоров
однородной ВС, которая выполняет алгоритм, представленный информационным
графом G = (X, P, Г ), за время, не превышающее заданное
значение T, необходимо
и достаточно, чтобы n было наименьшим числом, для которого можно
построить
граф G' = (X, P, Г'), объединив вершины, соответствующие
работам каждого
ПМВНР, который содержит r > n работ r - n
ориентированными дугами в n путей
не содержащих общих вершин. При этом длина критического пути в графе G' не
должна превышать значение T.
Алгоритм 7 решения задачи 1
— нахождения
графа-решения G'
Для графа G и времени T находим значения
ранних $$\{ \tau _{1j}\}$$ и поздних $$\{ \tau _{j}(T)\} ,j = 1 , \dots , m$$, сроков окончания выполнения работ. (Если задача поставлена
корректно, то$$\begin{align*}
\max \{\tau_{1j}\} = T_\text{кр} \le T .)\\
j
\end{align*}$$
n процессоров, которое
необходимо для
выполнения заданного алгоритма за время, не превышающее T.Пусть $$\nu$$ — номер шага решения задачи. Полагаем $$\nu = 1$$.
Находим наименьшее значение $$t_{\nu }$$ такое, что
$$F(\tau _{11}, \tau _{12} , \dots , \tau _{1m}, t_{\nu } ) = r_{\nu } > n$$.
Если такого $$t_{\nu }$$ нет, то n — решение
задачи.
Выделяем множество работ $$A_{\nu } = \{ \alpha _{j\mu }\} , \mu =1 , \dots ,r_{\nu }$$, для которых
$$\tau _{1j\mu } - t_{j\mu } \le t_{\nu } < \tau _{1\mu }$$,
т.е. тех работ, которые "порождают" данное значение F. Множество A является
подмножеством некоторого ПМВНР.
r -
n связей, как указано
в теореме — так, чтобы длина критического пути в изменившемся при этом графе G не превысила T.n — решение, выполняем
операцию n := n + 1 и
переходим к выполнению 3. Если $$\nu \ne 0$$, восстанавливаем
значения $$\{ \tau _{1j}\}$$ и $$\{ \tau _{2j}(T)\} ,$$
найденные на данном шаге, и переходим к выполнению 6.Конец алгоритма.
n. Пытаемся
сгладить значение
этой функции, введя дополнительные связи между работами, допускаемые
ограничением T. В случае неудачи вернёмся на шаг назад и
попытаемся ввести
другую комбинацию связей. При переборе всех комбинаций связей на первом шаге,
не приведших к успеху, увеличим предполагаемое число процессоров и начнём
процесс сглаживания функции плотности загрузки сначала.
Примечания
Пусть $$A_{\nu }$$ — множество r - n связей по условию теоремы, т.е. построить
некоторый граф, связывающий вершины $$A_{\nu }$$. Построим матрицу
следования $$L_{\nu }$$,
соответствующую этому графу. Первоначально эта матрица —
нулевая. Вводим $$r_{\nu } - n$$ единиц так, чтобы:
Перемещая последнюю единицу сначала по строке, затем по столбцам, затем перейдя к предпоследней единице и т.д., осуществляем перебор всех возможных комбинаций связей между работами множества $$A_{\nu }$$.
Можно рекомендовать T, необходимо вновь пересчитать
значение
функции $$\phi$$ с учётом новых связей на всех отрезках $$[\theta _{1}, \theta _{2}] \subseteq [t_{\nu }, T].$$ Если для
испытываемого значения n на этих отрезках выполняется соотношение
(7.2),
данная комбинация связей может быть признана удачной. Таким образом, выполнение
соотношения (7.2) в совокупности с допустимым увеличением длины критического
пути определяет "границы" при ветвлении.
(Напомним, что метод "ветвей и границ", как NP -
Пример.
Найдём минимальное число n процессоров, необходимое
для выполнения
алгоритма, который представлен графом G на рисунке 7.21а, за
время T = 7.
(рис 7.21) Последовательные действия при точном решении задачи 1
По алгоритму 4 найдёем нижнюю оценку n = 2, исследовав 28
значений $$\varphi ^{(7)}(\theta _{1},\theta _{2})$$
для всех $$[\theta _{1}, \theta _{2}] \subseteq [0, 7].$$ При этом $$\tau _{11} = 1, \tau _{12} = \tau _{13} = \tau _{14} = 2,\tau _{15} = \tau _{16} = 4, \tau _{17} = 5, \tau _{21}(7) = \tau _{22}(7) = 4, \tau _{23} (7) =\tau _{24}(7) = \tau _{26} (7) = 6,\tau _{25}(7) = \tau _{27} = 7$$. Мы не собираемся впредь иллюстрировать
нахождение функции
минимальной загрузки, поэтому не будем приводить динамически уточняемые
значения
поздних сроков окончания выполнения работ.
$$F(\tau _{11} , \dots , \tau _{17}) = 4 > 2$$, т.е. t1 =
0. В формировании этого значения участвуют
работы 1, 2, 3, 4. Составим квадратную матрицу L1 (рис. 7.21в)
с первоначально
нулевыми элементами. Постараемся последовательно ввести в неё два единичных
элемента. Первая возможная комбинация двух таких элементов соответствует связям 3 -> 2 -> 1. Длина критического пути в графе G, дополненном дугами в
соответствии с
этими связями, превышает 7. Пробуем заменить вторую связь следующей возможной.
Новая испытываемая комбинация связей 4 -> 2 ->
1 также приводит к недопустимому
увеличению длины критического пути. Единичные элементы, соответствующие
отвергнутым связям, на рисунке зачёркнуты.
Вновь меняем вторую связь, полагая равным единице первый элемент третьей
строки матрицы L1. Новая комбинация связей 2 -> 1
-> 3 не приводит к недопустимому
увеличению длины критического пути в графе G. По графу,
учитывающему
введённые связи, находим ранние и поздние сроки окончания выполнения работ.
На рис. 7.21г, приведена диаграмма выполнения алгоритма при
Найдём t2 = 3 такое, что F(3, 2, 5, 2, 6, 5, 6, 3) =
3 > 2. Данное
значение функции плотности загрузки определяется выполнением работ 3, 5,
6. Составляем матрицу L2 (рис. 7.21д) и стараемся ввести в ней
единственный единичный элемент. Однако перебор всех возможных способов
введения такого элемента приводит к длине критического пути в образующемся
графе, превышающей 7. Возвращаемся на шаг назад к анализу матрицы L1 и
пробуем ввести другую допустимую комбинацию связей. Такой комбинацией
является 2 -> 1, 4 -> 3. На рис. 7.21е
представлена
диаграмма выполнения алгоритма при уточнённых
Вновь находим значение t2 = 3 такое, что F(3, 2, 4,
2, 6, 5, 6, 3) = 3 > 2.
(Совпадение значений t2 и выделенных работ с ранее
исследованными является
скорее случайным.) Вновь формируем матрицу L2 (индекс указывает
номер шага,
новая матрица L2 в общем случае ничем не схожа с аналогичной
ранее рассмотренной
матрицей), и находим первую из допустимых связей — связь 6 ->
3 (рис. 7.21ж).
Вновь (рис. 7.21з) находим значение t3 = 5, где плотность
загрузки превышает
значение 2. Составляем матрицу L3 (рис. 7.21и). Находим в ней
единственную
единицу, соответствующую допустимой связи 5 -> 7. На
рис. 7.21к представлена
диаграмма выполнения алгоритма, удовлетворяющая решению задачи.
Собственно расписание определяется найденными на последнем шаге значениями $$\{ \tau _{1j}\} .$$
Формулировка задачи:
Для данного алгоритма, которому соответствует информационный
граф G, найти минимальное время T и план выполнения
этого алгоритма на данной
однородной ВС, содержащей n процессоров.
Теорема. Для того, чтобы T было
минимальным временем
выполнения алгоритма,
представленного G = (X, P, Г), на
однородной ВС,
состоящей из n процессоров, T
было наименьшей
из возможных длин критических путей в графах вида G'= (X, P,
Г'), что получены
из данного объединением вершин, соответствующих работам каждого ПМВНР, который
содержит r > n работ, r - n ориентированными
дугами в n путей, не
содержащих общих вершин.
(рис 7.22) Информационный граф распараллеливаемой задачи
Алгоритм 8 решения задачи 2 — нахождения
графа-решения G'
T = T0 минимального времени
выполнения данного
алгоритма на ВС, содержащей n процессоров.n процессоров выполнить данный
алгоритм за время T0.
Если T0 — не решение задачи 2, используем следующий метод.Находим наименьшее значение $$t_{\nu }$$ такое, что $$F(\tau _{11} , \dots , \tau _{1m}, t_{\nu }) = r_{\nu } > n$$.
Если такого значения $$t_{\nu }$$ нет на первом же шаге сглаживания
плотности загрузки
(при $$\nu = 1$$ ), то значение Tкр — решение
задачи 2. Если такого значения больше
нет при $$\nu > 1$$, то увеличиваем значение $$\mu$$ на
единицу и полагаем $$T_{\mu } = max\{ \tau _{11}, \dots , \tau _{1m}\} ,$$ т.е. длине критического пути в графе G', построенном в соответствии с
условиями теоремы. Не меняя значение $$\nu,$$ переходим к выполнению
6. (Если $$T_{\mu } =T_{0} + 1$$, то т.к. T0 — не решение задачи, искать
значение $$T < T_{\mu }$$ нецелесообразно,
т.е. найденное значение $$T_{\mu }$$ — решение задачи 2).
Если значение $$t_{\nu }$$, обеспечивающее неравенство в пункте 4, найдено, выделяем множество работ $$A_{\nu } = \{ \alpha _{j\rho }\} , \rho = 1 , \dots , r_{\nu }$$, для которых
$$\tau _{1j\rho } - t_{j\rho } \le t_{\nu } < \tau _{1j\rho }$$.
Множество $$A_{\nu }$$ является подмножеством некоторого ПМВНР.
G' была меньше $$T_{\mu }$$.Конец алгоритма.
Пример.
Пусть заданы 6 задач (m = 6), заданы их частичная упорядоченность
графом G, заданы времена решения (веса вершин). Требуется найти
расписание
выполнения этих задач на двух процессорах (n = 2) — такое,
чтобы время
решений этих задач было минимальным.
Найдём нижнюю T.
Первоначально полагаем $$T = \max \left \{ \left] \frac{1}{n}\suml_{j=1}^m t_j \right [, \,T_\text{кр} \right \} = {\max \{ 6,6 \} = 6}$$.
По алгоритму 6, испытывая значения функции минимальной загрузки, найдём, что $$\frac{\varphi^{6}(1,6)}{5} = \frac{11}{5} > 2$$. Произведем единственное уточнение значения $$T_0 = 6 + \left]\frac{1}{2}(\frac{11}{5}-2)\right [=7$$.
Без учета реально доступного количества процессоров составим (рис. 7.23) временную диаграмму решения всей совокупности задач — такую, при которой каждая из задач решается как можно раньше, и определим загрузку как бы неограниченного числа процессоров:
(рис 7.23) Временная диаграмма решения задач
находим первый момент времени, при котором по этой диаграмме нам
требуется
более двух процессоров: при t=1 это количество F(1)=3. Выделим образующие это
значение F задачи: {2, 3, 4} и составим матрицу L1 (рис. 7.24а). Первой
испытываемой связью является связь 3 -> 2. Диаграмма,
соответствующая этой связи, —
на рис. 7.24б.
(рис 7.24) Первый шаг распределения: а — матрица следования, б — временная диаграмма
Т.к. больше нет значений функции плотности загрузки, превышающих 2, то мы предполагаем возможное решение, но продолжаем перебор связей для поиска более короткого расписания.
следующей испытываемой связью по матрице L1, определяющей
длину
критического пути, меньшую 8, является связь 4 -> 2.
Соответствующее расписание — на рис. 7.25.
(рис 7.25) Введение новой связи: а — матрица следования, б — временная диаграмма
вновь находим первый момент времени, при котором нам требуется более двух
процессоров: при t = 2 это количество F(2) = 3.
Выделим образующие это значение F задачи: {2, 3, 6} и составим матрицу L2 (рис. 7.26а). Первой возможной связью,
не приводящей к длине критического пути, равной 8 или выше, является связь 2 -> 3.
Диаграмма, соответствующая этой связи, — на рис. 7.26б.
(рис 7.26) Введение последней связи: а — матрица следования, б — окончательный вид временной диаграммы
Т.к. значение функции плотности загрузки больше не превышает значение 2, то мы нашли оптимальное расписание, ибо его длина не превосходит нижней оценки — значения 7.
Задачи точного распараллеливания в настоящей лекции освещаются только для однородных систем исполнителей, когда все такие исполнители "умеют" всё и каждую работу выполняют за одинаковое время. Это предполагает применение методов для однородных вычислительных систем. Однако при более широком применении методов распараллеливания в управлении и экономике актуальна постановка этих задач для неоднородного состава исполнителей, в частности — когда исполнители обладают разной специализацией. Достаточно рассмотреть управление строительством или уборочной кампанией. Алгоритмы точного решения задач распараллеливания для неоднородных систем представлены в [3].
Высокая производительность ВС достигается
Проблема её программирования — это
С ориентацией на достижение максимальной производительности ВС, а также на специальное применение в составе конкретных систем, например, в составе сложных систем управления, различают две взаимно-обратные задачи параллельного программирования.
Задача 1.
Под стоимостью понимают
В однородной ВС задача 1 вырождается в задачу
Задача 2.
Представим себе программу решения задачи, которая отображает
последовательное
изложение алгоритма на машинном языке, ассемблере или
Например, программа F представляется как
F = F1(X1 , X2 ; X3 , X4 ) F2 (X2 ; X5 ) F3 (X3 ; X6 ) F4 (X1 ,
X4 ;
X7 ) F5 (X3 , X4 , X5 ; X8 ) F6 (X3 , X4 , X7 ; X9 ) F7 (X5 , X7 ;
X10) F8 (X6 , X8 , X9 , X10 ; Y),
где точкой с запятой отделены входные данные от выходных, X = {X1,
X2} —
исходные данные задачи, Y — выходные данные или результат.
Итак, мы разбили заданный алгоритм решения задачи на ряд модулей,
операторов,
работ и установили информационную взаимосвязь этих работ. Чтобы подчеркнуть
общность задач и методов распараллеливания, не ограничивающуюся применением
только для ВС, будем пользоваться термином
Для решения задач оптимального выполнения работ многими исполнителями (т.е.
процессорами ВС) нам понадобятся временные оценки выполнения как программы в
целом, так и каждого
Пусть относительно данного алгоритма и предполагаемой ВС нам известны
следующие
оценки T = {t1, t2, ... , t8}.
Тогда, чтобы отразить прохождение обрабатываемой информации и выявить
возможности
распараллеливания, представим G (рис. 7.1). Вершины соответствуют работам. Дуги отражают
частичную упорядоченность работ.
(рис 7.1) Информационный граф алгоритма
А именно, если работа $$\beta$$ использует в качестве входной
информации результат
выполнения работы $$\alpha,$$ то её выполнение не может быть начато
до того, как
закончится выполнение работы $$\alpha.$$ Такая преемственность
информации и отражена в
графе. Граф G — взвешенный, ориентированный и не содержит
контуров. (Т.к. время
выполнения алгоритма конечно, то программные циклы либо погружены внутрь работ,
либо развёрнуты.)
Например, представим себе информационный
граф, соответствующий скалярному
умножению векторов заданной длины: A = B x C способом
"пирамиды", В = {b1 , ... , b8}, C = {c1 , ... , c8}. Схема счёта показана
на рис. 7.2.
(рис 7.2) Схема счёта "пирамидой"
Примем время сложения равным единице. Время умножения пусть превышает время
сложения в четыре раза. G, соответствующий
счёту способом
"пирамиды", представлен на рис. 7.3.
(рис 7.3) Информационный граф — "пирамида"
Мы рассмотрели составление
Например, может быть целесообразным следующее разбиение программы (алгоритма) на модули (работы):
F = F1(X1; X2) if A then F2(X2; X3) else F3(X1;X4) F4(X1, X3, X4; Y).
Информационно-логический граф G — на рис. 7.4.
(рис 7.4) Информационно-логический граф
Преемственность информации (1 -> 2), а также (1
-> 3), при наличии
"жирной"
стрелки "по управлению" можно не указывать, так как частичная
упорядоченность
работ в таком случае полностью определена.
Рассмотрение информационно-логических графов сильно усложняет решение задач оптимизации параллельных вычислений. Практически ограничиваются планированием выполнения самой сложной, трудоемкой ветви алгоритма или решают её для разных ветвей отдельно, — т.е. сводят оптимизацию к рассмотрению только информационных графов.
Для формальных исследований G
представляется матрицей
следования S, или, с добавлением столбцов весов, — расширенной
матрицей следования S*. При этом, т.к. граф G не содержит контуров
(циклов), то S может быть сведена
к треугольной "правильным" выбором нумерации вершин. Ниже (рис. 7.5) приведены
матрицы S и S* для графа, представленного на
рис. 7.1, и для некоторых известных
значений весов.
(рис 7.5) Матрица следования с задающими связями
Определение 1. Назовём все связи по
информации, обусловленные исходным видом
графа G,
Определение 2. G будем называть последовательности вершин вида a1, a2 , ... , as такие, что для любой пары соседних вершин ai и ai+1 существует
дуга, исходящая из вершины ai и входящая в вершину ai+1.
Будем считать все пути в графе G допустимыми, т.е. реально
существующими
ветвями отображаемой программы.
Определение 3. G назовём
сумму весов вершин,
составляющих этот путь.
Определение 4. Tкр в информационном графе G назовём
В одном графе может быть несколько путей равной длины, являющихся критическими.
Если в графе G есть дуга, исходящая из вершины a и входящая в вершину b, т.е.
существует a -> b, а также есть дуга,
исходящая из вершины b и
входящая в вершину c, т.е. существует b
-> c, но нет задающей
связи a -> c, очевидно, что последовательный порядок
выполнения работ a и c
определяется двумя указанными задающими связями. Т.е. граф G
можно дополнить
дугой, соответствующей связи a -> c, что только
подтвердит заданную частичную
упорядоченность работ.
Определение 5. Множество связей, которые
введены направленно внутри всех пар
работ, принадлежащих одному пути в графе G и не связанных
задающими связями,
назовём
Алгоритм 1 дополнения треугольной матрицы S транзитивными связями.
S.i -й строке организуем просмотр элементов в
порядке увеличения j номеров столбцов.(i, j)=1, складываем строки i и j по операции дизъюнкции.S нетреугольная,
последовательный просмотр
её строк производится неоднократно до установления факта неизменности
окончательно полученной матрицы.)Конец алгоритма.
В представленном выше примере после введения всех
S примет вид, представленный на рисунке 7.6)рисунке 7.6
(введённые транзитивные
связи выделены курсивом).
(рис 7.6) Матрица следования с транзитивными связями
С помощью введения G. О наличии контуров
свидетельствуют
появившиеся ненулевые диагональные элементы, указывающие на связь вида a
-> a.
Например, пусть задан граф G
на рис. 7.7.
(рис 7.7) Граф алгоритма и матрица следования
После первого шага преобразования S принимает вид, показанный
на рис. 7.8.
(рис 7.8) Первый шаг обнаружения контура
После второго шага преобразования S принимает вид, показанный
на рис. 7.9.
(рис 7.9) Обнаружение контура
Т.к. на главной диагонали матрицы появились единицы, то граф G содержит циклы
(контуры). Из рисунка графа виден цикл 2 -> 6 -> 3
-> 5 ->. "Участники" цикла отмечены единицами на
главной диагонали.
Определение 6. Работы a и b будем называть S выполняется условие (a, b) = (b, a) = 0.
Определение 7. Работы {ai}, i = 1, ... , s,
образуют
Например, для графа G,
представленного на рис. 7.1, после введения транзитивных
связей, что учтено в матрице следования на рис. 7.6, можно установить
следующие
ПМВНР: {1,2}, {2,3,4}, {3,4,5}, {2,3,6}, {3,5,6,7}, {8}.
Таким образом, для каждой i = 1 , ... , m работы алгоритма,
представленного
T < Tкр, то для
каждой
работы можно найти и i -й работы позже этого срока приводит к тому, что выполнение
других
работ, следующих за данной, не может быть закончено до истечения времени T. Иначе говоря, поздний срок окончания выполнения данной работы
не
может превышать разности между значением T и максимальной из длин
путей,
в первую вершину которых входит дуга, что исходит из вершины,
соответствующей данной работе. Без задания значения T
(ограничения на
длительность вычислительного процесса) определение позднего срока
окончания выполнения работы не имеет смысла.
При T = Tкр ранние сроки окончания выполнения работ,
составляющих критические
пути, совпадают с поздними сроками окончания их выполнения.
Прежде чем рассмотреть алгоритм нахождения ранних и поздних сроков окончания
выполнения работ по S*, отметим,
что учёт
G не содержит контуров, то матрица следования S
может быть преобразована в
треугольную. Однако при построении алгоритмов решения задач распараллеливания
не представляется удобным преобразовывать матрицу следования. Поэтому будем
считать, что в общем случае матрица S не треугольная.
Алгоритм 2 нахождения ранних сроков окончания выполнения работ.
S, находим
очередную из
необработанных строк. Если все строки обработаны, выполнение алгоритма
заканчивается.j — номер найденной необработанной строки. Если j -я строка не содержит
единичных элементов, полагаем $$\tau _{1j} = t_{j}$$. Переходим к
выполнению шага 6.j -я строка содержит единичные элементы, выбираем
элементы множества $$\{ \tau _{11} , \dots , \tau _{1m}\}$$, соответствующие номерам единичных
элементов j -й строки.Если все выбранные таким образом элементы, образующие множество $$\{ \tau _{1j(\nu )}\} , \nu = 1, \dots , k_{j}$$, отличны от нуля, полагаем $$\tau _{1}j = max \tau _{1 j\nu } + t_{j}$$.
Если хотя бы один из выбранных элементов нулевой (соответствующий ранний срок ещё не найден), выполняем шаг 2.
Обработанную j -ю строку метим, чтобы исключить её повторную
обработку.
Переходим к выполнению шага 2.
Примечание. Если граф G не содержит контуров, зацикливание при этом невозможно.
Конец алгоритма.
Если матрица S треугольная, то никогда не складываются условия
для многократного
циклического обзора строк. Тогда ранние сроки окончания выполнения работ
находятся за один последовательный просмотр строк матрицы S.
Очевидно, что $$T_{кр} = max \{ \tau _{11} , \dots ,\tau _{1m}\}$$.
По матрице S* ( S — треугольная) на рис. 7.5 (граф G — на рис. 7.1) находим
$$\tau _{11} = t_{1} = 2, \tau _{12} = t_{2} = 3, \tau _{13} = \tau _{11} + t_{3}=3, \tau _{14}= \tau _{11} + t_{4} = 4,\tau _{15} = max \{ \tau _{11}, \tau _{12} + t_{5}= 7, \tau _{16} = max\{ \tau _{11},\tau _{14}\} + t_{6} = 8, \tau _{17} = max \{ \tau _{12},\tau _{14} \} + t_{7} = 6,\tau _{18} = max \{ \tau _{13}, \tau _{15}, \tau _{16}, \tau _{17}\} + t_{8} = 9; T_{кр} = 9$$.
Чтобы рассмотреть пример с нетреугольной матрицей следования, выберем граф G без контуров с "неправильно" пронумерованными
вершинами (рис. 7.10).
(рис 7.10) Информационный граф с не треугольной матрицей следования
После обработки первой строки $$\tau _{11} = 1$$. Попытка
обработать вторую строку неудачна,
т.к. $$\tau _{13}$$ и $$\tau _{14}$$ ещё не найдены. После
обработки третьей строки $$\tau _{13} = \tau _{11} + t_{3} = 3$$.
Обработка четвёртой строки даёт $$\tau _{14} = 2$$. После обработки
пятой строки $$\tau _{15} = \tau _{13} + t_{5} = 4$$. Попытка обработки шестой строки
неудачна, т.к.
не найдено значение $$\tau _{12}$$. Приступаем к следующему циклу
обзора необработанных
строк S.
Обрабатываем вторую строку: $$\tau _{12} = max \{ \tau _{13}, \tau _{14}\} +t_{2} = 6$$.
После обработки шестой строки $$\tau _{16} = \tau _{12} + t_{6} = 7.T_{кр} = 7$$.
Для удобства представления наряду с другими способами будем пользоваться
наглядными диаграммами выполнения работ при заданных значениях времени начала
или окончания их выполнения. Работы обозначаются прямоугольниками с постоянной
высотой и длиной, равной времени выполнения. Стрелки, связывающие
прямоугольники-работы, соответствуют дугам в графе G. На рис. 7.11 представлена
диаграмма выполнения работ, отраженных графом G на рис. 7.1 и
расширенной
матрицей следования на рис. 7.5 — при
(рис 7.11) Временная диаграмма выполнения работ при ранних сроках окончания
Алгоритм 3 нахождения поздних сроков окончания выполнения работ при заданном
значении Т.
S, находим
очередной из не обработанных ещё столбцов. Если все столбцы обработаны,
выполнение алгоритма заканчивается.j — номер найденного необработанного столбца. Если j -й столбец не
содержит единичных элементов, полагаем $$\tau _{2j}(T) = T$$.
Переходим к выполнению шага 6.j -й столбец содержит единичные элементы, выбираем
элементы множества $$\{ \tau _{21}(T) , \dots ,\tau _{2m}(T) \}$$, соответствующие номерам
единичных элементов j-го столбца.Если все выбранные таким образом элементы $$\{ \tau _{2j\nu }\} (T)\} \subset \{ \tau _{21}(T), \dots , \tau _{2m}(T)\} , \nu = 1 , \dots , k_{j}$$, отличны от нуля, полагаем
$$\tau _{2j} (T) = min \{ \tau _{2j\nu } (T) - t_{j\nu } \}$$.
В противном случае выполняем шаг 2.
j -й столбец метим с целью исключения его
повторной обработки.
Переходим к выполнению шага 2.Конец алгоритма.
Если матрица S — треугольная, то поздние сроки окончания
выполнения работ
находятся за один просмотр столбцов.
Для матрицы S* (матрица S — треугольная) на
рис. 7.5 и для T = 10 за один просмотр
находим
$$\tau _{28}(10) = 10, \tau _{27}(10) = \tau _{28}(10) - t_{8} = 9, \tau _{26}(10) = \tau _{28}(10)- t_{8} = 9, \tau _{25}(10) = \tau _{28}(10) - t_{8} = 9 ,\tau _{24} = min \{ \tau _{26}(10), - t_{6}, \tau _{27}(10) - t_{7}\} = 5, \tau _{23}(10) = \tau _{28}(10) - t_{8} = 9, \tau _{22}(10) = min \{ \tau _{25}(10) - t_{5},\tau _{27}(10) - t_{7} \} = 5, \tau _{21}(10) = min \{ \tau _{23}(10) - t_{3}, \tau _{24}(10) - t_{4},\tau _{25}(10) - t_{5}, \tau _{26}(10) - t_{6}\} = 3$$.
Для нетреугольной матрицы S на рис. 7.10 при T =
10 находим $$\tau _{26}(10) = \tau _{25}(10) = 10$$. Обработка четвёртого
столбца откладывается, т.к. не
найдено значение $$\tau _{22}(10)$$. По этой же причине не
обрабатывается третий столбец.
После обработки второго столбца находим $$\tau _{22}(10) = \tau _{26}(10)- t_{6} = 9$$.
Обработка первого столбца невозможна, т.к. ещё не найдено значение $$\tau _{23}(10)$$. Продолжаем циклический обзор столбцов. После обработки четвёертого столбца получаем $$\tau _{24}(10) = \tau _{22}(10) - t_{2} = 6$$. Обработка третьего столбца даёт $$\tau _{23}(10) = min \{ \tau _{22}(10) - t_{2}, \tau _{25}(10) - t_{5}\} =6$$. После обработки первого столбца находим $$\tau _{21}(10) = \tau _{23}(10) - t_{3} = 4$$.
Диаграммы выполнения работ при поздних сроках окончания, по графам на
рис. 7.1 и
7.10, при T = 10 представлены на
рис. 7.12 — (а) и (б),
соответственно.
(Стрелки, соответствующие дугам в графах, опущены в связи с их
избыточностью.)
(рис 7.12) Диаграммы выполнения работ при поздних сроках окончания: а — для графа на рис. 7.1,б — для графа на рис. 7.10
Пусть $$\tau _{j}$$ — произвольное значение момента окончания
выполнения j -й работы, j =1 , ... , m,
$$\tau _{1j} \le \tau _{j} \le \tau _{2j}(T) (\tau _{j} \in [\tau _{1j}, \tau _{2j}(T)])$$.
Меняя значения $$\{ \tau _{j}\} , j = 1 , \dots ,m$$, но соблюдая при этом
порядок следования
работ, мы получим
Определение 7. Функцию$$\begin{align*} F(\tau_1,\tau_2 \dts \tau_m,t) = \sum_{j=1}^m f(\tau_j,t), \end{align*} где \begin{align*} f(\tau_j,t)= \left\{ \begin{array}{rcl} 1 \text{ при } t \in \lfloor \tau_j - t_j,\tau_j\rfloor \\ 0 \text{ в противном случае }, \end{array} \right. \end{align*}$$ назовём плотностью загрузки, найденной для значений $$\tau _{1} , \dots ,\tau _{m}$$.
Для заданных $$\tau _{1} , \dots , \tau _{m}$$ значение функции F в каждый момент времени t совпадает с числом одновременно (параллельно) выполняющихся в
этот момент работ.
Например, по диаграмме на 7.11,
т.е. для $$\tau _{1} = \tau _{11}, \tau _{2} = \tau _{12}, \dots , \tau _{8} = \tau _{18}$$,
функция F(2, 3, 3, 4, 7, 8, 6, 9, t) имеет вид, представленный на
рис. 7.13а.
Для F(2, 4, 3, 4, 8, 9, 7, 10, t)
имеет вид, представленный на рис. 7.13б.
(рис 7.13) Графики функции: а — для ранних сроков окончания работ,,б — для некоторого допустимого расписания
Для графического представления функции F удобно пользоваться
временной диаграммой,
которая для второго случая, например, имеет вид, представленный на рисунке 7.14..
(рис 7.14) Временная диаграмма функции F
Пусть данный граф G, в котором учтены l
полных множеств ri, i = 1 , ... , l,
число работ,
образующих i -е полное множество и найдём
R = max {r1 , ... , rl}.
Тогда$$\begin{align*}
R = \max\limits_{\tau_1,\tau_2 \dts \tau_m} F(\tau_1,\ldots \tau_m, t),
\end{align*}$$
т.к. возможно и такое распределение выполняемых работ во времени, задаваемое
набором $$\tau _{1} , \dots , \tau _{m}$$, (т.е. R
работ.
Например, для графа на рис. 7.1 мы нашли ПМВНР {3,5,6,7},
включающее четыре
работы. Тогда существует F равно четырём (рис. 7.15).
(рис 7.15) Максимальное значение плотности загрузки
Таким образом, справедливо утверждение
Лемма.
Минимальное число n процессоров
одинаковой специализации и производительности (т.е. в однородной ВС), способных
выполнить данный алгоритм
за время T >= Tкр, не превышает R = max
{r1 , ... , rl }, где ri , i = 1 , ... , l,
— число работ, входящих в i -е ПМВНР, которое составлено по
G,
соответствующему этому алгоритму.
Определение 8. Функцию$$\begin{align*}
\text{Ф} (\tau_1 \dts \tau_m, \theta_1, \theta_2)= \int_{\theta_1}^{\theta_2}
F(\tau_1 \dts \tau_m,t)dt
\end{align*}$$
назовём
Функция Ф определяет объём работ (суммарное время их
выполнения) на
фиксированном отрезке их выполнения при заданном допустимом расписании.
Так, для отрезка времени $$[0, 4] \subset [0, 10]$$ на рис. 7.13а Ф = 10 ; для отрезка
времени [1, 3] на ррис. 7.13б Ф= 4 ; для
отрезка времени [2, 5] на рис. 7.15 Ф = 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*}$$
назовём минимальной
Функция определяет минимально возможный объём работ, который при
данном T и при различных допустимых значениях
(расписаниях) $$\tau _{1} , \dots , \tau _{m}$$
должен быть выполнен на отрезке времени $$[\theta _{1}, \theta _{2}]\subset [0, T]$$.
Это означает,
что как бы мы не планировали вычислительный процесс, который должен
быть
закончен к моменту времени T, т.е. какой бы набор
значений $$\tau _{1} , \dots , \tau _{m}$$
мы не выбрали, объём работ, выполняемых на отрезке времени $$[\theta _{1}, \theta _{2}]$$,
не может быть меньше значения $$\varphi ^{(T)} = (\theta _{1},\theta _{2})$$.
Теорема 1. Для того чтобы T
было наименьшим временем выполнения данного
алгоритма однородной вычислительной системой, состоящей из n
процессоров,
либо чтобы n процессоров было достаточно для выполнения данного
алгоритма за время T, необходимо, чтобы для данного отрезка
времени $$[\theta _{1}, \theta _{2}] \subset [0, T]$$ выполнялось соотношение$$\begin{align*}
\varphi^{(T)}(\theta_1, \theta_2) \le n ( \theta_2 - \theta_1) \notag
\end{align*}$$
Доказательство. Нетрудно
видеть, что если при данном наборе $$\tau _{1} , \dots , \tau _{m}$$ — сроках окончания выполнения работ, в том
числе и при таком наборе,
при котором обеспечивается минимальное или заданное $$T = max \{ \tau _{1}, \dots , \tau _{m}\}$$,
для реализации алгоритма достаточно n процессоров, то$$\begin{align*}
\max_{t\in[0,T]}F(\tau_1 \dts \tau_m\,t)\le n.
\end{align*}$$
Отсюда, для любого отрезка времени $$[\theta _{1}, \theta _{2}] \subset [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*}$$
Для получения полной оценки надо перебрать все отрезки $$[\theta _{1},\theta _{2}] \subset [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*}$$
Проанализируем все возможные отрезки $$[\theta _{1}, \theta _{2}] \subset [0,3] : \varphi ^{(3)}(0, 1) = \varphi ^{(3)}(1, 2) \varphi ^{(3)}(2, 3) = 0, \varphi ^{(3)}(0, 2) = \varphi ^{(3)}(1, 3)= 3, \varphi ^{(3)}(0, 3) = 6$$. Находим
минимальное n = 2, удовлетворяющие (7.3). Однако из рисунка
видно, что не
существует плана выполнения работ на двух процессорах за время T=3.
Минимально достаточное число процессоров здесь n = 3.
Функция $$\varphi ^{(T)}(\theta _{1}, \theta _{2})$$ минимальной
Предварительно определим функцию$$\begin{align*} \xi (x) = \left\{ \begin{array}{rcl} x \text { при } x\ge 0 \\ 0 \text { при } x< 0. \end{array} \right. \end{align*}$$
Тогда значение $$\xi (\tau _{1j} - \theta _{1})$$ характеризует
условный объём части работы j на
отрезке времени $$[\theta _{1}, \theta _{2}]$$ при условии $$\tau _{1j} - t_{j} \le \theta _{1}$$ и при максимальном
смещении времени выполнения работы j влево (рис. 7.17а).
Значение $$\xi (\theta _{2} - \tau _{2j}(T) + t_{j})$$ характеризует
аналогичный объём работы j при
максимальном смещении времени выполнения работы j вправо. Это
соответствует,
например, ситуации, изображённой на рис. 7.17б.
(рис 7.17) Нахождение минимальной плотности загрузки отрезка: все различные случаи соотношения времени выполнения работ и сроков
Если для работы j оба указанных выше значения функции $$\xi$$ отличны от нуля,
но не превышают значение tj и $$\theta _{2} - \theta _{1}$$,
то максимально разгрузить отрезок $$[\theta _{1}, \theta _{2}]$$ от работы j можно смещением
времени его выполнения в сторону,
обеспечивающую меньшее из двух указанных выше значений $$\xi$$ (рис. 7.17в).
Существуют два случая, когда работа j не может быть хотя бы
частично смещена
с отрезка $$[\theta _{1}, \theta _{2}]:$$
а) $$\theta _{1} \le \tau _{1j} - t_{j} < \tau _{2j} (T) \le \theta _{2}$$, в этом случае очевидно,
что $$t_{j} \le \theta _{2} - \theta _{1}$$
(рис. 7.17г), и объём работы j, выполняемой на отрезке,
совпадает с объёмом tj всей этой работы;
б) $$\tau _{1j} \ge \theta _{2} \Lambda \tau _{2j}(T) - t_{j} \le \theta _{1}$$, в этом случае очевидно,
что $$t_{j} \ge \theta _{2} - \theta _{1}$$
(рис. 7.17д), и объём части работы j, выполняемой на отрезке $$[\theta _{1}, \theta _{2}]$$
совпадает со значением $$\theta _{2} - \theta _{1}$$.
Приведённый ниже алгоритм объединяет все возможные указанные выше случаи.
Алгоритм 4 нахождения значения функции $$\varphi ^{(T)}(\theta _{1}, \theta _{2})$$.
1. Предполагаем, что для каждой работы j = 1, ... , m, известны
значения $$t_{j},\tau _{1j}, \tau _{2j}(T)$$. Полагаем равным нулю значение переменной $$\phi.$$
2. Организуем j = 1, ... , m.
3. Для каждой работы j полагаем
$$\varphi := \varphi + min \{ \xi (\tau _{1j} - \theta _{1}), \xi (\theta _{2} -\tau _{2j}(T) + t_{j}), t_{j} , \theta _{2} - \theta _{1}\}$$.
После перебора всех работ $$\varphi = \varphi ^{(T)}(\theta _{1},\theta _{2})$$.
Конец алгоритма.
Выше было получено соотношение (7.2) , которое можно использовать для n процессоров, необходимых
для выполнения данного алгоритма
за время, не превышающее T.
Приведём аналогичное соотношение для нижней оценки минимального времени Т.
Теорема 2. Пусть заданный алгоритм выполняется на ВС, состоящей
из n процессоров,
и T* — текущее значение оценки снизу времени выполнения
алгоритма. Пусть на
отрезке времени $$[\theta _{1}, \theta _{2}] \subset [0, T^{*}]$$
выполняется соотношение
$$\varphi ^{(T*)}(\theta _{1},\theta _{2}) - n(\theta _{2} - \theta _{1}) = d > 0$$.
Тогда минимальное время T выполнения алгоритма удовлетворяет
соотношению$$\begin{align*}
T \ge T^* + \frac{d}{n}.
\end{align*}$$
Теоремы 1 и 2 на основе анализа такой локальной характеристики параллельного алгоритма, как значение функции $$\phi$$ минимальной загрузки отрезка, предлагают способы оценки снизу ресурсов, необходимых для реализации каждого заданного алгоритма:
n процессоров при заданном ограничении на
длительность T процесса;T, необходимого для реализации
данного алгоритма при
заданном числе n процессоров.(рис 7.18) К примеру нахождения нижней оценки числа исполнителей
Алгоритм 5.
n = 0.Организуем перебор всех отрезков $$[\theta _{1}, \theta _{2}] \subseteq [0, T]$$ в порядке$$\begin{align*} [0,1] ;\\ [0,2] ; [1,2] ;\\ [0,3] ; [1,3] ; [2,3] ;\\ . . . . . . . . . . . . . . . . . . . . . . . . . .\\ [0,T] ; [1,T] ; \ldots , [T-1,T] . \end{align*}$$
Всего таких отрезков T(T+1)/2.
n' > n, выполняем операцию n := n'.
После перебора всех отрезков
окажется найденным значение n, которое равно максимальному из
значений,
удовлетворяющих (7.2).Пример. Нахождение оценки n.
Нахождение $$\varphi ^{(4)}(\theta _{1},\theta _{2})$$ будем иллюстрировать графически, возможными временными диаграммами (рис. 7.19).
(рис 7.19) Нахождение нижней оценки числа исполнителей(рис 7.19) Окончание
В результате анализа всех отрезков находим n = max n' = 2.
Алгоритм 6.
Первоначально полагаем
$$\begin{align*} T = \max \left \{ ]\frac{1}{n}\sum_{j=1}^m t_j[,\,T_\t{кр}\right \}. \end{align*}$$
T может увеличиваться, что при данном
порядке
перебора не приведёт к усложнению алгоритма.)Для очередного анализируемого отрезка времени $$[\theta _{1},\theta _{2}]$$ находим значение
$$d = \varphi ^{(T)}(\theta _{1},\theta _{2}) - n(\theta _{2} - \theta _{1})$$
d > 0, выполняем операцию T := T + ] d/n
[.После перебора всех отрезков $$[\theta _{1}, \theta _{2}]$$ окажется
найденным окончательное
значение T — нижняя оценка минимального времени выполнения
данного алгоритма
на данной ВС.
Пример.
Произведём оценку T для графа G, рассмотренного в
предыдущем
примере, и ВС, состоящей из двух процессоров, n = 2 (рис. 7.20).
(рис 7.20) Оценка снизу минимального времени выполнения работ(рис 7.20) Окончание
Первоначально находим$$T = \max \left \{ \frac{1}{2}\cdot (2+2+1+1),T_{кр}=3\right \}=3.$$
После перебора всех отрезков, с учётом уточнения оценки времени в процессе
этого перебора, окончательно находим T = 4.
G, и для времени T, отведённого для его
выполнения, найти наименьшее
число n процессоров, составляющих однородную ВС, и план
выполнения работ на
них.
Метод точного решения задачи (метод "ветвей и границ") основан на следующей основной теореме.
Теорема. Для того чтобы значение n являлось наименьшим числом процессоров
однородной ВС, которая выполняет алгоритм, представленный информационным
графом G = (X, P, Г ), за время, не превышающее заданное
значение T, необходимо
и достаточно, чтобы n было наименьшим числом, для которого можно
построить
граф G' = (X, P, Г'), объединив вершины, соответствующие
работам каждого
ПМВНР, который содержит r > n работ r - n
ориентированными дугами в n путей
не содержащих общих вершин. При этом длина критического пути в графе G' не
должна превышать значение T.
Алгоритм 7 решения задачи 1
— нахождения
графа-решения G'
Для графа G и времени T находим значения
ранних $$\{ \tau _{1j}\}$$ и поздних $$\{ \tau _{j}(T)\} ,j = 1 , \dots , m$$, сроков окончания выполнения работ. (Если задача поставлена
корректно, то$$\begin{align*}
\max \{\tau_{1j}\} = T_\text{кр} \le T .)\\
j
\end{align*}$$
n процессоров, которое
необходимо для
выполнения заданного алгоритма за время, не превышающее T.Пусть $$\nu$$ — номер шага решения задачи. Полагаем $$\nu = 1$$.
Находим наименьшее значение $$t_{\nu }$$ такое, что
$$F(\tau _{11}, \tau _{12} , \dots , \tau _{1m}, t_{\nu } ) = r_{\nu } > n$$.
Если такого $$t_{\nu }$$ нет, то n — решение
задачи.
Выделяем множество работ $$A_{\nu } = \{ \alpha _{j\mu }\} , \mu =1 , \dots ,r_{\nu }$$, для которых
$$\tau _{1j\mu } - t_{j\mu } \le t_{\nu } < \tau _{1\mu }$$,
т.е. тех работ, которые "порождают" данное значение F. Множество A является
подмножеством некоторого ПМВНР.
r -
n связей, как указано
в теореме — так, чтобы длина критического пути в изменившемся при этом графе G не превысила T.n — решение, выполняем
операцию n := n + 1 и
переходим к выполнению 3. Если $$\nu \ne 0$$, восстанавливаем
значения $$\{ \tau _{1j}\}$$ и $$\{ \tau _{2j}(T)\} ,$$
найденные на данном шаге, и переходим к выполнению 6.Конец алгоритма.
n. Пытаемся
сгладить значение
этой функции, введя дополнительные связи между работами, допускаемые
ограничением T. В случае неудачи вернёмся на шаг назад и
попытаемся ввести
другую комбинацию связей. При переборе всех комбинаций связей на первом шаге,
не приведших к успеху, увеличим предполагаемое число процессоров и начнём
процесс сглаживания функции плотности загрузки сначала.
Примечания
Пусть $$A_{\nu }$$ — множество r - n связей по условию теоремы, т.е. построить
некоторый граф, связывающий вершины $$A_{\nu }$$. Построим матрицу
следования $$L_{\nu }$$,
соответствующую этому графу. Первоначально эта матрица —
нулевая. Вводим $$r_{\nu } - n$$ единиц так, чтобы:
Перемещая последнюю единицу сначала по строке, затем по столбцам, затем перейдя к предпоследней единице и т.д., осуществляем перебор всех возможных комбинаций связей между работами множества $$A_{\nu }$$.
Можно рекомендовать T, необходимо вновь пересчитать
значение
функции $$\phi$$ с учётом новых связей на всех отрезках $$[\theta _{1}, \theta _{2}] \subseteq [t_{\nu }, T].$$ Если для
испытываемого значения n на этих отрезках выполняется соотношение
(7.2),
данная комбинация связей может быть признана удачной. Таким образом, выполнение
соотношения (7.2) в совокупности с допустимым увеличением длины критического
пути определяет "границы" при ветвлении.
(Напомним, что метод "ветвей и границ", как NP -
Пример.
Найдём минимальное число n процессоров, необходимое
для выполнения
алгоритма, который представлен графом G на рисунке 7.21а, за
время T = 7.
(рис 7.21) Последовательные действия при точном решении задачи 1
По алгоритму 4 найдёем нижнюю оценку n = 2, исследовав 28
значений $$\varphi ^{(7)}(\theta _{1},\theta _{2})$$
для всех $$[\theta _{1}, \theta _{2}] \subseteq [0, 7].$$ При этом $$\tau _{11} = 1, \tau _{12} = \tau _{13} = \tau _{14} = 2,\tau _{15} = \tau _{16} = 4, \tau _{17} = 5, \tau _{21}(7) = \tau _{22}(7) = 4, \tau _{23} (7) =\tau _{24}(7) = \tau _{26} (7) = 6,\tau _{25}(7) = \tau _{27} = 7$$. Мы не собираемся впредь иллюстрировать
нахождение функции
минимальной загрузки, поэтому не будем приводить динамически уточняемые
значения
поздних сроков окончания выполнения работ.
$$F(\tau _{11} , \dots , \tau _{17}) = 4 > 2$$, т.е. t1 =
0. В формировании этого значения участвуют
работы 1, 2, 3, 4. Составим квадратную матрицу L1 (рис. 7.21в)
с первоначально
нулевыми элементами. Постараемся последовательно ввести в неё два единичных
элемента. Первая возможная комбинация двух таких элементов соответствует связям 3 -> 2 -> 1. Длина критического пути в графе G, дополненном дугами в
соответствии с
этими связями, превышает 7. Пробуем заменить вторую связь следующей возможной.
Новая испытываемая комбинация связей 4 -> 2 ->
1 также приводит к недопустимому
увеличению длины критического пути. Единичные элементы, соответствующие
отвергнутым связям, на рисунке зачёркнуты.
Вновь меняем вторую связь, полагая равным единице первый элемент третьей
строки матрицы L1. Новая комбинация связей 2 -> 1
-> 3 не приводит к недопустимому
увеличению длины критического пути в графе G. По графу,
учитывающему
введённые связи, находим ранние и поздние сроки окончания выполнения работ.
На рис. 7.21г, приведена диаграмма выполнения алгоритма при
Найдём t2 = 3 такое, что F(3, 2, 5, 2, 6, 5, 6, 3) =
3 > 2. Данное
значение функции плотности загрузки определяется выполнением работ 3, 5,
6. Составляем матрицу L2 (рис. 7.21д) и стараемся ввести в ней
единственный единичный элемент. Однако перебор всех возможных способов
введения такого элемента приводит к длине критического пути в образующемся
графе, превышающей 7. Возвращаемся на шаг назад к анализу матрицы L1 и
пробуем ввести другую допустимую комбинацию связей. Такой комбинацией
является 2 -> 1, 4 -> 3. На рис. 7.21е
представлена
диаграмма выполнения алгоритма при уточнённых
Вновь находим значение t2 = 3 такое, что F(3, 2, 4,
2, 6, 5, 6, 3) = 3 > 2.
(Совпадение значений t2 и выделенных работ с ранее
исследованными является
скорее случайным.) Вновь формируем матрицу L2 (индекс указывает
номер шага,
новая матрица L2 в общем случае ничем не схожа с аналогичной
ранее рассмотренной
матрицей), и находим первую из допустимых связей — связь 6 ->
3 (рис. 7.21ж).
Вновь (рис. 7.21з) находим значение t3 = 5, где плотность
загрузки превышает
значение 2. Составляем матрицу L3 (рис. 7.21и). Находим в ней
единственную
единицу, соответствующую допустимой связи 5 -> 7. На
рис. 7.21к представлена
диаграмма выполнения алгоритма, удовлетворяющая решению задачи.
Собственно расписание определяется найденными на последнем шаге значениями $$\{ \tau _{1j}\} .$$
Формулировка задачи:
Для данного алгоритма, которому соответствует информационный
граф G, найти минимальное время T и план выполнения
этого алгоритма на данной
однородной ВС, содержащей n процессоров.
Теорема. Для того, чтобы T было
минимальным временем
выполнения алгоритма,
представленного G = (X, P, Г), на
однородной ВС,
состоящей из n процессоров, T
было наименьшей
из возможных длин критических путей в графах вида G'= (X, P,
Г'), что получены
из данного объединением вершин, соответствующих работам каждого ПМВНР, который
содержит r > n работ, r - n ориентированными
дугами в n путей, не
содержащих общих вершин.
(рис 7.22) Информационный граф распараллеливаемой задачи
Алгоритм 8 решения задачи 2 — нахождения
графа-решения G'
T = T0 минимального времени
выполнения данного
алгоритма на ВС, содержащей n процессоров.n процессоров выполнить данный
алгоритм за время T0.
Если T0 — не решение задачи 2, используем следующий метод.Находим наименьшее значение $$t_{\nu }$$ такое, что $$F(\tau _{11} , \dots , \tau _{1m}, t_{\nu }) = r_{\nu } > n$$.
Если такого значения $$t_{\nu }$$ нет на первом же шаге сглаживания
плотности загрузки
(при $$\nu = 1$$ ), то значение Tкр — решение
задачи 2. Если такого значения больше
нет при $$\nu > 1$$, то увеличиваем значение $$\mu$$ на
единицу и полагаем $$T_{\mu } = max\{ \tau _{11}, \dots , \tau _{1m}\} ,$$ т.е. длине критического пути в графе G', построенном в соответствии с
условиями теоремы. Не меняя значение $$\nu,$$ переходим к выполнению
6. (Если $$T_{\mu } =T_{0} + 1$$, то т.к. T0 — не решение задачи, искать
значение $$T < T_{\mu }$$ нецелесообразно,
т.е. найденное значение $$T_{\mu }$$ — решение задачи 2).
Если значение $$t_{\nu }$$, обеспечивающее неравенство в пункте 4, найдено, выделяем множество работ $$A_{\nu } = \{ \alpha _{j\rho }\} , \rho = 1 , \dots , r_{\nu }$$, для которых
$$\tau _{1j\rho } - t_{j\rho } \le t_{\nu } < \tau _{1j\rho }$$.
Множество $$A_{\nu }$$ является подмножеством некоторого ПМВНР.
G' была меньше $$T_{\mu }$$.Конец алгоритма.
Пример.
Пусть заданы 6 задач (m = 6), заданы их частичная упорядоченность
графом G, заданы времена решения (веса вершин). Требуется найти
расписание
выполнения этих задач на двух процессорах (n = 2) — такое,
чтобы время
решений этих задач было минимальным.
Найдём нижнюю T.
Первоначально полагаем $$T = \max \left \{ \left] \frac{1}{n}\suml_{j=1}^m t_j \right [, \,T_\text{кр} \right \} = {\max \{ 6,6 \} = 6}$$.
По алгоритму 6, испытывая значения функции минимальной загрузки, найдём, что $$\frac{\varphi^{6}(1,6)}{5} = \frac{11}{5} > 2$$. Произведем единственное уточнение значения $$T_0 = 6 + \left]\frac{1}{2}(\frac{11}{5}-2)\right [=7$$.
Без учета реально доступного количества процессоров составим (рис. 7.23) временную диаграмму решения всей совокупности задач — такую, при которой каждая из задач решается как можно раньше, и определим загрузку как бы неограниченного числа процессоров:
(рис 7.23) Временная диаграмма решения задач
находим первый момент времени, при котором по этой диаграмме нам
требуется
более двух процессоров: при t=1 это количество F(1)=3. Выделим образующие это
значение F задачи: {2, 3, 4} и составим матрицу L1 (рис. 7.24а). Первой
испытываемой связью является связь 3 -> 2. Диаграмма,
соответствующая этой связи, —
на рис. 7.24б.
(рис 7.24) Первый шаг распределения: а — матрица следования, б — временная диаграмма
Т.к. больше нет значений функции плотности загрузки, превышающих 2, то мы предполагаем возможное решение, но продолжаем перебор связей для поиска более короткого расписания.
следующей испытываемой связью по матрице L1, определяющей
длину
критического пути, меньшую 8, является связь 4 -> 2.
Соответствующее расписание — на рис. 7.25.
(рис 7.25) Введение новой связи: а — матрица следования, б — временная диаграмма
вновь находим первый момент времени, при котором нам требуется более двух
процессоров: при t = 2 это количество F(2) = 3.
Выделим образующие это значение F задачи: {2, 3, 6} и составим матрицу L2 (рис. 7.26а). Первой возможной связью,
не приводящей к длине критического пути, равной 8 или выше, является связь 2 -> 3.
Диаграмма, соответствующая этой связи, — на рис. 7.26б.
(рис 7.26) Введение последней связи: а — матрица следования, б — окончательный вид временной диаграммы
Т.к. значение функции плотности загрузки больше не превышает значение 2, то мы нашли оптимальное расписание, ибо его длина не превосходит нижней оценки — значения 7.
Задачи точного распараллеливания в настоящей лекции освещаются только для однородных систем исполнителей, когда все такие исполнители "умеют" всё и каждую работу выполняют за одинаковое время. Это предполагает применение методов для однородных вычислительных систем. Однако при более широком применении методов распараллеливания в управлении и экономике актуальна постановка этих задач для неоднородного состава исполнителей, в частности — когда исполнители обладают разной специализацией. Достаточно рассмотреть управление строительством или уборочной кампанией. Алгоритмы точного решения задач распараллеливания для неоднородных систем представлены в [3].
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.