ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ —
УДК 004.92+004.94
ИТЕРАТИВНАЯ РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В СРЕДЕ ParJava
© 2009 г. А. И. Аветисян, С. С. Гайсарян, В. В. Бабкова
Институт системного программирования РАН 109004 Москва, ул. Солженицына, 25 E-mail: {arut, ssg, barbara} @ispras.ru Поступила в редакцию 28.08.2008 г.
Рассматривается технологический процесс итеративной разработки параллельных программ и поддерживающие его инструментальные средства, реализованные в среде ParJava. Одним из достоинств среды ParJava является возможность выполнения большей части разработки на инструментальном компьютере с использованием модели разрабатываемой параллельной программы. Это существенно сокращает накладные расходы по времени разработки и по используемым ресурсам. Предложенный процесс демонстрируется на примере разработки параллельной программы моделирования интенсивных атмосферных вихрей.
1. ВВЕДЕНИЕ
Одной из фундаментальных проблем параллельного программирования является проблема организации высокопродуктивных вычислений. Под высокопродуктивными вычислениями [1] понимается комплексный подход к оценке качества высокопроизводительных программ, при котором учитывается не только время выполнения (эффективность), но и ресурсы, затраченные на разработку.
В настоящее время обеспечение высокой продуктивности существенно осложняется тем, что промышленная разработка прикладных параллельных программ для систем с распределенной памятью (кластеров) ведется на последовательных языках программирования с явным использованием обращений к коммуникационной библиотеке MPI, что связано с необходимостью ручной доводки программ (распределение данных, шаблоны коммуникаций и др.).
Актуальной является задача создания технологических процессов и поддерживающих их инструментальных средств разработки параллельных программ, позволяющих сократить неприемлемо высокие затраты времени и человеческих ресурсов на разработку приложений.
Конечно, наиболее кардинальным решением было бы создание нового языка высокого уровня, который обеспечил бы возможность разрабатывать параллельные программы с помощью оптимизирующих компиляторов. Но, к сожалению, исследования по высокоуровневым языкам параллельного программирования, проводившиеся начиная с 1988 года, не увенчались успехом. Ни один из разработанных языков: HPF (и его Java-версия HPJava), Cilk, UPC (и его Java-версия Titanium) и ряд других менее известных языков, - не сумел решить поставленных перед ним задач [2]. Основная причина неудачи в том, что, несмотря на значительные усилия, до сих пор не удалось разработать компиляторные технологии, позволяющие генерировать эффективный параллельный код. Отметим также, что надежды, связанные с созданием языков нового поколения X10, Chapel, Fortress, даже несмотря на то, что эти языки требуют более детально описывать структуру параллельной вычислительной среды, пока не оправдываются.
В данной статье описан технологический процесс разработки параллельных программ и инструменты среды ParJava [3], поддерживающие этот процесс. Процесс проиллюстрирован на
примере разработки параллельной программы моделирования интенсивных атмосферных вихрей.
2. ТЕХНОЛОГИЯ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В СРЕДЕ РагЛауа
В данном разделе описан технологический процесс разработки параллельных программ решения уравнений математической физики и инструменты РагЛауа, поддерживающие этот процесс. Технологический процесс включает следующие этапы:
1) Реализация последовательной версии разрабатываемой программы.
2) Оценка максимального потенциально достижимого ускорения по доле последовательных вычислений в программе.
3) Обеспечение возможности параллельного выполнения гнезд циклов:
a. Исследование гнезд циклов на возможность параллельного выполнения (вычисление вектора направлений и вектора расстояний между итерациями гнезда циклов с помощью Омега-теста).
b. Преобразование гнезд циклов к виду, допускающему параллельное выполнение (устранение зависимостей по данным между итерациями).
4) Распределение данных по узлам вычислительной сети.
a. Минимизация количества операций обмена.
b. Обеспечение локальности данных на узле.
5) Выбор операций обмена данными.
6) Оценка границ области масштабируемости и времени счета на реальных данных.
7) В случае необходимости, использование механизма контрольных точек.
Инструментальные средства среды ParJava позволяют увязать перечисленные этапы в единый технологический процесс, обеспечивающий итеративную разработку параллельной программы: если после очередного этапа выясняется невозможность выполнения необходимых требований к качеству параллельной программы (масштабируемости), следует вернуться на предыдущий этап и скорректировать решения, принятые на этом этапе. Например, если после второго этапа выяснится, что минимально возможная доля последовательных вычислений слишком велика, необходимо вернуться на первый этап и изменить последовательный алгоритм.
Отметим, что итеративная разработка предполагает достаточно большое число итераций, что может привести к большим накладным расходам по времени разработки и ресурсам. Итеративная разработка реальных программ, предлагаемая в данной работе, возможна благодаря тому, что большая часть процесса выполняется на инструментальном компьютере, в том числе за счет использования инструментов, базирующихся на интерпретаторе параллельных программ.
Таким образом, чтобы получить масштабируемую программу, надо, в первую очередь, свести к минимуму долю вычислений, которые не могут выполняться параллельно. Это те вычисления, время выполнения которых не зависит от количества процессоров. Согласно закону Амда-ля, если f - доля последовательных вычислений и если параллельная программа выполняется на p-вычислителях без накладных расходов на организацию параллельных вычислений, максимально достижимое ускорение (независимо от числа используемых вычислителей) при f = 50% составит не более 2, а при f = 1% не более 50. Следовательно, приступая к распараллеливанию программы, необходимо оценить и по возможности минимизировать f. При этом надо учитывать следующее: 1) если аппаратура целевой вычислительной системы или используемая версия MPI не поддерживает параллельный ввод/вывод, то операторы ввода/вывода входят в f ; 2) если цикл не распараллеливается, то он входит в f.
В среде ParJava реализован инструмент "MaxSpeed-up", который, используя временной профиль последовательной программы (строит-
for (i=1; i <= 100; i++) for(j=1; j <=100; j++)
{
X[i,j]=X[i,j] + Y[i - 1,j]; /*s1*/
Y[i,j]=Y[i,j] + X[ij - 1]; /*s2*/
}
Рис. 1.
ся инструментом "Profiler"), оценивает f и строит для этой программы график зависимости потенциально достижимого ускорения от количества вычислителей. По умолчанию предполагается, что все циклы могут быть распараллелены, при этом пользователь имеет возможность отметить циклы, которые он не собирается распараллеливать. В случае, если потенциально достижимое ускорение удовлетворительно, переходим к следующему этапу.
Цель третьего этапа - выбор (построение) для каждого гнезда циклов максимального подгнез-да, допускающего параллельное выполнение, то есть все циклы, которые рассматривались как потенциально распараллеливаемые, исследуются на возможность их реального распараллеливания. Сначала для каждого гнезда циклов вычисляются вектор направлений и вектор расстояний между итерациями, которые выявляют особенности зависимостей по данным между итерациями. Для этого в среде ParJava реализован Омега-тест (инструмент "Loop Analyzer"). Для определения зависимостей существует большое количество тестов. Бесполезно решать задачу напрямую, даже с линейными индексными выражениями, так как нахождение зависимостей сводится к решению системы диофантовых уравнений (или задаче целочисленного линейного программирования), что является NP-полной задачей. Тесты для определения зависимостей можно условно разбить на простые, но не точные, и точные, но сложные. Компромиссным вариантом здесь является Омега-тест [4], который основан на последовательном применении набора тестов от простого к сложному.
В случае наличия зависимостей исследование вектора направлений и вектора расстояний помогает выбрать такое преобразование гнезда циклов [5], которое приводит его к распараллеливаемому виду. Отметим, что в настоящее время не существует общего подхода к решению
проблемы и на данный момент в среде ParJava не реализовано инструментов преобразований циклов. Предполагается, что пользователь вручную выполняет необходимые преобразования циклов, верифицируя их результаты с помощью инструмента "Loop Analyzer". Во многих случаях проблему удается решить при помощи сравнительно простых преобразований: изменения порядка циклов в гнезде, слияния и расщепления циклов, замены индекса и др. Кроме того, есть простой способ обойти зависимости, используя дополнительные буферы для хранения копий массивов (применим, если объем используемой памяти не критичен).
На следующем этапе необходимо распределить данные по вычислителям таким образом, чтобы минимизировать коммуникации между вычислителями.
Существует класс задач, для которых можно так распределить данные, что обмены данными между вычислителями будут полностью исключены. Хорошо известны такие тривиальные случаи, как обработка изображений, метод Монте-Карло и др. Однако существуют случаи, когда возможность такого распределения данных по вычислителям неочевидна. В качестве примера рассмотрим цикл, приведенный на рис. 1.
Распределение данных по вычислителям для таких задач можно построить с помощью инструмента среды ParJava "DataDistr", который использует методы целочисленного программирования. Для приведенного примера этот инструмент выдаст распределение, показанное на рис. 2, где p - номер вычислителя, а цикл по p определяет распределение данных по вычислителям. Таким образом, исходный цикл расщепился на 200 цепочек вычислений, каждая из которых может выполняться независимо.
Однако для большей части программ параллельное выполнение без обменов невозможно. Потребность в обменах возникает тогда, когда р
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.