Супероптимизация - Superoptimization

Супероптимизация это процесс автоматического поиска оптимального код последовательность для одной последовательности инструкций без петель. Это выполняется в компьютере и с его помощью. программного обеспечения названный компилятор. Реальные компиляторы обычно не могут создавать по-настоящему оптимальный код. Хотя большинство стандартных оптимизация компилятора улучшить код только частично, цель супероптимизатора - найти оптимальную последовательность, каноническая форма. Супероптимизаторы можно использовать для улучшения обычных оптимизаторов, выделяя упущенные возможности, чтобы человек мог написать дополнительные правила.

История

Термин супероптимизация был впервые введен Алексия Массалин в статье 1987 г. Супероптимизатор: взгляд на самую маленькую программу.[1] В 1992 году GNU Superoptimizer (GSO) был разработан для интеграции в Коллекция компиляторов GNU (GCC).[2][3] Позднее работа развила и расширила эти идеи.

Методы

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

В 2001 году целенаправленная супероптимизация была продемонстрирована в проекте Denali исследования Compaq.[4] В 2006 г. набор ответов декларативное программирование был использован для супероптимизации в проекте Total Optimization using Answer Set Technology (TOAST) в Университет Бата,[5][6].

Супероптимизация может использоваться для автоматического создания универсальных глазок оптимизаторы.[7]

Общедоступные супероптимизаторы

Несколько супероптимизаторов доступны для бесплатной загрузки.

Смотрите также

использованная литература

  1. ^ Массалин, Генри (1987). «Супероптимизатор: взгляд на самую маленькую программу» (PDF). Новости компьютерной архитектуры ACM SIGARCH. 15 (5): 122–126. Дои:10.1145/36177.36194. В архиве (PDF) из оригинала на 2017-07-04. Получено 2012-04-25. Учитывая набор инструкций, супероптимизатор находит самую короткую программу для вычисления функции. Были созданы поразительные программы, многие из которых были заняты запутанной перестановкой битов, мало похожей на исходные программы, которые определяли функции. Ключевая идея супероптимизатора - вероятностный тест, который делает практичным исчерпывающий поиск программ полезного размера.
  2. ^ а б Гранлунд, Торбьёрн; Кеннер, Ричард (июль 1992 г.). «Устранение ветвей с помощью супероптимизатора и компилятора GNU C». Уведомления ACM SIGPLAN. 27 (7): 341–352. CiteSeerX  10.1.1.58.3509. Дои:10.1145/143095.143146. ISBN  978-0-89791475-8. S2CID  8825539.
  3. ^ а б "Индекс / gnu / superopt". Операционная система GNU. Free Software Foundation, Inc. 14 июня 1995 г. В архиве из оригинала на 2016-09-11. Получено 2016-09-03.
  4. ^ Джоши, Раджив; Нельсон, Грег; Рэндалл, Кейт (30.07.2001). «Денали: целеустремленный супероптимизатор». Центр системных исследований Compaq. Лаборатория HP. Hewlett-Packard Co. В архиве из оригинала от 27.05.2016. Получено 2016-09-02.
  5. ^ Мозг, Мартин; Крик, Том; Де Вос, Марина; Фитч, Джон (17 августа 2006 г.). «TOAST: Применение программирования набора ответов к супероптимизации». В Etalle, Сандро; Трушчинский, Мирослав (ред.). Логическое программирование. Springer-Verlag, Берлин / Гейдельберг. С. 270–284. ISBN  978-3-540-36636-2.
  6. ^ "ТОСТ - KRRwiki". Отделение компьютерных наук, группа математических основ. Группа представления и рассуждения знаний (KRR). Университет Бата. 2007-08-07. Архивировано из оригинал на 2012-11-28. Получено 2016-09-03.
  7. ^ Бансал, Сорав; Айкен, Алекс (21.10.2006). «Автоматическая генерация супероптимизаторов глазка» (PDF). Стэндфордский Университет. Лаборатория компьютерных систем Стэнфордского университета. В архиве (PDF) из оригинала на 2016-06-11. Получено 2016-09-02.
  8. ^ Бансал, Сорав; Айкен, Алекс (25 октября 2006 г.). «Двоичный перевод с использованием супероптимизаторов Peephole» (PDF). Департамент компьютерных наук. Индийский технологический институт, Дели. В архиве (PDF) из оригинала на 08.09.2016. Получено 2016-10-17.
  9. ^ Серпелл, Дэниел (2003). «SuperOptimizer для микроконтроллеров Microchip PIC». Сайты Google. В архиве из оригинала на 2016-10-11. Получено 2016-09-06.
  10. ^ Серпелл, Дэниел (21.06.2003). «СуперОптимизатор микроконтроллера PIC». Freecode. Slashdot Media. В архиве из оригинала от 17.09.2016. Получено 2016-09-06.
  11. ^ Хьюм, Том (21.08.2012). «Программа Clojure для исчерпывающего поиска оптимальных программ на Java». GitHub. В архиве с оригинала на 2018-06-10. Получено 2016-09-06.
  12. ^ Кабрера Артеага, Хавьер; Донде, Шриниш; Гу, Цзянь; Флорос, Орестис; Сатабин, Лукас; Бодри, Бенуа; Монперрус, Мартин (2020). «Супероптимизация байт-кода WebAssembly». Сопутствующая конференция 4-й Международной конференции по искусству, науке и инженерии программирования. Порту, Португалия: ACM: 36–40. arXiv:2002.10213. Дои:10.1145/3397537.3397567. ISBN  978-1-4503-7507-8. S2CID  211259480.