초최적화

Superoptimization

초최적화는 하나의 루프가 없는 명령 시퀀스에 대해 최적의 코드 시퀀스를 자동으로 찾아내는 과정이다.그것은 컴파일러라고 불리는 컴퓨터 소프트웨어의 종류와 안에서 수행된다.실제 컴파일러는 일반적으로 진정으로 최적의 코드를 만들 수 없다.대부분의 표준 컴파일러 최적화는 부분적으로만 코드를 개선하지만, 슈퍼 옵티마이저의 목표는 최적의 순서인 표준 형태를 찾는 것이다.초최적화기는 인간이 추가 규칙을 작성할 수 있도록 놓친 기회를 강조함으로써 기존의 최적화를 개선하는 데 사용될 수 있다.

역사

초최적화라는 용어는 1987년 논문 슈퍼최적화기: A Look at the Smally Program에서 알렉시아 마살린에 의해 처음 만들어졌다.[1]1992년에는 GNU 슈퍼최적화기(GSO)가 개발되어 GNU 컴파일러 컬렉션(GCC)에 통합되었다.[2][3]이후 작업은 이러한 아이디어를 더욱 발전시키고 확장시켰다.

기술

일반적으로 초최적화는 유효한 명령 시퀀스 공간에서 철저한 브루트 포스 검색을 통해 수행된다.이것은 비용이 많이 드는 방법이며, 따라서 범용 컴파일러에게는 비실용적이다.그러나, 그것은 성능에 중요한 내부 루프를 최적화하는 데 유용한 것으로 밝혀졌다.시만텍 해결사를 활용해 문제에 접근하는 것도 가능하다.

2001년에는 콤팩 리서치에 의해 데날리 프로젝트에서 목표 지향적인 초최적화가 입증되었다.[4]2006년에는 배스 대학의 TOAST(응답 세트 기술) 프로젝트를 이용한 Total Optimization에서 초최적화를 위해 응답 세트 선언 프로그래밍을 사용하였다.[5][6]

초최적화를 사용하여 범용 핍홀 최적화기를 자동으로 생성할 수 있다.[7]

공개적으로 사용할 수 있는 수퍼최적화 프로그램

몇 가지 수퍼 옵티마이저를 무료로 다운로드할 수 있다.

참고 항목

참조

  1. ^ Massalin, Henry (1987). "Superoptimizer: A look at the smallest program" (PDF). ACM SIGARCH Computer Architecture News. 15 (5): 122–126. doi:10.1145/36177.36194. Archived (PDF) from the original on 2017-07-04. Retrieved 2012-04-25. Given an instruction set, the superoptimizer finds the shortest program to compute a function. Startling programs have been generated, many of them engaging in convoluted bit-fiddling bearing little resemblance to the source programs which defined the functions. The key idea in the superoptimizer is a probabilistic test that makes exhaustive searches practical for programs of useful size.
  2. ^ a b Granlund, Torbjörn; Kenner, Richard (July 1992). "Eliminating branches using a superoptimizer and the GNU C compiler". ACM SIGPLAN Notices. 27 (7): 341–352. CiteSeerX 10.1.1.58.3509. doi:10.1145/143095.143146. ISBN 978-0-89791475-8. S2CID 8825539.
  3. ^ a b "Index of /gnu/superopt". GNU Operating System. Free Software Foundation, Inc. 1995-06-14. Archived from the original on 2016-09-11. Retrieved 2016-09-03.
  4. ^ Joshi, Rajeev; Nelson, Greg; Randall, Keith (2001-07-30). "Denali: a goal-directed superoptimizer". Compaq Systems Research Center. HP Labs. Hewlett-Packard Co. Archived from the original on 2016-05-27. Retrieved 2016-09-02.
  5. ^ Brain, Martin; Crick, Tom; De Vos, Marina; Fitch, John (2006-08-17). "TOAST: Applying Answer Set Programming to Superoptimisation". In Etalle, Sandro; Truszczyński, Mirosław (eds.). Logic Programming. Springer-Verlag, Berlin / Heidelberg. pp. 270–284. ISBN 978-3-540-36636-2.
  6. ^ "TOAST – KRRwiki". Department of Computer Science, Mathematical Foundations Group. Knowledge Representation and Reasoning (KRR) group. University of Bath. 2007-08-07. Archived from the original on 2012-11-28. Retrieved 2016-09-03.
  7. ^ Bansal, Sorav; Aiken, Alex (2006-10-21). "Automatic Generation of Peephole Superoptimizers" (PDF). Stanford University. Computer Systems Lab, Stanford University. Archived (PDF) from the original on 2016-06-11. Retrieved 2016-09-02.
  8. ^ Bansal, Sorav; Aiken, Alex (2006-10-25). "Binary Translation Using Peephole Superoptimizers" (PDF). Department of Computer Science. Indian Institute of Technology, Delhi. Archived (PDF) from the original on 2016-09-08. Retrieved 2016-10-17.
  9. ^ Serpell, Daniel (2003). "SuperOptimizer for Microchip's PIC microcontrollers". Google Sites. Archived from the original on 2016-10-11. Retrieved 2016-09-06.
  10. ^ Serpell, Daniel (2003-06-21). "PIC Microcontroller SuperOptimizer". Freecode. Slashdot Media. Archived from the original on 2016-09-17. Retrieved 2016-09-06.
  11. ^ Hume, Tom (2012-08-21). "Clojure program to exhaustively search for optimal Java programs". GitHub. Archived from the original on 2018-06-10. Retrieved 2016-09-06.
  12. ^ Cabrera Arteaga, Javier; Donde, Shrinish; Gu, Jian; Floros, Orestis; Satabin, Lucas; Baudry, Benoit; Monperrus, Martin (2020). "Superoptimization of WebAssembly bytecode". Conference Companion of the 4th International Conference on Art, Science, and Engineering of Programming. Porto Portugal: ACM: 36–40. arXiv:2002.10213. doi:10.1145/3397537.3397567. ISBN 978-1-4503-7507-8. S2CID 211259480.