»

Май 30

Модель параллельных вычислений

Модель параллельных вычислений

Владимир Биллиг

лекция из учебника “Параллельные вычисления”

Рассмотрим программу P, состоящую из n модулей

P = {M1, M2, …Mn}                                        (1)

Будем предполагать, что программа P выполняется на компьютере, обладающим некоторым числом процессоров, работающих на общей памяти. Выходные данные, полученные в результате работы модуля Mi, могут являться входными данными для модуля Mj.
Так, естественным образом, возникает зависимость между модулями, определяющая
возможный порядок их выполнения.

Множество модулей разобьём на k уровней. К уровню i отнесем те модули, для начала работы которых требуется завершение работы модулей, из которых хотя бы один принадлежит уровню i – 1. Модуль уровня i с номером k будем обозначать как Mki.

Модули, принадлежащие уровню 1, имеют все необходимые данные,
полученные от внешних источников. Они не требуют завершения работы других
модулей и в принципе могут выполняться параллельно, будучи запущенными в
начальный момент выполнения программы.

Свяжем с программой P ориентированный граф зависимостей
модулей. Граф не содержит циклов и отражает разбиение модулей на уровни. Модули являются вершинами графа,  а дуги отражают зависимости между модулями. Дуга ведет от модуля Mki к модулю Mlj, если для начала выполнения модуля Mki требуется завершение работы модуля Mlj.
В узлах графа содержится информация об ожидаемом времени выполнения модуля, где время измеряется в некоторых условных единицах. На рис.1_1 показан пример графа зависимостей:

Рис. 1_1 Пример графа зависимостей

Обозначим через T1 - время, требуемое для выполнения программы P одним процессором, Tp  - p процессорами, T- время, требуемое в случае, когда число процессоров неограниченно.
В последнем случае достаточно n процессоров, по числу модулей нашей программы.

Предполагается, что все эти характеристики рассчитываются  при соблюдении двух условий:

  • Выполняются зависимости между модулями, заданные
    графом зависимостей.
  • Характеристики вычислены для оптимального
    расписания работы процессоров.

В случае одного процессора достаточно выполнение только первого условия. Обычно предполагается естественный порядок выполнения модулей, – последовательное выполнение модулей  одного уровня, затем переход к выполнению модулей следующего уровня.

Для случая неограниченного числа процессоров оптимальным  является такое расписание, когда каждый модуль начинает выполняться, как только
завершены все модули, необходимые для его работы.

Для случая p процессоров можно распределить модули по процессорам, задав
для каждого процессора Pi множество модулей, выполняемых этим процессором:

Распределение модулей по процессорам совместно с графом  зависимостей однозначно определяет расписание работ и время выполнения  программы при данном расписании. Предполагается, что каждый процессор выполняет
модули из распределения D(Pi). После завершения очередного модуля он сразу же переходит к выполнению следующего  модуля, если для этого модуля выполнены все зависимости, заданные графом  зависимостей. В противном случае процессор ждет окончания работы требуемых  модулей. Время завершения последнего модуля в распределении D(Pi) задает время работы данного процессора. Тот  процессор, который последним заканчивает работу и определяет общее время решения задачи TpD для данного расписания. Введенная ранее характеристика Tp предполагает
оптимальное расписание:

Cоставление  оптимального расписания является сложной задачей.

Для введенных характеристик выполняется естественное  соотношение:

Понятно, что когда p = n, Tp будет совпадать с T. Этого же результата можно добиться зачастую и при  меньшем числе процессоров.

Для строго последовательной программы, когда i-й модуль зависит от модуля i-1, все три характеристики  будут совпадать. Для строго последовательной программы дополнительные процессоры  не позволяют уменьшить время выполнения программы в сравнении со временем  выполнения этой же программы одним процессором. Так, например, задача о  «Ханойской башне» на суперкомпьютере с сотнями тысяч процессоров будет решаться  столь же долго, как и на компьютере с одним процессором. Это вытекает из сути задачи, – перенос следующего кольца требует завершение переноса предыдущего кольца, – параллельно эту работу выполнять нельзя.

Давайте получим соотношения для расчета введенных характеристик. Рассмотрим вначале упрощенную ситуацию, предположив, что время выполнения всех модулей одинаково и равно t. Нетрудно видеть, что

T1 = n * t                                                                    (2)

Действительно, один процессор должен выполнить все модули программы, проходя, например, последовательно один уровень за другим.

Нетрудно посчитать и время T

T= k * t                                                                    (3)

Действительно, пусть на первом уровне n1 модулей. У них есть все необходимые данные, и они могут выполняться параллельно. Поскольку число процессоров неограниченно, то запустив каждый модуль на одном из n1 имеющихся процессоров, за время t завершим выполнение модулей первого уровня. Пусть за время i * t завершено выполнение всех модулей всех уровней от первого до i–го.
Тогда возможно параллельно выполнять модули следующего i + 1–го уровня, число которых равно  n i +1. Процессоров у нас хватает, поэтому на завершение всех
модулей этого уровня потребуется t времени, и общее время выполнения равно
(i + 1) * t, что по индукции доказывает справедливость формулы (3).

Для времени Tp  получим оценки  сверху и снизу. Понятно, что p процессоров
могут выполнить вычисление niмодулей уровня i за время

,
где ⌈x⌉
обозначает минимальное целое, большее или равное x. Два процессора смогут выполнить пять модулей уровня 1 за время 3 * t.
Отсюда следует, что общее время работы Tp  дается формулой (4):

Поскольку ⌈x⌉ ≥ x, то справедливо (5)

Это соотношение дает нижнюю оценку времени выполнения работы p процессорами.

Tp ≥ T1/p                                                                                         (6)

Если на каждом уровне число модулей ni кратно p, то оценка достижима. В лучшем
случае p процессоров могут сократить время выполнения программы в p раз в сравнении со временем, требуемом для выполнения этой работы одним процессором.

Получим теперь оценку сверху. Поскольку ⌈x⌉ ≤ x + 1, то справедливо соотношение (7)

Объединяя (6) и (7), получим (8)

Рассмотрим теперь, что происходит, когда модули программы для своего выполнения требуют разного времени. Пусть Mi – множество модулей уровня i:

(9)

 

Для каждого из этих модулей известно время, требуемое на выполнение – ti, j.

И в этом случае нетрудно рассчитать время T1 – время, требуемое на выполнение всей работы одним процессором:

(10)

 

Как рассчитать время T в этой ситуации, когда мы располагаем неограниченным числом процессоров? Введем для каждого модуля время окончания его работы – tji.
Это время будем рассчитывать по следующей формуле:

                                                                          

                                                     (11)

 

Здесь

– время окончания работы того модуля уровня i-1, который:

 

a) необходим для работы модуля Mji ;

b) из всех необходимых модулей завершает свою работу последним.

Тогда время T можно рассчитать следующим образом:

(12)

 

 

Формула (12) говорит, что время завершения последнего модуля уровня k и является временем T при оптимальном расписании работ. Справедлива следующая теорема:

Теорема_1

Время T задается максимально нагруженным путем в графе зависимостей.

Прежде всего, докажем, что при неограниченном числе процессоров оптимальное расписание каждого процессора содержит не более одного модуля на каждом уровне. Доказательство дается индукцией по числу уровней. Для уровня 1
утверждение справедливо, поскольку на этом уровне число процессоров совпадает с
числом модулей этого уровня для оптимального расписания. Пусть утверждение
справедливо на уровне j.
Покажем, что оно остается справедливым и для модулей следующего уровня j + 1. Действительно, рассмотрим процессор Pr, выполняющий i-й модуль уровня j  - Mij. Когда этот процессор завершит работу, то может оказаться, что появятся готовые к
выполнению m модулей уровня j +1, ожидавших завершения работы Mij.Только один из этих модулей включается в оптимальное расписание процессора Pr, а остальные будут включены в расписание свободных процессоров, участвующих в работе. Если таковых не окажется, то всегда можно добавить новые процессоры, так что все модули, ожидавшие завершения работы модуля Mij,одновременно начнут выполняться.

Отсюда по индукции следует справедливость утверждения для всех уровней. Отсюда же следует, что T не может быть больше времени, задаваемого критическим путем.

Покажем теперь, что оптимальное расписание может быть составлено таким образом, чтобы критический путь был назначен одному процессору. Пусть процессор Ps – тот процессор, который последним закончил работу, выполняя модуль Mik последнего уровня k, лежащий на критическом пути. Чтобы модуль Mik мог начать
выполняться, необходимо завершение всех модулей уровня k -1, необходимых модулю Mik. Среди всех этих модулей есть модуль Mik-1, последним завершающим работу. Именно он лежит на критическом пути, его и включим в расписание процессора Ps.
Это расписание оптимально, поскольку как только процессор завершает работу над
модулем уровня i-1, он тут же приступает к выполнению модуля на уровне i, и ни один из процессоров не может начать эту работу раньше. Подъем по уровням показывает, что при прохождении критического пути оптимальное расписание может быть составлено таким образом, что  критический путь включается в
расписание одного процессора. Заметьте, критический путь, вообще говоря, может
быть не единственным.

На этом доказательство утверждения закончено.

Сложнее получить формулу для вычисления Tp. Это время необходимо вычислять для оптимального расписания, а его составление является весьма сложной задачей. Проблема составления оптимального расписания в этих условиях относится к NP
– полным проблемам, что означает, отсутствие алгоритма полиномиальной
сложности, и для решения задачи необходимы переборные алгоритмы. Этим мы не
будем заниматься.

Займемся тем, что покажем справедливость ранее полученных оценок (8) для Tp и в случае, когда время выполнения модулей различно и в графе зависимостей для каждого модуля задано время его работы:

Приведу раньше пример.
Рассмотрим двух уровневую систему модулей, граф зависимостей которых показан на рис. 1.1

Нетрудно посчитать, что в этом случае:

T1 = 30;            T = 13;

Для случая двух процессоров для этого конкретного примера нетрудно задать оптимальное расписание. Для первого процессора последовательность выполняемых им модулей может быть следующей:

P1 = {M11, M21, M12, M32}

Для второго процессора последовательность следующая:

P2 = {M31, M41, M22}

Время работы первого процессора равно 15, второго – 15.
Следовательно, T2 равно 15. Критический путь входит в расписание второго процессора.

Оценка снизу

Лемма 1

Для Tp справедлива оценка

 

 

►Докажем справедливость оценки снизу для Tp. Пусть p процессоров выполняют работу согласно оптимальному расписанию, и ни один из процессоров не
простаивает до окончания всей работы. Поскольку в результате все модули будут
выполнены, и ни один модуль не будет выполняться дважды, то суммарное время
работы всех процессоров равно T1:

(13)

 

Поскольку Tp – это максимальное значение, затраченное одним из процессоров, на выполнение своей работы, то:

(14)

 

Справедливость нижней оценки

(15)

 

следует из общих свойств суммы компонентов. Максимальный компонент всегда больше или равен среднего арифметического значения суммы.

Равенство достигается в единственном случае, когда все компоненты суммы имеют  одно и то же значение. Содержательно это означает, что все процессоры одновременно начинают свою работу и одновременно ее заканчивают. В этом случае общее время выполнения работы сокращается в p раз.

Оценка сверху

Дадим вначале графическую интерпретацию. Задание нижней и верхней оценки для Tp означает, что эта функция ограничена двумя гиперболами.
Функция убывающая. В начальной точке при p =1 по определению Tp(1) = T1, так что функция находится в заданном коридоре. Это
же справедливо и для конечных точек, для всех p, больших некоторого значения p*, при котором Tp= T.
Остается показать, что утверждение верно и для остальных значений  1 <  p < p*.
На рис. 1_2 дана графическая интерпретация поведения Tp.

 

 

 

 

 

 

 

Рис.1_2 Поведение функции Tp

Пусть работу выполняют p процессоров. Составление расписания означает, что граф зависимостей разбивается на p непересекающихся подграфов. Все модули каждого из подграфов выполняются одним процессором.
Подграф с максимальным временем выполнения для данного разбиения будем называть максимально нагруженным подграфом. Оптимальное расписание предполагает такое разбиение, при котором максимально нагруженный подграф выполняется за минимально возможное время. Ранее мы доказали, что оптимальное расписание может быть составлено таким образом, чтобы критический путь выполнял один процессор.
Отсюда незамедлительно следует, что критический путь полностью принадлежит
одному из подграфов. Итак, будем предполагать, что граф зависимостей G разбит
на непересекающиеся подграфы Gi:

(16)

 

Пусть для определенности подграф G1 – максимально нагруженный подграф. Возможны два случая. В первом случае G1содержит критический путь Path_crit, так что:

(17)

 

Во втором случае критический путь не входит в максимально нагруженный подграф.

Лемма 2

Для Tp справедлива оценка

(18)

 

Случай 1. G1 – максимально нагруженный подграф, содержащий критический путь. Так что Tp – это время выполнения подграфа G1.

Доказательство от противного. Предположим, что в этом случае утверждение леммы несправедливо и имеет место отношение


Покажем, что тогда разбиение не является оптимальным и может быть улучшено, что ведет к уменьшению времени Tp.

Учитывая соотношение (17), получим:

(19)

 

Так как время выполнения критического пути равно T, то отсюда следует, что время выполнения подграфа G1 больше среднего времени T1/p. В нашем разбиении подграфа G существует подграф Gi , время работы которого меньше среднего времени. Приходим к противоречию. Наше разбиение не является оптимальным, поскольку подграф G1можно заменить подграфом Gi, уменьшив время выполнения Tp.

Случай 1 доказан.

Случай 2.

G1 – максимально нагруженный подграф, не содержащий критический путь.

Доказательство от противного. Предположим, что утверждение леммы несправедливо и имеет место отношение

Покажем, что и в этом случае разбиение не является оптимальным и может быть
улучшено, что приведет к уменьшению времени Tp.

Итак, предположим, что

(20)

 

Отсюда следует:

 

 

 

Пусть G0 – минимально нагруженный подграф, тогда время его выполнения не больше среднего времени выполнения, так что имеем:

(21)

 

Подграфу  G0 можно передать часть работ подграфа G1, уменьшив суммарное время работы. Действительно, подграф  G1 – это максимальный подграф, не содержащий
критического пути, поэтому его можно представить в виде:

Путь Path, начинающийся на первом уровне меньше критического пути. При передаче его подграфу G0 время выполнения этого подграфа будет меньше времени выполнения подграфа G1. Общее время выполнения работ при этом уменьшится. Следовательно, пришли к противоречию с утверждением об оптимальности расписания, что доказывает справедливость соотношения:

(22)