«Автоматическое отображение Фортран-программ на графический процессор»



жүктеу 480.53 Kb.
бет1/7
Дата19.07.2016
өлшемі480.53 Kb.
  1   2   3   4   5   6   7


Московский Государственный Университет

им. М.В.Ломоносова

Факультет Вычислительной математики и кибернетики

Кафедра Системного программирования

ДИПЛОМНАЯ РАБОТА

Тема: «Автоматическое отображение Фортран-программ на графический процессор»

Выполнил:

Хайминов Алексей Павлович

группа 528

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

д. ф.-м. н., профессор

Крюков Виктор Алексеевич
Москва, 2013

Аннотация


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


Содержание



Аннотация 3

Содержание 4

1 Введение 6

6

1.1 Модели параллельного программирования 8



1.2 Особенности графических ускорителей 10

1.3 Автоматизация распараллеливания программ 12

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

3 Существующие исследования по анализу эффективности 16

3.1 Аналитическая модель с учётом внутреннего параллелизма 16

3.2 Аналитическая модель конвейерного исполнения 16

3.3 Особенности настоящего исследования в сравнении с существующими 17

4 Исследование и построение решения задачи 18

4.1 Входные данные. Система САПФОР. 18

4.2 Обзор модели программы для исполнения на графическом ускорителе. 19

4.3 Алгоритмы 19

4.3.3 Алгоритм базового подсчёта числа инструкций. 19

4.3.4 Алгоритм анализа доступов в глобальную память 20

4.3.5 Алгоритм подсчёта ресурсов, необходимых блоку. 22

4.3.6 Алгоритм анализа выполнения коллективных операций 22

4.3.7 Алгоритм использования кэш-памяти в модели 23

4.3.7 Алгоритм построения вычислительной сетки нитей и блоков. 23

4.3.8 Алгоритм построения вычислительной решётки 24

4.4 Моделирование порядка исполнения блоков 25

5 Прогнозирование выполнения модели 27

5.1 Модель графического ускорителя 27

5.2 Оценка производительности 28

5.2.1 Внешний параллелизм 29

5.2.2 Внутренний параллелизм 30

5.3 Оценка времени исполнения 32

5.3.1 Доминирование задержек обмена с глобальной памятью 33

5.3.2 Доминирование вычислений 33

5.3.3 Недостаточное число активных варпов 33

5.3.4 Затраты на синхронизацию 33

5.4 О построенной оценке эффективности 34

6 Полученные результаты 36

Заключение 40

Литература 41



1 Введение


Исторически так сложилось, что с момента появления ЭВМ одной из их основных функций является выполнение трудоёмких вычислений. Интенсивные вычислительные задачи регулярно возникают в областях квантовой и механической физики, молекулярного моделирования, исследования климата, предсказания погоды, структурной биологии, генетики человека, астрономии, управляемого термоядерного синтеза, исследовании сверхпроводимости, распознавания изображений, распознавания и синтеза речи, криптоанализа и многих других.
В настоящее время для решения подобных задач успешно применяются вычислительные кластеры. Под вычислительным кластером в дальнейшем будем понимать мультикомпьютер, состоящий из множества отдельных компьютеров (узлов), связанных единой коммуникационной системой. Каждый узел имеет свою локальную оперативную память. Коммуникационная система позволяет узлам обмениваться информацией посредством передачи сообщений. Если, дополнительно к этому, на кластере аппаратно или программно-аппаратно реализована распределённая общая память, то программы, выполняющиеся на разных узлах, также могут взаимодействовать через общие переменные. В узлах современного кластера могут использоваться как современные многоядерные процессоры, так и графические ускорители. При этом если все входящие в состав вычислительного кластера узлы имеют одну и ту же архитектуру и производительность, то мы имеем дело с однородным вычислительным кластером. Иначе – с неоднородным.
Очевидно, что для эффективной работы вычислительной системы, следует ­­­наилучшим образом распределить данные и вычисления по узлам, с учётом их производительности и архитектуры. Неоднородность вычислительной системы вносит следующие проблемы:

  • Необходимость учёта различной производительности узлов и соответствующее распределение работы между ними;

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

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

Тем не менее в настоящее время наиболее выгодно показывают себя (с точки зрения отношения производительность/стоимость) неоднородные вычислительные кластеры, в узлах которых используются графические процессоры (GPU). Основные достоинства графических ускорителей – высокая вычислительная мощность и низкое энергопотребление. Неудивительно, что системы, построенные именно с использованием графических процессоров, занимают верхние позиции в списке TOP-500 в последние годы. Графические ускорители имеют другую структуру, в сравнении с традиционными процессорами. Различаются и цели использования. Если обычные центральные процессоры в настоящее время состоят из нескольких ядер, созданных для обработки последовательного набора инструкций, то графические процессоры состоят из сотен и тысяч микроядер, нацеленных на параллельную обработку данных одним алгоритмом.


1.1 Модели параллельного программирования


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


Модель передачи сообщений. MPI.
В модели передачи сообщений параллельная программа представляет собой множество процессов, каждый из которых имеет собственное локальное адресное пространство. Обмен данными и синхронизация осуществляются посредством передачи сообщений. В 1993 году был разработан стандарт MPI (Message Passing Interface).
В числе основных достоинств MPI отмечают:

  • Возможность использования в языках Фортран, Си, Си++;

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

  • Предоставление возможностей для совмещения обменов сообщениями и вычислений;

  • Широкий набор коллективных и редукционных операций, имеющих эффективную реализацию.


Модель параллелизма по данным. HPF.
В модели параллелизма по данным отсутствует понятие процесса и, как следствие, явная передача сообщений или явная синхронизация. В этой модели данные последовательной программы распределяются программистом по процессорам параллельной машины. Ответственность за преобразование последовательной программы в параллельную возлагается на компилятор. Каждый процессор производит вычисления только над теми данными, которые на него распределены (собственные данные). Интересно отметить, что первые шаги к автоматизации параллельного отображения программы на кластер были сделаны в именно HPF: имелись специальные директивы для поддержки распознавания параллелизма [3, 9]. Однако, полностью автоматическое отображение (без участия человека) реализовано не было.

Модель параллелизма по управлению. OpenMP.
Модель возникла применительно к многопроцессорным машинам. Вместо программирования в терминах нитей предлагалось использовать специальные конструкции – параллельные циклы и параллельные секции. Создание, уничтожение нитей, распределение на них витков параллельных циклов или параллельных секций – всё это брал на себя компилятор. Стандартом для этой модели сейчас является интерфейс OpenMP [4];
Гибридная модель параллелизма по управлению с передачей сообщений. MPI+OpenMP.
В этой модели программу можно представить, как систему взаимодействующих MPI-процессов, каждый из которых программируется на OpenMP. Особенно эффективен такой подход в случае наличия в программе двух уровней параллелизма – между подзадачами и внутри подзадачи. Такая ситуация возникает, например, при использовании многообластных (многоблочных) методов решения вычислительных задач. При этом вполне естественным будет реализовать взаимодействие между подзадачами с использованием MPI, а программирование самой подзадачи на OpenMP. Широкое распространение кластеров, имеющих в качестве узлов мультипроцессоры, также подталкивает к использованию гибридного подхода, поскольку использование OpenMP на мультипроцессоре может для некоторых задач дать заметный выигрыш в эффективности.

Модель параллелизма по данным и управлению. DVM.
Эта модель, положенная в основу языков параллельного программирования Фортран-DVM и Си-DVM, объединяет достоинства модели параллелизма по данным и модели параллелизма по управлению. Базирующаяся на этих языках система разработки параллельных программ (DVM) создана в Институте прикладной математики им. М.В. Келдыша РАН.
Особенности DVM-модели:

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

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

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

  • языки параллельного программирования, используемые в DVM представляют из себя стандартные языки последовательного программирования, расширенные спецификациями параллелизма;

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

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


Параллелизм на графических ускорителях. CUDA.
Compute Unified Device Architecture (CUDA) [12] – программная модель, включающая описание вычислительного параллелизма и иерархичной структуры памяти графического ускорителя непосредственно в язык программирования. Графическому процессору отводится роль массивно-параллельного сопроцессора. Основная система, к которой подключен GPU называется термином хост (host), а сам GPU по отношению к хосту называется устройством (device). CUDA-программа задействует как CPU, так и GPU. На CPU выполняется последовательная часть кода и подготовительные стадии для вычислений на ускорителе. Параллельные участки кода могут быть перенесены на GPU, где будут выполняться одновременно множеством нитей (threads). Необходимо отметить, что нить GPU чрезвычайно легковесна, её контекст минимален, регистры распределены заранее. Нити объединяются в группы, называемые варпами (waprs), причём в пределах одного варпа нити выполняются физически одновременно. Размер такой группы строго определён и зависит от архитектуры графического ускорителя. Управление работой варпов производится на аппаратном уровне.

Функция в модели CUDA представляет из себя ядро (kernel), выполняемое в последовательном режиме на CPU (в случае задания соответствующего атрибута) или параллельно на потоковых мультипроцессорах (streaming multiprocessor) графического ускорителя. Стоит отметить, что подобная модель унаследована от архитектуры обработчиков графической информации, где массивы пикселей должны быть обработаны неким универсальным алгоритмом (шейдером). Для лучшего понимания организации параллелизма на графическом ускорителе рассмотрим GPU более подробно.



  1   2   3   4   5   6   7


©dereksiz.org 2016
әкімшілігінің қараңыз

    Басты бет