Impact of Tile-Size Selection for Skewed Tiling

Tile-size selection is known to be a complex problem. Thjs paper develops a new selecbion algorithm. Unlike previous algorithms, this new algorithm considers the effect of loop skewing on cache miss-. It also estimates loop overhead and incorporates them into the execution cost model, which turns out to be critical to the decision between tiling a single loop level vs. tiling two loop levels. Our preliminary experimental results sliow a significant impact of these pre\lously ignored issues on the execution time of tiled loops. In our experiments, we measured the cache miss rate and the execution time of five benchmark programs on a single processor and we compared ow algorithm with previous algorithms. Our algorithm achieves an average speedup of 1.27 to 1.63 over all the other algorithms.