Каркасы, поддерживающие многогранную модель - Frameworks supporting the polyhedral model

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

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

Есть много каркасы, поддерживающие многогранную модель. Некоторые из этих фреймворков используют одну или несколько библиотек для выполнения многогранных операций. Другие, в частности Omega, объединяют все в одном пакете. Среди наиболее часто используемых библиотек - Omega Library.^[1] (и более поздняя вилка),^[2] пиплиб^[3]^[4] ПолиЛиб,^[5]^[6] PPL,^[7] остров,^[8]генератор многогранного кода Клуга,^[9]^[10] и библиотека barvinok для подсчета целочисленных решений.^[11]Из этих библиотек PolyLib и PPL ориентированы в основном на рациональные значения, тогда как другие библиотеки сосредоточены на целочисленных значениях. gcc называется графитом.^[12] Полли^[13] обеспечивает многогранную оптимизацию для LLVM, и R-Stream^[14] имеет многогранный картограф с ок. 2006 г.

Общие сильные стороны

Структуры многогранников предназначены для поддержки методов компилятора для анализа и преобразования кодов с вложенными циклами, обеспечивая точные результаты для гнезд циклов с аффинными границами цикла и индексами («Статические управляющие части» программ). Их можно использовать для представления и рассуждения о казни (итерации) операторов, вместо того, чтобы рассматривать оператор как единый объект, представляющий свойства всех выполнений этого оператора. Полиэдральные каркасы обычно также позволяют использовать символьные выражения.

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

Пример противопоставления многогранных каркасов предыдущим работам

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

за я: = 0 к N делать      А (я): = (А (я) + А (N-я)) / 2

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

Подходы, которые обрабатывают символические термины, но представляют зависимости через векторы направления или векторы расстояний, будут определять, что цикл i несет зависимость (неизвестного расстояния), поскольку, например, когда N = 10 итерация 0 цикла записывает элемент массива (A (0) ), который будет считан на итерации 10 (как A (10-10)) и считывает элемент массива (A (10-0)), который позже будет перезаписан на итерации 10 (как A (10)). Если все, что мы знаем, это то, что цикл i имеет зависимость, мы снова не сможем безопасно запустить его параллельно.

На самом деле, есть только зависимости от первых N / 2 итераций до последних N / 2, поэтому мы можем выполнить этот цикл как последовательность двух полностью параллельных циклов (от 0 ... N / 2 и от N / 2 + 1 ... N). Характеристика этой зависимости, анализ параллелизма и преобразование кода могут быть выполнены с точки зрения информации по экземплярам, предоставляемой любым многогранным каркасом.

Анализ и преобразование по экземплярам позволяет модели многогранника объединять дополнительные преобразования (такие как разделение набора индексов, отслаивание петель, мозаичное объединение или разделение петель и преобразование несовершенно вложенных петель) с теми, которые уже объединены унимодулярной структурой (например, петля чередование, перекос и разворот идеально вложенных циклов). Это также стимулировало разработку новых преобразований, таких как нарезка пространства итераций Пью и Россера (экземплярная версия нарезки программы; обратите внимание, что код никогда не выпускался с библиотекой Omega).

Более интересный пример

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

за t: = 0 к Т делать    за я: = 1 к N-1 делать        new (i): = (A (i-1) + A (i) + A (i) + A (i + 1)) * .25 // явная прямая разница с R = 0,25 конец    за я: = 1 к N-1 делать        A (i): = новый (i) конецконец

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

Было бы неплохо повторить здесь два подхода к этому примеру, но пока посмотрите отдельные статьи Воннакотта,^[15]^[16] и Sadayappan et al.^[17] а также других, кто изучал этот код с использованием различных фреймворков, таких как Сонг и Ли.^[18]

Различия в презентации или словарном запасе

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

Классификация зависимостей

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

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

Например, «отношения зависимости», полученные с помощью Omega Test, и «квасты», созданные с помощью алгоритмов Feautrier или Maydan и Lam, содержат точную информацию (хотя и в различных формах) об итерациях цикла, участвующих в зависимости. Результаты любой из тестов можно преобразовать в более традиционную форму «вектора зависимости», но поскольку эта абстракция обеспечивает меньшую точность, большая часть информации о зависимости будет потеряна. Оба метода производят точную информацию для программ с аффинным управлением и выражениями нижнего индекса, а также должны быть аппроксимированы для многих программ вне этой области (т. е. при наличии неаффинных индексов, таких как массивы индексов). Первоначальная работа Feautrier была сосредоточена на описании истинный зависимости, которые мы будем называть зависимости расхода на основе точных значений Проект Omega также описал использование своих алгоритмов для основанных на ценности выходных и антизависимостей, хотя квасты Feautrier, по-видимому, можно было бы легко адаптировать и к этому.

Визуализация преобразований и тайлинга

Существует множество способов визуального изображения процесса преобразования и мозаичного размещения итерационного пространства. Некоторые авторы изображают преобразования, изменяя расположение точек на странице, по существу выравнивая изображение с осями координат преобразованного пространства; на таких диаграммах плитки выглядят как выровненные по оси прямоугольники / прямоугольные тела, содержащие итерации. Примеры этого подхода можно найти в публикациях и программном обеспечении для визуализации преобразований Мишель Миллс Строут.^[19]

Другие авторы изображают различные преобразования как разные волновые фронты выполнения, которые перемещаются через точки исходной системы координат под разными углами. На таких диаграммах плитки выглядят как параллелограммы / параллелепипеды. Примеры этого подхода можно найти в смещение во времени публикации Дэвида Г. Воннакотта.^[20]

Различия в подходах или статусе реализации

Некоторые из библиотек претерпели более широкое развитие, чем библиотека Omega в начале 2000-х, и во многих местах имеют гораздо более сложные алгоритмы. В частности, пользователи сообщили о хороших результатах с генератором кода Cloog (как с точки зрения генерируемого кода, так и с точки зрения возможности контролировать компромиссы при генерации кода), а также с алгоритмами подсчета целочисленных решений (Александр Барвинок с^[21] для работы требуется описание вершины многогранника, что не поддерживается в библиотеке Omega).

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

Точность и скорость

Целочисленное программирование является НП-полный, а Майдан показал, что проблема проверки псевдонима массива во вложенных циклах с аффинными границами и индексами эквивалентна целочисленному программированию; другие операции, такие как анализ потока данных массива, еще более сложны (алгоритмы библиотеки Omega обрабатывают весь язык арифметики Пресбургера, то есть O (2 ^ 2 ^ 2 ^ n)). Таким образом, явно нереалистично ожидать точных быстрых результатов для произвольных задач сглаживания массива или потока данных массива, даже в аффинной области. К счастью, многие проблемы попадают в подмножество этой области, где общие алгоритмы могут дать точный ответ за полиномиальное время.^[22]^[23]

Вне этой области Omega Library, piplib и isl делают упор на получение точного результата (за исключением случаев использования неинтерпретированных функциональных символов в Omega), несмотря на высокую сложность. В некоторых случаях, таких как исключение переменных («проекция»), PolyLib и PPL в основном используют алгоритмы для рациональной области и, таким образом, производят аппроксимацию результата для целочисленных переменных. Возможно, это снижает общий опыт работы с библиотекой Omega, в которой незначительное изменение одного коэффициента может вызвать резкое изменение реакции алгоритмов библиотеки.

В Polylib есть несколько операций для получения точных результатов для Z-многогранники (целые точки, ограниченные многогранниками), но на момент написания этой статьи сообщалось о существенных ошибках.^[24] Обратите внимание, что ошибки также существуют в библиотеке Omega, включая использование аппаратных целочисленных типов и случаев полных арифметических алгоритмов Пресбургера, которые не были реализованы в библиотеке. Пользователям, которым нужны точные результаты для целочисленных переменных, может потребоваться осторожность с любой библиотекой.

Техника Барвинока для подсчета целочисленных решений требует описания вершин (и ограничивающих лучей) многогранника, но дает точный ответ, который может быть гораздо более эффективным, чем методы, описанные Пью. Алгоритм Барвинока всегда полиномиален по входному размеру, для фиксированной размерности многогранника и фиксированной степени весов, тогда как «дробление» в алгоритме Пью может расти с увеличением значений коэффициентов.^[25] (и, следовательно, экспоненциально с точки зрения размера входных данных, несмотря на фиксированный размер, если не существует некоторого ограничения на размеры коэффициентов).

Перечисление вершин

Полиэдральные библиотеки, такие как PolyLib и PPL, используют двойное описание многогранников и поэтому естественным образом поддерживаютперечисление вершин на (непараметрических) многогранниках. Библиотека Omega внутренне выполняет перечисление вершин во время вычисления выпуклой оболочки. PolyLib и isl обеспечивают перечисление вершин на параметрических многогранниках, что важно для применения алгоритма Барвинока к параметрическим многогранникам.

Индикация примерного результата

В некоторых частях компилятора приблизительный результат в определенных случаях приемлем. Например, когда анализ зависимости используется для управления преобразованием цикла, обычно допустимо использовать расширенный набор истинных зависимостей - это может предотвратить оптимизацию, но не допускает недопустимые преобразования кода. Когда библиотека Omega дает приблизительный ответ, ответ соответствующим образом отмечается как верхняя граница (например, через «и НЕИЗВЕСТНО») или как нижняя граница (например, через «или НЕИЗВЕСТНО»). Не отмеченные таким образом ответы являются точным описанием наборов целочисленных точек (кроме случаев ошибок в программе).

Работа с нелинейными условиями

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

Операция переходного закрытия

Некоторые виды анализа, такие как анализ Пью и Россера. нарезка итерационного пространства, проще всего выразить в терминах транзитивного замыкания информации о зависимости. И Omega Library, и isl обеспечивают операцию транзитивного закрытия, которая является точной для многих случаев, возникающих в программах с простыми шаблонами зависимости. В других случаях библиотека Omega создает подмножество транзитивного замыкания, в то время как isl создает надмножество. В случае библиотеки Omega само подмножество может быть приблизительным, что приводит к верхней границе (с тегами) нижней границы (не tagged) транзитивного замыкания. Обратите внимание, что вычисление точного транзитивного замыкания неразрешимо.^[26]

Смотрите также

Оптимизация гнезда петель
Жан-Франсуа Коллар Рассуждения о преобразованиях программ,^[27] охватывает часть общей философии этих проектов.
Диссертация Седрика Бастула^[28] дает введение в модель полиэдра.
Запись "Omega Test" в будущей энциклопедии параллельных вычислений Springer^[29] описывает приложения и алгоритмы библиотеки Omega, указывая основные публикации проекта Omega, где можно найти более подробную информацию. Более ранний вариант этого содержания можно найти в форме технического отчета как Отчет о компьютерных науках Хаверфордского колледжа.^[30]
Ссылки на соответствующие библиотеки с открытым исходным кодом приведены в первом абзаце этой статьи.
Резервуарные лаборатории^[31] предоставляет "Jolylib", Java-реализацию Polylib и т.д., которая "обеспечивает улучшенную производительность, стабильность и функции". Джолилиб доступен для коммерческого и академического использования.