В данном разделе будет описана методика переноса кода на графические ускорители.
В некоторых случаях нет необходимости (или даже вредно с точки зрения общей производительности) полностью переносить выполнение программы с классического процессора на ускоритель: некоторые части программы могут использовать специфический способ работы с памятью, который неэффективно реализуется на графической архитектуре. Поэтому методика позволит переносить только часть кода на ускоритель вычислений.
В тоже время не будет рассмотрено распаралленивание одной и той же работы между графическим и классическим процессорами — с нашей точки зрения это в большинстве случаев не целесообразно из-за значительно более высокой производительности графических ускорителей вычислений.
Изолированные стадии программыВ рамках данной методики важное значение имеет понятие стадии или этапа (stage). Под изолированной стадией программы будем понимать часть программы (например, процедуру или отдельный цикл), про которую полностью известно (в момент компиляции) какие данные эта стадия использует (читает или пишет).
Такую стадию можно автоматическим образом выполнить на любом вычислительном устройстве с любой организацией памяти: все необходимые данные известны и из можно перенести на нужное вычислительное устройство (например, классический процессор или графический ускоритель вычислений), исполнить стадию на этом устройстве и перенести все данные обратно.
Понятие изолированной стадии можно применять как к последовательной программе, так и к программе, реализованной на системе параллельного программирования. В параллельном случае необходимо дополнительно потребовать, чтобы в изолированной стадии отсутствовали (явные или неявные) синхронизации и передача данных между процессом, исполняющим данную стадию и другими процессами (которые могут параллельной исполнять как ту же стадию, так и другой код). В общем случае несколько экземпляров этой части программы могут исполняются одновременно и независимо на нескольких устройствах. Без ограничения общности можно считать, что любая программа логически представляется в виде нескольких стадий и возможных обменов между стадиями.
Одна из главных целей данной библиотеки — автоматизация организации межстадийных обменов и минимизация их интенсивности как по числу синхронизаций, так и по количеству передаваемых данных.
Предлагаемая методика заключается в том, что пользователь должен явно разбить свою программу на изолированные стадии и для каждой стадии описать, какие глобальные данные используются и какие модифицируются в процессе ее исполнения. Затем пользователь просто перечисляет эти стадии в порядке порядке их исполнения с указанием того, на каком типе устройства должна исполняться каждая стадия. Остальную работу берет на себя библиотека, а именно — осуществляет минимально необходимые обмены данными между стадиями.
Коммуникационные шаблоны и изолированные стадииЕсли применить методы, описанные в разделе Коммуникационные шаблоны, для всех циклов программы, то она окажется разбита на отдельные стадии-циклы. Каждый шаблон задает, какие данные необходимы для изолированного исполнения стадии.
Для исполнения стадии на графическом ускорителе вычислений лишь необходимо для каждой стадии предоставить код для ускорителя. Это может быть как отдельный код, который компилируется специализированным образом. А может быть специализированный язык программирования, который по одному и тому же коду построит бинарный код как для классического процессора, так и для ускорителя вычислений.
Например, можно использовать абстрактный интерфейсный класс Stage на языке C++, который описывает код, который можно исполнить на классическом процессоре (функция runOnHost), и код, который можно исполнить на ускорителе вычислений (функция runOnHost):
class Stage {
public:
virtual void runOnHost() = 0;
virtual void runOnDevice() = 0;
};
Указание, на каком вычислительном устройстве проводить вычисления может задаваться как в момент создания стадия, так и в момент его вызова. Вызывается стадия с помощью вызова, например,
void runStage (Stage *);
Класс Stage кроме описания функций хранит описание необходимых данных.
Представление единиц обменаВ рамках данного подхода необходимо уметь четко выделять единицы обмена — подмножества глобальных данных, с которыми производятся операции в рамках каждой стадии. Чтобы была возможность указать, что некоторый кусок данных обрабатывается (читается и/или модифицируется) в процессе исполнения стадии. Тогда реализация библиотеки сможет подкачивать те и только те данные, которые требуются для исполнения текущей стадии и были модифицированы ранее.
Возможна реализация таких кусков данных в виде абстрактного интерфейсного класса SharedDatum на языке C++:
class SharedDatum {
public:
virtual void copyToDevice() = 0;
virtual void copyFromDevice() = 0;
};
Функция copyToDevice копирует данные на ускоритель вычислений, функция copyFromDevice — с ускорителя.
Подразумевается, что каждый тип разделяемого куска данных должен быть описан в виде класса, наследующего SharedDatum. Здесь не накладывается ограничений на вид этой области памяти — в простых случаях это может быть сплошной массив, но могут быть и более сложные — например, какие-нибудь разреженные структуры данных. Кроме того, описываемые области могут пересекаться. В любом случае реализация методов копирования должна учитывать эти особенности: агрегировать разреженные данные, агрегировать соседние области (например, два лежащих подряд сплошных массива) в рамках одной передачи, выяснять необходимость копирования данных, лежащих на пересечении нескольких областей.
Необходимо отметить, как и в случае с распараллеливанием на распределенной памяти с помощью шаблонов, перемещение данных между ускорителем вычислений и классическим процессором не обязано происходить строго между стадий. Более эффективно совмещать передачу данных и вычисления. Если зависимости по данным позволяют, то более эффективно начинать передачу данный как только они будут готовы, не дожидаясь стадии, на которой они будут использованы.
Проверка корректности арифметики на ускорителе CUDAОтдельной проблемой является проверка корректности распараллеливания. Для контроля корректности распараллеливания (как на графических ускорителях, так и на множестве узлов вычислительной системе) было бы идеально иметь побитовое совпадение результатов работы распараллеленной программы и программы, исполняемой на (одном) стандартном процессоре.
Этому подходу, однако, препятствуют особенности вычислений с плавающей запятой, проводимых на ускорителе, а именно:- Графические ускорители фирмы Nvidia поддерживают вычисления с плавающей запятой с двойной точностью (64 бита), только начиная с CUDA версии 2.0. Предыдущие версии ускорителей могут проводить вычисления с плавающей запятой лишь одинарной точности (32 бита).
- Операции над числами с плавающей запятой не являются ассоциативными, что может приводить к изменению результата работы программы при ее распараллеливании вследствие возможного изменения порядка выполнения операций.
- Ускорители фирмы Nvidia поддерживают операцию FMA (Fused Multiply-Add — вычисление выражения (X*Y+Z) с тем же темпом выдачи, что просто умножение или просто сложение), и компилятор CUDA довольно агрессивно оптимизирует код путем использования FMA. При этом FMA делает округление результата, не округляя промежуточные значения, что приводит к неэквивалентности операции FMA и соответствующей ей композиции операций сложения и умножения. Подавляющее большинство современных универсальных процессоров такую операцию не поддерживает. Поэтому при вычислении выражения (X×Y+Z) на стандартном процессоре будет сделано две операции округления, и результат может (и в большинстве случаев будет) отличаться от результата, полученного на ускорителе.
- Результат работы стандартных математических функций, реализуемых в библиотеке (таких как log, exp, pow, sin и т.д.), не обязан совпадать при вычислении на ускорителе и на стандартном процессоре, так как математические библиотеки для этих устройств различны и могут, вообще говоря, использовать разные алгоритмы.
Отметим, что использование на стандартном процессоре инструкций из набора x87 (использующих расширенную 80-битную арифметику) также приведет к расхождению результатов работы. Однако в большинстве современных (64-битных) систем по умолчанию используются инструкции из набора sse (или более старших), удовлетворяющие стандарту выполнения операций с плавающей запятой IEEE 754, а x87-инструкции не задействуются.
Учитывая приведенные особенности, проводить проверку корректности переноса частей алгоритма на GPGPU путем побитового сравнения результатов все-таки возможно. Для этого, во-первых, следует использовать устройства с архитектурой CUDA 2.0 или старше, что дает двойную точность.
Во-вторых, операция редукции по неассоциативной операции (например, сложение или умножение с плавающей запятой) , результат которой, вообще говоря, зависит от порядка вычислений, может быть переписана таким образом, чтобы последовательность вычислений была детерминирована. Для этого придется упорядочивать редуцируемый набор значений. Конечно, это вносит дополнительную косвенность в метод проверки результатов; однако заметим, что данная проблема не является специфичной для ускорителей — она имеет место при распараллеливании на любой аппаратуре, включая стандартные многоядерные процессоры или многоузловые кластеры.
Для борьбы с расхождением результатов вычисления стандартных математических функций на универсальных процессорах и графических ускорителях предлагается использовать переносимую библиотеку математических функций, реализованную самостоятельно. В Centaur имеется возможность подключить математическую библиотеку, свободно-распространяемую в рамках проекта OSLib.
Итак, единственной проблемой, требующей решения для обеспечения побитового совпадения результатов, остается инструкция FMA, которая используется графическими ускорителями, и эта проблема наиболее неприятна, поскольку требует модификации исходных кодов — для компилятора с языка CUDA-C (в отличие от CUDA-Fortran) отсутствует опция, запрещающая генерировать использование этой инструкции. Единственным способом, запрещающим применение FMA, является использование специальных функций компилятора языка CUDA-C: __dadd_rn(x,y) для сложения и __dmul_rn(x,y) для умножения, которые компилятор не сливает в одну инструкцию. Так как компилятор для CUDA принимает на вход тексты не на С, а на С++, то для облегчения применения этих специальных функций можно реализовать С++-класс Double_rn, переопределяющий соответствующим образом арифметические операции и автоматически конструирующийся из значений типа double, а также приводящийся к ним обратно. В результате, используя в программе тип Double_rn вместо double либо оборачивая значения типа double в конструктор Double_rn, можно добиться того, что инструкция FMA использоваться не будет.
Таким образом, все проблемы, ведущие к расхождению результатов вычислений с плавающей запятой могут быть преодолены, что приводит к возможности побитового сравнения результатов работы на ускорителе и на стандартном процессоре.
ЗаключениеРазбитая на стадии программа становится вполне пригодной для распараллеливания на графических ускорителях CUDA. Корректно реализованная стадия уже содержит код для своего исполнения на CUDA, а копирование данных в память ускорителя и обратно должно осуществляться автоматически средствами библиотеки. Степень параллелизма, конечно, зависит от самой задачи и реализации конкретной стадии. Например, для задач вычислительной механики характерны стадии, состоящие из одного или нескольких циклов с независимыми витками. Поэтому может быть запущено множество CUDA-нитей, исполняющих виток цикла со своим значением параметра. Из-за ресурсных ограничений устройства нити могут запускаться не все сразу, а несколькими последовательными пачками. В любом случае, если разбиение программы на стадии проведено хорошо, удается извлечь почти весь параллелизм задачи, почти не прилагая дополнительных усилий. |