Fast searches for effective optimization phase sequences

Prasad Kulkarni, Stephen Hines, Jason Hiser, David Whalley, Jack Davidson, Douglas Jones

Research output: Contribution to conferencePaper

Abstract

It has long been known that a fixed ordering of optimization phases will not produce the best code for every application. One approach for addressing this phase ordering problem is to use an evolutionary algorithm to search for a specific sequence of phases for each module or function. While such searches have been shown to produce more efficient code, the approach can be extremely slow because the application is compiled and executed to evaluate each sequence's effectiveness. Consequently, evolutionary or iterative compilation schemes have been promoted for compilation systems targeting embedded applications where longer compilation times may be tolerated in the final stage of development. In this paper we describe two complementary general approaches for achieving faster searches for effective optimization sequences when using a genetic algorithm. The first approach reduces the search time by avoiding unnecessary executions of the application when possible. Results indicate search time reductions of 65% on average, often reducing searches from hours to minutes. The second approach modifies the search so fewer generations are required to achieve the same results. Measurements show that the average number of required generations decreased by 68%. These improvements have the potential for making evolutionary compilation a viable choice for tuning embedded applications.

Original languageEnglish (US)
Pages171-182
Number of pages12
DOIs
StatePublished - Jan 1 2004
EventProceedings of the 2004 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'04) - Washington, DC, United States
Duration: Jun 9 2004Jun 11 2004

Other

OtherProceedings of the 2004 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'04)
CountryUnited States
CityWashington, DC
Period6/9/046/11/04

Keywords

  • Genetic algorithms
  • Interactive compilation
  • Phase ordering

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Fast searches for effective optimization phase sequences'. Together they form a unique fingerprint.

  • Cite this

    Kulkarni, P., Hines, S., Hiser, J., Whalley, D., Davidson, J., & Jones, D. (2004). Fast searches for effective optimization phase sequences. 171-182. Paper presented at Proceedings of the 2004 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'04), Washington, DC, United States. https://doi.org/10.1145/996841.996863