На пути к светлому будущему «умных» компиляторов

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

    Где же именно пытаются применить методы машинного обучения при создании компиляторов? И почему до сих пор «умные» компиляторы не стали частью повседневной жизни разработчика?

    Варианты применения машинного обучения при разработке компиляторов


    Начнем с первого вопроса о конкретных вариантах использования машинного обучения. Дело в том, что современные компиляторы представляют собой сложные системы с большим количеством оптимизаций, позволяющих получать более эффективный машинный код. При этом некоторые из оптимизаций и другие задачи, например распределение регистров, являются 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-инструкции. За счет этого для базовых блоков находящихся в конце больших функций погрешность вычислений может оказаться очень большой, вплоть до полного смещения на другой блок/цикл. И хотя еще часть преобразований на поздних этапах можно отследить и учесть, гарантий по точности измерений это не даст, так как размер инструкций может меняться вплоть до линкера.



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

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

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 12

      +1
      Подбор ключей и эвристик, это полезно, но душа хочет интеллектуальной трансляции.
      Современный компилятор слишком алгоритмическая вещь, трансляция строится в основном на правилах переписывания. Конечно, есть более сложные техники, при распределении регистров применяется раскраска графов… Но между собой оптимизации взаимодействуют плохо, (по крайней мере, так было, когда я этим серьёзно занимался), при всём при этом качество кода того же gcc приятно удивляет.
      ИИ тут и приткнуться особо негде, нужен принципиально новый компилятор, возможно даже новый язык, где исходный код рассматривался бы не как инструкция, а как спецификация, которую транслятор может реализовывать как хочет. Думаю, прогресс придёт со стороны авто-доказателей теорем — agda, coq и прочих SAT.
        0
        > возможно даже новый язык, где исходный код рассматривался бы не как инструкция, а как спецификация, которую транслятор может реализовывать как хочет

        При этом целевой процессор, «данный нам в ощущения», уже служит ограничивающим фактором с заложенной в него архитектурой.
          0
          Э-э ну да, естественно? Не очень понял, что вы хотели сказать. Ограничения должны учитываться; если надо, представлять целое число машинным словом (общепринятый компромисс между точностью и производительностью).
            0
            То, что при неизменности бинарного кода, например х86 процессора, следующие поколения ядер ускоряют данный код не требуя его, зачастую, перекомпиляции.
            Сколько при этом внутри этих ядер транзисторов без предоставления внутренней спецификации к RISC ядру х86 процессора.

            P.S. Как, например, ещё и Java байт код в рантайме ускоряют. :)
            Умный компилятор для ограниченного процессорного ядра, не в этом ли один из принципиальных баръеров для умного компилятора. Отсюда и возникает конкуренция Софт-процессоров в FPGA с классикой.
          0
          при всём при этом качество кода того же gcc приятно удивляет

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

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

          К тому же, если, например, говорить о LLVM, который используют для написания компиляторов для множества языков, то в самой документации LLVM написано, что оптимизации настроены для clang, и если вы пишете свой фронтенд для другого языка, стоит поднастроить оптимизации по-другому, потому что иначе компилятор будет не очень эффективен.
            0
            Любая автоматизация это приятно, но у меня сомнения. Построение эффективной цепочки оптимизаций процесс творческий, включает как перебор, так и понимание происходящего, а система подбора параметров вторым не обладает, а рассматривает фазы оптимизации как чёрные ящики с рукоятками-параметрами. Нейросети наше всё, но чтобы работала регрессия, система должна быть более или менее линейной, не наш случай.
              0
              Я не спорю, что это сложная и отчасти творческая задача, но есть проблема, что и человеку сложно удержать в голове много мелких деталей, которые часто тоже влияют на общую картину. Иногда даже опытным инженерам нужно потратить много времени на понимание некоторых эффектов. Возможно, это должна быть в начале рекомендательная система, которая должна натолкнуть инженера при анализе или помочь собрать и визуализировать некоторые данные. Вариантов много. Начинать же с чего-то надо.
                0
                Если что-то полезное получится, то замечательно. Просто интуитивно инструмент не очень соответствует — пространство признаков больно сложное.
          +1
          Кстати, в мире FPGA тоже есть некоторый движ в этом направлении, например: www.plunify.com/en/intime. Здесь пытаются использовать ИИ для подбора лучших опций синтеза и place & route под конкретные проекты.
            0
            Спасибо, интересный материал.
            0
            В мануале по сборке SQLite есть рекомендация собирать скриптом все сишные файлы в один большой прежде чем компилировать. Утверждается, что это даст 5%-й выигрыш в скорости работы в сравнении с обычным способом. Это к слову, вдруг кому пригодится.
              0
              Да, это одна из известных техник, позволяющих предоставить компилятору больше контекста из-за чего, естественно, повышается эффективность оптимизаций, но интеллектуальности в этом не так уж много.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое