- author = "Eric Schkufza",
- title = "Stochastic program optimization for x86-64 binaries",
- school = "Computer Science, Stanford University",
- year = "2015",
- address = "USA",
- month = aug,
- keywords = "genetic algorithms, genetic programming, SBSE",
-
URL = "
http://purl.stanford.edu/fw184nf4136",
-
URL = "
http://theory.stanford.edu/~aiken/publications/theses/schkufza.pdf",
-
video_url = "https://www.youtube.com/watch?v=aD9mZDJzb58",
- size = "106 pages",
- abstract = "The optimization of short sequences of loop-free fixed-point x86_64 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 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 floating-point computations, we extend our technique to this domain and show a novel approach to trading full floating-point precision for further increases in performance. We demonstrate the ability to generate reduced precision implementations of Intel's handwritten C numerics library that are up to six times faster than the original code, and achieve end-to-end speedups of over 30percent on a direct numeric simulation and a ray tracer. Because optimisations that contain floating-point computations are not amenable to formal verification using the state of the art, we present a technique for characterizing maximum error and providing strong evidence for correctness.",
-
notes = "p1 Chapter 1 Introduction This thesis is about the
aggressive optimization of high-performance code. We
describe a non-traditional approach to the problem and
focus on application domains where every choice of
instruction and register matters. The key result of
this work is that the high volume application of small
random transformations is sufficient for producing very
highly optimized code sequences that are capable of
outperforming both the code produced by production
compilers, and in many cases expert hand-written
assembly.
p2 'in Chapter 2 where we reformulate the competing constraints of correctness and performance improvement as terms in a cost function defined over the space of all code sequences, and re-characterise the optimization task as a cost minimization problem.'
Supervisor: Alexander Aiken",
