On the role of search in generating high-performance BLAS libraries.

摘要

A key step in program optimization is the estimation of optimal values for parameters such as tile sizes and loop unrolling factors. Traditional compilers use simple analytical models to compute these values. In contrast, library generators like ATLAS use global search over the space of parameter values by generating programs with many different combinations of parameter values, and running them on the actual hardware to determine which values give the best performance. It is widely believed that traditional model-driven optimization cannot compete with search-based empirical optimization because tractable analytical models cannot capture all the complexities of modern high-performance architectures. This thesis disproves this belief.; In this work we replaced the global search engine in ATLAS with a model-driven optimization engine, and measured the relative performance of the code produced by the two systems on a variety of architectures. Our experiments show that model-driven optimization can be surprisingly effective., and can generate code with performance comparable to that of code generated by ATLAS using global search. For improving the code further, we advocate complementing modelling with local search and model refinement.; Model-driven optimization needs accurate values of hardware parameters. In this thesis we also describe X-Ray, a robust framework of micro-benchmark for measuring such hardware parameters. X-Ray is designed to be extensible to make it easy to implement new micro-benchmarks. We have developed novel algorithms for measuring hardware parameters commonly used in optimizing software performance, and we have implemented them in X-Ray. We evaluate X-Ray experimentally on traditional workstations and servers as well as on embedded architectures, and show that it produces more accurate and complete results than existing tools.