Программные продукты и системы

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

Для поддержки параллельных вычислений сделано достаточно много – начиная от архитектуры вычислительных систем, операционных систем, языков программирования до разработки специальных параллельных алгоритмов. Тем не менее программисту, решающему сложную задачу, построить и отладить эффективную параллельную программу все еще довольно трудно. В докладе [1] отмечалось, что к началу активного внедрения вычислительных систем параллельной архитектуры в практику решения больших прикладных задач не был построен нужный теоретический фундамент и не был развит математический аппарат исследований.

Цель данной работы – рассмотрение одной из моделей параллельного вычисления. Для нее необходимо получить оценки времени выполнения программы одним процессором – T1, конечным числом процессоров – Тp и для идеализированного случая неограниченным числом процессоров – T∞.

Рассмотрим программу P, состоящую из n модулей: P={M1, M2, …, Mn}.

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

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

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

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

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

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

–      выполняются зависимости между модулями, заданные графом зависимостей;

–      характеристики вычислены для оптимального расписания работы процессоров.

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

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

Для случая p процессоров можно распределить модули по процессорам, задав для каждого процессора Pi множество модулей, выполняемых этим процессором: D(Pi)={Mi,1, Mi,2, …, Mi,r}

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

Задача составления оптимального расписания относится к сложным [2]. На практике для программ большого размера не удается явно вычислить значение Tp. По этой причине несомненный интерес представляет получение оценок для Tp.

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

.                                                           (1)

Представляет интерес получение более точных оценок для Tp.

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

T1=n*t.                                                                     (2)

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

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

T∞=k*t.                                                                     (3)

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

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

Поскольку ⌈x⌉≥x, то

.                   (5)

Формула (5) дает нижнюю оценку времени выполнения работы p процессорами:

Tp≥T1/p.                                                                   (6)

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

Вычислим теперь оценку сверху. Поскольку ⌈x⌉≤x+1, то

     (7)

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

.                                                  (8)

Оценки (8) для случая, когда время выполнения всех модулей одинаково, известны [3].

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

.                                    (9)

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

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

.                                                           (10)

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

.                                                                                     (11)

Здесь  – время окончания работы того модуля уровня i–1, который необходим для работы модуля Mji и из всех необходимых модулей завершает свою работу последним.

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

.                                                        (12)

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

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

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

Покажем теперь, что оптимальное расписание может быть составлено таким образом, чтобы критический путь был назначен одному процессору. Пусть процессор Ps – тот процессор, которому назначен Mi1 первого уровня, лежащий на критическом пути. Спускаясь по уровням, этому процессору будем назначать модуль, лежащий на критическом пути. Построенное таким образом расписание сохраняет свойство оптимальности, поскольку процессор Ps не простаивает и никакой другой процессор не может начать выполнение модулей, лежащих на критическом пути, раньше процессора Ps. Обратим внимание, что критический путь, вообще говоря, может быть не единственным.

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

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

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

.                                                  (13)

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

Для примера рассмотрим двухуровневую систему модулей, граф зависимостей которых показан на рисунке 1.

Нетрудно посчитать, что в этом случае T1=30, T∞=13.

При наличии двух процессоров для этого конкретного примера несложно задать оптимальное расписание. Для первого процессора последовательность выполняемых им модулей может быть следующей: P1={M11, M21, M12, M32}, а для второго процессора – P2={M31, M41, M22}.

Время работы как первого, так и второго процессоров равно 15. Следовательно, T2 равно 15. Критический путь входит в расписание второго процессора. Подключение второго процессора в этой задаче позволяет вдвое уменьшить время выполнения по сравнению с использованием только одного процессора. Подключение третьего процессора позволит свести время выполнения до минимально возможного результата – T∞, это не так эффективно, поскольку время сократится незначительно. Добавление других процессоров не имеет смысла, так как время решения задачи не сокращается.

Опишем получение оценок.

Оценка снизу

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

.                                                                  (14)

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

,                                                         (15)

а максимальное время, затраченное одним из процессоров на выполнение своей работы, составит

.                                                     (16)

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

Если некоторые процессоры могут простаивать, то время Tp может только увеличиваться, что гарантирует выполнение условия (16).

Лемма доказана.

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

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

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

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

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

.                                                            (18)

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

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

.                              (19)

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

                     (20)

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

.                                     (21)

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

                                                     (22)

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

.             (23)

Лемма 2 доказана.

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

Эта разница максимальна для крайнего случая, когда все модули могут выполняться независимо и в графе зависимостей все они находятся на одном первом уровне. Критический путь в этом случае состоит из одного модуля, требующего максимального времени своего выполнения. Так что, T1 – это время выполнения всех модулей, а T∞ – время выполнения одного модуля. Привлечение p процессоров может дать существенный эффект, уменьшая время выполнения практически до среднего времени выполнения одного модуля T1/p.

Эта разница минимальна для другого крайнего случая – строго последовательной программы, когда N модулей программы расположены на N уровнях и критический путь задает выполнение всех модулей. В этом случае T1 и T∞ совпадают и, как следствие, Tp равно T1 при любом числе процессоров, поэтому привлекать дополнительные процессоры в этом случае бессмысленно.

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

Литература

1.     Воеводин В.В. Математические проблемы параллельных вычислений // Методы и средства обработки информации: тр. 2-й Всеросс. науч. конф. М.: Изд-во МГУ, 2005.

2.     Cormen T.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to Algorithms, 2009, Mit Press.

3.     Гергель В.П. Теория и практика параллельных вычислений. М.: Бином, 2007.