Обучение с подкреплением для управления процессом компиляции исходного кода

Студент: Чучин Дмитрий Юрьевич

Научный руководитель: Свидченко Олег Анатольевич

Научные консультанты: Косов Павел Владимирович, Хомутов Никита Юрьевич

Университет ИТМО

Санкт-Петербург, 2024

Определения эффективной последовательности оптимизаций компилятора

Оптимизации позволяют улучшить такие характеристики программы, как время исполнения или размер исполняемого файла

Сложности:

• Порядок применения оптимизаций влияет на результат
• Разным программам могут соответствовать разные оптимальные последовательности
• Число возможных решений растет экспоненциально при увеличении длины последовательности

В рамках работы рассматривалась задача оптимизации времени исполнения. Задача решалась для архитектуры x86-64 и инфраструктуры LLVM 10.0.0

Пример оптимизации instcombine для промежуточного представления LLVM

2 / 13

Существующие подходы

1. Kulkarni, Sameer and John Cavazos. (2012)

2. Mammadli, Rahim et al. (2020)

3 / 13

Определение порядка оптимизаций как задача обучения с подкреплением

представление IR, история действий, награда

LLVM IR

opt

Агент

применение

оптимизаций

4 / 13

2. Mammadli, Rahim et al. (2020)

Цель и задачи

Цель:

Разработать модель поиска эффективной последовательности оптимизаций компилятора в инфраструктуре LLVM для оптимизации времени исполнения, используя обучение с подкреплением

​

Задачи:

• Разработать и реализовать архитектуру модели
• Обучить и протестировать различные конфигурации модели
• Выбрать лучшую модель на основе экспериментальных данных

5 / 13

Архитектура модели. Векторное представление и награда

6 / 13

Архитектура модели. Пространство действий и алгоритм обучения с подкреплением

• Пространство действий
• POSET-manual ³: подпоследовательности -O3, сгруппированные по своей функциональности
• POSET-odg ³: последовательности построенные по графу зависимостей оптимизаций в последовательности -O3
• Cbench-inst-min: последовательности минимизирующие количество исполненных инструкций на наборе программ Cbench
• MiCOMP: последовательности из работы MiCOMP ⁴
• Алгоритм обучения с подкреплением
• Алгоритм: DQN (использовался в предыдущих работах ^{2, 3})
• Наблюдение: история действий и история векторных представлений IR
• Нейросеть: LSTM с полносвязными слоями для преобразований входов и выходов

7 / 13

2. Mammadli, Rahim et al. (2020)

3. Jain, Shalini et al. (2022)

4. Ashouri, Amir H. et al. (2017)

​

Обучение моделей. Датасет

Датасеты

• Jotai Benchmark Collection
• Исполняемые программы на языке C из одного исходного файла
• Составлен на основе программ из открытых репозиториев
• Каждая программа состоит из функции с логикой и функции запуска
• Входные данные каждой программы фиксированы
• llvm-test-suite
• Набор исполняемых программ (преимущественно на C и C++)
• Используется для тестирования компиляторов
• Включает 128 программ из одного исходного файла, подобранных для тестирования времени исполнения

Данные для обучения и тестирования

• Обучение: Jotai Benchmark Collection (4000 программ)
• Тест: Jotai Benchmark Collection (2000 программ) и llvm-test-suite (128 программ)

8 / 13

Обучение моделей. Сравнение наград

9 / 13

Параметры моделей:

• Представление: конкатенация IR2Vec, Autophase и Instcount
• Пространство действий: Cbench-inst-min

Обучение моделей. Сравнение пространств действий

Параметры моделей:

• Представление: конкатенация IR2Vec, Autophase и Instcount
• Функция стоимости в награде: количество исполненных инструкций

10 / 13

Выбор лучшей модели

11 / 13

Количество программ

Выбор лучшей модели. Применение для итеративной компиляции

4. Ashouri, Amir H. et al. (2017)

5. Sameer Kulkarni and John Cavazos. (2012)

12 / 13

• Обученная модель может быть применена в рамках итеративной компиляции, например можно запускать две скомпилированные программы: с оптимизациями модели и с оптимизациями O3

​

• Сравнение с другими моделями примененными в данном сценарии (в статье MiCOMP результаты моделей были получены путем leave-one-out кросс валидации на Cbench):

Результаты

13 / 13

Дополнительные слайды

Репозиторий: https://github.com/capitanFlint129/diplom_experiments

14 / 13

Архитектура модели. Агент

Был реализован DQN с LSTM для учета истории применения действий. Среди алгоритмов обучения с подкреплением в первую очередь был применен DQN поскольку, данный алгоритм использовался в предыдущей аналогичной работе, а сравнение эффективности различных алгоритмов не было первоочередной задачей работы

Преимущества алгоритма для данной задачи:

• Обучение за небольшое количество взаимодействий со средой
• Итоговая политика детерминированная

a_t - примененная оптимизация

o_t - наблюдение (например IR2Vec)

h_t - скрытое состояние LSTM

one-hot a_t-1

o_t

LSTM

h_t-1

a_t

Полносвязная сеть

h_t

+

h_t+1

one-hot a_t

o_t+1

LSTM

+

Полносвязная сеть

Полносвязная сеть

Полносвязная сеть

a_t+1

15 / 13

Обучение моделей. Сравнение представлений

Параметры моделей:

• Пространство действий: POSET-manual
• Функция стоимости в награде: количество исполненных инструкций

16 / 13

Обучение моделей. DQN Loss

Номер эпизода

Loss

17 / 13

Выбор лучшей модели. Применение для итеративной компиляции

2. Ashouri, Amir H. et al. (2017)

4. Sameer Kulkarni and John Cavazos. (2012)

18 / 13

Пространство действий Cbench-inst-min

Пример выбора ключевой оптимизации на программе stringsearch2

Индекс оптимизации в последовательности O3

Нормированное количество исполненных инструкций

19 / 13

Обучение моделей

Сравнение наград основанных на разных функциях стоимости:

Сравнение пространств действий (функция стоимости - количество исполненных инструкций):

20 / 13