Input-Dependent Autotuning

Event Date: April 26, 2013
Speaker: Maria J. Garzaran
Speaker Affiliation: Computer Science Department,
University of Illinois, Urbana-Champaign
Time: 11:00 AM
Location: EE 317
Contact Name: Professor Sam Midkiff
Contact Phone: (765) 494-3440
Contact Email:
Open To: Acceptable for ECE 694A

The growing complexity of modern processors has made the generation of highly efficient code increasingly difficult.   Manual code generation is time consuming, but it is often the only choice since the code generated by today’s compilers often has much lower performance than the best hand-tuned codes. A promising code optimization strategy, implemented by systems like ATLAS, FFTW, and SPIRAL, uses empirical search to find the parameter values of the implementation that delivers near-optimal performance for a particular machine. These autotuning systems have been quite successful and are making their way into everyday practice. An important line of research in this area is the study of autotuning mechanisms for the case when performance of the generated code depends on the input. This area has received relatively little attention since most existing systems, including the three mentioned above, handle algorithms whose performance is, or is assumed to be, independent of the input data.


In this talk, I will discuss some techniques that we have applied to generate libraries that adapt to the input. We have studied autotuning algorithms for sorting, datamining of frequent patterns, and the behavior of parallel graph algorithms. Our techniques make use of machine learning to select the best algorithm among a set of candidates or to build new hybrid algorithms. We have also studied the use of code specialization and runtime code generation for sparse computations.


Bio:  Maria J. Garzaran is a Research Assistant Professor at the Computer Science Department of the University of Illinois at Urbana-Champaign. Her research focuses on thread-level speculation, automatic performance tuning, parallel programming, compilation, and reliability. She has published in some of the most selective conferences in these areas, such as PLDI, HPCA, ISCA, PPoPP, PACT, and CGO. She was Program Co-Chair of the 2007 Workshop on Languages and Compilers for Parallel Computing (LCPC). She received a Ph.D. from Universidad de Zaragoza, Spain, in 2002. She is also the recipient of the 2002 Best PhD Thesis Award from Universidad de Zaragoza. She is IEEE Member and  Senior Member of ACM.