Технологический процесс разработки параллельных программ в среде ParJava
В рамках среды ParJava разработан и реализован ряд инструментальных средств, которые интегрированы с открытой средой разработки Java-программ Eclipse []. После подключения этих инструментальных средств к Eclipse, получилась единая среда разработки SPMD-программ, включающая как инструменты среды ParJava, так и инструменты среды Eclipse: текстовый редактор, возможность создания и ведения проектов, возможность инкрементальной трансляции исходной программы во внутреннее представление. Интеграция в среду Eclipse осуществлена с помощью механизма «подключаемых модулей».
При разработке параллельной программы по последовательной программе сначала оценивается доля последовательных вычислений, что позволяет (с помощью инструмента “Speed-up”) получить оценку максимального потенциально достижимого ускорения в предположении, что все циклы, отмеченные прикладным программистом, могут быть распараллелены. Затем с использованием инструмента “Loop Analyzer” среды ParJava циклы исследуются на возможность их распараллелить.
Для распараллеленных циклов с помощью инструмента “DataDistr” подбирается оптимальное распределение данных по узлам вычислительной сети. В частности, для гнезд циклов, в которых все индексные выражения и все границы циклов заданы аффинными формами, инструмент “DataDistr” позволяет с помощью алгоритма [] найти такое распределение итераций циклов по процессорам, при котором не требуется синхронизаций (обменов данными), если, конечно, требуемое распределение существует (см. ниже пример 1). В этом случае инструмент “DataDistr” выясняет, можно ли так распределить итерации цикла по узлам, чтобы любые два обращения к одному и тому же элементу массива попали на один и тот же процессор. Для этого методом ветвей и сечений находится решение задачи целочисленного линейного программирования, в которую входят ограничения на переменные циклов, связанные с необходимостью оставаться внутри границ циклов, и условия попадания на один и тот же процессор для всех пар обращений к одинаковым элементам массива.
Задача решается относительно номеров процессоров, причем для удобства процессоры нумеруются с помощью аффинных форм (т.е. рассматривается многомерный массив процессоров). Если оказывается, что для обеспечения сформулированных условий все данные должны попасть на один процессор, это означает, что цикл не может выполняться параллельно без синхронизации. В последнем случае инструмент “DataDistr” может в диалоговом режиме найти распределение данных по узлам, требующее минимального числа синхронизаций при обменах данными. Для этого к условиям сформулированной задачи линейного программирования добавляются условия на время обращений к одним и тем же элементам массива: например, в случае прямой зависимости, требуется, чтобы обращение по записи выполнялось раньше, чем обращение по чтению. В частности, при решении дополнительных временных ограничений, может оказаться, что они могут быть выполнены, если обрабатываемые в программе массивы будут разбиты на блоки. При этом смежные блоки должны быть распределены по процессорам «с перекрытием», чтобы все необходимые данные были на каждом из процессоров. При этом возникают так называемые теневые грани (т.е. части массива, используемые на данном процессоре, а вычисляемые на соседнем процессоре). Ширина теневых граней определяется алгоритмом решения задачи и определяет фактический объем передаваемых в сети сообщений. Количество теневых граней зависит выбора способа нумерации процессоров: априорно выгоднее всего, чтобы размерность массива процессоров совпадала с размерностью обрабатываемых массивов данных. Однако в некоторых случаях оказывается более выгодным, чтобы размерность массива процессоров была меньше, чем размерность обрабатываемых массивов данных. Пример 1. В качестве примера работы инструмента “DataDistr” рассмотрим цикл: for (i = 1; i
Для приведенного примера инструмент “DataDistr” выдаст следующее распределение: X[1,100] = X[1,100] + Y[0,100]; /*s1*/ for (p = -99; p = 0) Y[p+l,l] = X[p+l,0] + Y[p+l,l]; /*s2*/ for (i = max(l,p+2); i
где p – номер вычислителя, а цикл по p определяет распределение данных по вычислителям.
Таким образом, исходный цикл расщепился на 200 цепочек вычислений, каждая из которых может выполняться независимо. После того, как данные распределены по вычислителям, прикладному программисту необходимо выбрать такие операции обмена данными и так трансформировать свою программу, чтобы добиться максимально возможного перекрытия вычислений и обменов данными. Среда ParJava позволяет решать этот вопрос в диалоговом режиме, используя интерпретатор параллельных программ (инструмент “Interpreter”). В тривиальных случаях даже использование стандартных коммуникационных функций (MPI_send, MPI_receive) позволяет достичь достаточного уровня масштабируемости. Однако, в большинстве случаев это невозможно, так как приводит к большим накладным расходам на коммуникации, а это в соответствии с законом Амдаля существенно урезает масштабируемость. Достичь перекрытия вычислений и обменов для некоторых классов задач позволяет использование коммуникационных функций MPI_Isend, MPI_Ireceive совместно с функциями MPI_Wait и MPI_Test. Это поясняется примером 2. Пример 2. Как видно из схемы на рис. 1, необходимо добиться, чтобы во время передачи данных сетевым процессором (промежуток между моментами времени
и 
) вычислитель был занят обработкой данных, а не простаивал в ожидании окончания пересылки. 
Рис. 1. Схема передачи данных MPI Подбор оптимальных коммуникационных функций требует многочисленных интерпретаций различных версий разрабатываемой программы. Для ускорения этого процесса строится «скелет» программы и все преобразования делаются над ним. После достижения необходимых параметров параллельной программы автоматически генерируется вариант программы в соответствии с полученным коммуникационным шаблоном. Проиллюстрировать важность оптимального выбора операций пересылок можно на следующем «скелете» реальной программы моделирования торнадо (рис. 2а). Если в рассматриваемом «скелете» заменить блокирующие операции Send и Recv на неблокирующие и установить соответствующую операцию Wait после гнезда циклов получится «скелет», представленный на рис. 2б.
На рис. 3 приведены графики ускорения «скелетов» программы представленного на рис. 2а и 2б. Как видно, такая замена существенно расширила область масштабируемости программы. При этом окончательная версия «скелета», удовлетворяющая требованиям прикладного программиста, используется для построения трансформированной исходной программы.
Рис. 2. Схематичное изображение алгоритмов с блокирующими и неблокирующими пересылками К сожалению, в большинстве реальных программ такими простыми преобразованиями не удается достичь необходимого уровня перекрытия, либо такое преобразование невозможно. Использование предлагаемой технологии обеспечивает возможность применения различных преобразований программы, и достигать необходимых параметров программы в приемлемое время. Этот процесс отладки и оптимизации параллельной программы показывает, что задача сама по себе неформализована. На сегодняшний день не может быть реализован компилятор, делающий оптимизацию автоматически, т.к. в некоторых точках процесса программист обязан принимать волевые решения.
Рис. 3. Сравнение масштабируемости параллельных программ, использующих блокирующие и неблокирующие пересылки На следующем этапе, необходимо проинтерпретировать полученную программу на реальных данных, для того чтобы оценить, какое количество вычислителей будет оптимальным для счета. Для этого снова используется инструмент «Inerpreter». Поскольку интерпретатор использует смешанную технику, включающую в себя элементы прямого выполнения, довольно остро стоит проблема нехватки памяти на инструментальной машине. Моделирование некоторых серьёзных программ требует использования довольно больших массивов данных, которые не могут быть размещены в памяти одного вычислительного узла. Для решения этой проблемы проводится преобразование модели, представляющее собой удаление выражений программы, значение которых не влияет на поток управления. Это позволяет качественно изменить требования по памяти, в том числе существенно сократив время интерпретации. Таким образом, инструментальные средства среды ParJava позволяют реализовать технологический процесс, обеспечивающий итеративную разработку параллельной программы.Отметим, что итеративная разработка предполагает достаточно большое число итераций, что может привести к большим накладным расходам по времени разработки и ресурсам. Итеративная разработка реальных программ, предлагаемая в рамках ParJava, возможна благодаря тому, что большая часть процесса выполняется на инструментальном компьютере, в том числе за счет использования инструментов, базирующихся на интерпретаторе параллельных программ. Применение интерпретатора позволяет достаточно точно оценивать ускорение программы. Ошибка на реальных приложениях не превосходила 10%, и в среднем составила ~5% [36-44]. Окончательные значения параметров параллельной программы можно уточнить при помощи отладочных запусков на целевой аппаратуре.
