Superoptimización

Técnica de optimización del compilador

La superoptimización es el proceso mediante el cual un compilador encuentra automáticamente la secuencia óptima para una secuencia de instrucciones sin bucles. Los compiladores del mundo real generalmente no pueden producir código verdaderamente óptimo y, si bien la mayoría de las optimizaciones de compiladores estándar solo mejoran el código parcialmente, el objetivo de un superoptimizador es encontrar la secuencia óptima, la forma canónica . Los superoptimizadores se pueden utilizar para mejorar los optimizadores convencionales al resaltar las oportunidades perdidas para que un humano pueda escribir reglas adicionales.

Historia

El término superoptimización fue acuñado por primera vez por Alexia Massalin en el artículo de 1987 Superoptimizer: A Look at the Smallest Program [Superoptimizador: una mirada al programa más pequeño ] . ^[1] La etiqueta "optimización de programas" se le ha dado a un campo que no aspira a optimizar sino solo a mejorar. Este nombre erróneo obligó a Massalin a llamar a su sistema un superoptimizador, que en realidad es un optimizador para encontrar un programa óptimo. ^[2]

En 1992, se desarrolló el GNU Superoptimizer (GSO) para integrarlo en la Colección de compiladores GNU (GCC). ^{[3] [4]} Trabajos posteriores desarrollaron y ampliaron aún más estas ideas.

Técnicas

Tradicionalmente, la superoptimización se realiza mediante una búsqueda exhaustiva por fuerza bruta en el espacio de secuencias de instrucciones válidas. Este es un método costoso y, por lo tanto, poco práctico para compiladores de propósito general. Sin embargo, se ha demostrado que es útil para optimizar bucles internos críticos para el rendimiento. También es posible utilizar un solucionador SMT para abordar el problema, lo que mejora enormemente la eficiencia de la búsqueda (aunque las entradas más complejas que un bloque básico siguen estando fuera del alcance). ^[5]

En 2001, Compaq Research demostró la superoptimización dirigida a objetivos en el proyecto Denali. ^[6] En 2006, se utilizó la programación declarativa de conjuntos de respuestas para la superoptimización en el proyecto TOAST ( Optimización total mediante tecnología de conjuntos de respuestas ) de la Universidad de Bath . ^{[7] [8]}

La superoptimización se puede utilizar para generar automáticamente optimizadores de mirilla de propósito general . ^[9]

Superoptimizadores disponibles públicamente

Hay varios superoptimizadores disponibles para descarga gratuita.

• Para la familia de conjuntos de instrucciones x86:
  • Superoptimizador GNU (superopt) ^[10] (GSO) (1992) ^{[3] [4]} – también admite muchas otras ISA
  • STOKE, ^[11] un optimizador estocástico ^[12] para lenguaje ensamblador x86-64 x86 .
• Para ARM:
  • Superoptimizador ilimitado, ^[5] que transforma LLVM IR en un ensamblaje ARMv7-A
• Para sistemas integrados:
  • Microcontrolador PIC SuperOptimizer (2003) ^{[13] [14]}
  • Un estudio de viabilidad de Embecosm (2014) para AVR , basado en GSO ^{[15] [16]}
• Para la JVM:
  • Superoptimizador de Clojure para la máquina virtual Java (2012) ^[17]
• Para LLVM IR:
  • souper ^[18] superoptimizador para programas en el lenguaje intermedio LLVM .
• Para WebAssembly
  • slumps ^[19] proporciona superoptimización para programas WASM basados ​​en souper.

Véase también

• Optimización de mirillas
• Eliminación de código muerto
• Metacompilación

Referencias

1. Massalin, Henry (1987). "Superoptimizador: Una mirada al programa más pequeño" (PDF) . ACM SIGARCH Computer Architecture News . 15 (5): 122–126. doi :10.1145/36177.36194 . Consultado el 1 de mayo de 2023 . Dado un conjunto de instrucciones, el superoptimizador encuentra el programa más corto para calcular una función. Se han generado programas sorprendentes, muchos de los cuales implican una manipulación de bits complicada que guarda poca semejanza con los programas fuente que definieron las funciones. La idea clave del superoptimizador es una prueba probabilística que hace que las búsquedas exhaustivas sean prácticas para programas de tamaño útil.
2. Joshi, Rajeev; Nelson, Greg; Randall, Keith (2002). "Denali: un superoptimizador orientado a objetivos". Avisos SIGPLAN de la ACM . 37 (5): 304–314. doi :10.1145/543552.512566.
3. Granlund, Torbjörn; Kenner, Richard (julio de 1992). "Eliminación de ramas utilizando un superoptimizador y el compilador GNU C". Actas de la conferencia ACM SIGPLAN 1992 sobre diseño e implementación de lenguajes de programación - PLDI '92 . Vol. 27. págs. 341–352. CiteSeerX 10.1.1.58.3509 . doi :10.1145/143095.143146. ISBN  978-0-89791475-8.S2CID8825539  .​ {{cite book}}: |journal=ignorado ( ayuda )
4. "Índice de /gnu/superopt". Sistema operativo GNU . Free Software Foundation, Inc. 14 de junio de 1995 . Consultado el 1 de mayo de 2023 .
5. Jangda, Abhinav; Yorsh, Greta (25 de octubre de 2017). Unbounded superoptimization . Onward!'17, 25-27 de octubre de 2017, Vancouver, Canadá. págs. 78-88. doi :10.1145/3133850.3133856.
6. Joshi, Rajeev; Nelson, Greg; Randall, Keith (30 de julio de 2001). "Denali: un superoptimizador orientado a objetivos". Compaq Systems Research Center. HP Labs . Hewlett-Packard Co. Consultado el 1 de mayo de 2023 .
7. Brain, Martin; Crick, Tom; De Vos, Marina; Fitch, John (17 de agosto de 2006). "TOAST: aplicación de la programación de conjuntos de respuestas a la superoptimización". En Etalle, Sandro; Truszczyński, Mirosław (eds.). Programación lógica . Springer-Verlag , Berlín / Heidelberg. págs. 270–284. ISBN 978-3-540-36636-2.
8. "TOAST – KRRwiki". Departamento de Ciencias de la Computación, Grupo de Fundamentos Matemáticos. Grupo de Representación y Razonamiento del Conocimiento (KRR) . Universidad de Bath . 2007-08-07. Archivado desde el original el 2012-11-28 . Consultado el 2016-09-03 .
9. Bansal, Sorav; Aiken, Alex (2006). "Generación automática de superoptimizadores de mirilla" (PDF) . Consultado el 1 de mayo de 2023 .
10. "Superoptimizador GNU".
11. StanfordPL. "STOKE". GitHub .
12. Bansal, Sorav; Aiken, Alex (2008). "Traducción binaria mediante superoptimizadores de mirilla" (PDF) . Consultado el 1 de mayo de 2023 .
13. Serpell, Daniel (2003). «SuperOptimizer para microcontroladores PIC de Microchip». Sitios de Google . Archivado desde el original el 11 de octubre de 2016. Consultado el 6 de septiembre de 2016 .
14. Serpell, Daniel (21 de junio de 2003). "SuperOptimizador de microcontroladores PIC". Freecode . Slashdot Media. Archivado desde el original el 17 de septiembre de 2016. Consultado el 6 de septiembre de 2016 .
15. "Un estudio de viabilidad realizado por Embecosm".
16. Superoptimización – Código fuente de Embecosm
17. Hume, Tom (21 de agosto de 2012). «Programa Clojure para buscar exhaustivamente programas Java óptimos». GitHub . Archivado desde el original el 10 de junio de 2018. Consultado el 6 de septiembre de 2016 .
18. Sasnauskas, Raimondas; Chen, Yang; Collingbourne, Peter; Ketema, Jeroen; Lup, Gratian; Taneja, Jubi; Regehr, John (2017). "Souper: un superoptimizador sintetizador". arXiv : 1711.04422 [cs.PL].Código fuente de GitHub
19. Cabrera Arteaga, Javier; Donde, Shrinish; Gu, Jian; Floros, Orestis; Satabin, Lucas; Baudry, Benoit; Monperrus, Martin (23 de marzo de 2020). Superoptimización del bytecode de WebAssembly . MoreVMs: Taller sobre entornos de ejecución de lenguajes modernos, ecosistemas y máquinas virtuales. págs. 36–40. arXiv : 2002.10213 . doi :10.1145/3397537.3397567.Código fuente de GitHub