Scaling up Superoptimization

Abstract

Developing a code optimizer is challenging, especially for new, idiosyncratic ISAs. Superoptimization can, in principle, discover machine-specific optimizations automatically by searching the space of all instruction sequences. If we can increase the size of code fragments a superoptimizer can optimize, we will be able to discover more optimizations. We develop LENS, a search algorithm that increases the size of code a superoptimizer can synthesize by rapidly pruning away invalid candidate programs. Pruning is achieved by selectively refining the abstraction under which candidates are considered equivalent, only in the promising part of the candidate space. LENS also uses a bidirectional search strategy to prune the candidate space from both forward and backward directions. These pruning strategies allow LENS to solve twice as many benchmarks as existing enumerative search algorithms, while LENS is about 11-times faster.

Document Details

Document Type
Pub Defense Publication
Publication Date
Mar 25, 2016
Source ID
10.1145/2954679.2872387

Entities

People

  • Aditya Thakur
  • Dinakar Dhurjati
  • Phitchaya Mangpo Phothilimthana
  • Rastislav Bodík

Organizations

  • Defense Advanced Research Projects Agency
  • Google
  • National Science Foundation
  • Office of Science
  • Savannah River Operations Office
  • University of California, Berkeley
  • University of Washington

Tags

Fields of Study

  • Computer science

Readers

  • Artificial Intelligence
  • Operations Research

Technology Areas

  • Space
  • Space - Space Objects