Фреймворки, поддерживающие многогранную модель
Использование многогранной модели (также называемой моделью многогранника ) в компиляторе требует, чтобы программное обеспечение представляло объекты этой структуры (наборы целочисленных точек в областях различных пространств) и выполняло над ними операции (например, проверку того, является ли набор целочисленными точками в областях различных пространств). пустой).
Более подробную информацию об объектах и операциях в этой модели, а также пример, связывающий модель с компилируемыми программами, можно найти на странице многогранной модели.
Существует множество фреймворков, поддерживающих многогранную модель . Некоторые из этих фреймворков используют одну или несколько библиотек для выполнение полиэдральных операций. Другие, особенно Omega, объединяют все в одном пакете. Некоторые часто используемые библиотеки — это библиотека Omega. [1] (и более поздняя вилка), [2] пиплиб, [3] [4] ПолиЛиб, [5] [6] ЗГЗ, [7] остров , [8] генератор многогранного кода Cloog, [9] [10] и библиотека barvinok для подсчета целочисленных решений. [11] Из этих библиотек PolyLib и PPL в основном ориентированы на рациональные значения, тогда как другие библиотеки ориентированы на целочисленные значения. Многогранный каркас GCC называется графитом. [12] Полли [13] обеспечивает многогранную оптимизацию для LLVM и R-Stream. [14] имел многогранный картограф с ок. 2006.
Общие сильные стороны
[ редактировать ]Многогранные структуры предназначены для поддержки методов компиляторов для анализа и преобразования кода с вложенными циклами, дающих точные результаты для вложений циклов с аффинными границами циклов и индексами («части статического управления» программ). Их можно использовать для представления и обоснования выполнения (итераций) операторов, вместо того, чтобы рассматривать оператор как единый объект, представляющий свойства всех исполнений этого оператора. Многогранные структуры обычно также допускают использование символических выражений.
Многогранные структуры можно использовать для анализа зависимостей для массивов, включая как традиционный анализ псевдонимов, так и более продвинутые методы, такие как анализ потока данных в массивах или идентификация условных зависимостей. Их также можно использовать для представления преобразования кода и предоставления функций для генерации преобразованного кода на языке высокого уровня. Системы преобразования и генерации обычно могут обрабатывать неидеально вложенные циклы.
Пример сравнения многогранных каркасов с предыдущими работами.
[ редактировать ]Чтобы сравнить многогранную модель, основанную на ограничениях, с предыдущими подходами, такими как преобразования отдельных циклов и унимодулярный подход , рассмотрим вопрос о том, можем ли мы распараллелить (выполнить одновременно) итерации следующего надуманного, но простого цикла:
for i := 0 to N do
A(i) := (A(i) + A(N-i))/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...Н). Характеристика этой зависимости, анализ параллелизма и преобразование кода могут быть выполнены с точки зрения экземплярной информации, предоставляемой любой многогранной структурой.
Экземплярный анализ и преобразование позволяют многогранной модели унифицировать дополнительные преобразования (такие как разделение набора индексов, очистка циклов, мозаика, слияние или деление циклов, а также преобразование неидеально вложенных циклов) с теми, которые уже унифицированы унимодулярной структурой (например, цикл перестановка, перекос и обращение идеально вложенных циклов). Это также стимулировало разработку новых преобразований, таких как нарезка пространства итераций Пью и Россера (экземплярная версия нарезки программы; обратите внимание, что код никогда не выпускался вместе с библиотекой Omega).
Более интересный пример
[ редактировать ]Авторы многогранных каркасов исследовали простой одномерный конечно-разностного уравнения теплопроводности, расчет трафарета выраженный следующим псевдокодом :
for t := 0 to T do
for i := 1 to N-1 do
new(i) := (A(i-1) + A(i) + A(i) + A(i+1)) * .25 // explicit forward-difference with R = 0.25
end
for i := 1 to N-1 do
A(i) := new(i)
end
end
Этот кодекс сбивает с толку многие системы трансформации 20-го века. из-за необходимости оптимизировать несовершенное гнездо циклов. Многогранные структуры могут анализировать поток информации между различными выполнениями операторов в гнезде циклов и преобразовывать этот код для одновременного использования масштабируемого параллелизма и масштабируемой локальности .
Краткое изложение двух подходов в этом примере было бы неплохо, но пока ознакомьтесь с отдельными статьями Воннакотта, [15] [16] и Садаяппан и др. [17] а также другие, кто изучал этот код с использованием разных фреймворков, таких как Song и Li. [18]
Различия в изложении или словарном запасе
[ редактировать ]Сравнение работ с использованием разных фреймворков осложняется как техническими различиями (обсуждаемыми позже), так и различиями в словарном запасе и представлении. Ниже приведены примеры для облегчения перевода:
Классификация зависимостей
[ редактировать ]Многогранные структуры поддерживают анализ зависимостей различными способами. помогая уловить влияние символических терминов, выявить условные зависимости, и выделение эффектов псевдонимов памяти. Эффекты псевдонимов памяти, в частности, были описаны двумя способами: многие авторы различают «истинные» зависимости данных (соответствующие реальному потоку информации) от ложных зависимостей, возникающих из-за псевдонимов памяти или ограниченной точности анализа зависимостей.
В публикациях проекта «Омега» используются специальные термины для обозначения конкретных эффектов на анализ. Они сохраняют традиционное различие между потоком, выпуском и антизависимостью. в зависимости от типа доступа к массиву (запись для чтения, запись для записи или чтение для записи соответственно). Зависимости можно независимо классифицировать как основанные на памяти или основанные на значениях --- первый соответствует псевдонимам памяти, и последний не включает зависимости, прерванные промежуточной записью. Тест на зависимость может дать точную или приблизительную информацию. в зависимости от характера анализируемой программы и алгоритмов, используемых в тесте. Наконец, результаты анализа зависимостей будут представлены в виде абстракции зависимости. это обеспечивает определенную степень точности.
Например, «отношения зависимости», полученные с помощью Омега-теста, и «квасты», созданные алгоритмами Фотрие или Майдана и Лама, содержат точную информацию (хотя и в разных формах) об итерациях цикла, участвующих в зависимости. Результаты любого теста можно преобразовать в более традиционную форму «вектора зависимости». но поскольку эта абстракция обеспечивает меньшую точность, большая часть информации о зависимости будет утеряна. Оба метода дают точную информацию для программ с аффинным управлением и индексными выражениями. и должен аппроксимировать для многих программ за пределами этой области (т. е. при наличии неаффинных индексов, таких как индексные массивы). Оригинальная работа Фотрие была сосредоточена на описании истинных зависимостей. будут называться точными зависимостями потока, основанными на стоимости которые в проекте «Омега» . Проект «Омега» также описал использование своих алгоритмов для определения выходных и антизависимых зависимостей на основе значений, хотя квласты Фотрие, по-видимому, можно легко адаптировать и к этому.
Визуализация преобразований и тайлинга
[ редактировать ]Существует много способов создать визуальное изображение процесса преобразования и мозаики итерационного пространства. Некоторые авторы изображают трансформации путем изменения расположения точек на странице, по существу выравнивая картинку с осями координат трансформируемого пространства; на таких диаграммах плитки отображаются в виде выровненных по оси прямоугольников/прямоугольных тел, содержащих итерации. Примеры такого подхода можно найти в публикациях и программном обеспечении трансформационной визуализации Мишель Миллс Страут. [19]
Другие авторы изображают разные преобразования как разные волновые фронты исполнения, которые движутся через точки исходной системы координат под разными углами. На таких диаграммах плитки выглядят как параллелограммы/параллелепипеды. Примеры такого подхода можно найти в искажающих время публикациях Дэвида Г. Воннакотта. [20]
Различия в подходах или статусе реализации
[ редактировать ]Некоторые библиотеки получили более широкое развитие, чем библиотека Omega в начале 2000-х годов, и во многих местах имеют гораздо более сложные алгоритмы. В частности, пользователи сообщили о хороших результатах работы с генератором кода Cloog (как с точки зрения генерируемого кода, так и с точки зрения возможности контролировать компромиссы при генерации кода), а также с алгоритмами подсчета целочисленных решений ( автор Александр Барвинок ) . [21] для работы требуется вершинное описание многогранника, которое не поддерживается в библиотеке Omega).
Есть еще несколько моментов, по которым эти платформы различаются, а именно:
Точность и скорость
[ редактировать ]Целочисленное программирование является NP-полным , и Мэйдан показал, что проблема проверки псевдонимов массива во вложенных циклах с аффинными границами и индексами эквивалентна целочисленному программированию; другие операции, такие как анализ потока данных массива, еще более сложны (алгоритмы библиотеки Omega обрабатывают полный язык арифметики Пресбургера, то есть O(2^2^2^n)). Таким образом, явно нереально ожидать точных и быстрых результатов для произвольных задач псевдонимов массива или потока данных массива, даже в аффинной области. К счастью, многие проблемы попадают в подмножество этой области, где общие алгоритмы могут дать точный ответ за полиномиальное время. [22] [23]
За пределами этой области библиотеки Omega, 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] дает введение в многогранную модель.
- Запись «Омега-тест» в будущей Энциклопедии параллельных вычислений Springer. [29] описывает приложения и алгоритмы библиотеки Omega с указанием основных публикаций проекта Omega, в которых можно найти более подробную информацию. Более ранний вариант этого контента можно найти в форме технического отчета как Технический отчет Хаверфордского колледжа по компьютерным наукам. [30]
- Ссылки на соответствующие библиотеки с открытым исходным кодом приведены в первом абзаце этой статьи.
- Резервуарные лаборатории [31] предоставляет «Jolylib», Java-реализацию Polylib и т. д., которая «обеспечивает улучшенную производительность, стабильность и возможности». Jolylib доступен для коммерческого и академического использования.
Ссылки
[ редактировать ]- ^ «Структуры и алгоритмы анализа и трансформации научных программ» . Cs.umd.edu . Проверено 20 августа 2012 г.
- ^ "Инструменты" . Технология компилятора для оптимизации производительности . Университет Юты . Проверено 20 августа 2012 г.
- ^ Седрик Бастул. «www.PipLib.org — дом параметрического целочисленного программирования» . www.piplib.org . Проверено 4 июня 2014 г.
- ^ Поль Фотрие. Параметрическое целочисленное программирование. 1988 год
- ^ «Полилиб» . Icps.u-strasbg.fr . Проверено 20 августа 2012 г.
- ^ Уайльд, Доран К. (1993). «Библиотека для выполнения многогранных операций» . технический отчет . FTP.irisia.fr.
- ^ «ППЛ» . Бугсенг . Проверено 20 августа 2012 г.
- ^ «isl – Свободный код» . Freshmeat.net . Проверено 20 августа 2012 г.
- ^ Седрик Бастул. "www.CLooG.org, домашняя страница генератора Chunky Loop Generator" . www.cloog.org . Проверено 4 июня 2014 г.
- ^ Седрик Бастул. Генерация кода в многогранной модели проще, чем вы думаете. PACT'13 Международная конференция IEEE по параллельной архитектуре и методам компиляции (2004 г.)
- ^ гви (28 апреля 2007 г.). «барвинок – Фрикод» . Freshmeat.net . Проверено 20 августа 2012 г.
- ^ Себастьян Поп, Альберт Коэн, Седрик Бастул, Сильвен Жирбаль, Пьер Жувело, Жорж-Андре Зильбер и Николя Василаш. Графит: оптимизация цикла на основе многогранной модели для GCC. 4-й саммит разработчиков GCC. Оттава, Канада, июнь 2006 г.
- ^ «Полли — Полиэдральная оптимизация для LLVM» . Polly.llvm.org . Проверено 4 июня 2014 г.
- ^ Бенуа Мейстер, Николя Василаке, Дэвид Уолфорд, Мутху Баскаран, Аллен Люнг и Ричард Летин. Компилятор R-Stream. В Энциклопедии параллельных вычислений, изд. Дэвида Падуи, стр. 1756–1765, Springer, 2011.
- ^ Дэвид Воннакотт. Достижение масштабируемой локальности с искажением времени. Международный журнал параллельного программирования 30.3 (2002 г.)
- ^ Воннакотт, Д. (2000). «Использование отклонения времени для устранения простоя из-за пропускной способности памяти и ограничений сети». Материалы 14-го Международного симпозиума по параллельной и распределенной обработке. ИППДС 2000 . стр. 171–180. дои : 10.1109/IPDPS.2000.845979 . ISBN 0-7695-0574-0 . S2CID 9949169 .
- ^ Удай Бондхугула, Мутху Маникандан Баскаран, Шрирам Кришнамурти, Дж. Рамануджам, Атанас Рунтев, П. Садаяппан. Автоматические преобразования для минимизированной по связи распараллеливания и оптимизации локальности в многогранной модели. CC 2008 - Международная конференция по построению компиляторов
- ^ Юнхун Сон, Чжиюань Ли. Новые методы тайлинга для улучшения временной локальности кэша . Материалы конференции ACM SIGPLAN 1999 г. по разработке и реализации языков программирования (PLDI)
- ^ «Мишель Миллс Страут» . Cs.colostate.edu . Проверено 20 августа 2012 г.
- ^ «Дэвид Г. Воннакотт» . Cs.haverford.edu . Проверено 20 августа 2012 г.
- ^ «Александр Барвинок» . Math.lsa.umich.edu. 16 июня 2012 г. Проверено 20 августа 2012 г.
- ^ Пью, Уильям (1991). «Тест Омега: быстрый и практичный алгоритм целочисленного программирования для анализа зависимостей». Материалы конференции ACM/IEEE 1991 года по суперкомпьютерам — Supercomputing '91 . стр. 4–13. дои : 10.1145/125826.125848 . ISBN 0897914597 . S2CID 3174094 .
- ^ Ситер, Роберт; Воннакотт, Дэвид (2003). «Анализ потока данных полиномиального временного массива». Языки и компиляторы для параллельных вычислений . Конспекты лекций по информатике. Том. 2624. стр. 411–426. дои : 10.1007/3-540-35767-X_27 . ISBN 978-3-540-04029-3 .
- ^ «Фреймворки, поддерживающие многогранную модель» . Lipforge.ens-lyon.fr. [ постоянная мертвая ссылка ]
- ^ Вердулаге, Свен; Сегир, Рашид; Бейлс, Кристоф; Лехнер, Винсент; Брюйнуг, Морис. «Подсчет целочисленных точек в параметрических многогранниках с использованием рациональных функций Барвинка]. В разделе 6.1 обсуждается метод Пью и расщепление» (PDF) . Lirias.kuleuven.be.
- ^ Уэйн Келли, Уильям Пью, Эван Россер, Татьяна Шпейсман. Транзитивное замыкание бесконечных графов и его приложения. Языки и компиляторы для параллельных вычислений, 8-й международный семинар (LCPC 1995)
- ^ Жан-Франсуа Коллар, Рассуждения о трансформации программы, 2003 Springer-Verlag
- ^ Бастул, Седрик. Улучшение локальности данных в программах статического управления (PDF) . icps.u-strasbg.fr (Диссертация).
- ^ «Энциклопедия параллельных вычислений» . Springer.com . Проверено 20 августа 2012 г.
- ^ Воннакотт, Дэвид Г. «Ретроспектива проекта Омега» (PDF) . Отчет Хаверфорда по информационным технологиям за 2010-01 гг . Хаверфордский колледж .
- ^ «Резервуар Лабс, Инк» . Резервуар.com . Проверено 4 июня 2014 г.