The effect of cache models on iterative compilation for combined tiling and unrolling

Peter M. W. Knijnenburg, Toru Kisuki, Kyle Gallivan, Michael F. P. O'Boyle

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Iterative compilation, where we search for the best program transformation based on profile feedback information, has been highly successful in determining good program optimizations, typically outperforming all static approaches. However, this benefit has come at a price, namely, a large number of executions of the target program which in many cases is unacceptable. This paper is concerned with reducing the number of program executions needed by iterative compilation by incorporating static models. We examine how static models may be incorporated into a purely iterative approach by developing several characterized heuristics. We empirically explore the tradeoff between reducing the number of executions required and the ultimate performance achieved for differing parameters or slack factors. We focus on tiling and unrolling as transformations and cache models as a test case for the feasibility of this approach. We show that a highly accurate model, used as a filter to profiling and appropriately parameterized, can reduce the number of executions by 50%. We also show that using a simple model to rank transformations and profiling, only those with the highest ranking can reduce the number of executions even further up to 70%, in cases where there is only a limited number of profiles available. We conclude that a production compiler might perform best using the last approach, gaining the benefit of iterative compilation at a much reduced cost.
Original languageEnglish
Pages (from-to)247-270
Number of pages24
JournalConcurrency and Computation: Practice and Experience
Issue number2-3
Publication statusPublished - 7 Jan 2004


Dive into the research topics of 'The effect of cache models on iterative compilation for combined tiling and unrolling'. Together they form a unique fingerprint.

Cite this