Category: искусство

glider

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

Начав разбираться с GPGPU, я почти сразу узнал, что, несмотря на высокий пиковый перфоманс современных видеокарт (еще прошлое поколение GPU почти достигло single-precision терафлопа), программер должен весьма потрудиться для того, чтобы достигнуть хотя бы 30-50% теоретической производительности. Этот труд заключается в том, что после написания и отладки код, выражающий вычислительный алгоритм, уродуется до неузнаваемости и неподдерживаемости ручными оптимизациями, которые учитывают все штучки-огонёчки подлежащей хардварной платформы. Вот один из самых безобидных примеров таких оптимизаций: loop unrolling.

Естественный ужос толкнул меня на поиск математических моделей, которые позволяют все такие штуки производить автоматически на этапе компиляции, приближаясь хотя бы к 80-90% перфоманса хардкорного хэндкрафтинга. Конечно, в общем случае такая задача неразрешима и state of the art современной параллелизации склоняется к недетерминированным рантайм оптимизациями через спекуляцию и профилирование.

Впрочем, есть и хорошие новости. Для общего случая задачу решать совсем необязательно, ибо есть несколько удачных особенностей проблемной области. Во-первых, control flow программ для GPU в большинстве случаев статический, а, во-вторых, в значительном проценте вычислительных алгоритмов доступ к памяти происходит весьма регулярно (например, нет динамического диспатча). Эти ограничения на анализируемый алгоритм делают возможным использование полиэдральной модели (polyhedral model).

***

Полиэдральная модель предназначена для анализа и трансформации гнезд циклов (loop nests, т.е. набора возможно вложенных циклов), которые удовлетворяют ограничениям: 1) скалярности (данные, над которыми ведется работа, либо скалярны, либо являются массивами скаляров) , 2) линейности (т.е. границы циклов и индексы массивов либо константны, либо представляют собой линейную комбинацию счетчиков внешних циклов и констант) и 3) статичности (т.е. условия выхода из цикла статичны, внутри циклов нет ветвления). Удивительно, но очень много вычислительных алгоритмов (например, все дифуры, решаемые конечными разностями) сюда подходят.

В такой модели можно рассматривать пространство итераций (iteration space) как набор точек, ограниченный полиэдром (педанты разделяют понятия "политоп" в смысле "ограниченный многогранник" и "полиэдр" в смысле "неограниченный многогранник", но в этом потсе я не буду вдаваться в hair splitting). Таким образом, выполнение гнезда циклов моделируется обходом точек пространства итераций. В силу того, что моделируемый алгоритм удовлетворяет трем ограничениям выше, для каждого обхода можно аналитически и абсолютно детерминированно посчитать разные интересные характеристики - количество и качество вычислительных операций, паттерны доступа к памяти и так далее. Придумав для себя критерий оптимизации в виде функции от этих характеристик, можно перебрать все варианты обходов и найти такой обход, который максимизирует значение этого критерия.

Ниже приведен пример представления несложного гнезда циклов в полиэдральной модели (эта картинка и картинки ниже взяты из работ исследователей Стэнфордского университета - Майкла Вольфа и Моники Лэм: "A Loop Transformation Theory and an Algorithm to Maximize Parallelism" и "A Data Locality Optimizing Algorithm"; сорри за качество картинок, но работам почти 20 лет, отсканированы они хреново, а лучших примеров для введения в полиэдральную модель я не нашел). Несколько пояснений: 1) в примере границы циклов константны, но это не является обязательным условием для представления циклов в полиэдральной модели (см. дальнейшие примеры), 2) в примере рассматривается совершенное гнездо циклов (perfect loop nest), т.е. такое, что все операции производятся только в самом внутреннем цикле гнезда, но и это условие не является обязательным для полиэдральной модели, 3) зависимости между точками пространства итераций обозначаются стрелками (еще раз сорри за качество картинки).

Пример представления цикла в полиэдральной модели

***

Итак, в полиэдральной модели задача оптимизации гнезда циклов заключается в нахождении такого обхода пространства итераций, который сохраняет зависимости по данным (т.е. является "легальным") и максимизирует некоторую целевую функцию (например, степень параллелизма или процент кэш-хита). Это будет задача целочисленного линейного программирования (parametric integer programming, PIP). В общем случае PIP является NP-полной, поэтому надо применять какие-то эвристики по отсечению пространства перебора.

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

А сейчас пример. Вот два способа, которыми можно оптимизировать гнездо циклов на картинке выше. Некоторые пояснения: 1) в ручном труде нет необходимости - ужасные границы циклов и индексы массивов генерятся автоматически из матриц преобразования координат, 2) на первой картинке итерации внутреннего цикла работают с данными, лежащими недалеко друг от друга, что позитивно сказывается на перфомансе памяти, 3) на второй картинке мы, несмотря на неслабые зависимости по данным, все же нашли способ выделить параллелизм, 4) разница между первой и второй картинками всего лишь в матрице трансформации.

Пример вымощения пространства итераций для достижения хорошей локальности данных

Пример вымощения пространства итераций для достижения высокой степени параллелизма

То, что описано выше, было state of the art лет 15 назад, но сейчас разработаны гораздо более интересные штуки, которые позволяют достичь в среднем более хороших результатов оптимизации, например, и параллелизм выщемить, и локальность не упустить.

***

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

Применению фреймворка в контексте GPGPU посвящено несколько работ, из которых больше всего мне нравится "A Compiler Framework for Optimization of Affine Loop Nests for GPGPUs", которая, несмотря на свой полуторагодовалый возраст, покрывает подавляющее большинство современных техник автоматической оптимизации. В этой работе составлены несколько вариантов целевых функций, учитывающих особенности современных GPU, приведены эвристики по их комбинации и отсечению пространства решений.

Впрочем, несмотря на неплохие продвижения в применении полиэдральной модели для GPGPU, остается куча непонятных вопросов: 1) как производить более качественное отсечение пространства решений, не теряя хороших решений, но сохраняя полиномиальное время? 2) как моделировать локальные переменные? 3) как моделировать структуры? Есть надежда, что на эти вопросы удастся найти хорошие ответы, ибо уж очень велик соблазн уменьшить ручной труд, необходимый для оптимизации программ для GPU.