Doctoral Thesis: Autotuning Programs with Algorithmic Choice


Event Speaker: 

Jason Ansel

Event Location: 

32-D463 (Star Room)

Event Date/Time: 

Wednesday, December 18, 2013 - 2:00pm


The process of optimizing programs and libraries, both for performance
and quality of service, can be viewed as a search problem over the
space of implementation choices.  This search is traditionally
manually conducted by the programmer and often must be repeated when
systems, tools, or requirements change.  The overriding goal of this
work is to automate this search so that programs can change themselves
and adapt to work optimally in different environments and to conform
to different requirements.  To achieve this, first, this work presents
the PetaBricks programming language which focuses on ways for
expressing program implementation search spaces at the language level.
Second, this work presents OpenTuner which provides sophisticated
techniques for searching these search spaces in a way that can easily
be adopted by other projects.

PetaBricks is a implicitly parallel language and compiler where having
multiple implementations of multiple algorithms to solve a problem is
the natural way of programming.  Choices are provided in a way that
also allows our compiler to tune at a finer granularity.  The
PetaBricks compiler autotunes programs by making both fine-grained as
well as algorithmic choices.  Choices also include different automatic
parallelization techniques, data distributions, algorithmic
parameters, transformations, and blocking.  PetaBricks also introduces
novel techniques to autotune algorithms for different convergence
criteria or quality of service requirements.  We show that the
PetaBricks autotuner is often able to find non-intuitive
poly-algorithms that outperform more traditional hand written

OpenTuner is a new open source framework for building domain-specific
multi-objective program autotuners. OpenTuner supports
fully-customizable configuration representations, an extensible
technique representation to allow for domain-specific techniques, and
an easy to use interface for communicating with the program to be
autotuned. A key capability inside OpenTuner is the use of ensembles
of disparate search techniques simultaneously; techniques that perform
well will dynamically be allocated a larger proportion of tests.
OpenTuner has been shown to perform well on complex search spaces up
to 10^3000 possible configurations in size.
Thesis Supervisor: Saman Amarasinghe