Еще три года назад графические процессорные устройства (Graphical Processing Unit, GPU) рассматривались лишь как видеокарты для ПК, то сейчас отношение к ним изменилось — появились специальные серверные модели GPU, ориентированные на решение вычислительных задач, увеличилась производительность на вычислениях с двойной точностью, возникли системы рекордной производительности, занимающие высшие строки в Top500 . А как писать эффективные программы под такие машины? Стандартный ответ — связка CUDA или OpenCL для программирования GPU и MPI на уровне кластера. Эти инструменты доступны, активно поддерживаются производителями оборудования, под них уже написано много программ, однако есть и недостатки.

CUDA и OpenCL — расширения языка Си, они не сложны для изучения, хотя и являются достаточно низкуровневыми инструментами. С их помощью можно сравнительно быстро реализовать алгоритм для GPU, однако создать оптимизированную под конкретное приложение и конфигурацию версию оказывается значительно сложнее. Все оптимизации потребуется выполнять вручную, что приведет к увеличению размера кода и ухудшению его читаемости. И хотя программы, созданные при помощи OpenCL, будут переносимыми между широким спектром архитектур, производительность при таком переносе не сохранится. Требуются инструменты для программирования GPU более высокого уровня.

Создавать такие инструменты можно разными путями: вводить новый язык программирования; добавлять директивы в уже существующий язык, как делается в модели PGI Accelerator или CAPS HMPP; воспользоваться расширяемыми языками. Расширяемые языки  — языки программирования, синтаксис и семантика которых не фиксированы, а могут быть изменены в зависимости от потребностей программиста. По сравнению с традиционными, расширяемые языки обладают рядом преимуществ: в них проще добавлять новые возможности; они открыты; изучение новых моделей программирования на основе таких языков проще, поскольку требуется изучить лишь сравнительно небольшие по объему расширения; с помощью таких языков легче выполнять тонкую настройку и оптимизацию программ.

Расширяемые языки

Для того чтобы язык был расширяемым, необходимо чтобы в нем присутствовали:

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

Оказывается, что языков, удовлетворяющих этим требованиям, сравнительно немного: Lisp, Nemerle , Seed7, xoc и Stratego. При этом xoc, который предназначен для расширения языка Си, использует отдельный язык Zeta для написания расширений, а Stratego — это язык предметной области для создания преобразователей исходного кода. Nemerle — расширяемый язык, использующий среду. Net.

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

 

Рис. 1. Пример квазицитирования и эквивалентной записи дерева кода при помощи вызова конструкторов классов

 

 

В языке Nemerle для этого используется конструкция <[ ... ]>, например <[ def i = 0 ]> создает дерево, состоящее из объявления переменной i с начальным значением 0. Квазицитирование похоже на создание строковых объектов при строковых константах. На рис. 1 приведен пример квазицитирования. Конструкция интерполяции позволяет подставлять значения переменных в фиксированный шаблон внутри квазицитирования. В Nemerle для этого используются конструкции $(...), если требуется подставить список, например <[ def j = $a + $b ]>. Также в расширяемых языках присутствуют конструкции разбора дерева программы. В языке Nemerle для этого используется оператор match(...) { ... }, аналог switch из языка Си, в качестве веток которого используются конструкции квазицитирования. При этом интерполяция трактуется как объявление новых переменных, которые в случае успешного сопоставления получают значения соответствующих поддеревьев. Например, для оператора сопоставления match(e) {| <[$a + $b]> => ... }, если e содержит дерево <[ 1 + x ]>, в переменную a попадет <[ 1 ]>, а в переменную b <[ x ]>.

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

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

 

Рис. 2. Пример макроса с синтаксическим определением на языке Nemerle

 

Рис. 3. Пример преобразования кода, осуществляемого макросом из рис. 2

 

Исторически первым появился механизм макросов в Лиспе, программа в котором представляется как обычный список и не требует специальных конструкций для работы с деревом программы, поэтому именно в этом языке расширяемое программирование получило наибольшее распространение. Макросы в Nemerle аналогичны таковым в Лиспе. В системе xoc механизм расширений реализован через расширения грамматики и атрибуты дерева разбора. Любое расширение обязательно задает два атрибута: тип синтаксической конструкции и выражение на базовом языке, в которое она преобразуется.

Для расширяемых языков характерна реализация через макросы многих стандартных конструкций. В языке Nemerle все циклы и условные операторы, кроме match, реализованы через макросы, а в Лиспе макросами являются стандартные конструкции циклов и объявления функций.

Как использовать языки?

Для расширяемого языка программирования можно написать конструкции, позволяющие наиболее удобным способом программировать графические процессоры, что и было сделано в рамках проекта NUDA (Nemerle Unified Device Architecture), целью которого является создание расширений языка Nemerle для программирования GPU. В качестве интерфейса взаимодействия с GPU и целевого языка для представления программы используется OpenCL.

Для начала надо реализовать исполнение на GPU подмножества кода на языке Nemerle. При этом должны поддерживаться привычные операторы языка, такие как циклы и ветвления, а также работа с простыми типами данных, структурами и массивами. Код для GPU выносится в отдельные функции, или в ядра NUDA. Каждое ядро отмечается макросом nukernel, который по коду ядра генерирует код на OpenCL и метод-заглушку для вызова ядра на стороне хоста. Перед генерацией кода производится раскрытие всех макросов, за исключением макросов циклов и ветвления. Если внутри ядра требуется вызвать функцию, эта функция должна быть помечена макросом nucode, который сгенерирует для этой функции код на языке OpenCL. Вызов ядра осуществляется при помощи макроса nucall; помимо параметров ядра, ему передается еще и конфигурация решетки потоков, с которой оно запускается.

Чаще всего в качестве ядра для GPU используется тело цикла, поэтому хотелось бы сразу переносить цикл на GPU. В Nemerle это можно реализовать — соответствующий макрос в NUDA называется nuwork. В качестве обязательных параметров он принимает размер блока потоков и на основании текущего контекста и анализа кода тела цикла определяет набор переменных, которые необходимо передать ядру в качестве параметров. Тело ядра формируется из тела цикла, вычисления индексов цикла через глобальный номер потока, а также условия, позволяющего корректно исполнять цикл даже в том случае, когда глобальный размер сетки не делится на размер группы потоков. На место цикла подставляется вызов макроса nucall, осуществляющий вызов сгенерированного ядра.

В принципе можно разрешить использовать в GPU-программах обычные массивы языка Nemerle, но это приводит к высоким накладным расходам — массив требуется копировать в память GPU при каждом вызове ядра, а затем копировать обратно. Поэтому в программах для GPU используются специальные типы-массивы с ленивой синхронизацией между GPU и CPU. Это позволяет, с одной стороны, не загромождать текст программы командами копирования данных, а с другой — избежать накладных расходов на копирование данных. Для таких массивов, как и для обычных массивов в Nemerle, используется управление памятью при помощи сборки мусора. Для выделения памяти под такие массивы существует макрос nunew, который надо применить к обычному оператору выделения памяти.

На рис. 4 слева приведена обычная программа сложения массивов, а справа — аналогичная программа, но выполняющая вычисления на GPU. Получить GPU-программы из обычной достаточно просто — требуется лишь применить макросы к циклам и операциям выделения памяти, при этом объем кода практически не меняется. Программа, написанная с использованием NUDA, занимает менее 20 строк кода. Аналогичная программа, но на чистом языке Си и OpenCL занимает более 100 строк.

Помимо макросов, облегчающих работу с GPU, система расширений NUDA включает также аннотации для преобразования циклов. Аннотации, по сути, являются специальными макросами. Например, аннотация inline применяется к циклу с фиксированным числом итераций и выполняет его полную развертку. Аннотация dmine выполняет глубокую развертку цикла. “Глубокая развертка” означает, что создание нескольких копий тела цикла и перемешивание выполняются не только для самого преобразуемого цикла, но и для вложенных циклов, если они независимы.

 

Рис. 4. Обычная программа сложения массивов (слева) и аналогичная, задействующая ресурсы GPU

 

Эффект

Для чего программисту нужно учить новый язык и осваивать новые библиотеки расширяемых языков? Основной ответ — продуктивность. Имея алгоритм из параллельных циклов, работающих с массивами и записанный на языке Nemerle, достаточно добавить несколько аннотаций, чтобы получить программу для GPU. При этом программа будет исполняться на любом устройстве с поддержкой OpenCL, включая графические процессоры nVidia и AMD, а также процессоры x86. Чтобы добиться того же с помощью только технологий OpenCL или CUDA, потребуется затратить значительно больше ресурсов, которые уйдут не только на написание исходного кода, но и на отладку взаимодействия между хостом и GPU.

Другая причина — производительность созданного кода. На CUDA или OpenCL преобразования циклов потребуется выполнять вручную, причем отдельно для каждой архитектуры. Это долгий и чреватый ошибками процесс, а полученный в результате код трудночитаем и неудобен для сопровождения. С NUDA эту работу можно делать при помощи аннотаций. Например для нескольких ядер можно оптимизироватьации операции  свертки изображений или умножения матриц при помощи аннотаций inline и dmine. Без увеличения размера исходного кода удается добиться повышения производительности в два–пять раз. При этом, если бы те же самые преобразования выполнялись вручную, это привело бы к увеличению кода в разы, а иногда и на порядок, не говоря уже о затратах времени на отладку и подбор оптимальных параметров развертки. Например, универсальная аннотированная программа из семи строк в NUDA умножения транспонированной матрицы на матрицу с двойной точностью выполняется на nVidia Tesla C2050 лишь на 40% медленнее самой быстрой в настоящий момент реализации (CUBLAS 3.2). Аналогичная программа, написанная вручную, заняла бы 70 строк кода. Естественно, для стандартных задач можно один раз вручную написать код, чтобы повысить производительность, но для специфических задач снижение трудозатрат и повышение продуктивности будет очень кстати. Наконец, повышение продуктивности относится и к созданию самих расширений: создавать их при помощи расширяемых языков проще, чем с помощью традиционных инструментов. Вся система NUDA, несмотря на свою функциональность, занимает всего лишь 12 тыс. строк кода, не считая тестов. Это сравнительно немного, например, компилятор языка Nemerle (сборка 9025) занимает около 130 тыс. строк.

***

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

Андрей Адинец (adinetz@gmail.com) — м.н.с. НИВЦ МГУ (Москва).