La supeptimización es el proceso de encontrar automáticamente la secuencia de código óptima para una secuencia de instrucciones sin bucles. Se realiza en y por un tipo de software de computadora denominado compilador . Los compiladores del mundo real generalmente no pueden producir un código realmente óptimo . Si bien la mayoría de las optimizaciones estándar del compilador solo mejoran el código en parte, 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 . [1] En 1992, GNU Superoptimizer (GSO) se desarrolló para integrarse en GNU Compiler Collection (GCC). [2] [3] El trabajo posterior desarrolló y amplió estas ideas.
Técnicas
Normalmente, la superoptimización se realiza mediante una búsqueda exhaustiva de 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 los circuitos internos críticos para el rendimiento. También es posible utilizar un solucionador SMT para abordar el problema.
En 2001, la investigación de Compaq demostró la superoptimización dirigida por objetivos en el proyecto Denali. [4] En 2006, la programación declarativa de conjuntos de respuestas se utilizó para superoptimizar en el proyecto Total Optimization using Answer Set Technology (TOAST) en la Universidad de Bath . [5] [6]
La supeptimización se puede utilizar para generar automáticamente optimizadores de mirilla de uso general . [7]
Superoptimizadores disponibles al público
Varios superoptimizadores están disponibles para su descarga gratuita.
- Para la familia de conjuntos de instrucciones x86:
- Superoptimizer GNU (GSO) (1992) [2] [3]
- STOKE : un optimizador estocástico [8] para lenguaje ensamblador x86-64 x86
- Para sistemas integrados:
- Microcontrolador PIC SuperOptimizer (2003) [9] [10]
- Un estudio de viabilidad de Embecosm (2014)
- Para la JVM:
- Superoptimizador de Clojure para la máquina virtual Java (2012) [11]
- Para LLVM IR:
- Para WebAssembly
- depresiones ofrece superoptimization para los programas basados en WASM souper. [12]
Ver también
- Optimización de mirillas
- Eliminación de código muerto
Referencias
- ^ Massalin, Henry (1987). "Superoptimizer: Una mirada al programa más pequeño" (PDF) . ACM SIGARCH Computer Architecture News . 15 (5): 122-126. doi : 10.1145 / 36177.36194 . Archivado (PDF) desde el original el 4 de julio de 2017 . Consultado el 25 de abril de 2012 .
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 ellos involucrados en complicados juegos de bits que se parecen poco a los programas fuente que definieron las funciones. La idea clave en el superoptimizador es una prueba probabilística que hace que las búsquedas exhaustivas sean prácticas para programas de tamaño útil.
- ^ a b Granlund, Torbjörn; Kenner, Richard (julio de 1992). "Eliminando ramas usando un superoptimizador y el compilador GNU C". Avisos ACM SIGPLAN . 27 (7): 341–352. CiteSeerX 10.1.1.58.3509 . doi : 10.1145 / 143095.143146 . ISBN 978-0-89791475-8. S2CID 8825539 .
- ^ a b "Índice de / gnu / superopt" . Sistema operativo GNU . Free Software Foundation, Inc. 14 de junio de 1995. Archivado desde el original el 11 de septiembre de 2016 . Consultado el 3 de septiembre de 2016 .
- ^ Joshi, Rajeev; Nelson, Greg; Randall, Keith (30 de julio de 2001). "Denali: un superoptimizador dirigido a objetivos" . Centro de Investigación de Sistemas de Compaq. Laboratorios HP . Hewlett-Packard Co. Archivado desde el original, el 27/05/2016 . Consultado el 2 de septiembre de 2016 .
- ^ Brain, Martin; Crick, Tom; De Vos, Marina; Fitch, John (17 de agosto de 2006). "Brindis: aplicación de la programación de conjuntos de respuestas a la supeptimizació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.
- ^ "TOSTADA - KRRwiki" . Departamento de Informática, 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 28 de noviembre de 2012 . Consultado el 3 de septiembre de 2016 .
- ^ Bansal, Sorav; Aiken, Alex (21 de octubre de 2006). "Generación automática de superoptimizadores de mirilla" (PDF) . Universidad de Stanford . Laboratorio de sistemas informáticos, Universidad de Stanford. Archivado (PDF) desde el original el 11 de junio de 2016 . Consultado el 2 de septiembre de 2016 .
- ^ Bansal, Sorav; Aiken, Alex (25 de octubre de 2006). "Traducción binaria con superptimizadores de mirilla" (PDF) . Departamento de Ciencias de la Computación . Instituto Indio de Tecnología, Delhi. Archivado (PDF) desde el original el 8 de septiembre de 2016 . Consultado el 17 de octubre de 2016 .
- ^ 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 .
- ^ Serpell, Daniel (21 de junio de 2003). "SuperOptimizador del microcontrolador PIC" . Código libre . Slashdot Media. Archivado desde el original el 17 de septiembre de 2016 . Consultado el 6 de septiembre de 2016 .
- ^ Hume, Tom (21 de agosto de 2012). "Programa Clojure para la búsqueda exhaustiva de programas Java óptimos" . GitHub . Archivado desde el original el 10 de junio de 2018 . Consultado el 6 de septiembre de 2016 .
- ^ Cabrera Arteaga, Javier; Donde, Shrinish; Gu, Jian; Floros, Orestis; Satabin, Lucas; Baudry, Benoit; Monperrus, Martín (2020). "Superoptimización del código de bytes de WebAssembly". Compañero de la Conferencia de la IV Conferencia Internacional de Arte, Ciencia e Ingeniería de la Programación . Oporto Portugal: ACM: 36–40. arXiv : 2002.10213 . doi : 10.1145 / 3397537.3397567 . ISBN 978-1-4503-7507-8. S2CID 211259480 .