ABSTRACT

The growing complexity of modern processors has made the generation of highly ef?cient code increasingly dif?cult. 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 ?nd 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.

Més informació