Работы по практическому применению передовых подходов E-Graphs (дедуктивный синтез программ) и Equality Saturation (решение для проблемы phase ordering).
Особенно интересно, что для серьезных примеров использования взяты области, далекие от традиционных целевых представлений компиляторов. Это показывает, что компиляторные технологии имеют более широкое применение, чем иногда принято думать.
Carpentry Compiler
https://grail.cs.washington.edu/projects/carpentrycompiler/files/CarpentryCompiler.pdf
Synthesizing Structured CAD Models with Equality Saturation and Inverse Transformations
https://jamesrwilcox.com/szalinski.pdf
Для работы с E-Graphs авторами разработана библиотека egg (есть веб-демо).
egg: Easy, Efficient, and Extensible E-graphs
https://arxiv.org/pdf/2004.03082.pdf
https://github.com/mwillsey/egg
#optimization
Особенно интересно, что для серьезных примеров использования взяты области, далекие от традиционных целевых представлений компиляторов. Это показывает, что компиляторные технологии имеют более широкое применение, чем иногда принято думать.
Carpentry Compiler
https://grail.cs.washington.edu/projects/carpentrycompiler/files/CarpentryCompiler.pdf
Synthesizing Structured CAD Models with Equality Saturation and Inverse Transformations
https://jamesrwilcox.com/szalinski.pdf
Для работы с E-Graphs авторами разработана библиотека egg (есть веб-демо).
egg: Easy, Efficient, and Extensible E-graphs
https://arxiv.org/pdf/2004.03082.pdf
https://github.com/mwillsey/egg
#optimization
Основные работы по методу насыщения равенствами (equality saturation)
Denali: A Goal-directed Superoptimizer (в работе описывается применение E-Graphs для задач оптимизации программ)
https://courses.cs.washington.edu/courses/cse501/15sp/papers/joshi.pdf
Equality Saturation: A New Approach to Optimization (вместо E-Graphs используются PEG/E-PEG, поддерживающие управляющие конструкции)
https://www.cs.cornell.edu/~ross/publications/eqsat/
"Доказательство свойств функциональных программ методом насыщения равенствами" (диссертация на русском языке)
https://keldysh.ru/council/1/2017-grechanik/diss.pdf
#optimization #synth
Denali: A Goal-directed Superoptimizer (в работе описывается применение E-Graphs для задач оптимизации программ)
https://courses.cs.washington.edu/courses/cse501/15sp/papers/joshi.pdf
Equality Saturation: A New Approach to Optimization (вместо E-Graphs используются PEG/E-PEG, поддерживающие управляющие конструкции)
https://www.cs.cornell.edu/~ross/publications/eqsat/
"Доказательство свойств функциональных программ методом насыщения равенствами" (диссертация на русском языке)
https://keldysh.ru/council/1/2017-grechanik/diss.pdf
#optimization #synth
A Language for Describing Optimization Strategies
Пример использования стратегического переписывания термов в духе Stratego. В статье демонстрируются оптимизирующие преобразования на Scala, для GPU и других ускорителей.
https://arxiv.org/pdf/2002.02268.pdf
#optimization
Пример использования стратегического переписывания термов в духе Stratego. В статье демонстрируются оптимизирующие преобразования на Scala, для GPU и других ускорителей.
https://arxiv.org/pdf/2002.02268.pdf
#optimization
Использование рекомендательных систем для автонастройки компилятора, с учетом собранной ранее информации. Результаты внушают оптимизм.
A Collaborative Filtering Approach for the Automatic Tuning of Compiler Optimisations
https://arxiv.org/pdf/2005.04092.pdf
#autotuning #machinelearning #compiler #optimization
A Collaborative Filtering Approach for the Automatic Tuning of Compiler Optimisations
https://arxiv.org/pdf/2005.04092.pdf
#autotuning #machinelearning #compiler #optimization
📚 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