Каркасы, поддерживающие многогранную модель

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

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

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

Общие сильные стороны [ править ]

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

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

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

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

для i: = от 0 до N делать A (i): = (A (i) + A (Ni)) / 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 до T делать  для i: = от 1 до N-1 делать new (i): = (A (i-1) + A (i) + A (i) + A (i + 1)) * .25 // явная прямая разница с R = 0,25 конец  для i: = от 1 до N-1 делать A (i): = новый (i) конец конец

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

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

Различия в изложении или словарном запасе [ править ]

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

Классификация зависимостей [ править ]

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

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

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

Визуализация преобразований и мозаики [ править ]

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

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

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

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

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

Точность и скорость [ править ]

Целочисленное программирование является NP-полным , и Майдан показал, что проблема проверки алиасинга массивов во вложенных циклах с аффинными границами и индексами эквивалентна целочисленному программированию; другие операции, такие как анализ потока данных массива, еще более сложны (алгоритмы библиотеки 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, так и isl обеспечивают операцию транзитивного закрытия, которая является точной для многих случаев, возникающих в программах с простыми шаблонами зависимости. В других случаях библиотека Omega создает подмножество транзитивного замыкания, а isl создает надмножество. В случае с библиотекой Omega само подмножество может быть приблизительным, что приводит к верхней границе (помеченной) нижней границы (не помеченной) транзитивного замыкания. Обратите внимание, что вычисление точного транзитивного замыкания неразрешимо. ^[26]

См. Также [ править ]

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

Ссылки [ править ]