2014 Poster Sessions : Stochastic Optimization of x86-64 BinariesAbstract: The aggressive optimization of short sequences of loop-free fixed-point 64-bit x86 code sequences is an important problem in high-performance computing. Unfortunately, the competing constraints of trans

Student Name : Eric Schkufza
Advisor : Alex Aiken
Research Areas: Theory
Abstract:
The aggressive optimization of short sequences of loop-free fixed-point 64-bit x86 code sequences is an important problem in high-performance computing. Unfortunately, the competing constraints of transformation correctness and performance improvement often force even special purpose compilers to produce sub-optimal code. We show that by encoding these constraints as terms in a cost function, and using a Markov Chain Monte Carlo sampler to rapidly explore the space of all possible programs, we are able to rapidly generate aggressively optimized versions of a given target program. Beginning from binaries compiled by gcc -O0, we are able to produce provably correct code sequences that either match or outperform the code produced by gcc -O3, and in some cases, expert hand-written assembly.

Because most high-performance applications contain loops and floating-point computations, we extend our technique to both domains. We demonstrate the ability to generate reduced precision implementations of Intel's handwritten C numerics library which are up to six times faster than the original code, and achieve end-to-end speedups of over 30% on a direct numeric simulation and a ray tracer by optimizing kernels that can tolerate a loss of precision while still remaining correct. Because optimizations that contain loops and floating-point computations are not amenable to formal verification using the state of the art, we present techniques for characterizing maximum error, and in some cases obtaining a proof of formal equivalence.

Bio:
Eric Schkufza is a sixth year computer science PhD candidate at Stanford University advised by Professor Alex Aiken. His research is focused on the application of stochastic search and machine learning techniques to the design of optimizing compilers for high-performance computation.