Российская академия наук

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

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

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

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

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

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

вычислительных машин, комплексов и компьютерных сетей Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель – доктор физико-математических наук Крюков Виктор Алексеевич Москва – 2 Оглавление Введение

Актуальность темы

Цели работы

Постановка задачи

Научная новизна работы

Практическая значимость

Апробация работы и публикации

Краткое содержание работы

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

1.1 Разработанное расширение DVM-модели

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

1.1.3 Пример программы на языке Фортран-DVMH

1.2 Обзор высокоуровневых моделей программирования для ускорителей Глава 2. Схема построения компилятора с языка Фортран-DVMH........ 2.1 Схема работы компилятора с языка Фортран-DVMH

2.2 Основные функции системы поддержки выполнения DVMH-программ

Глава 3. Алгоритмы учета актуального состояния переменных при выполнении DVMH-программ

3.1 Способы управления перемещениями данных на ускоритель и обратно

3.1.1 Ручное копирование

3.1.2 Указание входных и выходных данных для фрагментов программы

3.2 Недостатки ручного копирования

3.3 Определения терминов и базовых операций

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

3.4.1 Обработка входа в вычислительный регион

3.4.2 Обработка запроса актуализации

3.4.3 Обработка указания SHADOW_RENEW

3.4.4 Обработка указания REMOTE_ACCESS

3.4.5 Обработка указания CONSISTENT

Глава 4. Режимы распределения данных и вычислений между вычислительными устройствами

4.1 Схема выполнения DVMH-программы

4.2 Режимы распределения данных и вычислений

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

4.2.2 Динамический режим с подбором распределения

4.2.3 Динамический режим с использованием подобранной схемы распределения

Глава 5. Алгоритм распределения подзадач между узлами кластера...... 5.1 Формализация постановки задачи

5.1 Эвристический алгоритм распределения подзадач

5.2 Способы применения предложенного алгоритма

Глава 6. Дополнительные возможности по функциональной отладке и отладке производительности

6.1 Сравнение при завершении региона

6.2 Сравнение при входе в регион и при выполнении запроса актуализации

6.3 Возможности по отладке производительности

Глава 7. Приложения и тесты, разработанные c использованием языка Фортран-DVMH

7.1 Приложения, демонстрирующие применимость языка Фортран-DVMH

7.1.1 Каверна

7.1.2 Контейнер

7.1.3 Состояния кубитов

7.1.4 Кристаллизация 3D

7.1.5 Спекание 2D

7.1.6 Спекание 3D

7.2 Тесты на производительность из набора NASA NPB

Заключение

Литература

Приложение 1. Описание программного интерфейса системы поддержки выполнения DVMH-программ

Инициализация системы поддержки и завершение с ней работы................ Запросы актуализации данных в основной памяти

Объявление актуальности данных в основной памяти

Вспомогательные функции для поддержки DVM-директив

Уничтожение переменных

Сервисные функции для вызова из обработчиков

Функции работы с вычислительными регионами

Функции работы с параллельными циклами и последовательными участками внутри регионов

Введение Актуальность темы В настоящее время большое количество параллельных программ для кластеров разрабатываются с использованием низкоуровневых средств передачи сообщений (MPI [1]). MPI-программы трудно разрабатывать, сопровождать и повторно использовать при создании новых программ.

Данная проблема осложняется тем, что в последнее время появляется много вычислительных кластеров с установленными в их узлах ускорителями. В основном, это графические процессоры. Программисту требуется теперь освоение на достаточном уровне сразу нескольких моделей и языков программирования. Традиционным подходом можно назвать использование технологии MPI для разделения работы между узлами кластера, а затем технологий OpenMP [2] и CUDA [3] или OpenCL [4] для загрузки всех ядер центрального и графического процессоров.

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

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

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

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

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

• разработка алгоритмов распределения вычислений между ЦПУ и ГПУ и алгоритмов управления перемещением данных между • разработка алгоритма распределения подзадач между узлами Постановка задачи Необходимо предложить принципы и алгоритмы отображения DVMпрограмм на кластер с ускорителями, позволящие использовать DVM-языки с минимальным их расширением. При этом исходить из того, что в узлах кластера будут размещаться ускорители разной архитектуры.

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

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

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

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

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

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

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

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

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

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

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

сервис в сети Интернет: поиск новых решений”, сентябрь 2012 г., г.

6. APOS/HOPSA Workshop on Exploiting Heterogeneous HPC Platforms, 7. Международной конференции "Параллельные вычислительные технологии (ПаВТ'2013)", апрель 2013 г., г. Челябинск.

8. Международной суперкомпьютерной конференции “Научный сервис в сети Интернет: все грани параллелизма”, сентябрь 2013 г., Имеется 12 публикаций [6-17], из которых три [10,12,16] – в журналах из списка ВАК.

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

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

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

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

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

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

разработанных c использованием языка Фортран-DVMH.

Автор выражает благодарность всем разработчикам DVM-системы.

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

М.В. Келдыша Крюкова Виктора Алексеевича, которому автор выражает искреннюю признательность.

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

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

Также используется модель односторонних коммуникаций, представителем которой является библиотека SHMEM [18].

Имеются и основанные на директивах высокоуровневые расширения стандартных языков программирования для программирования кластеров, языки Фортран-DVM [5, 19] и Си-DVM [5, 20]. Подобные расширения не являются широко используемыми, однако, представляют интерес как средство упрощения программирования кластеров.

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

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

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

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

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

Во-вторых, более сложная, иерархическая модель параллелизма;

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

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

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

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

1. Организация вычислений, спецификации потоков данных.

2. Управление отгружаемыми данными, актуальностью.

Далее вид всех директив приводится для языка Фортран-DVMH.

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

Например, с использованием CUDA-устройства может быть исполнен любой регион без использования операций ввода/вывода, вызовов внешних процедур, рекурсивных вызовов.

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

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

!DVM$ REGION [clause {, clause}] !DVM$ END REGION Вложенные (статически или динамически) регионы не допускаются.

region_inner – это нуль или более следующих друг за другом конструкций, каждая из которых является одним из нижеследующего:

• Параллельный DVM-цикл. Пространство витков параллельного цикла разделяется в соответствии с заданным в директиве вычислителями, выбранными для данного региона.

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

• Хост-секция. Хост-секция ограничивается специальными директивами:

!DVM$ HOSTSECTION hostsection_inner

!DVM$ END HOSTSECTION

Объявляет специального вида секцию исполнения на ЦПУ.

hostsection_inner – это часть программы с одним входом и одним последовательном режиме. Разрешено использование внутри таких секций директив get_actual. Директивы actual запрещены.

Всякие изменения переменных в этой секции могут пропасть.

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

В качестве clause для вычислительных регионов может быть задано:

1. in(subarray_or_scalar {, subarray_or_scalar}), out(subarray_or_scalar {, subarray_or_scalar}), inout(subarray_or_scalar {, subarray_or_scalar}), local(subarray_or_scalar {, subarray_or_scalar}), inlocal(subarray_or_scalar {, subarray_or_scalar}) Указание направления использования подмассивов и скаляров в регионе. in – по входу в регион нужны актуальные данные. out – в регионе значение переменной изменяется, причем это изменение может быть использовано далее. inout(a) – сокращенная запись одновременно двух указаний: in(a), out(a).

local — в регионе значение переменной изменяется, но это изменение не будет использовано далее. inlocal(a) — сокращенная запись одновременно двух указаний: in(a), local(a).

Если для переменной указано in, и не указано out или local, то считается, что в такую переменную в регионе вообще нет записей и она не меняется в процессе его исполнения.

2. targets(target_name {, target_name}) где target_name это CUDA или HOST Указание списка типов вычислителей, на которых предполагается исполнять регион. Такое указание может быть только одно в директиве региона. Данное указание ограничивает набор типов вычислительных устройств, для использования которых регион будет подготовлен компилятором. Действительное же выполнение региона может происходить только на доступных DVMH-программе ускорителях (или на ЦПУ), количество и типы которых указываются при ее запуске с помощью переменных окружения. Определение конкретных исполнителей региона (из сгенерированы программы региона) производится во время выполнения программы.

3. async Указание возможности асинхронного исполнения региона. При запуске региона в любом режиме (синхронный, асинхронный) ожидание завершения ранее запущенного региона возникает, необходимость изменить данные, используемые этим (ранее запущенным) регионом или необходимость использовать (запись или чтение) данные, изменяемые этим (ранее запущенным) регионом (out, inout, local, inlocal).

Управление не перейдет на следующий за синхронным регионом оператор, пока текущий регион не закончит исполнение.

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

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

полностью (не выделяются подмассивы).

2. Всякая переменная, которая используется на чтение получает 3. Всякая переменная, которая используется на запись получает использования которой не поддается определению, получает 5. Указания local и out в автоматическом режиме не проставляются.

1.1.2 Управление отгружаемыми данными, актуальностью осуществляется в соответствии с указаниями в директиве региона.

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

1. get_actual[(subarray_or_scalar {, subarray_or_scalar})] Делает все необходимые обновления для того, чтобы в основной памяти (памяти ЦПУ) были самые новые данные в указанном подмассиве или скаляре (при этом, возможно, ничего и не параметров все имеющиеся новые данные с ускорителей переписываются в основную память.

2. actual[(subarray_or_scalar {, subarray_or_scalar})] Объявляет тот факт, что указанный подмассив или скаляр самую новую версию имеет в основной памяти (памяти ЦПУ). При этом указанные переменные или элементы массивов, находящиеся в использованием будут по необходимости обновлены. В случае отсутствия параметров все переменные в памяти ускорителей объявляются устаревшими.

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

1. Использование в процессе инкрементального распараллеливания.

2. Использование для поддержки работы с библиотеками внешних функций, в том числе библиотек ввода/вывода.

1.1.3 Пример программы на языке Фортран-DVMH Рассмотрим программу для решения уравнения теплопроводности методом Якоби на языке Фортран-DVMH.

Пример программы на языке Фортран-DVMH

PROGRAM JACH

REAL A(L,L), EPS, MAXEPS, B(L,L) CDVM$ DISTRIBUTE (BLOCK, BLOCK) :: A CDVM$ ALIGN B(I,J) WITH A(I,J) CDVM$ REGION CDVM$ PARALLEL(J,I) ON A(I, J) IF(I.EQ.1.OR.J.EQ.1.OR.I.EQ.L.OR.J.EQ.L)THEN 1 CONTINUE

CDVM$ END REGION

CDVM$ ACTUAL(EPS) CDVM$ REGION CDVM$ PARALLEL(J,I)ON A(I,J), REDUCTION(MAX(EPS)) CDVM$ PARALLEL(J, I) ON B(I, J), SHADOW_RENEW(A)

CDVM$ END REGION

CDVM$ GET_ACTUAL(EPS) CDVM$ GET_ACTUAL(B) Программа на языке Фортран-DVMH представляет из себя программу на языке Фортран, дополненную директивами языка Фортран-DVMH.

Директивы DISTRIBUTE и ALIGN определяют распределение данных, в данном случае равномерное блочное распределение, которое задается для массива A, а для массива B задается его выравнивание на массив A, что означает распределение массива B так же, как и массива A.

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

Параллельные циклы расположены в вычислительных регионах (директивы REGION и END REGION), что приводит к подготовке компилятором выполнения этих циклов с использованием графических процессоров.

В показанном примере используются директивы актуализации (GET_ACTUAL) и объявления актуальности (ACTUAL) для сопряжения регионов с внерегионным пространством. Актуализация использована для переменных EPS и B перед выводом и использованием во внерегионном пространстве, а объявление актуальности использовано для переменной EPS после ее модификации во внерегионном пространстве.

Эта программа может быть выполнена на кластере с графическими процессорами, причем между ускорителями и многоядерными центральными процессорами будут распределены данные и вычисления.

1.2 Обзор высокоуровневых моделей программирования для ускорителей В 2011 году была предложена модель DVMH для программирования кластеров с ускорителями с помощью директив.

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

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

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

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

ориентированность на графические процессоры в части организации параллелизма, управляемого кеширования данных, отсутствия средств синхронизации и программного интерфейса времени выполнения, предназначенных для использования на ускорителе. Для OpenMP 4.0 это неверно и может являться определенным препятствием для его реализации для графических процессоров.

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

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

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

Прямое перемещение данных между ускорителями в стандартах OpenMP 4.0 и OpenACC не предусмотрено, в то время как в DVMH этот функционал имеется благодаря выбранной методике управления перемещениями данных.

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

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

Для написания программ для кластера с ускорителями DVMH предоставляет все средства, а при использовании OpenACC или OpenMP 4. придется добавить использование коммуникационной библиотеки, например, MPI.

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

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

Глава 2. Схема построения компилятора с языка Фортран-DVMH Компилятор с языка Фортран-DVMH является развитием компилятора с языка Фортран-DVM. Компилятор с языка Фортран-DVM является sourceto-source компилятором. Это позволяет:

1. Абстрагироваться от целевой процессорной архитектуры.

пользователем компилятор со стандартного языка Фортран, что пользователя библиотек.

3. Переложить тяжелую работу по оптимизации генерируемого стандартного языка Фортран.

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

Рисунок 1. Схема работы компилятора с языка Фортран-DVMH Анализатор строит структуру исходной программы и дополняет заданные программистом указания о режимах использования данных, для которых есть правила автоматического определения.

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

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

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

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

2.2 Основные функции системы поддержки выполнения DVMH-программ DVMH-программ являются:

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

создание и уничтожение распределенного массива;

параллельную машину;

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

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

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

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

• динамический подбор значений оптимизационных параметров;

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

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

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

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

Глава 3. Алгоритмы учета актуального состояния переменных при выполнении DVMH-программ При программировании графических процессоров применяется методика полного им управления со стороны ЦПУ. Это означает, что программист в первую очередь пишет программу для ЦПУ, из которой уже использует графический процессор.

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

Так как операции загрузки из памяти ЦПУ в память ГПУ и выгрузки из памяти ГПУ в память ЦПУ медленные (примерно в 100 раз медленнее доступа в память ГПУ с ГПУ), то программисту приходится применять иную схему работы с ГПУ, при которой данные по возможности не выгружаются, а остаются в памяти ГПУ до следующего их использования.

3.1 Способы управления перемещениями данных на ускоритель и обратно Есть как минимум два способа управления перемещениями данных на ускоритель и обратно:

1. Ручное копирование.

3.1.1 Ручное копирование копирования, в которых указывает адреса в памяти ГПУ и памяти ЦПУ, копирования (на ГПУ или с ГПУ).

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

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

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

3.1.2 Указание входных и выходных данных для фрагментов При данном способе управления перемещениями данных программист указывает входные и выходные данные для фрагментов программы. Каждый такой фрагмент исполняется либо на ЦПУ, либо на ГПУ. При этом обновления входных данных перед выполнением каждого фрагмента производятся на основании информации о том, на каком устройстве был исполнен последний фрагмент, для которого эти данные были выходными.

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

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

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

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

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

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

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

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

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

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

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

Для манипуляций с состояниями актуальности представителей переменных вводится особый вид функций – PCSn – как отображение из Zn в N U {0,+inf}. Ниже перечислены базовые операции над ними, где I(a) – индикаторная функция, принимающая значение 1 при истинном выражении, данном в качестве аргумента a; 0 – в противном случае:

• Объединение двух PCS. Объединением двух PCS p1 и p2 называется PCS p3 такое, что p3(x) = max(p1(x), p2(x)) • Разность двух PCS. Разностью двух PCS p1 и p2 называется PCS p такое, что p3(x) = I(p1(x)>p2(x))p1(x) • Понижение одного PCS на уровень другого PCS. Понижением одного PCS p1 на уровень другого PCS p2 называется PCS p3 такое, что p3(x) = I(p1(x)0)p2(x) • Горизонтальная разность двух PCS. Горизонтальной разностью PCS p1 и p2 называется PCS p3 такое, что p3(x) = I(p1(x)!=p2(x))p1(x) • Пересечение двух PCS. Пересечением двух PCS p1 и p2 называется PCS p3 такое, что p3(x) = min(p1(x), p2(x)) • Пересечение двух PCS с повышением. Пересечением двух PCS p1 и p2 с повышением называется PCS p3 такое, что p3(x) = I(0 0 такая, что для всех k из диапазона [Kmin,