Superoptimization

Superoptimization is the process of finding the optimal code sequence for one, loop-free sequence of instructions. It is performed in and by a type of computer software termed a compiler. While most standard compiler optimizations only improve code partly: real-world compilers generally cannot produce genuinely optimal code. A superoptimizer's goal is to find the optimal sequence.

The term superoptimization was first coined by Alexia Massalin in her 1987 paper, Superoptimizer: a look at the smallest program.[1] In 1992, the GNU Superoptimizer (GSO) was developed to integrate into the GNU Compiler Collection (GCC).[2][3] Later work further developed and extended these ideas. In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research.[4] In 2006, answer set declarative programming was used for superoptimising in the Total Optimisation using Answer Set Technology (TOAST) project at the University of Bath,[5][6] and superoptimizing was used to automatically generate general-purpose peephole optimizers.[7]

Typically, superoptimizing is performed via exhaustive brute-force search in the space of valid instruction sequences. This is a costly method, and thus impractical for general-purpose compilers. Yet, it has been shown to be useful in optimizing performance-critical inner loops.

Publicly available superoptimizers

Superoptimizer studies, documents, and several working examples, are available for free download.

References

  1. ↑ Massalin, Henry (October 1987). "Superoptimizer: a look at the smallest program". ACM SIGOPS Operating Systems Review. 21 (4): 122–126. doi:10.1145/36204.36194. Retrieved 2 September 2016.
  2. 1 2 Granlund, Torbjörn; Kenner, Richard (July 1992). "Eliminating branches using a superoptimizer and the GNU C compiler". ACM SIGPLAN Notices. 27 (7): 341–352. doi:10.1145/143095.143146. Retrieved 3 September 2016.
  3. 1 2 "Index of /gnu/superopt". GNU Operating System. Free Software Foundation, Inc. 14 June 1995. Retrieved 3 September 2016.
  4. ↑ Joshi, Rajeev; Nelson, Greg; Randall, Keith (30 July 2001). "Denali: a goal-directed superoptimizer". Compaq Systems Research Center. HP Labs. Hewlett-Packard Co. Retrieved 2 September 2016.
  5. 1 2 Brain, Martin; Crick, Tom; De Vos, Marina; Fitch, John (17–20 August 2006). "TOAST: Applying Answer Set Programming to Superoptimisation". In Etalle, Sandro; Truszczyński, Mirosław. Logic Programming. Springer Berlin Heidelberg. pp. 270–284. ISBN 978-3-540-36636-2.
  6. 1 2 "TOAST – KRRwiki". Department of Computer Science, Mathematical Foundations Group. Knowledge Representation and Reasoning (KRR) group. University of Bath. 7 August 2007. Retrieved 3 September 2016.
  7. ↑ Bansal, Sorav; Aiken, Alex (21–25 October 2006). "Automatic Generation of Peephole Superoptimizers" (PDF). Stanford University. Computer Systems Lab, Stanford University. Retrieved 2 September 2016.
  8. ↑ Bansal, Sorav; Aiken, Alex (25 October 2006). "Binary Translation Using Peephole Superoptimizers" (PDF). Department of Computer Science. Indian Institute of Technology, Delhi. Retrieved 17 October 2016.
  9. ↑ Serpell, Daniel (2003). "SuperOptimizer for Microchip's PIC microcontrollers". Google Sites. Google. Retrieved 6 September 2016.
  10. ↑ Serpell, Daniel (21 Jun 2003). "PIC Microcontroller SuperOptimizer". Freecode. Slashdot Media. Retrieved 6 September 2016.
  11. ↑ Hume, Tom (21 August 2012). "Clojure program to exhaustively search for optimal Java programs". GitHub. GitHub, Inc. Retrieved 6 September 2016.
This article is issued from Wikipedia - version of the 10/22/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.