- 28,940
- 46
- 8 Ноя 2022
Она перепишет правила оптимизации от нейросетей до процессоров Intel.
<div class="articl-text-cover" style="position:relative;width:100%;max-width:800px;margin-left:auto;margin-right:auto;aspect-ratio:1200/676;margin-bottom:2rem;overflow:hidden">
<div itemprop="articleBody">Компиляторам и другим инструментам для работы с кодом постоянно приходится решать одну трудную задачу: находить более простую и быструю версию программы, которая даст ровно тот же результат. Чем удачнее преобразование, тем меньше вычислительных ресурсов требует код, тем быстрее работает и тем проще запускается на разном оборудовании. Проблема в том, что единого метода оптимизации нет. Для 3D-моделей в САПР нужны одни приёмы, для SQL-запросов другие, для нейронных сетей и аппаратных схем третьи.
Открытая библиотека egg пытается отделить сам механизм поиска оптимального варианта от конкретной задачи. Разработчику по-прежнему нужно определить допустимые преобразования, но уже не обязательно вручную выстраивать точную последовательность их применения. Egg сохраняет много эквивалентных вариантов программы одновременно, а затем выбирает наиболее выгодный по заданному критерию.
В основе библиотеки лежат E-графы, структура данных для компактного хранения равнозначных выражений. Проще всего понять принцип на арифметическом примере. Выражение можно раскрыть, перегруппировать или переписать несколькими математически эквивалентными способами. Обычный оптимизатор применяет одно правило, получает новую версию и продолжает работу уже с ней. Предыдущий вариант при этом исчезает из дальнейшего поиска.
Ранний выбор иногда мешает получить лучший результат. Одно преобразование может привести в тупик, тогда как другая последовательность правил откроет возможность для дальнейшего упрощения. Разработчикам традиционных оптимизаторов поэтому приходится тщательно подбирать порядок операций и учитывать ситуации, когда правила мешают друг другу.
E-граф решает проблему иначе. Структура сохраняет исходное выражение и найденные эквивалентные версии вместе, объединяя их общие части. Когда очередное правило находит новый допустимый вариант, egg добавляет его в тот же граф вместо замены уже существующего выражения. В результате система постепенно собирает множество разных способов выполнить одно и то же вычисление.
Такой поиск называют насыщением равенствами . Алгоритм многократно применяет заданные правила и пополняет E-граф новыми эквивалентными выражениями. Процесс останавливается, когда правила больше не находят новых вариантов либо когда срабатывает установленное ограничение по времени, памяти или другим ресурсам. После поиска egg оценивает накопленные версии и извлекает вариант с минимальной стоимостью.
Понятие стоимости разработчик определяет под конкретную задачу. Компилятор может искать код с меньшим числом операций или меньшим временем выполнения. При проектировании электроники целью может быть сокращение аппаратной схемы. Численный оптимизатор способен выбирать формулу, которая даёт меньшую погрешность при вычислениях с плавающей точкой. Egg не предлагает единого определения лучшей программы, а предоставляет механизм для поиска среди математически или семантически тождественных вариантов.
Идея насыщения равенствами появилась задолго до egg. Метод для оптимизации программ подробно описали ещё в 2009 году, а научная статья о нём вышла в 2011 году. Исследователи предлагали отказаться от последовательного разрушительного переписывания программы и вместо него накапливать сведения об эквивалентности разных фрагментов. После насыщения оптимизатор мог выбирать готовую версию из множества найденных вариантов.
На практике подход долго упирался в производительность и память. Чем больше правил применяет система, тем быстрее растёт пространство возможных выражений. Даже компактное хранение общих частей не отменяет расходов на обработку большого E-графа. Egg, выпущенная как открытая библиотека в 2020 году, упростила реализацию алгоритма и ускорила работу настолько, что насыщение равенствами начали применять далеко за пределами экспериментальных оптимизаторов.
Одним из показательных примеров стал Herbie, инструмент для численных вычислений. Herbie ищет эквивалентные математические формулы, которые уменьшают ошибки округления при работе с числами с плавающей точкой. После интеграции egg производительность Herbie выросла примерно в 3000 раз, причём программа начала находить и более качественные варианты выражений.
E-графы применяют и при оптимизации нейронных сетей. В отдельных проектах разработчики получили 50-кратное ускорение самого процесса оптимизации. В задачах проектирования электроники подход позволял получать аппаратные схемы на 63% меньше исходных. Некоторые промышленные компиляторы также перестраивают вокруг E-графов, а инженеры Intel используют подобные структуры при проектировании микросхем.
Широкий набор применений не означает, что egg одинаково оптимизирует SQL-запрос, нейронную сеть и процессор. Для каждой области нужны собственные правила преобразования. Библиотека берёт на себя другую часть работы: хранит эквивалентные варианты, применяет правила без преждевременного удаления альтернатив и помогает выбрать результат по заданной функции стоимости.
За счёт этого egg подходит и для быстрых экспериментов. Разработчик может проверить набор преобразований, не создавая сразу полноценный оптимизатор со сложной системой приоритетов. Если эксперимент даёт полезный результат, найденные правила можно оставить в egg или перенести в специализированный инструмент.
У метода остаётся серьёзное ограничение: память. При большом числе возможных преобразований E-граф способен разрастись настолько, что использование egg теряет практический смысл. С такой проблемой разработчики столкнулись, например, в экспериментах с компьютерной графикой. В подобных случаях библиотеку можно использовать только для проверки идеи, а рабочий алгоритм затем реализовать традиционным способом.
Подробное описание egg опубликовали 29 июля в Communications of the ACM. Редакция включила работу в Research Highlights, раздел с отобранными исследованиями в области вычислительной техники. За шесть лет после выхода открытой библиотеки E-графы успели добраться до численных вычислений, нейронных сетей, аппаратного проектирования и промышленных компиляторов, хотя проблема быстрого роста потребления памяти по-прежнему ограничивает задачи, для которых насыщение равенствами подходит на практике.
<div class="articl-text-cover" style="position:relative;width:100%;max-width:800px;margin-left:auto;margin-right:auto;aspect-ratio:1200/676;margin-bottom:2rem;overflow:hidden">
<div itemprop="articleBody">Компиляторам и другим инструментам для работы с кодом постоянно приходится решать одну трудную задачу: находить более простую и быструю версию программы, которая даст ровно тот же результат. Чем удачнее преобразование, тем меньше вычислительных ресурсов требует код, тем быстрее работает и тем проще запускается на разном оборудовании. Проблема в том, что единого метода оптимизации нет. Для 3D-моделей в САПР нужны одни приёмы, для SQL-запросов другие, для нейронных сетей и аппаратных схем третьи.
Открытая библиотека egg пытается отделить сам механизм поиска оптимального варианта от конкретной задачи. Разработчику по-прежнему нужно определить допустимые преобразования, но уже не обязательно вручную выстраивать точную последовательность их применения. Egg сохраняет много эквивалентных вариантов программы одновременно, а затем выбирает наиболее выгодный по заданному критерию.
В основе библиотеки лежат E-графы, структура данных для компактного хранения равнозначных выражений. Проще всего понять принцип на арифметическом примере. Выражение можно раскрыть, перегруппировать или переписать несколькими математически эквивалентными способами. Обычный оптимизатор применяет одно правило, получает новую версию и продолжает работу уже с ней. Предыдущий вариант при этом исчезает из дальнейшего поиска.
Ранний выбор иногда мешает получить лучший результат. Одно преобразование может привести в тупик, тогда как другая последовательность правил откроет возможность для дальнейшего упрощения. Разработчикам традиционных оптимизаторов поэтому приходится тщательно подбирать порядок операций и учитывать ситуации, когда правила мешают друг другу.
E-граф решает проблему иначе. Структура сохраняет исходное выражение и найденные эквивалентные версии вместе, объединяя их общие части. Когда очередное правило находит новый допустимый вариант, egg добавляет его в тот же граф вместо замены уже существующего выражения. В результате система постепенно собирает множество разных способов выполнить одно и то же вычисление.
Такой поиск называют насыщением равенствами . Алгоритм многократно применяет заданные правила и пополняет E-граф новыми эквивалентными выражениями. Процесс останавливается, когда правила больше не находят новых вариантов либо когда срабатывает установленное ограничение по времени, памяти или другим ресурсам. После поиска egg оценивает накопленные версии и извлекает вариант с минимальной стоимостью.
Понятие стоимости разработчик определяет под конкретную задачу. Компилятор может искать код с меньшим числом операций или меньшим временем выполнения. При проектировании электроники целью может быть сокращение аппаратной схемы. Численный оптимизатор способен выбирать формулу, которая даёт меньшую погрешность при вычислениях с плавающей точкой. Egg не предлагает единого определения лучшей программы, а предоставляет механизм для поиска среди математически или семантически тождественных вариантов.
Идея насыщения равенствами появилась задолго до egg. Метод для оптимизации программ подробно описали ещё в 2009 году, а научная статья о нём вышла в 2011 году. Исследователи предлагали отказаться от последовательного разрушительного переписывания программы и вместо него накапливать сведения об эквивалентности разных фрагментов. После насыщения оптимизатор мог выбирать готовую версию из множества найденных вариантов.
На практике подход долго упирался в производительность и память. Чем больше правил применяет система, тем быстрее растёт пространство возможных выражений. Даже компактное хранение общих частей не отменяет расходов на обработку большого E-графа. Egg, выпущенная как открытая библиотека в 2020 году, упростила реализацию алгоритма и ускорила работу настолько, что насыщение равенствами начали применять далеко за пределами экспериментальных оптимизаторов.
Одним из показательных примеров стал Herbie, инструмент для численных вычислений. Herbie ищет эквивалентные математические формулы, которые уменьшают ошибки округления при работе с числами с плавающей точкой. После интеграции egg производительность Herbie выросла примерно в 3000 раз, причём программа начала находить и более качественные варианты выражений.
E-графы применяют и при оптимизации нейронных сетей. В отдельных проектах разработчики получили 50-кратное ускорение самого процесса оптимизации. В задачах проектирования электроники подход позволял получать аппаратные схемы на 63% меньше исходных. Некоторые промышленные компиляторы также перестраивают вокруг E-графов, а инженеры Intel используют подобные структуры при проектировании микросхем.
Широкий набор применений не означает, что egg одинаково оптимизирует SQL-запрос, нейронную сеть и процессор. Для каждой области нужны собственные правила преобразования. Библиотека берёт на себя другую часть работы: хранит эквивалентные варианты, применяет правила без преждевременного удаления альтернатив и помогает выбрать результат по заданной функции стоимости.
За счёт этого egg подходит и для быстрых экспериментов. Разработчик может проверить набор преобразований, не создавая сразу полноценный оптимизатор со сложной системой приоритетов. Если эксперимент даёт полезный результат, найденные правила можно оставить в egg или перенести в специализированный инструмент.
У метода остаётся серьёзное ограничение: память. При большом числе возможных преобразований E-граф способен разрастись настолько, что использование egg теряет практический смысл. С такой проблемой разработчики столкнулись, например, в экспериментах с компьютерной графикой. В подобных случаях библиотеку можно использовать только для проверки идеи, а рабочий алгоритм затем реализовать традиционным способом.
Подробное описание egg опубликовали 29 июля в Communications of the ACM. Редакция включила работу в Research Highlights, раздел с отобранными исследованиями в области вычислительной техники. За шесть лет после выхода открытой библиотеки E-графы успели добраться до численных вычислений, нейронных сетей, аппаратного проектирования и промышленных компиляторов, хотя проблема быстрого роста потребления памяти по-прежнему ограничивает задачи, для которых насыщение равенствами подходит на практике.
- Источник новости
- www.securitylab.ru
