Analytical bounds for optimal tile size selection

Abstract. In this paper, we introduce a novel approach to guide tile size se-lection by employing analytical models to limit empirical search within a sub-space of the full search space. Two analytical models are used together: 1) an existing conservative model, based on the data footprint of a tile, which ignores intra-tile cache block replacement, and 2) an aggressive new model that assumes optimal cache block replacement within a tile. Experimental results on multiple platforms demonstrate the practical effectiveness of the approach by reducing the search space for the optimal tile size by 1,307 × to 11,879 × for an Intel Core-2-Quad system; 358 × to 1,978 × for an Intel Nehalem system; and 45 × to 1,142× for an IBM Power7 system. The execution of rectangularly tiled code tuned by a search of the subspace identified by our model achieves speed-ups of up to 1.40 × (Intel Core-2 Quad), 1.28 × (Nehalem) and 1.19 × (Power 7) relative to the best possible square tile sizes on these different processor architectures. We also demonstrate the integration of the analytical bounds with existing search op-timization algorithms. Our approach not only reduces the total search time from Nelder-Mead Simplex and Parallel Rank Ordering methods by factors of up to 4.95 × and 4.33×, respectively, but also finds better tile sizes that yield higher performance in tuned tiled code.