Сейчас тема машинного обучения и искусственного интеллекта необычайно популярна, на данный момент благодаря вычислительным мощностям компьютеров идеи и алгоритмы, зародившиеся достаточно давно могут быть воплощены в жизнь и значительно доработаны. Практически каждый день можно прочитать новости о новых достижениях в этой сфере. Причем машинное обучение применяют практически во всех областях…и разработка компиляторов не исключение. Однако область достаточно специфичная и есть свои особенности и сложности в создании «умных» компиляторов. При этом исследований на данную тему достаточно много и ведутся они давно как в академической среде, так и внутри различных компаний.
Где же именно пытаются применить методы машинного обучения при создании компиляторов? И почему до сих пор «умные» компиляторы не стали частью повседневной жизни разработчика?
Начнем с первого вопроса о конкретных вариантах использования машинного обучения. Дело в том, что современные компиляторы представляют собой сложные системы с большим количеством оптимизаций, позволяющих получать более эффективный машинный код. При этом некоторые из оптимизаций и другие задачи, например распределение регистров, являются NP-полными, что вынуждает разработчиков компиляторов использовать эвристические алгоритмы. В результате большинство компиляторов имеют большое количество флагов оптимизаций, позволяющих настроить используемые эвристики. В LLVM практически у каждого прохода есть несколько скрытых опций, позволяющих повлиять на его работу, их можно использовать либо с помощью флага –mllvm при вызове clang, либо в утилите opt. Однако это многообразие флагов скрыто за куда более часто используемыми опциями, которые содержат сразу множество настроек и обычно называются уровнями оптимизации. Для C/C++ компиляторов это известные большинству -O1, -O2, -O3 для оптимизации времени исполнения и -Os для оптимизации размера кода. Но, к сожалению, не всегда в результате получается оптимальный код (знатоки ассемблера могут переписать сгенерированный код лучшим образом), многое зависит от самого исходного кода на языке высокого уровня, архитектуры процессора, особенностей языка и т.д.
Несмотря на то, что на сегодняшний день у современных процессоров достаточное количество оперативной памяти и достаточно высокая производительность, до сих пор существуют области, где производительность приложений, их энергоэффективность и размер машинного кода играют ключевую роль. Примерами таких областей могут служить разработка ПО для встраиваемых систем с ограниченным объемом оперативной памяти, цифровой обработки сигналов, систем реального времени и т.п. Поэтому в случаях, когда нужно получать высокопроизводительный машинный код для достаточно крупных систем, подбор правильных опций компиляции, дающих наилучший результат, является важной задачей. К тому же и проблема худшего времени выполнения (WCET) никуда не исчезла, когда в системах реального времени нужно вычислять и минимизировать по возможности время исполнения конкретной задачи на платформе. До сих пор программисты, работающие с системами с ограниченным объемом оперативной памяти, не могут полагаться полностью на компиляторы, и часто самостоятельно оптимизируют сгенерированный машинный код.
Человеку тяжело предугадать, какие оптимизации дадут хороший результат, а какие могут привести к регрессиям, потому что для этого нужно хорошо разбираться в тонкостях примененных эвристических алгоритмов, хорошо знать структуру и проходы используемого компилятора, и к тому же полностью знать код компилируемой программы, что в современном процессе разработки приложений невозможно. В итоге выявление наилучших параметров компиляции программы для человека становится задачей полного перебора различных комбинаций опций и замеров производительности и размеров кода.
К тому же, существует ограничение в виде единицы компиляции, с которой можно работать и для которой можно выбирать опции. Так для C/C++ это пока файл, который может содержать много кода, который, возможно, было бы полезно оптимизировать по-разному, но на данный момент это невозможно. Поэтому «умный» компилятор, который бы можно было бы обучать, а затем получать хорошо оптимизированный для самых разных случаев код, является мечтой для некоторых разработчиков.
Естественно, проблема автоматизированного выбора опций компиляции уже долгие годы интересует исследователей. Одним из наиболее известных проектов является разработка Г. Фурсина и исследователей из его команды MILEPOST GCC, который является версией компилятора gcc, способный сам выбирать оптимизационные проходы на основе предыдущего обучения на полученной выборке данных. В данной работе использовался набор из 55 характеристик для решения задачи и достаточно простая модель, построенная на идеи распространения хороших решений на основе алгоритма К ближайших соседей. Именно данная разработка показала, что настройка оптимизационных проходов может приводить к получению кода, который в два раза быстрее, чем код, полученный с помощью стандартной опции максимальной оптимизации -O3.
Также существуют исследования Г. Пехименко и А.Д. Браун для IBM’s TPO (Toronto Portable Optimizer). Их основной задачей являлся подбор эвристически выбираемых значений при оптимизациях и самого набора трансформаций кода. Для реализации была использована логистическая регрессия, которая позволяла производить эффективные настройки штрафов для более быстрого обучения. Классификатор строили в Matlab. Для каждого прохода рассчитывалась вероятность использования, и он применялся, если она составляла более 50%. В качестве результирующей характеристики, которую в данном исследовании пытались уменьшить, являлось статическое время компиляции.
Непосредственным подбором опций компиляции сразу для всей программы для минимизации времени выполнения, времени компиляции, размера кода и энергопотребления занимался А.Асхари. Для этого были использованы cTuning Framework и Collective Mind Framework, разработанные Г. Фурсиным и А. Лохмотовым (также разработка на GitHub).
Также существуют исследования М. Стефенсона и С. Амарасинге подбора оптимизаций для отдельных особенно важных алгоритмов (распределение регистров, DATA PREFETCHING, HYPERBLOCK FORMATION). Для каждой функции использовались соответственно свои характеристики. Для решения применялся генетический алгоритм. Тестирование разработанного продукта проводилось на Open Research Compiler (ORC).
Также существует проект MAGEEC (Machine Guided Energy Efficient Compiler), цели которого несколько отличны. Разработанная инфраструктура использует машинное обучение для выбора оптимизаций необходимых для генерации кода с максимальной энергоэффективностью для высокопроизводительных вычислительных систем. MAGEEC предназначен как для работы с gcc, так и с LLVM. Данный компилятор является частью более крупного проекта TSERO (Total Software Energy Reporting and Optimization).
Одним из исследований, напрямую связанным с LLVM, является LLVMTuner, программный продукт, разрабатываемый в Иллинойсском университете И. Ченом и В. Адве. В 2017 году был представлен доклад, описывающий имеющиеся на тот момент результаты. В данной работе производилась оптимизация отдельных «горячих» циклов. Данный фреймворк предназначен для автоматизированной настройки крупных программ. LLVMTuner работает на промежуточном коде LLVM IR, использует профилирование для идентификации «горячих» циклов, а затем автоматически настраивает эвристики для них. Основное внимание уделяется циклам на верхнем уровне. Выбранные циклы и любые функции вызова переносятся в отдельный модуль, который и подвергается в дальнейшем нужным оптимизациям. Данное решение позволяет получить улучшение производительности на больших программах.
Однако пока нет широко применяющегося компилятора, самостоятельно настраивающего эвристики оптимизирующих проходов. В чем же проблема? Как известно, эффективность применения методов машинного обучения и качество полученных моделей зависит от правильного выбора признаков и качества данных для обучения (несмотря на существование алгоритмов менее чувствительных к «зашумленным» данным). Не зная структуры и алгоритмов, используемых в компиляторе, подобрать полный и достаточный набор характеристик для обучения непросто, хотя и существуют вполне понятные и логичные, например, размер цикла, количество выходов из цикла и т.д. Поэтому разрабатывать универсальное решение, подходящее для множества компиляторов сразу, сложно, да и не факт, что вообще возможно. К тому же вполне вероятно, что это и не требуется.
Так как разработка компиляторов должна быть эффективна и выполнима в достаточно короткие сроки, то естественно даже крупные компании разрабатывают свои промышленные компиляторы на базе готовых решений. Большинство современных решений можно разделить на две категории: выполняемые на виртуальных машинах, например JVM – JIT компиляторы, и компиляторы, построенные на основе LLVM, системе, реализующей виртуальную машину с RISC-подобными инструкциями – статические и динамические компиляторы. Существуют, конечно, еще собственные решения компаний, но они становятся все менее конкурентоспособны из-за отсутствия большого сообщества, занимающегося развитием применяемых в них технологий. В результате на сегодняшний день многие крупные компании, такие как Google, Apple, Adobe, ARM используют LLVM для разработки собственных решений. Конечно, основным компилятором для C/C++ остается gcc, для других языков существуют иные решения, но все равно, если, например, будет найдено решение для LLVM это уже покроет приличную часть существующих на данный момент компиляторов.
Также большой проблемой становится сам сбор характеристик для обучения, так как многопроходные компиляторы сильно преобразуют промежуточное представление, и характеристики, собранные на первоначальном этапе, не вполне релевантны для поздних оптимизаций компилятора, эти характеристики могут измениться с большой вероятностью. Характеристики, к тому же, имеет смысл собирать отдельно для разного типа элементов: модулей, циклов, базовых блоков, так как оптимизации обычно предназначены для изменения конкретного типа элемента, в LLVM даже по такому признаку разделены проходы.
Но, во-первых, встает вопрос идентификации элементов, для которых нужно собирать характеристики. Способов рассчитать уникальные идентификаторы, которые можно сохранить во время всех оптимизаций, можно предложить множество, например:
Однако нужно правильно сохранять эти идентификаторы во время преобразований, когда элементы могут сливаться в один, разделяться, создаваться новые и удаляться исходные, что не является простой задачей.
Во-вторых, сложно в принципе оценить границы исходных циклов, базовых блоков и т.п., написанных в исходном коде, на уже преобразованном IR. Например, из-за многоэтапной генерации машинного кода, принятого в LLVM, информация о машинных базовых блоках теряется после генерации кода на основе машинных инструкций в AsmPrinter. А соответственно теряется и информация об идентификаторах базовых блоков и циклов, для которых и измеряется например смещение от начала функции, поэтому при данном способе только на этапе генерации машинного кода по инструкциям можно получить смещение в виде количества байт. Однако на последующих этапах генерации машинного кода при работе с машинными фрагментами в него могут добавляться различные выравнивания, которые меняют размер учтённых ранее инструкций, и также добавляются nop-инструкции. За счет этого для базовых блоков находящихся в конце больших функций погрешность вычислений может оказаться очень большой, вплоть до полного смещения на другой блок/цикл. И хотя еще часть преобразований на поздних этапах можно отследить и учесть, гарантий по точности измерений это не даст, так как размер инструкций может меняться вплоть до линкера.
Как видно, достаточно сложным и трудоемким получается даже сбор признаков, на основе которых нужно проводить обучение, и которые в дальнейшем, вероятно, станут входным набором для обученной модели для принятия решений. И какого-то очевидного решения у данных проблем нет, что затрудняет уже непосредственную работу, связанную с машинным обучением и привлечением большого количества людей из-за отсутствия достаточных датасетов. Ну а типичные сложности поиска решений задач машинного обучения, выбора моделей, методов, определения правильного поднабора признаков при большом их количестве и т.д. существуют и в данном случае. О них знает практически каждый, кто сталкивался с машинным обучением и чего-то уникального и специфичного именно для компиляторов здесь, пожалуй, нет.
Сложно предугадать, когда же «умные» компиляторы получат широкое распространение. У современных компиляторов существуют и другие проблемы, которые данным способом решить вряд ли получится, и которые на данный момент, наверное, приоритетнее. Однако компиляторы уже стали значительно интеллектуальнее, чем были на заре своего появления, и этот процесс будет продолжаться, хотя, возможно, несколько медленнее, чем хотелось бы большинству разработчиков.
Где же именно пытаются применить методы машинного обучения при создании компиляторов? И почему до сих пор «умные» компиляторы не стали частью повседневной жизни разработчика?
Варианты применения машинного обучения при разработке компиляторов
Начнем с первого вопроса о конкретных вариантах использования машинного обучения. Дело в том, что современные компиляторы представляют собой сложные системы с большим количеством оптимизаций, позволяющих получать более эффективный машинный код. При этом некоторые из оптимизаций и другие задачи, например распределение регистров, являются NP-полными, что вынуждает разработчиков компиляторов использовать эвристические алгоритмы. В результате большинство компиляторов имеют большое количество флагов оптимизаций, позволяющих настроить используемые эвристики. В LLVM практически у каждого прохода есть несколько скрытых опций, позволяющих повлиять на его работу, их можно использовать либо с помощью флага –mllvm при вызове clang, либо в утилите opt. Однако это многообразие флагов скрыто за куда более часто используемыми опциями, которые содержат сразу множество настроек и обычно называются уровнями оптимизации. Для C/C++ компиляторов это известные большинству -O1, -O2, -O3 для оптимизации времени исполнения и -Os для оптимизации размера кода. Но, к сожалению, не всегда в результате получается оптимальный код (знатоки ассемблера могут переписать сгенерированный код лучшим образом), многое зависит от самого исходного кода на языке высокого уровня, архитектуры процессора, особенностей языка и т.д.
Несмотря на то, что на сегодняшний день у современных процессоров достаточное количество оперативной памяти и достаточно высокая производительность, до сих пор существуют области, где производительность приложений, их энергоэффективность и размер машинного кода играют ключевую роль. Примерами таких областей могут служить разработка ПО для встраиваемых систем с ограниченным объемом оперативной памяти, цифровой обработки сигналов, систем реального времени и т.п. Поэтому в случаях, когда нужно получать высокопроизводительный машинный код для достаточно крупных систем, подбор правильных опций компиляции, дающих наилучший результат, является важной задачей. К тому же и проблема худшего времени выполнения (WCET) никуда не исчезла, когда в системах реального времени нужно вычислять и минимизировать по возможности время исполнения конкретной задачи на платформе. До сих пор программисты, работающие с системами с ограниченным объемом оперативной памяти, не могут полагаться полностью на компиляторы, и часто самостоятельно оптимизируют сгенерированный машинный код.
Человеку тяжело предугадать, какие оптимизации дадут хороший результат, а какие могут привести к регрессиям, потому что для этого нужно хорошо разбираться в тонкостях примененных эвристических алгоритмов, хорошо знать структуру и проходы используемого компилятора, и к тому же полностью знать код компилируемой программы, что в современном процессе разработки приложений невозможно. В итоге выявление наилучших параметров компиляции программы для человека становится задачей полного перебора различных комбинаций опций и замеров производительности и размеров кода.
К тому же, существует ограничение в виде единицы компиляции, с которой можно работать и для которой можно выбирать опции. Так для C/C++ это пока файл, который может содержать много кода, который, возможно, было бы полезно оптимизировать по-разному, но на данный момент это невозможно. Поэтому «умный» компилятор, который бы можно было бы обучать, а затем получать хорошо оптимизированный для самых разных случаев код, является мечтой для некоторых разработчиков.
Существующие исследования и решения
Естественно, проблема автоматизированного выбора опций компиляции уже долгие годы интересует исследователей. Одним из наиболее известных проектов является разработка Г. Фурсина и исследователей из его команды MILEPOST GCC, который является версией компилятора gcc, способный сам выбирать оптимизационные проходы на основе предыдущего обучения на полученной выборке данных. В данной работе использовался набор из 55 характеристик для решения задачи и достаточно простая модель, построенная на идеи распространения хороших решений на основе алгоритма К ближайших соседей. Именно данная разработка показала, что настройка оптимизационных проходов может приводить к получению кода, который в два раза быстрее, чем код, полученный с помощью стандартной опции максимальной оптимизации -O3.
Также существуют исследования Г. Пехименко и А.Д. Браун для IBM’s TPO (Toronto Portable Optimizer). Их основной задачей являлся подбор эвристически выбираемых значений при оптимизациях и самого набора трансформаций кода. Для реализации была использована логистическая регрессия, которая позволяла производить эффективные настройки штрафов для более быстрого обучения. Классификатор строили в Matlab. Для каждого прохода рассчитывалась вероятность использования, и он применялся, если она составляла более 50%. В качестве результирующей характеристики, которую в данном исследовании пытались уменьшить, являлось статическое время компиляции.
Непосредственным подбором опций компиляции сразу для всей программы для минимизации времени выполнения, времени компиляции, размера кода и энергопотребления занимался А.Асхари. Для этого были использованы cTuning Framework и Collective Mind Framework, разработанные Г. Фурсиным и А. Лохмотовым (также разработка на GitHub).
Также существуют исследования М. Стефенсона и С. Амарасинге подбора оптимизаций для отдельных особенно важных алгоритмов (распределение регистров, DATA PREFETCHING, HYPERBLOCK FORMATION). Для каждой функции использовались соответственно свои характеристики. Для решения применялся генетический алгоритм. Тестирование разработанного продукта проводилось на Open Research Compiler (ORC).
Также существует проект MAGEEC (Machine Guided Energy Efficient Compiler), цели которого несколько отличны. Разработанная инфраструктура использует машинное обучение для выбора оптимизаций необходимых для генерации кода с максимальной энергоэффективностью для высокопроизводительных вычислительных систем. MAGEEC предназначен как для работы с gcc, так и с LLVM. Данный компилятор является частью более крупного проекта TSERO (Total Software Energy Reporting and Optimization).
Одним из исследований, напрямую связанным с LLVM, является LLVMTuner, программный продукт, разрабатываемый в Иллинойсском университете И. Ченом и В. Адве. В 2017 году был представлен доклад, описывающий имеющиеся на тот момент результаты. В данной работе производилась оптимизация отдельных «горячих» циклов. Данный фреймворк предназначен для автоматизированной настройки крупных программ. LLVMTuner работает на промежуточном коде LLVM IR, использует профилирование для идентификации «горячих» циклов, а затем автоматически настраивает эвристики для них. Основное внимание уделяется циклам на верхнем уровне. Выбранные циклы и любые функции вызова переносятся в отдельный модуль, который и подвергается в дальнейшем нужным оптимизациям. Данное решение позволяет получить улучшение производительности на больших программах.
Существующие проблемы
Однако пока нет широко применяющегося компилятора, самостоятельно настраивающего эвристики оптимизирующих проходов. В чем же проблема? Как известно, эффективность применения методов машинного обучения и качество полученных моделей зависит от правильного выбора признаков и качества данных для обучения (несмотря на существование алгоритмов менее чувствительных к «зашумленным» данным). Не зная структуры и алгоритмов, используемых в компиляторе, подобрать полный и достаточный набор характеристик для обучения непросто, хотя и существуют вполне понятные и логичные, например, размер цикла, количество выходов из цикла и т.д. Поэтому разрабатывать универсальное решение, подходящее для множества компиляторов сразу, сложно, да и не факт, что вообще возможно. К тому же вполне вероятно, что это и не требуется.
Так как разработка компиляторов должна быть эффективна и выполнима в достаточно короткие сроки, то естественно даже крупные компании разрабатывают свои промышленные компиляторы на базе готовых решений. Большинство современных решений можно разделить на две категории: выполняемые на виртуальных машинах, например JVM – JIT компиляторы, и компиляторы, построенные на основе LLVM, системе, реализующей виртуальную машину с RISC-подобными инструкциями – статические и динамические компиляторы. Существуют, конечно, еще собственные решения компаний, но они становятся все менее конкурентоспособны из-за отсутствия большого сообщества, занимающегося развитием применяемых в них технологий. В результате на сегодняшний день многие крупные компании, такие как Google, Apple, Adobe, ARM используют LLVM для разработки собственных решений. Конечно, основным компилятором для C/C++ остается gcc, для других языков существуют иные решения, но все равно, если, например, будет найдено решение для LLVM это уже покроет приличную часть существующих на данный момент компиляторов.
Также большой проблемой становится сам сбор характеристик для обучения, так как многопроходные компиляторы сильно преобразуют промежуточное представление, и характеристики, собранные на первоначальном этапе, не вполне релевантны для поздних оптимизаций компилятора, эти характеристики могут измениться с большой вероятностью. Характеристики, к тому же, имеет смысл собирать отдельно для разного типа элементов: модулей, циклов, базовых блоков, так как оптимизации обычно предназначены для изменения конкретного типа элемента, в LLVM даже по такому признаку разделены проходы.
Но, во-первых, встает вопрос идентификации элементов, для которых нужно собирать характеристики. Способов рассчитать уникальные идентификаторы, которые можно сохранить во время всех оптимизаций, можно предложить множество, например:
- хэш на основе AST во фронтенде
- уникальные числа, присваиваемые при синтаксическом анализе кода во фронтенде
- 64-битного числа, генерируемые на основе дуг в CFG (control-flow graph) с помощью контрольной суммы (по аналогии с PGO (Profile-guided optimization) в LLVM)
Однако нужно правильно сохранять эти идентификаторы во время преобразований, когда элементы могут сливаться в один, разделяться, создаваться новые и удаляться исходные, что не является простой задачей.
Во-вторых, сложно в принципе оценить границы исходных циклов, базовых блоков и т.п., написанных в исходном коде, на уже преобразованном IR. Например, из-за многоэтапной генерации машинного кода, принятого в LLVM, информация о машинных базовых блоках теряется после генерации кода на основе машинных инструкций в AsmPrinter. А соответственно теряется и информация об идентификаторах базовых блоков и циклов, для которых и измеряется например смещение от начала функции, поэтому при данном способе только на этапе генерации машинного кода по инструкциям можно получить смещение в виде количества байт. Однако на последующих этапах генерации машинного кода при работе с машинными фрагментами в него могут добавляться различные выравнивания, которые меняют размер учтённых ранее инструкций, и также добавляются nop-инструкции. За счет этого для базовых блоков находящихся в конце больших функций погрешность вычислений может оказаться очень большой, вплоть до полного смещения на другой блок/цикл. И хотя еще часть преобразований на поздних этапах можно отследить и учесть, гарантий по точности измерений это не даст, так как размер инструкций может меняться вплоть до линкера.
Как видно, достаточно сложным и трудоемким получается даже сбор признаков, на основе которых нужно проводить обучение, и которые в дальнейшем, вероятно, станут входным набором для обученной модели для принятия решений. И какого-то очевидного решения у данных проблем нет, что затрудняет уже непосредственную работу, связанную с машинным обучением и привлечением большого количества людей из-за отсутствия достаточных датасетов. Ну а типичные сложности поиска решений задач машинного обучения, выбора моделей, методов, определения правильного поднабора признаков при большом их количестве и т.д. существуют и в данном случае. О них знает практически каждый, кто сталкивался с машинным обучением и чего-то уникального и специфичного именно для компиляторов здесь, пожалуй, нет.
Сложно предугадать, когда же «умные» компиляторы получат широкое распространение. У современных компиляторов существуют и другие проблемы, которые данным способом решить вряд ли получится, и которые на данный момент, наверное, приоритетнее. Однако компиляторы уже стали значительно интеллектуальнее, чем были на заре своего появления, и этот процесс будет продолжаться, хотя, возможно, несколько медленнее, чем хотелось бы большинству разработчиков.
