stringtranslate.com

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

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

История

Термин «супероптимизация» впервые был введен Алексией Массалин в статье 1987 года «Супероптимизатор: взгляд на самую маленькую программу» . [1] Ярлык «оптимизация программы» был дан области, которая не стремится к оптимизации, а только к улучшению. Это неправильное название заставило Массалин назвать свою систему супероптимизатором, которая на самом деле является оптимизатором для поиска оптимальной программы. [2]

В 1992 году был разработан GNU Superoptimizer (GSO) для интеграции в GNU Compiler Collection (GCC). [3] [4] Более поздние работы продолжили развивать и расширять эти идеи.

Методы

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

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

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

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

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

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

Ссылки

  1. ^ Massalin, Henry (1987). "Superoptimizer: A look at the smallly program" (PDF) . ACM SIGARCH Computer Architecture News . 15 (5): 122–126. doi :10.1145/36177.36194 . Получено 2023-05-01 . Учитывая набор инструкций, супероптимизатор находит самую короткую программу для вычисления функции. Были созданы поразительные программы, многие из которых занимались замысловатыми битовыми манипуляциями, имеющими мало общего с исходными программами, которые определяли функции. Ключевая идея в супероптимизаторе — вероятностный тест, который делает исчерпывающий поиск практичным для программ полезного размера.
  2. ^ Джоши, Раджив; Нельсон, Грег; Рэндалл, Кейт (2002). «Денали: Целенаправленный супероптимизатор». ACM SIGPLAN Notices . 37 (5): 304–314. doi :10.1145/543552.512566.
  3. ^ ab Granlund, Torbjörn; Kenner, Richard (июль 1992 г.). "Устранение ветвей с помощью супероптимизатора и компилятора GNU C". Труды конференции ACM SIGPLAN 1992 года по проектированию и реализации языков программирования - PLDI '92 . Том 27. С. 341–352. CiteSeerX 10.1.1.58.3509 . doi :10.1145/143095.143146. ISBN  978-0-89791475-8. S2CID  8825539. {{cite book}}: |journal=проигнорировано ( помощь )
  4. ^ ab "Индекс /gnu/superopt". Операционная система GNU . Free Software Foundation, Inc. 1995-06-14 . Получено 2023-05-01 .
  5. ^ ab Jangda, Abhinav; Yorsh, Greta (2017-10-25). Неограниченная супероптимизация . Вперед!'17, 25–27 октября 2017 г., Ванкувер, Канада. С. 78–88. doi :10.1145/3133850.3133856.
  6. ^ Джоши, Раджив; Нельсон, Грег; Рэндалл, Кейт (2001-07-30). «Denali: целевой супероптимизатор». Исследовательский центр Compaq Systems. HP Labs . Hewlett-Packard Co. Получено 01.05.2023 .
  7. ^ Brain, Martin; Crick, Tom; De Vos, Marina; Fitch, John (2006-08-17). "TOAST: применение программирования с набором ответов к супероптимизации". В Etalle, Sandro; Truszczyński, Mirosław (ред.). Logic Programming . Springer-Verlag , Berlin / Heidelberg. стр. 270–284. ISBN 978-3-540-36636-2.
  8. ^ "TOAST – KRRwiki". Департамент компьютерных наук, Группа математических основ. Группа представления и обоснования знаний (KRR) . Университет Бата . 2007-08-07. Архивировано из оригинала 2012-11-28 . Получено 2016-09-03 .
  9. ^ Бансал, Сорав; Айкен, Алекс (2006). «Автоматическая генерация супероптимизаторов Peephole» (PDF) . Получено 01.05.2023 .
  10. ^ «GNU Супероптимизатор».
  11. ^ СтэнфордПЛ. "СТОК". GitHub .
  12. ^ Бансал, Сорав; Айкен, Алекс (2008). «Двоичная трансляция с использованием супероптимизаторов Peephole» (PDF) . Получено 01.05.2023 .
  13. ^ Serpell, Daniel (2003). "SuperOptimizer for Microchip's PIC microcontrollers". Google Sites . Архивировано из оригинала 2016-10-11 . Получено 2016-09-06 .
  14. ^ Serpell, Daniel (2003-06-21). "PIC Microcontroller SuperOptimizer". Freecode . Slashdot Media. Архивировано из оригинала 2016-09-17 . Получено 2016-09-06 .
  15. ^ "Технико-экономическое обоснование Embecosm".
  16. ^ Супероптимизация – Исходный код Embecosm
  17. ^ Хьюм, Том (2012-08-21). "Программа Clojure для исчерпывающего поиска оптимальных программ Java". GitHub . Архивировано из оригинала 2018-06-10 . Получено 2016-09-06 .
  18. ^ Саснаускас, Раймондас; Чэнь, Ян; Коллингборн, Питер; Кетема, Йерун; Луп, Грациан; Танея, Джуби; Регер, Джон (2017). «Souper: синтезирующий супероптимизатор». arXiv : 1711.04422 [cs.PL].Исходный код GitHub
  19. ^ Кабрера Артеага, Хавьер; Донде, Шриниш; Гу, Цзянь; Флорос, Орестис; Сатабин, Лукас; Бодри, Бенуа; Монперрус, Мартин (2020-03-23). ​​Супероптимизация байт-кода WebAssembly . MoreVMs: Workshop on Modern Language Runtimes, Ecosystems, and VMs. стр. 36–40. arXiv : 2002.10213 . doi :10.1145/3397537.3397567.Исходный код GitHub