Лекция 5_новая

Алгоритм определения ПМВНР

Матрица следования
, где А – матрица смежности.
Определение. Путь максимальной длины Tкр в информационном графе G назовём критическим.
Внимание. Критических путей может быть несколько.
Определение. Пусть в G существуют прямые связи – ребра – (a, b), (b, c), но не существует прямой связи (a, c). Тогда связь (а, с) называется транзитивной.

Алгоритм 1 дополнения треугольной матрицы S
транзитивными связями
Организуем просмотр сверху вниз строк матрицы следования S.
В очередной i-й строке организуем просмотр элементов в порядке увеличения j номеров столбцов.
Если (i, j)=1, складываем строки i и j по операции дизъюнкции.
Если исходная матрица следования S не треугольная, последовательный просмотр её строк производится неоднократно до установления факта неизменности окончательно полученной матрицы.)

Определение контуров
Пусть задан граф G:
После первого шага преобразования S принимает вид:
После второго шага преобразования S принимает вид:
Контур:
2 → 6 → 3 → 5 →2

Полное множество взаимно независимых работ (ПМВНР)
Определение. Работы a и b будем называть взаимно независимыми, если в матрице следования S выполняется условие (a, b) = (b, a) = 0.
Организуем просмотр слева направо столбцов матрицы следования S.
В очередном j-м столбце организуем просмотр элементов в порядке увеличения i номеров строк, i>j. ПМВНР={j}.
Пример. Столбец 2. Просматриваем строки
начиная с 2-й.
Определение. Работы {i}, i = 1, ... , n, образуют полное множество взаимно независимых работ (ПМВНР), если для любой работы k ∉ {i}, существует задающая или транзитивная связь (μ , k) = 1 или (k, ν) =1, μ, ν ∈{i}, но между работами μ, ν ∈{i} связей нет, т.е. (μ , ν) = 0
Работа {i} ∈ ПМВНР, если (i, k) = (k, i) = 0 для k ∈ ПМВНР.

Полное множество взаимно независимых работ (ПМВНР)
Столбец 1. ПМВНР = {1, 2} Столбец 2. ПМВНР = {2, 3, 4}, {2, 3, 6}
Столбец 3. ПМВНР = {3, 4, 5}, {3, 5, 6, 7}
Столбец 4. ПМВНР = {4, 5}
Столбец 5. ПМВНР = {5, 6, 7}
Столбец 6. ПМВНР = {6, 7}
Столбец 7. ПМВНР = {7}
Столбец 8. ПМВНР = {8}
Итого ПМВНР:
{1,2}, {2,3,4}, {3,4,5},
{2,3,6}, {3,5,6,7}, {8}.
Порядок рассмотрения:
В столбце 2: нулевые элементы {2,3,4,6}
Т.к. (6,4)=1, то множество {2,3,4,6} разбивается на два:
{2,3,4}, {2,3,6}
В столбце 3: нулевые элементы {3,4,5,6,7}
Т.к. (6,4)=1, то множество {3,4,5,6,7}
разбивается на два: A1={3,4,5,7}, A2={3,5,6,7}
Т.к. (7,4)=1, то множество A1={3,4,5,7}
разбивается на два: A11={3,4,5}, A12={3,5,7}⊂A2,

Алгоритмы определения ранних и поздних сроков выполнения операций

Ранние и поздние сроки выполнения работ
Ранний срок τ1i окончания выполнения работы – минимальный срок окончания выполнения работы.
Поздний срок τ2i(T) окончания выполнения работы – максимальный срок окончания выполнения работы при ограничении на время выполнения алгоритма T > Tкр , где Tкр – минимальное время выполнения алгоритма.
При T = Tкр ранние сроки окончания выполнения работ, составляющих критические пути, совпадают с поздними сроками окончания их выполнения.

Алгоритм нахождения ранних сроков окончания
выполнения работ
Полагаем первоначально τ11 = τ12 = ... = τ1m = 0.
Производя циклический обзор строк матрицы следования S, находим очередную из необработанных строк. Если все строки обработаны, выполнение алгоритма заканчивается.
Пусть j — номер найденной необработанной строки. Если j-я строка не содержит единичных элементов, полагаем τ1j = tj. Переходим к выполнению шага 6.
Если j-я строка содержит единичные элементы, выбираем элементы множества {τ11 , ... , τ1m}, соответствующие номерам единичных элементов j-й строки.
Если все выбранные таким образом элементы, образующие множество {τ1j(ν)},
ν = 1, ... , kj, отличны от нуля, полагаем τ1j = max τ1 jν + tj.
Если хотя бы один из выбранных элементов нулевой (соответствующий ранний срок ещё не найден), выполняем шаг 2.
Обработанную j-ю строку метим, чтобы исключить её повторную обработку.
Переходим к выполнению шага 2.

Примечания
Если граф G не содержит контуров, зацикливание при этом невозможно.
Если матрица S треугольная, то никогда не складываются условия для многократного циклического обзора строк. Тогда ранние сроки окончания выполнения работ находятся за один последовательный просмотр строк матрицы S.
Tкр = max {τ11 , ... , τ1m}.
Пример:
τ11 = t1 = 2, τ12 = t2 = 3, τ13 = τ11 + t3 =3, τ14 = τ11 + t4 = 4, τ15 = max {τ11, τ12 }+ t5= 7, τ16 = max {τ11, τ14} + t6 = 8, τ17 = max {τ12,τ14 } + t7 = 6, τ18 = max {τ13, τ15, τ16, τ17} + t8 = 9; Tкр = 9.

Пример
τ11 = 1,
τ13 = τ11 + t3 = 3,
τ14 = 2,
τ15 = τ13 + t5 = 4,
τ12 = max {τ13, τ14} + t2 = 6,
τ16 = τ12 + t6 = 7.
Tкр = 7.
Временная диаграмма выполнения работ при ранних сроках окончания:

Алгоритм нахождения поздних сроков окончания
выполнения работ при заданном значении Т
Полагаем первоначально τ21(T) = ... = τ2m(T) = 0.
Производя циклический обзор справа налево столбцов матрицы S, находим очередной из не обработанных ещё столбцов. Если все столбцы обработаны, выполнение алгоритма заканчивается.
Пусть j — номер найденного необработанного столбца. Если j-й столбец не содержит единичных элементов, полагаем τ2j(T) = T. Переходим к выполнению шага 6.
Если j-й столбец содержит единичные элементы, выбираем элементы множества { τ21(T) , ... ,τ2m(T) }, соответствующие номерам единичных элементов j-го столбца.
Если все выбранные таким образом элементы {τ2jν}(T)} ⊂ {τ21(T), ... , τ2m(T)},
ν = 1 , ... , kj, отличны от нуля, полагаем
τ2j (T) = min {τ2jν (T) - tjν }.
В противном случае выполняем шаг 2.
Обработанный j-й столбец метим с целью исключения его повторной обработки. Переходим к выполнению шага 2.

Пример 1
Для T = 10:
τ28(10) = 10,
τ27(10) = τ28(10) - t8 = 9,
τ26(10) = τ28(10)- t8 = 9,
τ25(10) = τ28(10) - t8 = 9 ,
τ24 = min {τ26(10), - t6, τ27(10) - t7} = 5,
τ23(10) = τ28(10) - t8 = 9,
τ22(10) = min {τ25(10) - t5, τ27(10) - t7 } = 5,
τ21(10) = min {τ23(10) - t3, τ24(10) - t4, τ25(10) - t5, τ26(10) - t6} = 3.

Пример 2
Для T = 10:
τ26(10) = τ25(10) = 10.
τ22(10) = τ26(10) - t6 = 9.
τ24(10) = τ22(10) - t2 = 6.
τ23(10) = min {τ22(10) - t2, τ25(10) - t5} = 6. τ21(10) = τ23(10) - t3 = 4.
Диаграммы выполнения работ
при поздних сроках окончания
в примерах 1 и 2.

Самостоятельная работа
Найдите ранние и поздние сроки выполнения работ.
Постройте диаграммы по ранним и поздним срокам выполнения работ
t1=1, t2=2, t3=1, t4=3, t5=2, t6= 5, t7= 2, t8= 2, t9=1, t10= 6, t11=1, t12=2, t13=4.
t1=4, t2=1, t3=3, t4=3, t5=1, t6= 4, t7= 6, t8= 2, t9=5, t10= 1, t11=1, t12=2, t13=4, t14=2, t15=1, t16=2.
T =Tкр+2
T =Tкр+3

Алгоритмы поиска наименьших ресурсов: процессов и времени

Плотность загрузки вычислительной системы
Определение. Функция
где:
называется плотностью загрузки, найденной для значений τ1, …, τm
Пусть τj — произвольное значение момента окончания выполнения j-й работы:
, j =1 , ... , m,
Меняя значения {τj}, j = 1 , ... ,m, но соблюдая при этом порядок следования работ, мы получим множество допустимых расписаний выполнения работ.
Для заданных τ1 , ... , τm значение функции F в каждый момент времени t совпадает с числом одновременно (параллельно) выполняющихся в этот момент работ.

Пример
τ11 = 2,
τ12 = 3,
τ13 = 3,
τ14 = 4,
τ15 = 7,
τ16 = 8,
τ17 = 6,
τ18 = 9;
Tкр = 9.
Т = 10.
τ21 = 3,
τ22 = 5,
τ23 = 9,
τ24 = 5,
τ25 = 9 ,
τ26 = 9,
τ27 = 9,
τ28 = 10,
F(2, 3, 3, 4, 7, 8, 6, 9, t):
F(2, 4, 3, 4, 8, 9, 7, 10, t):

Пример
F(2, 3, 3, 4, 7, 8, 6, 9, t)

Максимальная ширина графа
Дано:
граф G,
L – число ПМВНР,
ri – число работ, образующих i-е полное множество;
i = 1 , ... , L,
Пусть R = max {r1 , ... , rl}
Тогда:
Лемма. Минимальное число n процессоров одинаковой специализации и производительности (т.е. в однородной ВС), способных выполнить данный алгоритм за время T >= Tкр, не превышает R = max {r1 , ... , rl },
где ri , i = 1 , ... , L, — число работ, входящих в i -е ПМВНР, которое составлено по взвешенному графу G, соответствующему этому алгоритму.

Пример
ПМВНР:
{1,2}, {2,3,4}, {3,4,5},
{2,3,6}, {3,5,6,7}, {8}.
Существует допустимое расписание, например,
τ1 = 2, τ2 = 3, τ3 = 5, τ4 = 4, τ5 = 8, τ6 = 8, τ7 = 6, τ8 = 9 такое, при котором максимальное значение плотности загрузки F равно четырём

Загрузка отрезка для допустимого расписания
Определение. Функция
называется загрузкой отрезка [θ1, θ2] ⊂ [0,T] для заданного допустимого расписания τ1, ... ,τm.
Функция Ф определяет объём работ (суммарное время их выполнения) на фиксированном отрезке их выполнения при заданном допустимом расписании.

Пример
Для отрезка времени
[0, 4] ⊂ [0, 10]:
Ф = 9
Для отрезка времени [1, 3]:
Ф = 4
Для отрезка времени [2, 5]:
Ф = 6

Минимальные оценки работ и вычислительных ресурсов
Определение. Функция
называется минимальной загрузкой отрезка [θ1, θ2] ⊂ [0, T].
Функция ϕ(T) определяет минимально возможный объём работ, который при данном T и при различных допустимых значениях (расписаниях) τ1 , ... , τm должен быть выполнен на отрезке времени
[θ1, θ2] ⊂ [0, T].
Теорема 1. Для того чтобы T было наименьшим временем выполнения данного алгоритма на однородной вычислительной системе, состоящей из n процессоров, либо чтобы n процессоров было достаточным для выполнения данного алгоритма за время T, необходимо, чтобы для данного отрезка времени [θ1, θ2] ⊂ [0, T] выполнялось соотношение:

Пример
Пусть T=3.
Из теоремы имеем:
Откуда получаем общее соотношение:
Для получения полной оценки надо перебрать все отрезки [θ1, θ2] ⊂ [0, T] и найти:

Продолжение примера
Проанализируем все возможные отрезки [θ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.
Минимальное n, удовлетворяющее условию (*): n = 2.
(*)
Но за время T=3 минимально достаточное число процессоров n = 3.

Условный объём части работы j на отрезке времени [θ1, θ2]
Определим функцию:
1) Значение ξ(τ1j - θ1) характеризует условный объём части работы j на отрезке времени [θ1, θ2] при условии τ1j - tj ≤ θ1 и при максимальном смещении времени выполнения работы j влево.
2) Значение ξ (θ2 - τ2j(T) + tj) характеризует аналогичный объём работы j при максимальном смещении времени выполнения работы j вправо.

Если для работы j оба указанных выше значения функции ξ отличны от нуля, но не превышают значение tj и θ2 - θ1, то максимально разгрузить отрезок [θ1, θ2] от работы j можно смещением времени его выполнения в сторону, обеспечивающую меньшее из двух указанных выше значений ξ
Условный объём части работы j на отрезке времени [θ1, θ2]

б) τ1j ≥ θ2 Λ τ2j(T) - tj ≤ θ1, в этом случае очевидно, что tj ≥ θ2 - θ1 и объём части работы j, выполняемой на отрезке [θ1, θ2] совпадает со значением θ2 - θ1.
Два случая, когда работа j не может быть хотя бы частично смещена с отрезка [θ1, θ2] :
а) θ1 ≤ τ1j - tj < τ2j (T) ≤ θ2, в этом случае tj ≤ θ2 - θ1 и объём работы j, выполняемой на отрезке, совпадает с объёмом tj всей этой работы;
Условный объём части работы j на отрезке времени [θ1, θ2]

Алгоритм нахождения значения функции ϕ(T)(θ1, θ2).
Предполагаем, что для каждой работы j = 1, ... , m, известны значения tj, τ1j, τ2j(T). Полагаем равным нулю значение переменной ϕ.
2. Организуем последовательный анализ работ j = 1, ... , m.
3. Для каждой работы j полагаем
ϕ:=ϕ + min {ξ (τ1j - θ1), ξ(θ2 - τ2j(T) + tj), tj , θ2 - θ1}.
После перебора всех работ ϕ=ϕ(T)(θ1, θ2).

Алгоритм нахождения значения функции ϕ(T)(θ1, θ2).
Теорема 2. Пусть заданный алгоритм выполняется на ВС, состоящей из n* процессоров, и T* — текущее значение оценки снизу времени выполнения алгоритма. Пусть на отрезке времени [θ1, θ2] ∈ [0, T*] выполняется соотношение:
ϕ(T*)(θ1,θ2) - n(θ2 - θ1) = d > 0.
Тогда минимальное время T выполнения алгоритма на n процессорах удовлетворяет соотношению:

Нижняя оценка минимального числа процессоров, необходимого для выполнения алгоритма за заданное время
1. Первоначально полагаем n = 0
2. Организуем перебор всех отрезков [θ1, θ2] [0, T] в порядке
3. Для очередного анализируемого отрезка времени [θ1, θ2] находим значение
4. Если n' > n, выполняем операцию n := n'.
После перебора всех отрезков окажется найденным значение n, которое равно максимальному из значений, удовлетворяющих условию:

Пример
Задача: Найти ϕ(4)(θ1,θ2) и n’.

Пример

Пример
n = max n' = 2.

Нижняя оценка минимального времени выполнения данного алгоритма на ВС
1. Первоначально полагаем:
2. Организуем перебор всех отрезков [θ1, θ2] [0, T] в той же последовательности, что и в предыдущем алгоритме.
3. Для очередного анализируемого отрезка времени [θ1, θ2] находим значение:
4. Если d > 0, выполняем операцию T := T + ] d/n [.
5. Полагаем τ2j(T) := τ2j(T) + ] d/n [ , j = 1 , ... , m.
После перебора всех отрезков [θ1, θ2] окажется найденным окончательное значение T — нижняя оценка минимального времени выполнения данного алгоритма на данной ВС.

Пусть число процессоров: n = 2
Пример
Первоначально находим:
Tкр=T=3
Находим для Ткр новые поздние сроки: τ21=2, τ22=2, τ23=2, τ24=3

Пример

Пример

Пример
T = 4