Неформальная постановка задач параллельного программирования ВС (стр. 6 )

По алгоритму 4 найдёем нижнюю оценку n = 2, исследовав 28 значений (7)(и1,и2) для всех [и1, и2] [0, 7] . При этом ф11 = 1, ф12 = ф13 = ф14 = 2, ф15 = ф16 = 4, ф17 = 5, ф21(7) = ф22(7) = 4, ф23 (7) = ф24(7) = ф26 (7) = 6, ф25(7) = ф27 = 7. Мы не собираемся впредь иллюстрировать нахождение функции минимальной загрузки, поэтому не будем приводить динамически уточняемые значения поздних сроков окончания выполнения работ.

F(ф11 , ... , ф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г, приведена диаграмма выполнения алгоритма при ранних сроках {ф11 = 3, ф12 = ф14 = 2}, ф13 = ф16 = 5, ф15 = ф17 = 6 окончания выполнения работ. Связи между работами не указаны.

Найдём 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е представлена диаграмма выполнения алгоритма при уточнённых ранних сроках окончания выполнения работ ф11 = 3, ф12 = ф14 = 2 ф13 = 4, ф15 = ф17 = 6, ф16 = 5

Вновь находим значение 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к представлена диаграмма выполнения алгоритма, удовлетворяющая решению задачи.

Собственно расписание определяется найденными на последнем шаге значениями {ф1j} .

Решение задачи 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].