Solution of applied problems in the parallel programming system aspect.pdf Современные суперкомпьютеры имеют сложную архитектуру. Они состоят из огромного количества вычислительных узлов, на каждом из которых есть несколько процессоров, каждый процессор содержит несколько ядер. Активно внедряются гибридные системы, где в дополнение к основным процессорам используются графические ускорители, специализированные вычислители типа Cell B.E., Matrix2000 или Intel Xeon Phi, вычислители на базе ASIC и PLD. Стремительный прогресс в использовании параллелизма аппаратной частью привел к большому разрыву между пред оставляемыми ресурсами и возможностями по их эффективному использованию с помощью имеющихся средств разработки. Для преодоления этого разрыва в России и за рубежом ведутся активные исследования по созданию средств параллельного программирования высокого уровня. К наиболее известным российским проектам можно отнести систему OpenTS [1] (Институт программных систем им. А.К. Айламазяна РАН), системы DVM [2] и НОРМА [3] (Институт прикладной математики им. М.В. Келдыша), язык mpC [4] (Институт системного программирования им. В.П. Иванникова), систему SFP [5] (Институт систем информатики им. А.П. Ершова), язык Пифагор [6] (Сибирский федеральный университет), систему ДВОР [7] (Южный федеральный университет), комплекс для параллельного программирования Graphplus templet [8] (Самарский государственный аэрокосмический университет). Результаты этих исследований показывают, что создание универсальной системы параллельного программирования высокого уровня трудно достижимо - слишком высока специфика отдельных предметных областей. Поэтому требуется дальнейшее изучение специализированных способов представления алгоритмов. В статье представлены результаты исследований решения ряда прикладных задач в системе параллельного программирования Аспект. Аспект - это экспериментальная система, разрабатываемая в Институте вычислительной математики и математической геофизики СО РАН и предназначенная для исследования новых форм представления алгоритмов и методов задания управления в параллельной программе. В статье кратко рассмотрены архитектура системы Аспект, особенности языка программирования Аспект, результаты применения системы Аспект для решения задачи LU-разложения матриц, задачи оценки математических ожиданий аддитивных функционалов от траекторий диффузионных процессов и задачи о взаимодействии короткого лазерного импульса с плазмой методом «частицы-в-ячейках». 1. Система параллельного программирования Аспект В основе системы параллельного программирования Аспект [9] лежат асинхронная модель вычислений с управлением на основе строгого частичного порядка [10] и фрагментированное программирование [11] как способ разработки параллельных программ. Архитектурно система Аспект состоит из транслятора с языка Аспект и исполнительной подсистемы. Суть фрагментированного программирования заключается в представлении алгоритма решения задачи в виде множества фрагментов данных и множества фрагментов кода. Фрагмент кода получает на вход набор входных фрагментов данных, на основе которых вычисляет набор выходных фрагментов данных. Подстановка фрагментов данных в качестве параметров фрагмента кода называется применением фрагмента кода к фрагментам данных (один и тот же фрагмент кода может применяться к различным фрагментам данных). Совокупность фрагмента кода и его входных и выходных фрагментов данных называется фрагментом вычислений. На множестве фрагментов вычислений задается частичный порядок, т.е. множество ограничений на порядок выполнения фрагментов (управление). Для реализации фрагментированного программирования на практике разработан язык управления вычислениями Аспект [12]. В нем фрагменты кода и фрагменты данных записываются на существующем процедурном языке программирования (в настоящее время поддерживается только С++), а фрагменты вычислений и частичный порядок их исполнения задаются средствами языка Аспект. Фрагменты вычислений, для которых зависимости явно не заданы, рассматриваются как независимые. Подробная информация о способах задания управления в языке Аспект приведена в [13]. Фрагментированная программа преобразуется транслятором языка Аспект в код на языке С++ и включается в одноименный класс, который предоставляет интерфейс для добавления фрагментов вычислений в очередь исполнения, а также осуществляет учет необходимых параметров (количество исполняемых фрагментов, количество готовых к исполнению фрагментов и др.). Для каждого фрагмента данных создается отдельный тип, с использованием которого объявляются данные задачи (переменные класса). Для каждого фрагмента кода генерируется метод класса, а также две переменных: признак завершения и переменная синхронизации. Исполнительная подсистема Аспект состоит из набора функциональных модулей: менеджер потоков (управляет распределением работы между процессорами (ядрами); обращается за очередной порцией работы к планировщику), менеджер памяти (управляет распределением памяти в системе, осуществляет ее выделение / освобождение для очередей и фрагментированных программ), планировщик (управляет набором приоритизированных очередей, реализованных в виде мониторов; имеет сложность планирования 0(1)). 2. Разложение матриц На примере задачи разложение квадратной матрицы A в произведение матриц L и U (LU-разло-жения) рассмотрим применение фрагментированного программирования для решения численных задач. Постановка задачи. Пусть имеется матрица A = (ay), i = 1...N, j = 1...N. Ее разложение в виде A = LU, где L = (lj) - нижняя треугольная матрица, а U = (%) - верхняя треугольная матрица с единицами на главной диагонали, может быть вычислено по формулам [14]: lj = a -Z См*(i ^ j) (1) Uj = f (a-Z ), (i < j). (2) Фрагментация алгоритма. Матрица A собирается из фрагментов данных (подматриц) A[i][j]. Выделяются четыре фрагмента кода F1, F2, F3 и F4. Первый фрагмент кода обрабатывает фрагменты данных, расположенные на главной диагонали матрицы A, по формулам (1) и (2); второй - фрагменты данных справа от диагональных элементов по формуле (1); третий - фрагменты данных под диагональными элементами по формуле (2); четвертый пересчитывает внутреннюю матрицу по формуле (3): е.. = a. - > l., ij j / i ik k Вычисления организуются по шагам. Первый шаг показан на рис. 1. Квадраты отображают фрагменты данных. Внутри каждого квадрата указано, какой экземпляр фрагмента вычислений его обрабатывает. Стрелками отображены зависимости между экземплярами фрагментов вычислений, а цифра в центре показывает порядок исполнения экземпляров. Первым запускается на исполнение экземпляр фрагмента вычислений G1[0] (применение фрагмента кода F1 к фрагменту данных A[0][0]), после чего параллельно могут исполняться экземпляры G2[0][1], G2[0][2], G3[1][0] и G3[2][0]. Любой из экземпляров с порядком исполнения 3 может начать исполнение, как только завершатся оба экземпляра, от которых он зависит. Например, G4[0][1][2] может начать исполнение после завершения G3[1][0] и G2[0][2]. Рис. 1. Первый шаг вычисления LU-разложения матрицы A Более подробно решение задачи LU-разложения матрицы разбирается в [11]. Текст программы LU-разложения матрицы на языке программирования Аспект можно найти в [13]. Результаты эксперимента. В качестве примера рассмотрим решение задачи о LU-разложении вещественной матрицы размера 5 040 х 5 040 при размере фрагмента данных 90 х 90 на системе HP ProLiant DL580 G5 (4 процессора Intel Xeon X7350, 16 ядер, 256 Гбайт RAM). Результаты представлены в табл. 1. Таблица 1 Результаты измерений производительности программы решения задачи о LU-разложении Характеристика Количество ядер 1 2 4 8 16 Время счета, с 31,01 15,6 7,93 4,13 2,35 Ускорение 1 1,99 3,91 7,51 13,2 Аспект-программа демонстрирует практически линейное ускорение, что объясняется фрагмен-тированным представлением алгоритма, за счет которого достигается более эффективное использование кэш-памяти. По этой же причине фрагментированный код лучше масштабируется. 3. Метод Монте-Карло Статистическое моделирование является одним из численных методов решения математических задач, при котором искомые величины представляются вероятностными характеристиками какого-либо явления и приближенно определяются путем наблюдения за поведением модели этого явления [15]. Задачи статистического моделирования, как правило, требуют больших вычислительных ресурсов, поскольку в среднем выборочное значение может долго вычисляться и / или из соображений точности необходимо моделировать большое число выборочных реализаций. (3) Рассмотрим задачу оценки математических ожиданий аддитивных функционалов от траекторий диффузионных процессов, представляющих собой интегралы по некоторым малым областям расширенного фазового пространства от концентрации траекторий7 [16]. На ее примере можно проследить, как в системе Аспект реализуются алгоритмы, которые можно фрагментировать на большое число независимых фрагментов вычислений. Постановка задачи. Пусть трехмерный диффузионный процесс y() задан системой стохастических дифференциальных уравнений в смысле Ито: dy(t) = a(y(t))dt + b(y(t))dw(t), 0 < t < T , у(0) = Уо, (4) где a(y) - трехмерная векторная функция, b(y) - матричная функция размерности 3 х 3, w(t) - трехмерный винеровский процесс, yo - случайный вектор. Моделирование траекторий системы (4) выполняется с помощью метода Эйлера: У+i = У +■Aa(y) + VAtb(y%, i = 0, 1, ..., n, где yi - численное решение системы (4) в узле ti равномерной сетки с постоянным шагом At = Т/ n, а {$■} - последовательность независимых между собой нормальных случайных векторов с независимыми в совокупности компонентами, имеющими стандартное нормальное распределение. Пусть необходимо вычислить полную концентрацию диффузионных траекторий Ф(Т, yc) во временном интервале [0, Т] в некоторой удаленной от источника точке yc. При переходе к приближенной оценке точные диффузионные траектории заменим приближенными траекториями Эйлера, а точку yc -шаром Qc малого радиуса Гс с центром в точке yc. Тогда будем иметь следующую статистическую оценку: n Ф(Т,у) - E£d = у)A , i=0 где ю(у) = iQc(y)IVc, Vc - объем шара Qc. Фрагментация алгоритма. Разобьем всё пространство моделируемых траекторий на m областей. Тогда входные фрагменты данных - это начальные значения генератора случайных чисел в каждой области, выходные фрагменты данных - значение концентрации в каждой области. Фрагментов кода необходимо два: первый вычисляет концентрацию в интервале jm, (j + 1)m - 1] (здесь j - номер части пространства моделирования), а второй осуществляет сложение всех концентраций, полученных на каждой области пространства моделирования, и вычисление окончательного результата. Фрагменты вычислений получаются применением фрагмента кода первого типа к каждому входному фрагменту данных. Так как моделируемые реализации не зависят друг от друга, потоковое управление между этими фрагментами вычислений отсутствует. Все фрагменты вычислений первого типа должны выполниться до начала исполнения фрагмента вычисления второго типа. Результаты эксперимента. В качестве примера рассмотрим систему (4) на временном интервале [0, 10] с постоянным вектором сноса a = (0, 0,5, 0,5)T, единичной матрицей диффузии b = I, шаром Qc радиуса rc = 0,1 с центром в точке yc = (8, 0, 0) и нулевым начальным условием yo = 0 [17]. Для метода Эйлера положим At = 10-2. Таблица 2 Результаты измерений производительности программы оценки математических ожиданий аддитивных функционалов от траекторий диффузных процессов методом Монте-Карло Характеристика Количество ядер 1 2 4 8 16 Время счета, c 23 805,50 12 051,00 5 939,00 2 990,00 1 510,68 Ускорение 1 1,97 4 7,96 15,75 Результаты измерений на системе HP ProLiant DL580 G5 для 64 000 000 смоделированных траекторий приведены в табл. 2. Видно, что ускорение практически линейное, что достигается за счет независимого расчета концентрации в каждом интервале, а также хорошей локальности данных, используемых в ходе расчета. Эта задача, тривиальная с точки зрения распараллеливания, тем не менее показывает, что сама система программирования Аспект не вносит существенных задержек и не требует существенных накладных расходов на исполнение фрагментов. 4. Метод частицы-в-ячейках Методы частиц, как и конечно-разностные методы, образуют особую группу вычислительных алгоритмов, объединенных способом дискретизации исходной математической задачи [18]. Их применение широко распространено для решения сложных физических задач (например, задач физики бес-столкновительной плазмы). Вычислительная сложность метода объясняется огромным количеством частиц, необходимых для получения результатов с хорошей точностью. Рассмотрим решение задачи о взаимодействии короткого лазерного импульса с плазмой методом «частицы-в-ячейках»8 [19]. Она позволяет оценить применение системы Аспект для решения достаточно сложной задачи численного моделирования, включающей в себя несколько различных алгоритмов. Постановка задачи. В области, имеющей форму параллелепипеда, находится фольга, представляемая тонким слоем плазмы. Плазма состоит из электронов и ионов одного типа. Лазерный импульс (в виде пакета электромагнитных волн различной амплитуды и поляризации) входит через поверхность параллелепипеда, взаимодействует с фольгой, частично отражаясь и проходя через нее. Описываемый физический процесс представляется уравнениями Власова для ионов и электронов: которые дополняются уравнениями Максвелла для электрического и магнитного полей: - 471-Г 1

Скачать электронную версию публикации