Sub-Tiling in Iterative Methods: Principles and Numerical Experiments

Abstract

we proposed and experimentally investigated a new approach to accelerating iterative methods called sub-tiling based on the ideas of conventional tiling. The new approach reuses the data loaded into the CPU cache, which significantly reduces the computation time and increases the efficiency of algorithms. The key idea is to form subtiles, or secondary tiles shifted diagonally by one node relative to the original tiles. We tested this concept using the iterative successive over-relaxation (SOR) method. The results of numerical experiments show that sub-tiling speeds up the computation by more than 5x. The paper presents an algorithm for sub-tile generation and application, and the analysis of the algorithm efficiency.