Решение задачи 2 распараллеливания для однородных ВС
Формулировка задачи: Для данного алгоритма, которому соответствует информационный граф G, найти минимальное время T и план выполнения этого алгоритма на данной однородной ВС, содержащей n процессоров.
Теорема. Для того, чтобы T было минимальным временем выполнения алгоритма, представленного информационным графом G = (X, P, Г), на однородной ВС, состоящей из n процессоров, необходимо и достаточно, чтобы T было наименьшей из возможных длин критических путей в графах вида G'= (X, P, Г'), что получены из данного объединением вершин, соответствующих работам каждого ПМВНР, который содержит r > n работ, r - n ориентированными дугами в n путей, не содержащих общих вершин.
Рис. 7.22. Информационный граф распараллеливаемой задачи
Алгоритм 8 решения задачи 2 — нахождения графа-решения G'
- По алгоритму 5 находим оценку T = T0 минимального времени выполнения данного алгоритма на ВС, содержащей n процессоров.
- Опыт подсказывает, что в подавляющем большинстве случаев полученная оценка совпадает с минимальным временем выполнения алгоритма на данной ВС. Чтобы сократить объём вычислений, целесообразно с помощью алгоритма 6 решения задачи 1 установить, способны ли n процессоров выполнить данный алгоритм за время T0. Если T0 — не решение задачи 2, используем следующий метод.
- Полагаем ? = ? = 1, T? = ?, где ? — заведомо большое число, например, максимально допустимое на используемой ЭВМ.
-
Находим наименьшее значение t? такое, что F(?11 , ... , ?1m, t?) = r? > n.
Если такого значения t? нет на первом же шаге сглаживания плотности загрузки (при ? = 1), то значение Tкр — решение задачи 2. Если такого значения больше нет при ? > 1, то увеличиваем значение ? на единицу и полагаем T? = max {?11
, ... , ?1m} , т.е. длине критического пути в графе G', построенном в соответствии с условиями теоремы. Не меняя значение ?, переходим к выполнению 6. (Если T? = T0 + 1, то т.к. T0 — не решение задачи, искать значение T < T? нецелесообразно, т.е. найденное значение T? — решение задачи 2).
-
Если значение t?, обеспечивающее неравенство в пункте 4, найдено, выделяем множество работ A? = {
j?}, ? = 1 , ... , r?, для которых?1j? - tj?
t? < ?1j?.Множество A? является подмножеством некоторого ПМВНР.
- Введём очередную, ещё не испытанную комбинацию r? - n связей, как указано в теореме, так, чтобы длина критического пути в полученном при этом графе G' была меньше T?.
- Если такая комбинация связей существует, увеличиваем ? на единицу, уточняем новые значения {?1j} , j = 1 , ... , m, переходим к выполнению 4.
- Если такой комбинации связей не существует или все они уже перебраны и при этом ? > 1, уменьшаем ? на единицу и переходим к 6. Если же испытаны все комбинации связей при ? = 1, то последнее значение T? определяет искомое T = T?.
Конец алгоритма.
Пример.
Пусть заданы 6 задач (m = 6), заданы их частичная упорядоченность графом G, заданы времена решения (веса вершин). Требуется найти расписание выполнения этих задач на двух процессорах (n = 2) — такое, чтобы время решений этих задач было минимальным.
Найдём нижнюю оценку длины расписания T.
Первоначально полагаем
По алгоритму 6, испытывая значения функции минимальной загрузки, найдём, что
. Произведем единственное уточнение значенияБез учета реально доступного количества процессоров составим (рис. 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].