На правах рукописи

Притула Михаил Николаевич

ОТОБРАЖЕНИЕ DVMH-ПРОГРАММ НА КЛАСТЕРЫ С

ГРАФИЧЕСКИМИ ПРОЦЕССОРАМИ

Специальность 05.13.11 – математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва – 2013

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

Научный руководитель:

Крюков Виктор Алексеевич, доктор физико-математических наук, профессор.

Официальные оппоненты:

Якобовский Михаил Владимирович, доктор физико-математических наук, профессор, заведующий сектором в Институте прикладной математики им.

М.В. Келдыша РАН.

Антонов Александр Сергеевич, кандидат физико-математических наук, ведущий научный сотрудник Лаборатории Параллельных информационных технологий НИВЦ МГУ.

Ведущая организация: Институт системного программирования РАН

Защита состоится «17» декабря 2013 г. в 11 часов на заседании Диссертационного совета Д 002.024.01 в Институте прикладной математики им.

М.В. Келдыша РАН по адресу: 125047, Москва, Миусская пл., 4.

С диссертацией можно ознакомиться в библиотеке Института прикладной математики им. М.В. Келдыша РАН.

Автореферат разослан «15» ноября 2013 г.

Ученый секретарь диссертационного совета Т.А.Полилова доктор физико-математических наук

Общая характеристика работы

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

Поэтому программисту необходимы высокоуровневые языки параллельного программирования, обеспечивающие эффективное использование современных параллельных систем. Такие языки могут быть построены путем расширения языков DVM-системы [http://www.keldysh.ru/dvm/], базирующихся на разработанной в ИПМ им.М.В.Келдыша РАН высокоуровневой модели параллельного программирования, получившей название DVM (Distributed Virtual Machine).

Эти языки (Фортран-DVM и Си-DVM) в течение многих лет использовались для создания параллельных программ для кластеров.

Цели работы Целями данной диссертационной работы являлись:

• исследование возможностей отображения DVM-программ на кластер с ускорителями, обеспечивающих распределение вычислений между универсальными многоядерными процессорами (ЦПУ) и несколькими графическими процессорами (ГПУ);

• разработка алгоритмов распределения вычислений между ЦПУ и ГПУ и алгоритмов управления перемещением данных между памятью ЦПУ и памятью ГПУ;

• разработка алгоритма распределения подзадач между узлами кластера.

Научная новизна работы 1. Разработаны алгоритмы распределения подзадач между узлами кластера, позволяющие балансировать загрузку вычислительных узлов кластера при выполнении многоблочных программ.

2. Разработаны алгоритмы распределения витков параллельных циклов внутри узлов между ядрами ЦПУ и несколькими ГПУ.

3. Разработаны алгоритмы автоматического перемещения требуемых актуальных данных между памятью ЦПУ и памятями нескольких 4. Созданы средства сравнительной отладки DVMH-программ, базирующиеся на сопоставлении результатов одновременного выполнения на ЦПУ и на ГПУ одних и тех же фрагментов программы.

Проведенные эксперименты с тестами и реальными приложениями показали, что для класса задач, при решении которых используются разностные методы на статических структурных сетках, можно писать программы на языке Фортран-DVMH, которые эффективно выполняются на кластерах с ускорителями.

Практическая значимость С использованием разработанных алгоритмов создана система поддержки компиляторов DVMH-программ. Разработка компилятора с языка ФортранDVMH существенно упростила создание эффективных программ для кластеров с ускорителями, способных автоматически настраиваться на целевую конфигурацию вычислительной системы. Компилятор с языка Фортран-DVMH, включающий в себя систему поддержки выполнения DVMH-программ, входит в состав DVM-системы и используется на факультете ВМК МГУ при проведении практикума по технологиям параллельного программирования. С использованием этого компилятора был распараллелен на кластер с ускорителями ряд прикладных вычислительных задач.

Апробация работы и публикации Основные результаты диссертации были доложены на российских и международных научных конференциях и семинарах:

1. Международной научной конференции “Научный сервис в сети Интернет: суперкомпьютерные центры и задачи”, сентябрь 2010 г., г.

2. Международной научной конференции “Научный сервис в сети Интернет: экзафлопсное будущее”, сентябрь 2011 г., г. Новороссийск.

3. XIII международном семинаре “Супервычисления и математическое моделирование”, октябрь 2011 г., г. Саров.

4. International Research Conference on Information Technology. Seventh International PhD&DLA Symposium, октябрь 2011 г., г. Pecs, Hungary.

5. Международной суперкомпьютерной конференции “Научный сервис в сети Интернет: поиск новых решений”, сентябрь 2012 г., г.

6. APOS/HOPSA Workshop on Exploiting Heterogeneous HPC Platforms, январь 2013 г., г. Berlin.

7. Международной конференции "Параллельные вычислительные технологии (ПаВТ'2013)", апрель 2013 г., г. Челябинск.

8. Международной суперкомпьютерной конференции “Научный сервис в сети Интернет: все грани параллелизма”, сентябрь 2013 г., г.

Имеется 12 публикаций, из которых три [5,7,11] – в журналах из списка ВАК.

Структура и объем работы Диссертация состоит из введения, семи глав, заключения, списка литературы (39 наименований) и одного приложения. Общий объем работы составляет 105 страниц, работа содержит 1 иллюстрацию и 9 таблиц.

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

В первой главе приводится обзор языков и технологий программирования для кластеров и графических процессоров.

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

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

Для программирования графических процессоров производители аппаратного обеспечения предложили две довольно низкоуровневые технологии – CUDA и OpenCL. Относительная сложность и необычность (в сравнении с работой на ЦПУ) использования графических процессоров для вычислений общего назначения удерживает их от повсеместного использования.

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

Однако распространить стандарт OpenMP на графические процессоры не получалось.

В ИПМ им. М. В. Келдыша РАН в 2011 году в рамках данного исследования было предложено расширение DVM-модели, позволяющее разрабатывать программы для кластеров с графическими процессорами. Эта расширенная модель названа DVMH (DVM for Heterogeneous systems).

В ноябре 2011 года был предложен стандарт OpenACC для программирования графических процессоров с помощью директив, его вторая версия вышла в июне 2013 года.

В июле 2013 года опубликован стандарт OpenMP 4.0, в который вошли средства для работы с подключаемыми вычислительными устройствами, обладающие собственной памятью (сопроцессоры, ускорители).

Приводится сравнение этих трех предлагаемых подходов.

Главное отличие этих подходов заключается в том, что DVMH предназначен для написания программ для кластеров, в узлах которых установлены многоядерные процессоры и ускорители разных архитектур, отличающиеся как по типу памяти (общая или раздельная), так и по скорости обменов между памятью ускорителей и памятью ЦПУ. Стандарты OpenACC и OpenMP 4.0 предназначены для написания программ, выполняющихся в отдельных узлах такого кластера.

В стандартах OpenACC и OpenMP 4.0 применяется методика управления перемещением данных, основанная на указании каждого перемещения пользователем и определяемых пользователем интервалах (для OpenMP 4.0 – только статически определенных) существования экземпляра переменной на ускорителе. В DVMH-языках применена иная методика, основанная на указаниях входных и выходных данных для фрагментов кода, предназначенных для выполнения на ускорителях (такие фрагменты называются вычислительными регионами или просто регионами), и позволяющая автоматически определять необходимые перемещения данных в зависимости от того, на каком устройстве (ускорителе или многоядерном процессоре) был выполнен тот или иной вычислительный регион.

В стандартах OpenACC и OpenMP 4.0 управление тем, исполнять ли данный регион на ускорителе или нет, задается вычисляемыми во время выполнения выражениями. В DVMH такой возможности нет, однако имеется набор режимов работы, задающих на каких устройствах выполнять регионы.

Модели DVMH и OpenMP 4.0 предусматривают использование нескольких ускорителей для одной программы. В OpenACC одновременная работа с несколькими ускорителями не предусмотрена.

По части поддержки циклов с зависимостями DVMH имеет поддержку редукционных зависимостей, регулярных зависимостей; OpenACC имеет поддержку только редукционных зависимостей; OpenMP 4.0 имеет поддержку редукционных зависимостей и предоставляет средства синхронизации для распараллеливания циклов и с другими типами зависимостей.

Вторая глава посвящена описанию схемы построения компилятора с языка Фортран-DVMH, функций системы поддержки выполнения DVMHпрограмм.

Рис. 1. Схема работы компилятора с языка Фортран-DVMH.

Компилятор с языка Фортран-DVMH состоит из блоков анализа программы, блока конвертации, системы поддержки выполнения DVMHпрограмм (библиотека LibDVMH).

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

Конвертер преобразует исходную программу в эквивалентную ей пару программ, которые опираются на систему поддержки выполнения DVMHпрограмм и уже могут быть скомпилированы в машинный код стандартными компиляторами.

LibDVMH является библиотекой функций, которая обеспечивает выполнение DVMH-программ, основные ее функции включают:

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

• отображение распределенного массива на абстрактную параллельную машину;

• отображение параллельного цикла и параллельных задач на абстрактную параллельную машину;

• создание и загрузка буферов для доступа к удаленным данным;

вычислительных регионов на разнородных вычислительных • балансировку загрузки узлов кластера и вычислительных устройств каждого узла (статическую и динамическую);

• управление текущим состоянием и местонахождением данных, их перемещениями;

• возможности для функциональной сравнительной отладки корректности работы на ускорителях;

• возможности для отладки производительности.

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

При компиляции вычислительных регионов происходит их разделение на составные части – параллельные гнезда циклов и последовательные операторы.

Эти части выделяются в отдельные подпрограммы с использованием соответствующих технологий программирования: для ГПУ – CUDA, для ЦПУ – OpenMP. Использование и настройка таких подготовленных подпрограмм ведется напрямую из LibDVMH, что позволяет их гибко комбинировать, многократно запускать, откладывать их выполнение (асинхронный режим).

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

Ручное управление программистом всеми перемещениями данных имеет ряд недостатков:

• Программисту приходится быть четко ориентированным на то, сколько и каких ускорителей используется в программе, а также предполагается ли одновременное использование ЦПУ для дополнительного разделения вычислений. Это может приводить к утере ее универсальности в плане используемой целевой ЭВМ, или же значительному усложнению программы.

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

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

• сравнительная функциональная отладка (выполнение региона с одними и теми же исходными данными на ЦПУ и на ускорителях, а затем сравнение значений полученных выходных данных);

• многократное выполнение регионов с одними и теми же исходными данными с целью поиска значений оптимизационных параметров.

Разработанные алгоритмы основываются на следующих понятиях:

• представитель некоторой переменной на некотором устройстве – экземпляр переменной, размещенный в памяти устройства;

• состояние актуальности представителя – задание для всех элементов представителя, являются ли они (элементы) актуальными, т.е. имеют ли они последнее присвоенное этому Для манипуляций с состояниями актуальности представителей переменных вводится особый вид функций – PCSn. Вводятся базовые операции над ними: объединение двух PCS, разность двух PCS, понижение одного PCS на уровень другого PCS, горизонтальная разность двух PCS, пересечение двух PCS, пересечение двух PCS с повышением.

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

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

• Вход в вычислительный регион. При входе в вычислительный регион системе поддержки выполнения сообщается о каждой переменной направления ее использования для ее подмассивов.

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

1. Для каждого используемого устройства:

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

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

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

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

Параллелизм в DVMH-программах проявляется на нескольких уровнях:

• Распределение данных и вычислений по MPI-процессам. Этот уровень задается специальными директивами распределения или перераспределения данных и спецификациями параллельных • Распределение данных и вычислений по вычислительным устройствам при входе в вычислительный регион.

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

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

Системой поддержки выполнения DVMH-программ поддерживаются три режима распределения данных и вычислений по вычислительным устройствам в точках входа в регионы:

1. Простой статический режим.

2. Динамический режим с подбором схемы распределения.

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

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

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

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

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

В пятой главе описывается алгоритм распределения подзадач между узлами кластера.

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

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

В данной работе предлагается эвристический алгоритм распределения подзадач для составления расписания прохождения подзадач, где для каждой подзадачи будет указано стартовое время, группа процессоров для ее счета.

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

Как известно, задача составления многопроцессорного расписания NPполна, а, значит, исследуемая задача NP-трудна, так как является обобщением NP-полной задачи.

За M обозначим количество процессоров, за N – количество подзадач.

Для каждой подзадачи t известно:

1. минимальное используемое количество процессоров Kmin(t) 2. максимальное используемое количество процессоров Kmax(t) 3. функция зависимости времени исполнения от количества процессоров time(t,k)>0 такая, что для всех k из диапазона [Kmin(t),