Недавно (27-28 апреля, 2020) состоялся европейский симпозиум по Лиспу.
European Lisp Symposium
https://www.european-lisp-symposium.org/2020/
Видеозаписи докладов: https://www.youtube.com/playlist?list=PLA66mD-6yK8yjlJCI0Ay2f2IvvmB9Ktga
Ниже краткая информация о 3 докладах по околокомпиляторной тематике:
Partial Evaluation Based CPS Transformation: An Implementation Case Study
Описание компилятора для диалекта Лиспа pLisp. В компиляторе используются частичные вычисления и CPS.
Слайды: https://www.european-lisp-symposium.org/static/2020/jayaprakash-slides.pdf
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf
LLVM Code Generation for Open Dylan
Dylan — это диалект Лиспа с Алгол-подобным синтаксисом. В начале 90-х этот язык развивался компанией Apple. В докладе представлено описание генератора кода для Dylan на основе LLVM.
Слайды: https://www.european-lisp-symposium.org/static/2020/housel-slides.pdf
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf
Later Binding: Just in Time Compilation of a Younger Dynamic Programming Language
Краткий анализ компилятора LuaJIT
Видео выступления: https://www.youtube.com/watch?v=FBk5XAEhu2s
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf
#conf #jit #llvm #cps #pe
European Lisp Symposium
https://www.european-lisp-symposium.org/2020/
Видеозаписи докладов: https://www.youtube.com/playlist?list=PLA66mD-6yK8yjlJCI0Ay2f2IvvmB9Ktga
Ниже краткая информация о 3 докладах по околокомпиляторной тематике:
Partial Evaluation Based CPS Transformation: An Implementation Case Study
Описание компилятора для диалекта Лиспа pLisp. В компиляторе используются частичные вычисления и CPS.
Слайды: https://www.european-lisp-symposium.org/static/2020/jayaprakash-slides.pdf
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf
LLVM Code Generation for Open Dylan
Dylan — это диалект Лиспа с Алгол-подобным синтаксисом. В начале 90-х этот язык развивался компанией Apple. В докладе представлено описание генератора кода для Dylan на основе LLVM.
Слайды: https://www.european-lisp-symposium.org/static/2020/housel-slides.pdf
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf
Later Binding: Just in Time Compilation of a Younger Dynamic Programming Language
Краткий анализ компилятора LuaJIT
Видео выступления: https://www.youtube.com/watch?v=FBk5XAEhu2s
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf
#conf #jit #llvm #cps #pe
Распределение регистров и планирование инструкций - важные аспекты реализации бэкенда компилятора. Обе задачи NP-полны и связаны между собой: распределение может внести в код новые инструкции, планирование же меняет инструкции местами. Несмотря на это в популярных компиляторах решаются они, как правило, раздельно и используют эвристические подходы.
Последние два десятилетия много исследований было посвящено точным комбинаторным методам решения тех же самых задач: предложены методы на основе целочисленного программирования, PBQP, программирования в ограничениях и др. Слабость таких подходов - большое время поиска оптимальных решений, что заставляет исследователей упрощать задачу, делая методы неприменимыми в универсальных компиляторах.
Роберто Лозано (Roberto Castaneda Lozano) задался целью разработать одновременно точный и легкий в реализации подход, причем решающий задачи планирования инструкций и распределения регистров совместно. За основу он взял программирование в ограничениях (constraint programming), позволяющее удобно выразить условия обеих задач и для которого существуют мощные решатели.
Проект Unison заменяет три фазы LLVM: предварительное планирование инструкций, распределение регистров и финальное планирование. Распределение проводится глобальное, планирование же локальное - последнее упрощение дает ощутимый эффект при умеренной сложности.
В отличие от предшественников Unison не упрощает задачу распределения. Все практические аспекты проблемы учитываются в решениях: спиллинг, алиасинг (aliasing), рематериализация (rematerialisation), разбиение областей жизни переменных (live range splitting), слияние (coalescing) и др. Программирование в ограничениях позволяет выразить любые проблемы распределения регистров лаконично и просто.
Оптимальность имеет свою цену: поиск решений занимает много времени. Размер компилируемых функций - до 1000 инструкций. Наибольший эффект от Unison был показан на спецпроцессоре Hexagon с длинным машинным словом (VLIW), где важно оптимальное расписание: на некоторых тестах реальное время исполнения снижается на 40%.
Лозано предлагает использовать Unison как инструмент для порождения кода к спецпроцессорам, оценки эффективности эвристических решений, поиска оптимальных решений в отдельных функциях.
Презентация на конференции LLVM (2017): https://www.youtube.com/watch?v=kx64V74Mba0
Обобщающая исследования Лозано диссертация (2018 год): http://kth.diva-portal.org/smash/get/diva2:1232941/FULLTEXT01.pdf
Оценка производительности Unison (2017): https://www.diva-portal.org/smash/get/diva2:1119107/FULLTEXT01.pdf
Сайт проекта: https://unison-code.github.io/
Программирование в ограничениях: https://ru.wikipedia.org/wiki/Программирование_в_ограничениях
Программная статья от именитых исследователей (Nuno P. Lopes и John Regehr) о роли точных методов в будущих компиляторах: https://arxiv.org/pdf/1809.02161.pdf
#registeralloc #instructionscheduling #constraintprogramming #unison #llvm
Последние два десятилетия много исследований было посвящено точным комбинаторным методам решения тех же самых задач: предложены методы на основе целочисленного программирования, PBQP, программирования в ограничениях и др. Слабость таких подходов - большое время поиска оптимальных решений, что заставляет исследователей упрощать задачу, делая методы неприменимыми в универсальных компиляторах.
Роберто Лозано (Roberto Castaneda Lozano) задался целью разработать одновременно точный и легкий в реализации подход, причем решающий задачи планирования инструкций и распределения регистров совместно. За основу он взял программирование в ограничениях (constraint programming), позволяющее удобно выразить условия обеих задач и для которого существуют мощные решатели.
Проект Unison заменяет три фазы LLVM: предварительное планирование инструкций, распределение регистров и финальное планирование. Распределение проводится глобальное, планирование же локальное - последнее упрощение дает ощутимый эффект при умеренной сложности.
В отличие от предшественников Unison не упрощает задачу распределения. Все практические аспекты проблемы учитываются в решениях: спиллинг, алиасинг (aliasing), рематериализация (rematerialisation), разбиение областей жизни переменных (live range splitting), слияние (coalescing) и др. Программирование в ограничениях позволяет выразить любые проблемы распределения регистров лаконично и просто.
Оптимальность имеет свою цену: поиск решений занимает много времени. Размер компилируемых функций - до 1000 инструкций. Наибольший эффект от Unison был показан на спецпроцессоре Hexagon с длинным машинным словом (VLIW), где важно оптимальное расписание: на некоторых тестах реальное время исполнения снижается на 40%.
Лозано предлагает использовать Unison как инструмент для порождения кода к спецпроцессорам, оценки эффективности эвристических решений, поиска оптимальных решений в отдельных функциях.
Презентация на конференции LLVM (2017): https://www.youtube.com/watch?v=kx64V74Mba0
Обобщающая исследования Лозано диссертация (2018 год): http://kth.diva-portal.org/smash/get/diva2:1232941/FULLTEXT01.pdf
Оценка производительности Unison (2017): https://www.diva-portal.org/smash/get/diva2:1119107/FULLTEXT01.pdf
Сайт проекта: https://unison-code.github.io/
Программирование в ограничениях: https://ru.wikipedia.org/wiki/Программирование_в_ограничениях
Программная статья от именитых исследователей (Nuno P. Lopes и John Regehr) о роли точных методов в будущих компиляторах: https://arxiv.org/pdf/1809.02161.pdf
#registeralloc #instructionscheduling #constraintprogramming #unison #llvm
В традиционных алгоритмах распределения регистров на основе задач упаковки в контейнеры или раскраски графов трудно учесть дополнительные ограничения на доступ к регистрам.
Речь идет об архитектурах с нерегулярным доступом к регистрам (register aliasing, ограничения на использование конкретных регистров в командах). И это относится к x86, но в еще большей мере — к DSP-процессорам и другим специализированным архитектурам.
За последние 3 десятилетия исследователи предложили несколько подходов к проблеме, в том числе метод на базе задачи о квадратичном присваивании (quadratic assignment problem, или QAP), верней частном ее случае: partitioned boolean quadratic optimization problem, или PBQP.
Бернард Шольц (Bernhard Scholz) в работе 2002 года сформулировал распределение регистров как задачу PBQP и показал, что метод позволяет моделировать особенности сложных архитектур. PBQP - NP-полная задача, поэтому впоследствии для метода были разработаны эффективные эвристики, делающие время поиска решений приемлемым.
Интересным метод является не только из-за применимости к отдельным архитектурам:
- возможно регулировать время работы решателя, то есть алгоритм становится прогрессивным;
- решатель может, применяя или не применяя эвристику, находить субоптимальные или оптимальные решения;
- алгоритм пытается избегать применения эвристики и в большинстве случаев находит оптимальные решения.
Наилучшие относительно других подходов результаты PBQP показывает именно в нерегулярных архитектурах, ради которых решатель PBQP был реализован сначала в libfirm, после - и в LLVM.
Впоследствии исследования применимости PBQP в распределении регистров и порождении кода вдохновили эксперименты в применении метода, например, к тестированию памяти или методам машинного обучения.
Понятия регулярности и ортогональности архитектур процессоров в классической работе (1981): https://www.cs.auckland.ac.nz/compsci703s1c/resources/Wulf.pdf
Оригинальная публикация, представляющая PBQP (2002): http://www.complang.tuwien.ac.at/scholz/publications/lctes02.ps.gz
Развитие идей, обновленный алгоритм и новая эвристика (2006): https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.131.4551&rep=rep1&type=pdf
Разработчики libfirm о применении к SSA (2011): https://link.springer.com/content/pdf/10.1007/978-3-642-19861-8_4.pdf
Неформальный пост от разработчиков libfirm (2011): https://beza1e1.tuxen.de/articles/pbqp.html
Сама задача: https://en.wikipedia.org/wiki/Quadratic_assignment_problem
Тестирование памяти (2020): https://dl.acm.org/doi/fullHtml/10.1145/3427378
Машинное обучение (2018): https://arxiv.org/pdf/1710.01079.pdf
#pbqp #registeralloc #libfirm #llvm
Речь идет об архитектурах с нерегулярным доступом к регистрам (register aliasing, ограничения на использование конкретных регистров в командах). И это относится к x86, но в еще большей мере — к DSP-процессорам и другим специализированным архитектурам.
За последние 3 десятилетия исследователи предложили несколько подходов к проблеме, в том числе метод на базе задачи о квадратичном присваивании (quadratic assignment problem, или QAP), верней частном ее случае: partitioned boolean quadratic optimization problem, или PBQP.
Бернард Шольц (Bernhard Scholz) в работе 2002 года сформулировал распределение регистров как задачу PBQP и показал, что метод позволяет моделировать особенности сложных архитектур. PBQP - NP-полная задача, поэтому впоследствии для метода были разработаны эффективные эвристики, делающие время поиска решений приемлемым.
Интересным метод является не только из-за применимости к отдельным архитектурам:
- возможно регулировать время работы решателя, то есть алгоритм становится прогрессивным;
- решатель может, применяя или не применяя эвристику, находить субоптимальные или оптимальные решения;
- алгоритм пытается избегать применения эвристики и в большинстве случаев находит оптимальные решения.
Наилучшие относительно других подходов результаты PBQP показывает именно в нерегулярных архитектурах, ради которых решатель PBQP был реализован сначала в libfirm, после - и в LLVM.
Впоследствии исследования применимости PBQP в распределении регистров и порождении кода вдохновили эксперименты в применении метода, например, к тестированию памяти или методам машинного обучения.
Понятия регулярности и ортогональности архитектур процессоров в классической работе (1981): https://www.cs.auckland.ac.nz/compsci703s1c/resources/Wulf.pdf
Оригинальная публикация, представляющая PBQP (2002): http://www.complang.tuwien.ac.at/scholz/publications/lctes02.ps.gz
Развитие идей, обновленный алгоритм и новая эвристика (2006): https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.131.4551&rep=rep1&type=pdf
Разработчики libfirm о применении к SSA (2011): https://link.springer.com/content/pdf/10.1007/978-3-642-19861-8_4.pdf
Неформальный пост от разработчиков libfirm (2011): https://beza1e1.tuxen.de/articles/pbqp.html
Сама задача: https://en.wikipedia.org/wiki/Quadratic_assignment_problem
Тестирование памяти (2020): https://dl.acm.org/doi/fullHtml/10.1145/3427378
Машинное обучение (2018): https://arxiv.org/pdf/1710.01079.pdf
#pbqp #registeralloc #libfirm #llvm
👍1
Представленный в 1969 году компилятор Fortran-H применял множество прежде трудных оптимизаций. Ключом к ним стала новаторская техника статического анализа: использование доминаторов узлов графа потока исполнения програмы.
Доминатором заданного узла называют такой узел, через который проходят все пути от входного узла к заданному. Непосредственные (то есть ближайшие к каждому из узлов) доминаторы образуют дерево доминаторов с корнем во входном узле графа.
Fortran-H показал, что в сочетании с анализом потоков данных отношение доминирования позволяет расширить до глобальной область применения локальных оптимизаций. К примеру, при помощи доминаторов проводилось удаление общих подвыражений: если среди доминаторов текущего узла уже вычислялось какое-либо выражение и ни один из операндов на пути к узлу не менялся, то результат выражения можно не вычислять повторно.
Одной из проблем использованного в Fortran-H метода поиска доминаторов стала высокая алгоритмическая сложность. Алгоритм Пурдома-Мура (Purdom-Moore, по именам разработчиков компилятора) элементарно объясняется и реализуется, но имеет квадратичную сложность.
Более эффективная версия алгоритма сложностью в O(m*log n) будет представлена только через 10 лет в статье 1979 года A Fast Algorithm for Finding Dominators in a Flowgraph за авторством Томаса Ленгауэра (Thomas Lengauer) и Роберта Тарьяна (Robert Tarjan).
Несмотря на наличие эффективного алгоритма доминаторы широко не использовались, пока в знаменитой публикации 1989 года (Efficiently Computing Static Single Assignment Form and the Control Dependence Graph) доминаторы не были использованы для размещения phi-узлов при построении SSA.
На волне обновленного интереса были предложены новые применения доминаторов: глобальная нумерация значений, глобальное планирование инструкций и прочие. Исследователи стали предлагать альтернативные алгоритмы поиска доминаторов, которые, впрочем, широкого распространения не получили, а алгоритм Ленгауэра-Тарьяна (или просто ЛТ) до сих пор широко используется, в том числе в GCC и LLVM.
https://en.wikipedia.org/wiki/Dominator_(graph_theory)
https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf - алгоритм Ленгауэра-Тарьяна (1979)
https://www.researchgate.net/profile/Edward-Lowry/publication/220421196_Object_code_optimization/links/564ca77708aedda4c13432b4/Object-code-optimization.pdf - описание реализации Fortran-H (1969), где впервые формулируется алгоритм Пурдома-Мура.
http://pages.cs.wisc.edu/~fischer/cs701.f08/ssa.pdf - получение SSA (1989)
https://www.doc.ic.ac.uk/~livshits/classes/CO444H/reading/dom14.pdf - предложение Купера по получению доминаторов путем анализа потоков данных (2001)
https://github.com/gcc-mirror/gcc/blob/master/gcc/dominance.c - реализация алгоритма ЛТ в GCC
#dominator #lengauertarjan #fortranh #llvm #gcc
Доминатором заданного узла называют такой узел, через который проходят все пути от входного узла к заданному. Непосредственные (то есть ближайшие к каждому из узлов) доминаторы образуют дерево доминаторов с корнем во входном узле графа.
Fortran-H показал, что в сочетании с анализом потоков данных отношение доминирования позволяет расширить до глобальной область применения локальных оптимизаций. К примеру, при помощи доминаторов проводилось удаление общих подвыражений: если среди доминаторов текущего узла уже вычислялось какое-либо выражение и ни один из операндов на пути к узлу не менялся, то результат выражения можно не вычислять повторно.
Одной из проблем использованного в Fortran-H метода поиска доминаторов стала высокая алгоритмическая сложность. Алгоритм Пурдома-Мура (Purdom-Moore, по именам разработчиков компилятора) элементарно объясняется и реализуется, но имеет квадратичную сложность.
Более эффективная версия алгоритма сложностью в O(m*log n) будет представлена только через 10 лет в статье 1979 года A Fast Algorithm for Finding Dominators in a Flowgraph за авторством Томаса Ленгауэра (Thomas Lengauer) и Роберта Тарьяна (Robert Tarjan).
Несмотря на наличие эффективного алгоритма доминаторы широко не использовались, пока в знаменитой публикации 1989 года (Efficiently Computing Static Single Assignment Form and the Control Dependence Graph) доминаторы не были использованы для размещения phi-узлов при построении SSA.
На волне обновленного интереса были предложены новые применения доминаторов: глобальная нумерация значений, глобальное планирование инструкций и прочие. Исследователи стали предлагать альтернативные алгоритмы поиска доминаторов, которые, впрочем, широкого распространения не получили, а алгоритм Ленгауэра-Тарьяна (или просто ЛТ) до сих пор широко используется, в том числе в GCC и LLVM.
https://en.wikipedia.org/wiki/Dominator_(graph_theory)
https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf - алгоритм Ленгауэра-Тарьяна (1979)
https://www.researchgate.net/profile/Edward-Lowry/publication/220421196_Object_code_optimization/links/564ca77708aedda4c13432b4/Object-code-optimization.pdf - описание реализации Fortran-H (1969), где впервые формулируется алгоритм Пурдома-Мура.
http://pages.cs.wisc.edu/~fischer/cs701.f08/ssa.pdf - получение SSA (1989)
https://www.doc.ic.ac.uk/~livshits/classes/CO444H/reading/dom14.pdf - предложение Купера по получению доминаторов путем анализа потоков данных (2001)
https://github.com/gcc-mirror/gcc/blob/master/gcc/dominance.c - реализация алгоритма ЛТ в GCC
#dominator #lengauertarjan #fortranh #llvm #gcc
📚 Breno Campos, Ferreira Guimarães
"Lazy Evaluation for the Lazy: Automatically Transforming Call-by-Value into Call-by-Need"
Proceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction. February 2023: 239–249
Ленивыми называются такие вычисления, которые программа не производит сразу, а откладывает, пока не потребуется их результат. Если выполнять редкие вычисления лениво, средняя производительность программы может вырасти.
Чтобы понять, какие вычисления выгодно производить лениво, программист делает предположения о сценариях выполнения программы или профилирует её. В языках с поддержкой ленивых вычислений можно просто пометить фрагмент программы как lazy, но во многих, особенно низкоуровневых языках, добиться ленивости сложнее, и это может потребовать существенной модификации кода.
Цель авторов — научить компиляторы находить вычисления, которые предпочтительно сделать ленивыми, не используя аннотирование lazy вручную и даже поддержку ленивости со стороны языка. Для этого они реализовали внутри LLVM специальную profile-guided оптимизацию, делающую вычисление некоторых аргументов функций ленивым. Оптимизация происходит на уровне LLVM IR в SSA форме.
Статья описывает два алгоритма:
1) модификацию Value Slicing, которая строит замыкание для вычисления произвольного значения в SSA IR.
2) Lazification по информации от профилировщика заменяет call-by-value на call-by-need.
Выбор вычислений для lazification и необходимое профилирование программы описаны в более ранней статье:
Chang, Stephen. "Laziness by need." Programming Languages and Systems: 22nd European Symposium on Programming, ESOP 2013
Авторы добились роста производительности программ на C и C++ от 1% до ~10% за счет увеличения размера на ~10%; тесты включают в себя SPEC CPU 2017.
#optimization #profiling #lazy #llvm
"Lazy Evaluation for the Lazy: Automatically Transforming Call-by-Value into Call-by-Need"
Proceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction. February 2023: 239–249
Ленивыми называются такие вычисления, которые программа не производит сразу, а откладывает, пока не потребуется их результат. Если выполнять редкие вычисления лениво, средняя производительность программы может вырасти.
Чтобы понять, какие вычисления выгодно производить лениво, программист делает предположения о сценариях выполнения программы или профилирует её. В языках с поддержкой ленивых вычислений можно просто пометить фрагмент программы как lazy, но во многих, особенно низкоуровневых языках, добиться ленивости сложнее, и это может потребовать существенной модификации кода.
Цель авторов — научить компиляторы находить вычисления, которые предпочтительно сделать ленивыми, не используя аннотирование lazy вручную и даже поддержку ленивости со стороны языка. Для этого они реализовали внутри LLVM специальную profile-guided оптимизацию, делающую вычисление некоторых аргументов функций ленивым. Оптимизация происходит на уровне LLVM IR в SSA форме.
Статья описывает два алгоритма:
1) модификацию Value Slicing, которая строит замыкание для вычисления произвольного значения в SSA IR.
2) Lazification по информации от профилировщика заменяет call-by-value на call-by-need.
Выбор вычислений для lazification и необходимое профилирование программы описаны в более ранней статье:
Chang, Stephen. "Laziness by need." Programming Languages and Systems: 22nd European Symposium on Programming, ESOP 2013
Авторы добились роста производительности программ на C и C++ от 1% до ~10% за счет увеличения размера на ~10%; тесты включают в себя SPEC CPU 2017.
#optimization #profiling #lazy #llvm
👍25
Таким образом, CFM-CS лучше работает для ветвей с похожей структурой, а SEME-fusion предпочтителен в ситуациях SEME-регионов или для сильно различающихся по структуре ветвей.
Так как эти два подхода ортогональны, авторы реализовали специальный проход по модулям в LLVM, применяющий к регионам с ветвлением обе трансформации и выбирающий лучшую.
[1] B. Coutinho, D. Sampaio, F. M. Q. Pereira, and W. Meira Jr. 2011. Divergence Analysis and Optimizations. In 2011 International Conference on Parallel Architectures and Compilation Techniques. 320–329.
[2] Saumya, Charitha, Kirshanthan Sundararajah, and Milind Kulkarni. "DARM: Control-Flow Melding for SIMT Thread Divergence Reduction--Extended Version." arXiv preprint arXiv:2107.05681 (2021).
[3] https://en.wikipedia.org/wiki/Sequence_alignment
[4] Rocha, Rodrigo CO, et al. "HyFM: Function merging for free." Proceedings of the 22nd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems. 2021.
#llvm #function_merging #optimization #branch_merging #code_size_reduction
Так как эти два подхода ортогональны, авторы реализовали специальный проход по модулям в LLVM, применяющий к регионам с ветвлением обе трансформации и выбирающий лучшую.
[1] B. Coutinho, D. Sampaio, F. M. Q. Pereira, and W. Meira Jr. 2011. Divergence Analysis and Optimizations. In 2011 International Conference on Parallel Architectures and Compilation Techniques. 320–329.
[2] Saumya, Charitha, Kirshanthan Sundararajah, and Milind Kulkarni. "DARM: Control-Flow Melding for SIMT Thread Divergence Reduction--Extended Version." arXiv preprint arXiv:2107.05681 (2021).
[3] https://en.wikipedia.org/wiki/Sequence_alignment
[4] Rocha, Rodrigo CO, et al. "HyFM: Function merging for free." Proceedings of the 22nd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems. 2021.
#llvm #function_merging #optimization #branch_merging #code_size_reduction
ResearchGate
(PDF) HyBF: A Hybrid Branch Fusion Strategy for Code Size Reduction
PDF | On Feb 17, 2023, Rodrigo C. O. Rocha and others published HyBF: A Hybrid Branch Fusion Strategy for Code Size Reduction | Find, read and cite all the research you need on ResearchGate
👍11
Я и мой студент, Кирилл Павлов, опубликовали статью "Библиотека llvm2py для анализа промежуточного представления LLVM и её применение в оценке степени распараллеливания линейных участков кода".
Чем может быть интересна работа студента второго курса бакалавриата? Анализ распараллеливания делается для варианта LLVM IR, где линейные участки заданы ярусно-параллельной формой (ЯПФ). Автоматическое построение ЯПФ позволяет узнать минимальное число шагов, за которое неограниченно параллельный LLVM-процессор может выполнить код линейного участка.
В реальных процессорах число параллельно работающих вычислительных элементов конечно. Поэтому важно экономить ресурсы: получить минимальную ширину ЯПФ, при которой достигается минимальное число шагов параллельной LLVM-машины. Так можно предварительно оценить выбор того или иного аппаратного ускорителя или же узнать, какой "шириной" должен обладать проектируемый нами ускоритель. В статье эта задача сводится к задаче программирования в ограничениях и эффективно решается с помощью инструментария Google OR-Tools.
P.S. Сама библиотека llvm2py, предназначенная для создания такого рода статических анализаторов кода LLVM IR, была полностью реализована Кириллом.
#llvm #analysis #solver
Чем может быть интересна работа студента второго курса бакалавриата? Анализ распараллеливания делается для варианта LLVM IR, где линейные участки заданы ярусно-параллельной формой (ЯПФ). Автоматическое построение ЯПФ позволяет узнать минимальное число шагов, за которое неограниченно параллельный LLVM-процессор может выполнить код линейного участка.
В реальных процессорах число параллельно работающих вычислительных элементов конечно. Поэтому важно экономить ресурсы: получить минимальную ширину ЯПФ, при которой достигается минимальное число шагов параллельной LLVM-машины. Так можно предварительно оценить выбор того или иного аппаратного ускорителя или же узнать, какой "шириной" должен обладать проектируемый нами ускоритель. В статье эта задача сводится к задаче программирования в ограничениях и эффективно решается с помощью инструментария Google OR-Tools.
P.S. Сама библиотека llvm2py, предназначенная для создания такого рода статических анализаторов кода LLVM IR, была полностью реализована Кириллом.
#llvm #analysis #solver
👍56