Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,737

ОПТИМИЗАЦИЯ ВРЕМЕННОЙ ЛОКАЛЬНОСТИ ДАННЫХ ПРИ АВТОМАТИЧЕСКОМ РАСПАРАЛЛЕЛИВАНИИ ЛИНЕЙНЫХ ПРОГРАММ

Лебедев А.С. 1
1 ФГБОУ ВПО Рыбинский государственный авиационный технический университет имени П.А. Соловьева
Рассматривается задача поиска расписания для линейной программы, оптимизирующего временную локальность данных, как задача многокритериального выбора в условиях полной определенности. Разработан метод, опирающийся на техники модели многогранников, и позволяющий минимизировать задержку использования данных для каждой информационной зависимости, исходя из системы предпочтений лица, принимающего решение (ЛПР) относительно качества оптимизации для каждой информационной зависимости. Система предпочтений ЛПР задается набором весовых коэффициентов для применения техники линейной свертки. Поиск оптимальной по Парето альтернативы расписания сводится к задаче линейного целочисленного программирования. Разработанный метод позволяет точнее осуществлять задание системы предпочтений ЛПР (в особенности для программ со слабой параметризацией или с ослабленной параметризацией при Just-In-Time компиляции) по сравнению с распространенным на момент исследования подходом, реализованным в компиляторе Pluto. Применение метода иллюстрируется примером распараллеливания алгоритма LU-разложения. Параллельный вариант алгоритма, полученный с помощью разработанного метода, показывает лучшее быстродействие по сравнению с результатом работы компилятора Pluto.
автоматическое распараллеливание
модель многогранников
локальность данных
Многокритериальная оптимизация
1. Bastoul C. Code generation in the polyhedral model is easier than you think //Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques. – IEEE Computer Society, 2004. – С. 7-16.
2. Bondhugula U. et al. A practical automatic polyhedral parallelizer and locality optimizer //ACM SIGPLAN Notices. – 2008. – Т. 43. – №. 6. – С. 101-113.
3. Bondhugula U. et al. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model //Compiler Construction. – Springer Berlin Heidelberg, 2008. – С. 132-146.
4. Clauss P. Counting solutions to linear and nonlinear constraints through Ehrhart polynomials: Applications to analyze and transform scientific programs //Proceedings of the 10th international conference on Supercomputing. – ACM, 1996. – С. 278-285.
5. Feautrier P. Parametric integer programming //RAIRO Recherche opérationnelle. – 1988. – Т. 22. – №. 3. – С. 243-268.
6. Feautrier P. Some efficient solutions to the affine scheduling problem. I. One-dimensional time //International journal of parallel programming. – 1992. – Т. 21. – №. 5. – С. 313-347.
7. Feautrier P. Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time //International journal of parallel programming. – 1992. – Т. 21. – №. 6. – С. 389-420.
8. Lengauer C. Loop parallelization in the polytope model //CONCUR'93. – Springer Berlin Heidelberg, 1993. – С. 398-416.
9. Loechner V. PolyLib: A library for manipulating parameterized polyhedra. – 1999. URL: http://icps.u-strasbg.fr/polylib/ (дата обращения: 26.11.14).
10. Makhorin A. GNU linear programming kit //Moscow Aviation Institute, Moscow, Russia. – 2012. URL: http://www.gnu.org/software/glpk (дата обращения: 26.11.14).

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

Большинство вычислительно емких научных и инженерных приложений тратят значительную часть времени исполнения на вложенности циклов, часто отвечающие критериям линейности программ. Модель многогранников [8] предоставляет мощный математический аппарат, упрощающий анализ и преобразование таких программ с целью улучшения быстродействия путем повышения параллелизма и оптимизации локальности данных при вычислениях.

Методы модели многогранников широко используются в статической компиляции. Код, написанный на языке высокого уровня (чаще всего это C или FORTRAN), оптимизируется для параллельного выполнения и компилируется для целевой архитектуры.

Распараллеливание в модели многогранников осуществляется в пять этапов.

1. Анализ зависимостей операций по данным. Рассматриваются потоковые зависимости (чтение после записи), антизависимости (запись после чтения), зависимости через выход (запись после записи).

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

3. Поиск для каждой операции функции размещения, ставящей в соответствие операции индекс виртуального процессора.

4. Разбиение индексного пространства виртуальных процессоров — сопоставление виртуальных процессоров физическим.

5. Генерация параллельной программы по алгоритму [1] в соответствии с пространственно-временным преобразованием, заданным функциями расписания и размещения, и разбиением.

Широко применяемыми на практике стали классические методы поиска расписаний, ориентированные на минимизацию задержки расписания [6, 7] (поиск расписаний с наибольшим параллелизмом), и современный подход [3], ориентированный на минимизацию задержки использования данных (поиск расписаний, обеспечивающих временную локальность данных для более эффективного использования кэшей процессоров).

Подход к оптимизации временной локальности данных, предложенный в работе [3] и реализованный в компиляторе Pluto, демонстрирует эффективность на практике [2]. Однако, метод, его реализующий, не лишен следующего конструктивного недостатка: поскольку задача сводится к поиску лексикографического минимума на многограннике [5], возникает вопрос о порядке следования переменных в целевом векторе, или, в терминах теории принятия решений, вопрос о предпочтениях ЛПР (лица, принимающего решение) относительно качества оптимизации для каждой зависимости по данным. Кроме того, в такой постановке задачи оптимизации невозможно задать одинаковый приоритет различным зависимостям, поскольку невозможно поставить две переменные на одну и ту же позицию в целевом векторе.

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

1. Базовые понятия модели многогранников

Модель многогранников рассматривает класс линейных программ и полагается на поиск расписаний в аффинном виде. Эти программы удовлетворяют следующим ограничениям:

  • единственным типом исполнительного оператора может быть оператор присваивания, правая часть которого является арифметическим выражением;
  • все повторяющиеся операции описываются только с помощью циклов DO языка FORTRAN (либо эквивалентными циклами for языка С); структура вложенности циклов может быть произвольной; шаги изменения параметров циклов всегда равны +1;
  • допускается использование условных и безусловных операторов перехода, передающих управление «вниз» по тексту; не допускаются побочные выходы из циклов;
  • все индексные выражения переменных, границы изменения параметров циклов и условия передачи управления задаются неоднородными формами, линейными по совокупности параметров циклов и внешних переменных программы; все коэффициенты линейных форм являются целыми числами;
  • внешние переменные программы всегда целочисленные; конкретные значения внешних переменных известны только во время работы программы.

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

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

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

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

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

2. Минимизация задержки использования данных в модели многогранников

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

Требования приводят к следующей формулировке задачи многокритериальной оптимизации. Определим множество исходов (совпадающее со множеством альтернатив):

.

Здесь – вектор-столбец из элементов, – скаляр (значения принадлежат множеству ), – аффинная функция расписания для инструкции ().

Показатели качества решения задаются функциями , , которые требуется минимизировать: .

Будем искать эффективный вектор как оптимальное по Парето решение, применив технику линейной свертки: , где – весовые коэффициенты, отражающие предпочтения ЛПР относительно качества оптимизации для каждой зависимости по данным. Такая формулировка позволяет точнее отразить предпочтения ЛПР в силу большей гибкости относительно [3].

Для программ со слабой параметризацией, или в случае Just-In-Time компиляции, когда значения внешних переменных программы становятся известными, становится возможной приоритезация зависимостей на основе частоты возникновения ситуаций доступа к одной ячейке памяти: , где – количество точек с целочисленными координатами внутри многогранника зависимостей , которое может быть вычислено с помощью алгоритма Клаусса [4], реализованного в библиотеке PolyLib [9]. Такая постановка реализует естественную эвристику: ЛПР заинтересовано в наилучшем качестве оптимизации для тех зависимостей, которые чаще возникают.

Для каждого ребра наложим ограничения на функции расписания инструкций и , затем составим систему из всех этих ограничений:

.

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

Лемма Фаркаша. Пусть – непустой многогранник, определённый с помощью аффинных неравенств (граней): . Аффинная форма неотрицательна в любой точке тогда и только тогда, когда она является неотрицательной аффинной комбинацией: . Неотрицательные константы называются множителями Фаркаша.

Для каждой инструкции выписывается шаблон функции расписания, неотрицательной внутри ее домена: где – множители Фаркаша, а неравенств определяют домен , .

Применим лемму Фаркаша для каждого ограничения:

Здесь и – множители Фаркаша, а неравенств определяют многогранник зависимостей , – составной вектор индексов для обеих инструкций в ,. В итоге система ограничений примет вид:

Приравнивание соответственных множителей при компонентах векторов в левых и правых частях ограничений позволяет оставить в системе только множители Фаркаша и переменные-ограничители .

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

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

Решение задачи ЛЦП может быть осуществлено, например, методом ветвей и границ, реализованным в библиотеке GNU Linear Programming Kit [10]. Подстановка значений в соответствующие шаблоны функций расписания для каждой инструкции дает решение задачи поиска расписания .

3. Распараллеливание LU-разложения

Рассмотрим алгоритм LU-разложения с его информационными зависимостями (рисунок 1) и найдем два расписания, используя разработанный метод.

for (int k = 0; k < N; k++) {

for (int j = k + 1; j < N; j++)

A[j * N + k] /= A[k * N + k]; //S1

for (int i = k + 1; i < N; i++)

for (int j = k + 1; j < N; j++)

A[i * N + j] -= A[i * N + k] * A[k * N + j]; //S2

}

Рис. 1. Код LU-разложения на языке C и обобщенный граф зависимостей

Ослабим параметризацию программы, зафиксировав . Изменяя коэффициенты в целевой функции задачи ЛЦП можно управлять задержкой использования данных: например, для функции расписания примут вид и (при этом ), а для получаем и (при этом ; именно такое расписание находит компилятор Pluto [2]).

Эксперименты на четырехъядерном процессоре Intel Core i7 930 показывают ускорение от распараллеливания в 3,96 раза для и , и ускорение в 3,21 раза для и , что свидетельствует об эффективности разработанного метода и целесообразности более точного задания системы предпочтений ЛПР.

Заключение

В ходе исследования была показана необходимость совершенствования способа задания системы предпочтений ЛПР для того, чтобы повысить качество оптимизации временной локальности данных при автоматическом распараллеливании линейных программ. Предложен метод поиска расписания, минимизирующего задержку использования данных для каждой информационной зависимости. Рассмотрение задачи поиска расписания как задачи многокритериального выбора в условиях полной определенности позволяет задать линейную свертку критериев качества, точнее отражающую систему предпочтений ЛПР и потому позволяет находить более удачные (в плане повышения быстродействия синтезированной параллельной программы) расписания, чем распространенный на момент исследования метод [3], опирающийся на технику поиска лексикографического минимума на многограннике.

Работа выполнена в рамках проекта РФФИ №14-37-50316 «Исследование и разработка методов автоматического распараллеливания программ для гетерогенных вычислительных систем и систем с распределенной памятью» при финансовой поддержке Фонда.

Рецензенты:

Хачумов В.М., д.т.н., профессор, зав. лабораторией интеллектуального управления, ФГБУН Институт системного анализа Российской академии наук, г. Москва;

Цирлин А.М., д.т.н., профессор, зам. директора по научной работе ФГБУН Институт программных систем им. А.К. Айламазяна Российской академии наук, Ярославская обл., с. Веськово.


Библиографическая ссылка

Лебедев А.С. ОПТИМИЗАЦИЯ ВРЕМЕННОЙ ЛОКАЛЬНОСТИ ДАННЫХ ПРИ АВТОМАТИЧЕСКОМ РАСПАРАЛЛЕЛИВАНИИ ЛИНЕЙНЫХ ПРОГРАММ // Современные проблемы науки и образования. – 2014. – № 6.;
URL: http://science-education.ru/ru/article/view?id=16255 (дата обращения: 24.08.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252