Система автоматизации распараллеливания программ на промежуточном представлении LLVM

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

Само по себе распараллеливание является трудоемкой задачей. Существуют инструменты, такие как pthreads, OpenMP и другие, которые позволяют разработчикам создавать параллельные программы. При их использовании программист вручную производит разделение кода на независимые составляющие, обеспечивает обмен данными и синхронизацию между ними (подход pthreads), либо указывает компилятору, как и какие участки кода нужно распараллеливать (подход OpenMP). Однако у таких ручных методов есть существенные недостатки. Во-первых, человек может произвести некорректное распараллеливание, внести ошибку в программу, и затем потратить много времени на поиск ошибки, так как известно, что параллельные программы очень сложно отлаживать. Во-вторых, при таком подходе мы упускаем возможность использования аппаратной поддержки. В-третьих, процедура распараллеливания кода в больших проектах является дорогим, долгим и утомительным делом. Это побуждает исследователей искать механизмы автоматического распараллеливания.

Проблемы автоматического распараллеливания

Автоматическое распараллеливание состоит из двух основных подзадач: обнаружения потенциально распараллеливаемых участков кода и их преобразования. При решении этих подзадач необходимо произвести анализ зависимостей и сохранить синтаксическую и семантическую корректность программы при применении преобразований.

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

Статический и динамический анализ

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

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

Полиэдральная модель

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

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

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

1. Данные, над которыми ведется работа, либо скалярны, либо являются массивами скаляров.
2. Ограничения циклов и индексы массивов либо константы, либо представляют собой линейную комбинацию счётчиков внешних циклов и констант.
3. Условия выхода из цикла статичны, внутри циклов нет ветвления.

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

Два подхода к реализации полиэдральной модели в компиляторах

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

В основном такие компиляторы используют абстрактное синтаксическое дерево (AST) программы и основаны на source-to-source трансляции кода. Достоинством такого подхода является то, что после трансляции разработчик может продолжать работу с исходным кодом программы. Однако синтаксис современных языков очень богат и поэтому эффективное обнаружение релевантных участков кода при анализе AST представляет сложную задачу. Большие трудности скрываются в неявных правилах языка программирования. Например, целочисленное переполнение в языке С приводит к тому, что сумма двух положительных чисел a + b может быть меньше, чем a. Другие особенности, такие как макросы препроцессора, алиасы, перегрузка операторов в C++, несут в себе дополнительную сложность.

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

Low Level Virtual Machine

Low Level Virtual Machine (LLVM) — это набор инструментов и библиотек для построения компиляторов. Построенный вокруг языко- и машинно-независимого промежуточного представления, LLVM предоставляет инструменты анализа, оптимизации и кодогенерации. Кроме поддержки генерации на x86, x86_64 и ARM индустриального качества, существует также генерация на язык программирования С, различные GPU ускорители и другое. Существуют основанные на LLVM статические и динамические (Just-In-time, JIT) компиляторы для 9 из 10 самых распространенных языков программирования.

Проект Polly

Polly — это open-source проект, который возник на базе LLVM. Polly применяет полиэдральные оптимизации к промежуточному представлению LLVM, используя плюсы абстрактного подхода. Трансляция языков в промежуточное представление LLVM (LLVM-IR) позволяет использовать методы семантического анализа. Более того, LLVM применяет к промежуточному представлению преобразования, которые приводят представление к каноническому виду. В результате, использование LLVM упрощает работу и два значительные преимущества:

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

Другими словами, Polly независим от языка программирования и прозрачно поддерживает сложные конструкции, такие, как С++ итераторы, арифметика указателей, циклы с goto и другие реализации циклов.

Дизайн Polly

Polly спроектирован как набор фаз анализа и оптимизации. Условно фазы могут быть разделены на три части: Front-end, Middle-end, Back-end.

• Front-end производит подготовительные фазы и транслирует LLVM-IR в полиэдральное представление.
• Middle-end преобразует и оптимизирует представление, осуществляет его экспорт/импорт.
• Back-end транслирует представление обратно в LLVM-IR.

Front-end: семантический анализ LLVM-IR

Первый шаг, необходимый для того, чтобы применить к программе полиэдральные оптимизации, — обнаружение подходящих участков кода и создание для них полиэдрального описания. Эти участки кода называются Static Control Part (SCoP). Именно SCoP-ы являются объектом оптимизаций Polly.

Для обнаружения возможных SCoP-ов в Polly реализован подход, основанный на регионах.

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

Для нахождения SCoP-ов Front-end обнаруживает максимальные регионы, являющиеся SCoP-ами. Поиск начинается с корня дерева регионов. Если регион является SCoP-ом, то он запоминается. В противном случае поиск продолжается по всем дочерним вершинам. Получается набор максимальных канонических регионов — SCoP-ов. Затем эти регионы комбинируются в неканонические. В итоге, мы имеем набор максимальных регионов, являющихся SCoP-ами.

Middle-end: полиэдральная модель

Polly использует классическое описание полиэдра. Для каждого оператора SCoP-а определяется три свойства: домен, расписание и доступ. Домен — это множество значений, которые принимают счётчики объемлющих циклов оператора. Расписание — отображение, которое определяет порядок выполнения оператора на определенной итерации. Доступ — отображение домена на участки памяти. Использование матричного представления позволяет удобно совмещать различные преобразования.

Рассмотрим эти свойства на примере:

for( int i = 0; i < 10; i++ ) array[i] = i;

Домен: { [i]: 0 <= i < 10 }.

Расписание: { [i] -> [i] }. Поскольку витки цикла независимы, расписание { [i] -> [0] } также будет корректным. Такое расписание говорит, что все витки цикла запускаются в начальный момент и происходит их параллельное выполнение.

Доступ: array[i].

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

Back-end: генерация параллельного кода

После оптимизации полиэдральное представление необходимо преобразовать обратно в LLVM-IR. Для этого используется инструмент CLooG. CLooG позволяет преобразовать полиэдральное описание в обобщенное AST дерево. AST затем транслируется в LLVM-IR.

Примеры кода

Для иллюстрации общего подхода в следующих трёх разделах приведём конкретные примеры кода.

Распараллеливание внешнего цикла с помощью OpenMP

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

В Polly реализована фаза анализа зависимостей, что позволяет автоматически обнаруживать параллельные циклы. После того, как параллельный цикл обнаружен, мы можем сгенерировать код с вызовами GNU OpenMP библиотеки libgomp, как если бы пользователь сам вставлял прагмы OpenMP.

Рассмотрим, что нужно сделать для вставки вызовов libgomp в LLVM-IR на примере простого цикла:

for( int i = 0; i <= N; i++ ) A[i] = 1;

Этот цикл распознается как параллельный и заменяется на последовательность следующих вызовов:

• GOMP_parallel_loop_runtime_start
• subfunction
• GOMP_parallel_end

Внутри subfunction генерируется код для тела цикла, за которым следуют вызовы:

• GOMP_loop_runtime_next
• GOMP_loop_end_nowait

Сначала для выполнения этих вставок создаются прототипы каждой функции в LLVM представлении. Код прототипа для GOMP_parallel_end приведён ниже:

Module *M = Builder.GetInsertBlock()−>getParent()−>getParent();  
LLVMContext &Context = Builder.getContext();  
if (!M−>getFunction("GOMP_parallel_end")) {  
  FunctionType *FT = FunctionType::get(Type::getVoidTy(Context), false);  
  Function::Create(FT, Function::ExternalLinkage, "GOMP_parallel_end", M);  
}

Вначале мы получаем глобальный модуль M, где будет сохранена информация о создаваемой функции. FunctionType::get добавляет информацию о типах аргументов и возвращаемого значения. Function::Create создает и вставляет прототип в код. Похожим образом добавляются прототипы для остальных функций.

На следующем шаге вставляются вызовы функций библиотеки. Эти вызовы замещают последовательный код цикла, а тело цикла встраивается в функцию subfunction, которая будет выполняться как OpenMP нить.

Ниже представлен код вызова GOMP_parallel_end:

Function *FN = M->getFunction("GOMP_parallel_end");  
Builder.CreateCall(FN);

Для создания функции subfunction создается новый базовый блок, который привязывается к уже существующим. Код, который создаст пустое тело для функции subfunction:

LLVMContext &Context = FN−>getContext();  
BasicBlock *BB = BasicBlock::Create(Context, "entry", FN);  
BasicBlock *PrevBB = Builder−>GetInsertBlock();  
Builder.SetInsertPoint(BB);  
Builder.CreateRetVoid();  
Builder.SetInsertPoint(PrevBB);

Полный граф потока управления тела subfunction для типичного цикла показан на рисунке сверху. В блоке omp.checkNext мы вызываем функцию GOMP_loop_runtime_next, которая определяет параметры для каждой OpenMP нити. В блоке polly.loop_body содержится последовательный код цикла. На данный момент вышеуказанные вставки могут выполняться только для самого внешнего цикла. Следующим этапом является поддержка вложенных циклов.

Вложенные циклы

Часто вложенному циклу для выполнения требуются значения внешних счётчиков циклов и параметров:

for (int i = 0; i < M; i++)  
  for (int j = 0; j < N; j++)  
    A[j] += M;

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

Локальные массивы

Рассмотрим другую ситуацию:

#define N 10
void foo( ) {
  float A[N];
  for( int i = 0; i < N; i++ )
    A[ i ] = 10;
  return;
}

Сложность здесь следующая. Цикл for является параллельным, поэтому для него сгенерируется функция subfunction. Однако в теле цикле происходит обращение к неглобальному массиву A, который недоступен внутри subfunction. Для разрешения такой ситуации мы воспользуемся тем, что для каждого оператора LLVM-IR предоставляет информацию о базовых адресах используемой им памяти. Адрес A будет передаваться в функцию subfunction, которая уже вычислит корректный адрес, по которому произвести запись.

Ссылки по теме

LLVM, промежуточное представление, Polly, Tobias Grosser.