WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     ||
|

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

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

В разделе 2.1 отмечается, что при разработке планировщика для OpenTS, а также для ранних версий NewTS, целью ставилось достижение приемлемой эффективности на существовавших в то время приложениях для Т-системы. Математические методы для изучения механизмов планирования при этом не использовались. Недостатком такого подхода является то, что он ориентируется на конкретные классы приложений. Разработка новых прикладных программ для Т-системы часто выявляла недостатки в планировщике. Для их исправления в код планировщика (или других модулей системы) вносились изменения, которые приводили к более равномерной загрузке узлов на данной программе. При этом эффективность выполнения других программ, как правило, снижалась.

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

• объяснение причин неэффективного исполнения некоторых прикладных программ в существующих средствах, основанных на балансировке нагрузки, и, в частности, в реализациях Т-системы;

• выделение класса прикладных программ, которые могут быть эффективно исполнены с помощью динамического планирования;

• создание алгоритма планирования, эффективно исполняющего программы упомянутого выше класса и формальное доказательство его эффективности.

В разделе 2.1 вводится предлагаемая автором математическая модель, описывающая процесс исполнения параллельных программ в системе динамического распараллеливания. При ее построении за основу была взята модель, изложенная в работах Р. Блюмоффа (Robert D. Blumofe) и Ч. Лейсерсона (Charles E. Leiserson)6. В ней параллельная программа представляется в виде ориентированного ациклического графа (V, E), где V множество вершин графа, E V V множество его ребер.

Вершинам графа соответствуют подзадачи, участки последовательного исполнения программы. Выделяется начальная vs V вершина графа.

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

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

Для описания временных характеристик процесса исполнения каждой подзадаче ставится в соответствие ее вес, или вычислительная сложность, то есть время, необходимое для ее исполнения. Вычислительная сложность задается с помощью функции w : V R+.

Определение 1. Набор (V, vs, E = Ec Es Ed, w), удовлетворяющий описанным выше условиям, называется параллельной программой.

Вводится определение плана исполнения параллельной программы, который для каждой вершины v V определяет время запуска и номер вычислительного узла7. Раздел 2.2 посвящен изучению свойств жадных планов исполнения, а именно таких, в которых готовые к исполнению задачи начинают сразу исполняться при наличии свободных узлов.

Blumofe R. D., Leiserson C. E. Scheduling multithreaded computations by work stealing // J. ACM.

1999. Vol. 46, no. 5. Pp. 720–748.

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

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

Теорема 1. Пусть T1 общее время исполнения данной параллельной программы на одном узле, T время исполнения программы на неограниченном количестве узлов. Тогда для любого жадного плана для P узлов справедливо неравенство TP T1/P +T, где TP время исполнения программы в данном плане.

Эта теорема является обобщением результатов Блюмоффа и Лейсерсона, которые доказали аналогичную теорему в рамках своей модели.

Ключевое отличие между этими теоремами заключается в том, что в модели Блюмоффа и Лейсерсона веса всех вершин предполагаются равными единице, а в настоящей диссертации теорема доказана для программ с произвольными весами вершин. Доказательство заключается в выборе некоторого жадного плана для неограниченного числа узлов и его преобразовании в план для P узлов. Показывается, что при этом план остается жадным, а время исполнения возрастает не более, чем на T1/P.

В разделе 2.3 описано обобщение модели на случай неоднородных вычислительных систем. Предполагается, что производительность (далее по тексту мощность) каждого узла может быть описана одним числом.

Определение 2. Вычислительным комплексом называется конечная непустая последовательность C = (c1, c2,..., cN), ci R+, ci 0. При этом ве личина c = ci называется суммарной мощностью узлов, а величина i cmin = mini ci минимальной мощностью узлов.

В этом случае вычислительная сложность задачи обозначает не время ее исполнения, а число операций, необходимое для ее завершения. Время исполнения подзадачи v на узле i считается равным w(v)/ci. В этих условиях определения T1 и T становятся некорректными. Вместо них используются следующие определения.

Определение 3. Общей вычислительной сложностью параллельной программы (V, vs, E, w) называется сумма весов ее вершин, W1 = w(v).

vV Определение 4. Глубиной параллельной программы (V, vs, E, w) называется максимум суммы весов вершин во всех путях в графе (V, E):

W = max w(vi).

(v1,v2,...,vk) путь в (V,E) i[1,k] В отличие от T1 и T, которые задают время исполнения параллельной программы, W1 и W показывают ее вычислительную сложность и измеряются в операциях.

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

Теорема 2. Пусть C = (c1, c2,..., cP ) вычислительный комплекс.

Для любого жадного плана на этом комплексе справедливо неравенство W1 W TC + c cmin где TC время исполнения программы в данном плане.

С использованием теоремы 2 коэффициент эффективности параллельной программы оценивается как W1 W1 Keff = =, W c W1 W TCc + c 1 + · W1 cmin c cmin и оценка является асимптотически оптимальной при W1/W c/cmin.

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

В разделе 2.4 приводится обобщение модели на случай распределенных вычислительных систем. Предполагается, что время, необходимое для обращения к произвольному удаленному узлу и получению ответа, фиксировано. Такое время обозначается через tRT T.

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

Теорема 3. Пусть (V, vs, E, w) параллельная программа, в которой каждая вершина имеет не более двух исходящих ребер. Пусть tRT T время обращения за задачей к произвольному узлу, T1 время исполнения программы на одном узле, T время ее исполнения на неограниченном числе узлов, tmin минимальное время исполнения подзадачи из V. Тогда математическое ожидание общего времени исполнения программы на P узлах с использованием указанного выше алгоритма оценивается следующим образом:

T1 (3 + 2 ln P ) tRT T E(TP ) < 2 + 2 + T + tmin.

P tmin В доказательстве этой теоремы рассматриваются два случая: когда используется более P/2 узлов, и когда более половины узлов простаивают. В первом случае оценивается выполняемая вычислительная работа, и делается вывод, что такое состояние может длиться не более 2T1/P времени. Во втором случае оценивается время поиска готовых к исполнению задач свободными узлами.

В разделах 2.5 и 2.6 описываются два алгоритма планирования для системы NewTS. Алгоритм Fishing действует по методу заимствования заданий. Узел, на котором отсутствуют готовые к исполнению задачи, отправляет запрос на другой, случайным образом выбранный узел. В каждый момент времени с одного узла может быть отправлен только один запрос, который может пересылаться случайным образом до тех пор, пока не найдет узел с готовой к исполнению задачей. Максимальное число пересылок ограничено параметром планировщика. Описаны две модификации этого алгоритма, повышающие производительность в случае программ с централизованным порождением задач, а также на распределенных вычислительных установках.

Алгоритм балансирующего планировщика действует по методу разделения работы. Узлы под управлением этого планировщика обмениваются информацией о количестве готовых к исполнению задач. Пересылки осуществляются таким образом, чтобы достичь максимально равномерного распределения задач. Упомянутые алгоритмы реализованы в планировщиках для системы NewTS. Они имеют несколько параметров, влияние которых на исполнение пользовательских программ изучается в главе 5.

Описанные в разделах 2.5 и 2.6 алгоритмы планирования достигают высокой эффективности планирования для многих приложений. Однако, для этих алгоритмов отсутствуют оценки эффективности. В связи с этим обстоятельством, автором был реализован в программном комплексе NewTS неблокирующий режим исполнения, описанный в разделе 2.7.

В неблокирующем режиме используется алгоритм планирования, используемый в доказательстве теоремы 3. По этой причине, для программ, исполняемых в этом режиме, справедлива оценка из теоремы 3. Математическое ожидание времени исполнения программ в этом режиме на P узлах убывает как 1/P при условии T1/T P ln P.

Третья глава диссертации посвящена разработке и реализации методов эффективного исполнения мелкозернистых8 (fine-grained) паралAndersen B. Fine-grained parallelism in Ellie // J. Object Oriented Program. 1992. Vol. 5, no. 3.

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

В диссертации рассматривается метод эффективного исполнения мелкозернистых программ, основанный на объединении нескольких задач в одну во время исполнения программы. Такое объединение в литературе называется включением задач (task inlining). Решение о возможности объединения принимается на основе информации о загруженности узлов вычислительной системы. Включение задач ускоряет исполнение мелкозернистых программ за счет уменьшения накладных расходов на создание и использование структур ядра NewTS.

В разделе 3.1 рассматривается пример мелкозернистой параллельной программы. В разделе 3.2 приводится краткий обзор методов включения задач. По результатам обзора для применения в NewTS выбирается метод включения задач, основанный на загруженности вычислительных узлов, также называемый load-based inlining.

В разделах 3.3 и 3.4 описываются детали реализации метода включения задач в NewTS. Особое внимание уделяется корректности этой операции. В некоторых случаях включение задач может изменить результат работы программы по той причине, что дочерняя задача использует контекст родительской, и переключение на нее невозможно. Таким образом, Pp. 55–62.

Blelloch G. E., Gibbons P. B., Matias Y. Provably efficient scheduling for languages with fine-grained parallelism // SPAA ’95: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures. New York, NY, USA: ACM Press, 1995. Pp. 1–12.

программа может оказаться в состоянии взаимоблокировки (deadlock).

В диссертации предлагается достаточное условие корректности, состоящее в том, что включение некоторой функции является безопасным (не может привести к взаимоблокировке), если все ее предки не используют отложенных значений. Разделы 3.3 и 3.4 посвящены методам эффективной проверки этого условия.

В четвертой главе излагаются особенности программной реализации планировщиков в системе NewTS. В разделе 4.1 описана структура данных для хранения готовых к исполнению задач. Модуль планирования NewTS позволяет определить несколько планировщиков и выбирать планировщик, используемый при запуске программы. В разделах 4.2 и 4.описаны интерфейсы модуля планирования и отдельных планировщиков.

В разделах 4.4 и 4.5 приведены детали реализации балансирующего планировщика и планировщика Fishing.

Пятая глава посвящена тестированию разработанных планировщиков, которое проводилось на вычислительном кластере МВС-15000 BM МСЦ РАН, а также на гетерогенной распределенной вычислительной системе, описанной далее. Кластер МВС-15000 состоит из 574 узлов, каждый из которых содержит два процессора PowerPC 970 2.2 ГГц. Для передачи данных используется коммуникационная сеть Myrinet.

Одна из программ, используемых в тестировании программа RT, которая строит изображение трехмерных объектов с высоким разрешением методом трассировки лучей. Граф вызовов в программе RT представляет собой сбалансированное в смысле числа вершин бинарное дерево. Каждая листовая Т-функция вычисляет прямоугольную область изображения, их вычислительная сложность различна и зависит от входных данных.

Pages:     ||
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.