Login
Computer Science @ Rochester
Monday, November 25, 2002
11:00 AM
CSB 209
David Padua
U. Illinois, Urbana-Champaign
Empirical Search and Architectural Models in Program Generation and Optimization
Despite more than five decades of compiler research, hand-tweaked code often outperforms the code generated by the best optimizing compilers to the point that assembly is, in some cases, the language of choice for certain architectures and applications.

Part of the problem is that, although program analysis and transformation are well-understood subjects, there is no reliable method for selecting from the astronomical number of possible transformation sequences. A strategy that has proven successful in the automatic generation of high-quality libraries is to execute on the target machine many different forms of the code to be generated and select the fastest. The total number of forms is usually too large for an exhaustive search and, therefore, simple heuristics and intelligent search strategies must be used. Systems that follow this approach include ATLAS, FFTW, and Spiral.

It has been suggested that this empirical search approach can be transplanted to conventional optimizing compilers. However, executing many versions of the target code tends to be expensive and the measured performance does not necessarily represent the performance of the code for all possible input data sets. The use of architectural models to evaluate performance and guide the search could help overcome this difficulty. In this talk, I will discuss our experience with library generators and the use of architectural models as a replacement of empirical models.