Tiling optimizations for stencil computations

Optimization;Tiling;Stencil Computation

Zhou, Xing

关键词: Optimization;    Tiling;    Stencil Computation;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/44340/Xing_Zhou.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

This thesis studies the techniques of tiling optimizations for stencil programs.Traditionally, research on tiling optimizations mainly focuses on tessellatingtiling, atomic tiles and regular tile shapes. This thesis studies several noveltiling techniques which are out of the scope of traditional research.In order to represent a general tiling scheme uniformly, a unified tilingrepresentation framework is introduced.With the unified tiling representation, three tiling techniques are studied.The first tiling technique is Hierarchical Overlapped Tiling, based onthe idea of reducing communication overhead by introducing redundant computations.Hierarchical Overlapped Tiling also applies the idea of hierarchical tiling totake advantage of hardware hierarchy, so that the additional overhead introducedby redundant computations can be minimized.The second tiling technique is called Conjugate-Trapezoid Tiling,which schedules the computations and communications within a tile inan interleaving way in order to overlap the computation time and communication latency.Conjugate-Trapezoid Tiling forms a pipeline of computations and communications,hence the communication latency can be hidden.Third, this thesis studies the tile shape selection problem for hierarchical tiling.It is concluded that optimaltile shape selection for hierarchical tiling is a multidimensional, nonlinear, bi-level programming problem.Experimental results show that the irregular tile shapes selected by solvingthe optimization problem have the potentialto outperform intuitive tiling shapes.