Аннотация

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

Введение

Появление вычислительных машин предоставило человечеству новые возможности, упростило, облегчило вычислительный труд. Компьютеры произвели настоящий переворот в вычислительной технике. Важно отметить, что ни одна отрасль не развивалась так стремительно. Развитие компьютеров характеризуется постоянным ростом производительности, снижением стоимости и повышением экономичности. В 1965 году на основании своих наблюдений Гордон Мур выявил зависимость: количество транзисторов интегральной схеме с минимальной стоимостью удваивается каждые 18 месяцев. Однако, в силу атомарной природы вещества и ограниченной скорости света, очевидно, что закон Мура перестанет действовать в обозримом будущем. Впервые проблемы возникли в эпоху Pentium 4 из-за тепловыделения. Производители процессоров избрали другой путь — вместо увеличения тактовой частоты и количества транзисторов на одноядровом кристалле получили распространение процессоры с несколькими ядрами меньшей мощности. По вычислительной способности такое решение превосходит традиционное, а энергопотребление у него меньше. Любопытно заметить, что для большей вычислительной эффективности в современных процессорах, использующих несколько ядер, воплощены варианты параллелизации, которые зародились в 60-е — 80-е гг. прошлого века, как-то: конвейеризация (перекрытие при исполнении последовательных инструкций — инструкционный параллелизм), суперскалярность (возможность выполнять несколько операций за такт — возможна, при наличии нескольких исполнительных блоков на процессоре), векторизация (использование векторных инструкций). Ядра современных многоядерных процессоров имеют возможность передавать друг другу данные через общую память. Это приводит к тому, что можно рассматривать многоядерный процессор как мультипроцессор.

Суперкомпьютеры применяются для решения интенсивных вычислительных задач, возникающих в областях квантовой и механической физики, молекулярного моделирования, исследования климата, предсказания погоды, структурной биологии, генетики человека, астрономии, управляемого термоядерного синтеза, исследовании сверхпроводимости, распознавания изображений, распознавания и синтеза речи, криптоанализа и многих других. В силу очевидных причин, необходимо сделать вычисления на кластере наименее энергозатратными, но наиболее эффективными. Следовательно, необходимо распределить данные и вычисления по узлам кластера, чтобы каждый процессор, на котором она запускается, посчитал часть задачи, а затем вернул полученные ре. Параллелизовать можно поток инструкций (параллелизм по управлению, пример — технология OpenMP [4] ), также можно разделить данные между узлами (параллелизм по данным – подход применённый в HPF [3] ), некоторые системы позволяют осуществлять параллелизм и по данным, и по управлению ( DVM [1] ). Написание программ, эффективно использующих возможности сложной массивно-параллельной архитектуры, - задача нетривиальная и крайне трудоёмкая.

Наиболее перспективными с вычислительной точки зрения являются системы, основанные на кластерах с гетерогенными узлами. Они отвечают наилучшему соотношению затрат и качества. В разных узлах такой системы могут быть использованы разные процессоры или даже графические ускорители. Высокая вычислительная мощность и низкое (в сравнении с обычными CPU) энергопотребление - основные достоинства графических процессоров (GPU). Неудивительно, что системы, построенные именно с использованием графических процессоров, занимают верхние позиции в списке TOP-500 сейчас. Графические ускорители имеют другую структуру, в сравнении с традиционными процессорами. Различаются и цели использования. Если обычные центральные процессоры в настоящее время состоят из нескольких ядер, созданных для обработки последовательного набора инструкций, то графические процессоры состоят из сотен и тысяч микроядер, нацеленных на параллельную обработку данных одним алгоритмом. В известном смысле разработка программ для кластеров, в составе которых присутствуют графические ускорители усложнилась: ведь для программирования вычислений приходится использовать помимо технологий для передачи сообщений, таких как MPI или SHMEM, низкоуровневые технологии CUDA или OpenCL. Одной из альтернатив является использование высокоуровневых моделей и соответствующих им языков программирования (OpenMP, DVM, DVMH, PGI APM, CAF, OpenAcc, UPC) [1]-[8]. Особо выделяются модели, в которых для отображения на параллельные системы в текст программ добавляются спецификации. Эти спецификации оформляются либо в виде комментариев особого вида (справедливо для систем, основанных на языке Фортран), либо в виде директив компилятору (для систем, основанных на языках С/С++). Такой моделью для мультипроцессоров является OpenMP, для кластеров - DVM и HPF. Главное преимущество такого подхода состоит в том, что в последние годы были разработаны высокоуровневые модели с поддержкой вычислений на графических процессорах.

Стоит отметить, что первые шаги к автоматизации параллельного отображения программы на кластер были сделаны в HPF: имелись специальные директивы для поддержки распознавания параллелизма [10]. Однако, полностью автоматическое отображение (без участия человека) реализовано не было. Автоматическое отображение привлекательно тем, что с увеличением объёма параллельной программы становится очень сложно эффективным образом осуществлять отображение вручную. Следовательно, необходимо автоматическим образом собрать характеристики программы (например, наличие зависимостей между витками циклов) и построить схему распараллеливания на кластер, оценить её эффективность. Человек при этом подсказывал бы инструменту, какой из вариантов распараллеливания выбрать, если возникнут сложности.

Альтернативы метода создания параллельной программы - создание новой
программы или распараллеливания старой. Распараллеливание последовательной
программы - с помощью языков (и технологий) параллельного программирования вручную или с помощью систем автоматизированного распараллеливания. Современные системы такого рода поддерживают кластеры с гетерогенными узлами. Одной из таких систем является САПФОР.

Модели для оценки времени выполнения и эффективности

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

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

Недостатком модели [11] является расчёт, который основан в предположение того, что код пользователя написан и скомпилирован под конкретную архитектуру. В частности, примеры в данной работе написаны с использованием CUDA, протестированы для ускорителей с поддержкой CUDA 1.0 и CUDA 1.3. Предполагается, что количество инструкций - параметр модели, пользователь вычисляет сам каким-либо способом по скомпилированому коду.

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

Модель предоставляет высокую точность предсказания тактов работы: ошибка не превосходит 10-13%.

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

В работе [12] программа рассматривается как набор ядровых функций, запускаемых на графическом процессоре независимо друг от друга. На основании моделей [13]-[15], в исследовании была построена собственная модель для оценки времени исполнения ядровых функций, с учётом особенностей архитектуры GPU. Подробно рассмотрены случаи полного перекрытия и отсутствия перекрытия выполнения арифметических операций и доступов к памяти. На практике оба этих случая достаточно редки, т. к. чаще всего можно осуществить хотя бы частичное перекрытие счёта и обменов с памятью. Подход, принятый в данной модели, описывает степень такого совмещения.

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

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

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

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