Автоматическое распараллеливание последовательных программ для многоядерных кластеров

Размещено на http://www.allbest.ru/

УДК 519.685.1

Учреждение Российской академии наук Институт прикладной математики им. М.В. Келдыша РАН

Автоматическое распараллеливание последовательных программ для многоядерных кластеров

В.А. Бахтин

М.С. Клинов

Разработка программ для высокопроизводительных кластеров и других параллельных систем с распределенной памятью продолжает оставаться исключительно сложным делом, доступным узкому кругу специалистов и крайне трудоемким даже для них. Основная причина - это низкий уровень современной технологии автоматизации разработки параллельных программ. В настоящее время практически все параллельные программы для многоядерных кластеров (SMP-кластеров) разрабатываются с использованием низкоуровневых средств передачи сообщений (MPI). MPI-программы трудно разрабатывать, сопровождать и повторно использовать при создании новых программ. Использование гибридной модели параллельного программирования (MPI/OpenMP) является еще более сложной задачей. Поэтому вполне естественно, что прикладной программист хотел бы получить либо инструмент, автоматически преобразующий его последовательную программу в параллельную программу, либо высокоуровневый язык параллельного программирования, обеспечивающий эффективное использование современных параллельных систем.

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

Поэтому исследователи сосредоточились на двух направлениях:

· разработка высокоуровневых языков параллельного программирования (HPF, OpenMP-языки, DVM-языки, CoArray Fortran, UPC, Titanium, Chapel, X10, Fortress);

· создание систем автоматизированного распараллеливания (CAPTools/Parawise, FORGE Magic/DM, BERT77), в которых программист активно вовлечен в процесс распараллеливания.

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

В системах автоматизированного распараллеливания на программиста стали возлагаться ответственные решения не только по уточнению свойств его последовательной программы (результатов анализа), но и по ее отображению на параллельную ЭВМ. Кроме того, отсутствие широко распространенного высокоуровневого языка параллельного программирования вынуждало использовать в качестве выходного языка систем автоматизированного распараллеливания низкоуровневые языки. Полученные на них программы сложны для восприятия и внесения в них даже небольших модификаций, что приводило к необходимости повторять процесс распараллеливания при модификации исходной последовательной программы. Все это вызывало огромные трудности при внедрении таких систем.

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

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

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

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

На втором этапе автоматически распараллеливающий компилятор преобразует потенциально параллельную программу в параллельную программу для заданной ЭВМ.

Достижение приемлемой эффективности выполнения параллельной программы может потребовать многократного повторения этих двух этапов, но система автоматизации распараллеливания должна быть ориентирована на сокращение таких итераций. Прежде всего, она должна позволить на инструментальной машине и еще до появления текста параллельной программы оценить эффективность ее работы на разных ЭВМ.

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

Далее рассматриваются принципы построения автоматически распараллеливающего компилятора АРК-DVM, алгоритмы отображения на многоядерный кластер, приводятся результаты экспериментальной проверки компилятора.

1. Автоматически распараллеливающий компилятор

Компилятор АРК-DVM ориентирован на автоматическое распараллеливание программ из класса задач, при решении которых используются разностные методы на статических структурных сетках. К тому же на данный момент последовательные программы должны удовлетворять следующим требованиям:

· быть написаны на языке Fortran 77;

· не содержать процедуры или допускать их инлайн-подстановку.

Компилятор на вход получает текст потенциально параллельной программы вместе со специальными аннотациями, которую для простоты изложения будем называть просто «последовательной программой». Автоматически распараллеливающий компилятор состоит из блоков анализа последовательной программы (анализаторов) и блоков отображения на параллельные ЭВМ (экспертов). Их взаимодействие осуществляется через специальную базу данных.

Допускается использование нескольких анализаторов для дополнения базы данных более точными результатами анализа. Анализаторы могут различаться методами анализа (статические или динамические) и алгоритмами (более быстрыми или более точными).

Эксперты могут отличаться алгоритмами отображения на параллельные ЭВМ и используемыми языками параллельного программирования. Функциями эксперта являются:

· построение схем распараллеливания;

· оценка схем посредством прогнозирования времени выполнения параллельной программы на заданной ЭВМ;

· получение текста параллельной программы для лучшей схемы.

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

На вход эксперту, кроме структуры и свойств последовательной программы, поступает описание ЭВМ (в нем задается архитектура - мультипроцессор, кластер или многоядерный кластер, число узлов и ядер в узлах, производительности ядер и параметры коммуникационной среды) и параметры задачи (значения переменных, которые определяют размеры массивов и количество витков циклов).

Выходом компилятора АРК-DVM является текст параллельной программы на языке Fortran DVM/OpenMP [1, 2].

Язык Fortran DVM/OpenMP представляет собой расширение стандартного языка Fortran 95 директивами параллелизма. В результате компиляции программа на языке Fortran DVM/OpenMP преобразуется в программу на стандартном языке Fortran OpenMP, которая выполняется на узлах кластера и использует библиотеку MPI для организации взаимодействия между узлами.

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

2. Алгоритмы отображения на многоядерный кластер

Блок отображения (DVM/OpenMP эксперт) на многоядерный кластер можно рассматривать как дальнейшее развитие блока отображения на кластер (DVM эксперта) для обеспечения распараллеливания программы внутри каждого узла средствами OpenMP. Поскольку алгоритмы отображения на кластер были ранее уже описаны [3], то ниже приводятся только алгоритмы распараллеливания программы внутри каждого узла.

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

В текущей версии компилятора не используется вложенный параллелизм, поскольку на данный момент количество ядер в узле пока невелико (8 - 12 ядер) и выигрыш от его использования в таком случае незначителен. Поэтому среди множества вложенных друг в друга потенциально параллельных циклов выбирается один цикл, распараллеливание которого может дать наибольший эффект. Для каждого такого распараллеливаемого цикла генерируются соответствующие OpenMP-указания:

· директива PARALLEL DO - для циклов без зависимости по данным;

· клауза REDUCTION - для циклов c редукционными зависимостями;

· клаузы PRIVATE или FIRSTPRIVATE - для циклов c приватными переменными.

Для циклов с зависимостью по данным организуется конвейерное выполнение (см. Приложение 1).

3. Результаты экспериментальной проверки компилятора

Компилятор АРК-DVM был испытан на реальных приложениях: тестах NAS [4] BT, LU, SP, и разработанных в ИПМ им. М.В. Келдыша РАН программах MHPDV [5, 2] и ZEBRA [6]. Тексты последовательных версий этих программ были получены из их DVM-версий путем удаления всех DVM-директив и инлайн-подстановки процедур в тело головной подпрограммы.

Программа BT (Block Tridiagonal Solver) - нахождение конечно-разностного решения 3-х мерной системы уравнений Навье-Стокса для сжимаемой жидкости или газа. Используется трех диагональная схема, метод переменных направлений. При выполнении программы задавался класс С (сетка 162x162x162) и класс А (сетка 64x64x64).

Программа LU (Lower-Upper Solver) отличается от BT тем, что применяется метод LU-разложения с использованием алгоритма SSOR (метод верхней релаксации), а программа SP (Scalar Pentadiagonal Solver) - тем, что используется скалярная пяти диагональная схема.

Программа MHPDV осуществляет трехмерное моделирование сферического взрыва во внешнем магнитном поле с помощью решения уравнений идеальной магнитной гидродинамики.

Программа ZEBRA производит расчет нейтронных полей атомного реактора в диффузионном приближении.

Полученные в результате автоматического распараллеливания программы на языке Fortran DVM/OpenMP могут рассматриваться как программы для кластера (на языке Fortran DVM) и как программы для мультипроцессора (на языке Fortran OpenMP). Поэтому они сравнивались с эталонными вариантами (программами, распараллеленными вручную) сначала для кластера, затем для мультипроцессора. В таблице 1 и 2 приведены времена их выполнения.

Программу SP автоматически распараллелить для кластера не удалось (никаких DVM-директив в нее не было вставлено). Необходима ее серьезная модификация, чтобы избавиться от имеющихся там зависимостей между витками циклов, препятствующих их параллельному выполнению (первые три витка цикла модифицируют один и тот же элемент массива, который не является редукционной или приватной переменной). Такие циклы можно распараллелить, если обеспечить, чтобы зависимые витки выполнялись на одном процессоре, что и было сделано при ручном распараллеливании.

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

На программах MHPDV и ZEBRA времена выполнения автоматически распараллеленных вариантов и вручную распараллеленных - близки. Увеличение количества процессоров для программы ZEBRA (свыше 64-х) уже не ускоряет ее выполнение.

Из-за отсутствия версий программ, распараллеленных вручную для мультипроцессора при помощи языка Fortran OpenMP, для сравнительной оценки качества распараллеливания компилятором АРК-DVM использовались вручную распараллеленные программы на языке Fortran DVM и программы, автоматически распараллеленные компилятором фирмы Интел. кластер распараллеливающий компилятор многоядерный

Заключение

Разработка компилятора АРК-DVM для современных кластеров и исследование его применимости на реальных приложениях показали, что удалось решить принципиальную задачу - обеспечить эффективное автоматическое отображение последовательной программы на кластер. При этом для эффективного отображения на многоядерные кластеры потребовалась реализация двух уровней параллелизма (модель передачи сообщений между узлами и модель общей памяти в узлах).

Необходимо отметить ту важную роль, которую сыграли разработанные в рамках системы DVM средства функциональной отладки программ на языке Fortran DVM/OpenMP. Эти средства отладки поддерживают два метода отладки, наиболее автоматизирующие процесс отладки программ, получаемых в результате автоматического распараллеливания. Первый метод - метод динамического контроля корректности спецификаций параллелизма (DVM-директив и OpenMP-директив). Важнейшим достоинством этого метода является точность локализации ошибки в программе. Второй метод - метод сравнительной отладки, основанный на автоматическом сравнении промежуточных результатов выполнения исходной последовательной программы и параллельного выполнения сгенерированной программы на языке Fortran DVM/OpenMP. Без этих средств автоматизированной отладки экспериментальная проверка компилятора АРК-DVM на достаточно больших и сложных программах потребовала бы огромных усилий и очень продолжительного времени.

В настоящее время ведется развитие компилятора в двух направлениях - расширение входного языка Fortran 77 до языка Fortran 95 и снятие ограничений на использование процедур. Кроме того, в рамках создания системы автоматизации распараллеливания ведется разработка ее диалоговой подсистемы. Их успешное выполнение позволит перейти к практическому внедрению системы автоматизированного распараллеливания программ на языке Fortran и ее дальнейшему развитию применительно к кластерам с неоднородными узлами (содержащими в качестве ускорителей графические процессоры, например).

Благодарности

Работа поддержана программой Союзного государства СКИФ-ГРИД, программами Президиума РАН №14 и №15, грантами РФФИ № 08-01-00479 и № 10-07-00211, грантом Президента РФ МК-3324.2010.9.

Список литературы

1. Бахтин В.А., Коновалов Н.А., Крюков В.А., Поддерюгина Н.В. Fortran OpenMP/DVM - язык параллельного программирования для кластеров // Материалы второго Межд. науч.-практ. cем. «Высокопроизводительные параллельные вычисления на кластерных системах», Нижний Новгород, 26-29 ноября 2002 г. C. 28-30.

2. Бахтин В.А., Коновалов Н.А., Поддерюгина Н.В., Устюгов С.Д. Гибридный способ программирования DVM/OpenMP на SMP-кластерах // Труды Всерос. науч. конф. «Научный сервис в сети Интернет: технологии параллельного программирования», Новороссийск, 18-23 сентября 2006 г. М.: Изд-во МГУ, 2006. С. 128-130.

3. Клинов М.С., Крюков В.А. Автоматическое распараллеливание Фортран-программ. Отображение на кластер // Вестник Нижегородского университета им. Н.И. Лобачевского. 2009. № 2. С. 128-134.

4. Ustyugov S.D. Three Dimensional Numerical Simulation of MHD Solar Convection on Multiproccesors Supercomputer Systems // Proc. of the NSO 23 Workshop «Solar MHD: Theory and Observations - a High Spatial Resolution Perspective», Sunspot, New Mexico, USA, Jul. 2005.

5. Arzhanov V.I., Voronkov A.V., Golubev A.S., Zemskov E.A., Konovalov N.A., Krukov V.A. Development of explicit cyclic schemes with Chebyshev's polinomials for space neutron kinetics on the multiprocessor computers. // Proc. of INFORUM-99 Annual Meeting on Nuclear Technology, Karlsruhe, Germany, May 1999, P. 19-23.

Приложение

Таблица 1. Времена выполнения вариантов программ на кластере МВС-100К (в секундах) («авт» - автоматическое распараллеливание компилятором АРК-DVM, «ручн» - ручное)

Варианты	Число процессоров 1	Число процессоров 8	Число процессоров 64	Число процессоров 256	Число процессоров 1024
BT-авт (класс С)	мало памяти	1255.97	182.70	54.64	21.36
BT-ручн	мало памяти	817.88	128.01	30.27	7.19
LU-авт (класс С)	3482.40	1009.49	148.78	40.33	25.55
LU-ручн	2103.14	858.26	122.61	34.99	19.97
SP-авт (класс С)	1982.00	-	-	-	-
SP-ручн	2601.85	-	-	-	-
MHPDV-авт	3703.23	500.78	89.32	34.75	12.78
MHPDV-ручн	3574.29	486.74	79.63	32.15	10.98
ZEBRA-авт	75.09	11.13	1.96	-	-
ZEBRA-ручн	75.62	10.18	1.85	-	-

Таблица 2. Времена выполнения вариантов программ на одном узле кластера СКИФ-МГУ (в секундах) («авт» - автоматическое распараллеливание компилятором АРК-DVM, «авт-Интел» - автоматическое распараллеливание компилятором Интел, «ручн» - ручное)

Варианты	Число ядер 1	Число ядер 2	Число ядер 4	Число ядер 8
BT-авт (класс А)	119.04	61.39	39.56	34.66
BT-ручн	109.78	55.88	37.65	34.73
BT-авт-Интел	115.12	109.38	106.81	106.45
LU-авт (класс А)	110.42	60.56	39.01	33.35
LU-ручн	106.58	57.09	37.88	35.53
LU-авт-Интел	105.04	91.05	83.97	83.94
SP-авт (класс А)	81.08	76.64	75.42	76.62
SP-ручн	102.82	51.42	33.19	32.91
SP-авт-Интел	78.82	72.09	70.21	69.85
MHPDV-авт	300.19	148.87	82.89	51.60
MHPDV-ручн	333.80	169.97	91.25	57.55
MHPDV-авт-Интел	297.70	260.14	252.82	261.10
ZEBRA-авт	45.91	21.85	11.71	5.92
ZEBRA-ручн	53.68	26.17	14.72	8.11
ZEBRA-авт-Интел	55.38	55.09	55.55	55.21

Пример АВТОМАТИЧЕСКОГО РАСПАРАЛЛЕЛИВАНИЯ

Ниже приводится текст параллельной программы на языке Fortran DVM/OpenMP, сгенерированный компилятором АРК-DVM по последовательной программе, который был дополнен пояснениями авторов в виде текста курсивом. В последовательную программу, реализующую метод последовательной верхней релаксации (SOR), компилятором АРК-DVM были добавлены DVM-спецификации и OpenMP-спецификации параллелизма, оформленные в виде спецкомментариев, начинающихся с префиксов «CDVM$» и «!$OMP» соответственно, а также OpenMP-операторы для организации работы конвейера на узле кластера, начинающиеся с префикса «!$». Эти спецкомментарии и операторы будут игнорироваться, если программа компилируется как последовательная, и будут учитываться, если программа компилируется в режиме DVM, OpenMP или DVM/OpenMP. Все остальные операторы последовательной программы остались без изменений.

PROGRAM SOR

PARAMETER ( N = 1000, M = 1000 )

REAL A(N, M), EPS, MAXEPS, W

INTEGER ITMAX

первое измерение массива а - распределяется блоками между узлами кластера

CDVM$ DISTRIBUTE (BLOCK,*) :: a

!$ INTEGER OMPEXP_IAM,OMPEXP_NUMT,OMPEXP_ILIMIT

!$ INTEGER OMPEXP_ISYNC(0:32)

!$ INTEGER OMP_GET_NUM_THREADS

!$ INTEGER OMP_GET _THREAD_NUM

PRINT *, '********** TEST_SOR **********'

ITMAX=20

MAXEPS = 0.5E - 5

W = 0.5

итерация (j,i) параллельного многомерного цикла выполняется, на том узле, где размещен элемент a(i,j). Выполнение итераций цикла на узле распределяется между OpenMP-нитями

CDVM$ PARALLEL (j,i) ON a(i,j)

!$OMP PARALLEL DO PRIVATE(i,j)

DO J = 1, M

DO I = 1, N

IF ( I .EQ.J) THEN

A( I, J ) = N + 2

ELSE

A( I, J ) = -1.0

ENDIF

ENDDO

ENDDO

DO IT = 1, ITMAX

!$OMP PARALLEL PRIVATE(OMPEXP_IAM, OMPEXP_NUMT, OMPEXP_ILIMIT, j, s, i),

!$OMP* REDUCTION(MAX: eps)

OMPEXP_IAM, OMPEXP_NUMT, OMPEXP_ILIMIT, j, s, i - приватные переменные (их использование локализовано в пределах одной нити), редукционная переменная EPS используется для вычисления максимума. OMPEXP_IAM - номер нити в группе, OMPEXP_NUMT - количество нитей в группе, OMPEXP_ILIMIT - максимальное количество нитей, которые требуются для конвейерного выполнения цикла

!$ OMPEXP_IAM = OMP_GET_THREAD _NUM ()

!$ OMPEXP_NUMT = OMP_GET_NUM_THREADS ()

OMPEXP_ISYNC - синхронизационный массив, значение OMPEXP_ISYNC(OMPEXP_IAM) устанавливается равным 0, поскольку нить еще не посчитала свою порцию витков цикла

!$ OMPEXP_ISYNC (OMPEXP_IAM) = 0

Если количество нитей в группе больше количества витков распределяемого цикла, то часть нитей не получит работу и не будет участвовать в выполнении цикла

!$ OMPEXP_ILIMIT=MIN(OMPEXP_NUMT-1,n - 1 - 2)

!$OMP BARRIER

итерация (j,i) параллельного многомерного цикла выполняется на том узле, где размещен элемент a(i,j), спецификация ACROSS указывает на регулярную зависимость по первому измерению массива a

CDVM$ PARALLEL (j,i) ON a(i,j),

CDVM$* ACROSS (a(1:1,0:0))

DO J = 2, M-1

!$ IF (OMPEXP_IAM .GT. 0 .AND. OMPEXP_IAM .LE. OMPEXP_ILIMIT) THEN

цикл ожидания пока нить с меньшим номером не посчитает свою порцию витков цикла

!$ DO WHILE (OMPEXP_ISYNC(OMPEXP_IAM-1) .EQ. 0)

!$OMP FLUSH (OMPEXP_ISYNC)

!$ ENDDO

приступаем к работе и разблокируем нить с меньшим номером

!$ OMPEXP_ISYNC(OMPEXP_IAM-1)=0

!$OMP FLUSH (OMPEXP_ISYNC)

!$ ENDIF

!$OMP DO SCHEDULE (STATIC)

DO I = 2, N-1

S = A( I, J )

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

* A( I, J+1 )) + ( 1-W ) * A( I, J)

EPS = MAX ( EPS, ABS( S - A( I, J )))

ENDDO

!$OMP ENDDO NOWAIT

!$ IF (OMPEXP_IAM .LT. OMPEXP_ILIMIT) THEN

цикл ожидания пока нить с большим номером не приступит к работе

!$ DO WHILE (OMPEXP_ISYNC (OMPEXP_IAM) .EQ. 1)

!$OMP FLUSH (OMPEXP_ISYNC)

!$ ENDDO

устанавливаем признак, что посчитана очередная порция данных

!$ OMPEXP_ISYNC (OMPEXP_IAM)=1

!$OMP FLUSH (OMPEXP_ISYNC)

!$ ENDIF

ENDDO

!$OMP END PARALLEL

PRINT 200, IT, EPS

200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)

IF (EPS .LT. MAXEPS ) GO TO 4

ENDDO

4 OPEN (3, FILE='SOR.DAT', FORM='FORMATTED',STATUS='UNKNOWN')

WRITE (3,*) A

CLOSE (3)

END

Вычисление элемента а(i,j) двумерной матрицы размером N*M должно производиться после вычисления элементов а(i,j-1) и а(i-1,j). Первое достигается использованием последовательного цикла по j, а второе - распределением вычислений между узлами кластера и выполнением их в виде конвейера, а также синхронизацией работы нитей одного узла кластера на каждом витке цикла по j (пока К-ая нить не посчитает элемент а(i-1,j) следующая нить с номером К+1 не начинает свою работу) с помощью установки и проверки специальных синхронизационных переменных. При этом, как после установки, так и перед проверкой синхронизационной переменной, необходимо выполнять операцию FLUSH.

Чтобы не использовать матрицу синхронизационных переменных размером Т*M (где Т - число нитей, а M - число столбцов матрицы), в данном алгоритме используется вектор размера Т. Но для многократного использования каждого элемента вектора потребовалась еще одна синхронизация, чтобы на каждом витке последовательного цикла по j каждая нить сбрасывала в нуль уже использованный ею на этом витке элемент вектора.

Аннотация

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

Ключевые слова: Высокопроизводительные вычисления, параллельные вычисления, автоматическое распараллеливание, многоядерный кластер.

Размещено на Allbest.ru

...