Дальневосточный федеральный университет В статье предлагается асинхронная модель вычислений, отличительной особенностью которой является управление на основе строгого частичного порядка. Показано, что такой способ задания управления обладает рядом преимуществ для параллельных вычислений, в частности, позволяет представлять алгоритмы с высокой степенью непроцедурности, а также полностью отделяет управление от вычислений. Разработан алгоритм преобразования этой модели в известную асинхронную модель с управляющими операторами. На базе предложенной модели разработана и реализована система программирования Аспект. Ключевые слова: асинхронная модель вычислений, язык параллельного программирования, представление алгоритмов с высокой степенью непроцедурности.
agora.guru.ru/pavt ности представления алгоритмов через явное задание информационных и управляющих зависимостей. За счет этого, а также за счет специализации системы на решении задач численного моделирования, планируется добиться высокого качества автоматически конструируемых параллельных программ, в том числе, возможности адаптации к различным аппаратным архитектурам.
Одной из задач в рамках поставленной цели является разработка подходящей модели параллельных вычислений. Ее обсуждению и посвящена статья. 2. Асинхронная модель вычислений 2.1. Простая асинхронная модель вычислений блоков, A = \bigl{ Ak | k \in 1, n\bigr} .
Асинхронная модель вычислений была впервые предложена в работе [
Асинхронная программа (или А-программа ) представляет собой набор P = (M, A), где M – конечное множество переменных, M = \{ x1, x2, . . . , xm\} ; A – конечное множество АМножество M называется памятью. Память состоит из переменных с неразрушающим чтением и записью, стирающей предыдущее содержимое переменной. Выделяется информационная IM и управляющая CM памяти: M = IM \cup CM .
Каждый А-блок Ak образован четверкой (Mk, Tk, Ok, Ck), где Mk — подмножество памяти M , используемое А-блоком Ak, причем Mk = TkIn \cup OkIn \cup OkOut \cup CkIn \cup CkOut, TkIn \subetq M ,
CM ; Tk — спусковая функция (или триггерфункция), представляющая собой предикат Tk(x1, x2, . . . , xl), xi \in TkIn, i = 1, l; Ok — операция, которая по значениям входных переменных x1, x2, . . . , xm вычисляет значения выходных переменных y1, y2, . . . , yn, xi \in
OkOut, i = 1, m, j = 1, n; Ck — управляющий оператор, который по значениям входных переменных x1, x2, . . . , xp вычисляет значения выходных переменных y1, y2, . . . , yq, xi \in
CkOut, i = 1, p, j = 1, q. Под «вычислением» понимается вычисление одной или несколких частично рекурсивных функций.
Асинхронный вычислительный процесс — это множество T процессов \{ t1, t2, . . . , tn\} , где каждый процесс ti исполняет некоторый А-блок Ak, то есть вычисляет его операцию Асинхронная система (или А-система ) есть набор правил, позволяющих произвести Ok, а затем — управляющий оператор Ck. вычисления для заданной А-программы P : 1. В произвольный момент времени вычисляются триггер-функции А-блоков из некоторого непустого подмножества A\prime множества A-блоков A и формируется множество = \bigl{ Ak | Ak \in A\prime w\edg Tk = ИСТИНА, k = 1, n\bigr} , готовых к исполнению А-блоков A\prime :
A\prime A\prime s\ubetq A, A\prime s\ubetq
A\prime . 2. Из множества готовых А-блоков A\prime выделяется некоторое подмножество A\prime , А-блоки которого запускаются на исполнение. Для каждого А-блока создается соответствующий процесс. Процессы исполняются независимо друг от друга. 3. Исполнение А-программы завершается, когда ни один процесс не исполняется и значения триггер-функций всех А-блоков ложны. Правила формирования множеств A\prime и
A\prime асинхронной системой не регламентируются. 2.2. Асинхронная модель вычислений с массовыми операциями С точки зрения параллельных вычислений, простая асинхронная модель вычислений имеет тот недостаток, что она не позволяет явно описывать массовые вычисления. Их либо приходится программировать внутри А-блоков, что скрывает большую часть параллелизма алгоритма, либо необходимо задать фиксированное количество одинаковых А-блоков, что не позволяет обрабатывать данные неизвестной длины, а также существенно увеличивает размер программы.
Для преодоления этих недостатков в [
Здесь i \in \BbN , j \in \BbN , i n\ot= j. 3. Значение триггер-функции проверяется для всех невыполняющихся экземпляров Ai . k Любой экземпляр Aik с истинным значением триггер-функции Tki может начать исполнение, которое состоит в исполнении операции Oki, а затем управляющего оператора Ci .
k 2.3. Асинхронная модель вычислений с управлением на основе строгого частичного порядка В моделях, описанных выше, управление полностью определяется управляющими операторами и скрыто внутри них, что делает эту информацию недоступной для анализа, который необходим для автоматизированного распределения ресурсов. Кроме того, для повышения уровня параллельного программирования необходимы более явные средства задания управления.
Асинхронная модель вычислений с управлением на основе строгого частичного порядка отображает информацию об управлении на уровне модели, изменяя асинхронную модель вычислений с массовыми А-блоками следующим образом: i
k 1. Экземпляр А-блока Aik описывается четверкой (Mki, Tki, Oki, Rki), где Mki, Tki и Oki имеют прежнее значение, а Rki есть строгий частичный порядок, заданный на подмножестве Cki экземпляров А-блоков А-программы A: \lange Cki , Rki\rangle , которое будем также обозначать l\ange Cki , <\rangle . Rk = \bigcup Rki, R = \bigcup Rk. 2. Каждый экземпляр А-блока исполняется не более одного раза. Многократное исполнение простого А-блока можно представить в виде одного массового А-блока (если снять ограничение на то, что экземпляры А-блока обязательно отличаются хотя бы одним входным параметром, то есть требование Mki \not= Mkj исчезает), где каждому исполнению простого А-блока соответствует один экземпляр массового А-блока. Такое изменение позволяет однозначно идентифицировать исполнение любого экземпляра его именем, что необходимо для задания управления частичным порядком.
А-программа, определенная таким образом, позволяет определить любую частично
рекурсивную функцию даже в случае, когда операции экземпляров А-блоков реализуют лишь
простейшие вычислимые функции. Доказательство этого факта можно найти в [
Степень непроцедурности представления алгоритмов в асинхронной программе можно
регулировать на двух уровнях:
b\ulet первоначальная степень непроцедурности определяется программистом при разбиение
алгоритма на А-блоки;
b\ulet при конструировании параллельной программы имеется возможность уменьшить
степень непроцедурности за счет группировки [
Реализация управления в асинхронной модели вычислений на основе строгого частичного порядка может быть выполнена во время исполнения программы в режиме интерпретации, однако более эффективно до начала исполнения сгенерировать специализированный код, который реализует корректное управление. Для этого необходимо формально определить содержимое управляющих операторов, а также разработать алгоритмы, позволяющие автоматически преобразовывать управление на основе строгого частичного порядка в управление на основе управляющих операторов. 3.1. Определение управляющего оператора
Признак завершения А-блока . Это формальное определение было предложено в
работе [
Управляющий оператор Cki присваивает переменной P (Aik) значение ИСТИНА, проверяет все экземпляры, которые могут начать исполнение после завершения Aik, и добавляет в множество готовых экземпляров те из них, у которых признак завершения всех предшествующих экземпляров имеет значение ИСТИНА и которые имеют истинное значение триггер-функции.
А-программа представляет собой набор P = (M, A, A0), где M и A имеют прежнее значение, а A0 есть множество А-блоков, готовых к исполнению сразу после старта Апрограммы. Достоинства: b\ulet независит от типа переменной (простая, структурная); b\ulet независит от типа управления (прямое, потоковое); b\ulet объем управляющей памяти зависит от количества А-блоков. Недостатки: b\ulet в случае реализации экземпляра А-блока с помощью А-программы, невозможно отслеживать вычисление отдельных переменных, а только всех переменных целиком; b\ulet чем больше зависимостей у экземпляра А-блока, тем сложнее вычислить триггерфункцию.
Признак готовности переменной . Каждой переменной xj \in M в управляющей памяти ставится в соответствие переменная логического типа, которую будем называть признаком готовности переменной xj и обозначать P (xj). Если xj — структурная переменная, то каждому компоненту x\=[j] ставится в соответствие собственный признак готовности P (x\=[j]). Истинность переменной P (xj) означает, что переменная xj вычислена. В начальном состоянии памяти P (xj) = ИСТИНА для переменных, содержащих исходные данные задачи и P (xj) = ЛОЖЬ для всех остальных переменных, xj \in M , j = 1, m.
Управляющий оператор Cki присваивает всем переменным P (xq), где xq \in OkiOut значение ИСТИНА, проверяет все экземпляры, которые могут начать исполнение после завершения Aik, и добавляет в множество готовых экземпляров те из них, у которых признак готовности всех входных переменных имеет значение ИСТИНА и которые имеют истинное значение триггер-функции.
Достоинства: b\ulet возможно запускать зависимые блоки по мере вычисления переменных. Недостатки: b\ulet чем больше входных переменных, тем сложнее вычислить триггер-функцию (если входная переменная А-блока является структурной, необходимо проверить готовность всех ее компонент); b\ulet объем управляющей памяти зависит от количества переменных; b\ulet затруднена реализация прямого управления, когда информационные зависимости между А-блоками отсутствуют.
Подход на основе признаков готовности переменной хорошо подходит для теоретических работ. С точки зрения практической реализации более перспективен подход на основе признаков завершения А-блоков. Определим для него А-систему асинхронной модели вычислений с массовыми А-блоками через набор правил: 1. В пустое множество готовых экземпляров A\prime включаются все экземпляры из множества A0, у которых истинно значение триггер-функции: A\prime = \{ Ak | Tki = ИСТИНА, Ak \in i
A0\} . 2. Из множества готовых экземпляров A\prime выбирается некоторое подмножество A\prime , экземпляры которого запускаются на исполнение. Для каждого экземпляра А-блока создается процесс tk,i, который вычисляет его операцию Oi , а затем управляющий k оператор Ci . В результате в множество A\prime , возможно, будут добавлены новые экземk пляры. Каждый экземпляр А-блока выполняется не более одного раза. 3. Выполнение А-программы завершается, когда множество A\prime становится пустым и не существует исполняющихся процессов. 3.2. Алгоритм конструирования управляющих операторов
Для автоматического конструирования управляющих операторов, определенных через признак завершения А-блока, предлагается использовать следующий алгоритм: ВХОД : асинхронная программа P с управлением на основе строгого частичного порядка, экземпляр А-блока Ai .
k ВЫХОД : код управляющего оператора Cki для экземпляра А-блока Ai . k ШАГИ : 1. Генерируется команда, которая установит признак завершения для Aik в значение ИСТИНА. 2. Формируется множество S экземпляров А-блоков, зависящих от Aik: S = \{ Slj | Aik < Sj, Slj \in A, (Aik, Slj) \in R}\ . В результате исполнения экземпляра Aik каждый экземпляр l
Slj потенциально может стать готовым к исполнению. 3. Для каждого экземпляра Slj: b\ulet формируется множество U экземпляров А-блоков, которые должны исполниться до запуска Slj: U = \{ Uqp | Uqp < Slj, Uqp \in A, (Uqp, Slj) \in R}\ ; b\ulet генерируется команда создания переменной с именем f lagjl и ей присваивается значение ИСТИНА;
p b\ulet для каждого элемента Uq \in U генерируется команда, объединяющая значение признака завершения P(Uqp) со значением переменной f lagjl по принципу И; b\ulet генерируется набор команд, который: – проверяет значение переменной f lagjl; – если оно истинно, проверяет значение триггер-функции Tlj экземпляра Slj; – если значение триггер-функции Tlj истинно, добавляет экземпляр Slj в множество готовых к исполнению экземпляров.
Для правильного функционирования алгоритма необходимо обеспечить корректную синхронизацию. Действительно, пусть R = \{ (A < C), (B < C)\} и пусть исполнение экземпляров A и B находится на стадии исполнения их управляющих операторов, причем уже выполнены команды P (A) = ИСТИНА и P (B) = ИСТИНА. Тогда проверка множества U и триггер-функции T А-блока C в каждом из управляющих операторов окажется истинной и каждый управляющий оператор добавит А-блок C в множество готовых к исполнению А-блоков, что неверно. Поэтому код, выполняющий изменение признака готовности экземпляра А-блока Aik и проверку всех зависимых экземпляров из множества S на предмет их готовности должен быть атомарным с точки зрения остальной программы. 4. Система программирования Аспект
Система программирования Аспект [
В основе архитектуры системы Аспект лежит ее разделение на два компонента: транслятор с языка Аспект и исполнительную подсистему. Транслятор осуществляет перевод Аспект-программы в асинхронную программу с массовыми А-блоками на языке C++, а исполнительная подсистема обеспечивает поддержку времени выполнения (управление потоками, памятью, очередями готовых А-блоков). 4.1. Язык программирования Аспект
Ключевым компонентом системы Аспект является язык программирования Аспект [
Если в императивных языках все команды по умолчанию исполняются последовательно, а участки программы, пригодные для параллельного исполнения, необходимо явно указать, то в языке Аспект используется прямо противоположный подход: по умолчанию считается, что все А-блоки могут исполняться параллельно, а если необходим порядок (например, из-за зависимости по данным), то его необходимо явно задать.
Для иллюстрации возможностей языка Аспект по заданию управления рассмотрим Аспект-программу, решающую задачу умножения матриц (см. рис. 1). В программе заданы матрицы A, B и C, состоящие из N \times N элементов. Каждый элемент есть матрица размера M \times M (фрагмент данных Frg). Кроме того, определен фрагмент кода Mult, который получает три матрицы (фрагменты данных X, Y и Z) на вход и добавляет произведение X на Y к выходу (фрагмент данных Z). Вычисления задаются на языке C++.
В секции «task computation» задан массовый А-блок S с областью применимости (0..N 1) \times (0..N - 1) \times (0..N - 1), при этом имя S[i][j][k] обозначает соответствующий экземпляр S. Каждый экземпляр осуществляет вычисление фрагмента кода Mult с фрагментами данных, указанными для экземпляра в качестве фактических параметров.
В секции «task control» на множестве экземпляров А-блока S задан такой частичный порядок, что каждый k -й экземпляр А-блока должен выполниться перед соответствующим program MultMatrix preface { const i n t M = 3; const i n t N = 3; }; data fragments
double Frg [M ][ M ]; code fragments
Mult ( in Frg X , Frg Y , Frg Z; out Frg Z) { f o r ( i n t i =0; i <M; ++ i) f o r ( i n t k =0; k <M; ++ k) f o r ( i n t j =0; j <M; ++ j)
Z[i ][ j] += X[i ][ k ]* Y[k ][ j ]; }; task data
Frg A[N ][ N ]; Frg B[N ][ N ];
Frg C[N ][ N ]; task computations
S[i ][ j ][ k ]: Mult (A[i ][ k], B[k ][ j], C[i ][ j], C[i ][ j ])
where i: 0..N -1 , j: 0..N -1 , k: 0..N -1; task control
S[i ][ j ][ k] < S[i ][ j ][ k +1]; end
Рис. 1. Умножение матриц (инициализация данных и вывод результата опущены) (k+1 )-м экземпляром. Управление отражает тот факт, что для вычисления C[i][j] необходимо просуммировать все матрицы, полученные в результате вычисления произведения фрагментов A[i][k] на B[k][j] (это делается внутри фрагмента Mult добавлением результата умножения к старому значению C[i][j]), и для исключения «гонки» данных (data race) суммирование необходимо выполнять последовательно.
Все экземпляры А-блока S[i][j][k] с одинаковым индексом k могут исполняться одновременно, при этом, если выполнился экземпляр S[i][j][k], то экземпляр S[i][j][k+1] может стартовать, не дожидаясь завершения исполнения других экземпляров с индексом k, то есть нет барьерной зависимости между «слоями» вычислений. 4.2. Транслятор с языка Аспект
Рассмотрим результаты работы транслятора c языка Аспект, полученые после трансляции Аспект-программы, приведенной на рис. 1. Наибольший интерес представляют две сгенерированные процедуры: b\ulet aplMain(), отвечающая за инициализацию А-Программы (см. рис. 2). Эта процедура реализует п. 1 определения А-системы из раздела 3.1. В результате ее исполнения все экземпляры S[i][j][0] будут добавлены в множество готовых экземпляров, так как будет ложно условие зависимости в силу проверки (k-1) >= 0. Выражения вида «(0)», «if(true)» являются заготовками. В случае использования более сложного управления (индексации с помощью выражений, не пустых триггер-функций и др.), они будут заполнены полезными вычислениями. Использование таких заготовок в тексте программы не приводит к потере производительности, так как любой современный оптимизирующий компилятор сможет исключить их из результирующего бинарного кода. b\ulet aplControlS(int i, int j, int k), реализующая управляющий оператор для экземпляра А-блока S[i][j][k] (см. рис. 3) согласно алгоритму из п. 3.2. Вначале процедуры проверяется, существуют ли экземпляры, зависимые от исполнившегося экзепляра. Только при их наличии захватывается примитив синхронизации и они проверяются на готовность к исполнению. Процедуры, начинающиеся с префикса «es», относятся к исполнительной подсистеме. };
} 4.3. Результаты тестовых испытаний
В таблицах 1 и 2 приведены результаты тестовых испытаний Аспект-программы умножения матриц. Тестирование проводилось на машине с 4 процессорами Intel Xeon Х7350 (16 ядер) под управлением Cent OS 5.3 64 bit. Размер матрицы брался равным 5040x5040, а размер фрагмента данных – 90x90. Время выполнения тестов указано в секундах. Таблица 1. Результаты измерений производительности программы умножения матриц Реализация Аспект-программа демонстрирует практически линейное ускорение, а также существенное превосходство над C++/OpenMP-реализацией. Это объясняется блочным представлением алгоритма, за счет которого достигается более эффективное использование кэшпамяти. По этой же причине блочный код лучше масштабируется.
Подробное обсуждение результатов тестовых испытаний выходит за рамки статьи. В
работе [
esSpinLock ( aplSLock [i -(0)][ j -(0)][( k +1) -(0)]); aplS [i -(0)][ j -(0)][ k -(0)] = true ;
// Control for operation S i f ( aplS_0 ) { bool res = true ; bool aplS0 = ( true ) && (i >= (0) && i <= ((N -1))) && (j >= (0) && j <= ((N -1))) && (k >= (0) && k <= ((N -1))); bool aplS1 = aplS0 ; aplS1 = aplS1 && aplS [i -(0)][ j -(0)][ k -(0)]; res = res && ((! aplS0 && ! aplS1 ) | (! aplS0 && aplS1 ) |
( aplS0 && aplS1 )); i f ( res )
esAddMassiveItemToQueue (0 , i , j , (k +1)); }; i f ( aplS_0 )
esSpinUnlock ( aplSLock [i -(0)][ j -(0)][( k +1) -(0)]); };
Рис. 3. Управляющий оператор для А-блока S Таблица 2. Ускорение программы умножения матриц Ускорение Аспект С++/OpenMP 1 1 1 Количество ядер 2 4 8
16 1,99 3,97 7,84 15,39 5. Близкие работы
Наиболее близким к предложенному подходу с концептуальной точки зрения можно
считать программирование с типами управления [
В работе [
Из реализованных языков для параллельных вычислений наиболее близким к
языку Аспект является язык Барс [
Весьма интересным является проект PLASMA [
В статье предложена асинхронная модель вычислений с управлением на основе строгого частичного порядка. Разработан алгоритм преобразования этой модели в известную асинхронную модель вычислений с управляющими операторами. На базе предложенной модели разработана и реализована система программирования Аспект.
Дальнейшее направление исследований связано с разработкой системы синтеза параллельных программ на базе вычислительных моделей, выходным языком которой будет являться язык программирования Аспект. Литература 1. Андрианов А.Н., Бугеря А.Б., Ефимкин К.Н., Колударов П.И. Модульная архитектура компилятора языка Норма+. Препринты ИПМ им. М. В. Келдыша. 2011. № 064. 16 с. 3. Lastovetsky A. Adaptive parallel computing on heterogeneous networks with mpC //
Parallel Computing. 2002. Vol. 28. No. 10. Pp. 1369–1407. 4. Kale L.V., Bhatele A. Parallel Science and Engineering Applications: The Charm++
Approach. CRC Press, 2013. 123 P. 5. Chamberlain B.L., Callahan D., Zima H.P. Parallel Programmability and the Chapel Language // International Journal of High Performance Computing Applications. 2007.
Vol. 21. No. 3. Pp. 291–312. 11. Arykov S.B., Malyshkin V.E. Asynchronous Language and System of Numerical Algorithms Fragmented Programming // Proceedings of the 10th International Conference on Parallel Computing Technologies (PaCT’2009). Berlin: Springer-Verlag, 2009. LNCS 5698. Pp. 1–7. 15. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВПетербург, 2002. 608 с. 17. Buttari A., Langou J., Kurzak J., Dongarra J. A class of parallel tiled linear algebra algorithms for multicore architectures // Parallel Computing. 2009. Vol. 35. No. 1. Pp. 38–53. Asynchronous model of computation controlled by strict partial order
The article proposes an asynchronous model of computation, the distinguishing feature of which is computation control based on strict partial order. It’s shown that such approach to define control in the program provides several advantages for parallel computing, in particular, allows to represent algorithms with high level of non-procedurality and completely separates control from computations. An algorithm of convertation of that model to well-known asynchronous model with control operators is developed. Aspect programming system was designed and developed on the basis of the proposed model.
Keywords: asynchronous model of computations, parallel programming language, algorithms representation with high non-procedurality 3. Lastovetsky A. Adaptive parallel computing on heterogeneous networks with mpC //
Parallel Computing. 2002. Vol. 28. No. 10. Pp. 1369–1407. 4. Kale L.V., Bhatele A. Parallel Science and Engineering Applications: The Charm++
Approach. CRC Press, 2013. 123 P. 5. Chamberlain B.L., Callahan D., Zima H.P. Parallel Programmability and the Chapel Language // International Journal of High Performance Computing Applications. 2007.
Vol. 21. No. 3. Pp. 291–312.