A methodology for speeding up loop kernels by exploiting the software information and the memory architecture

KELEFOURAS, Vasileios, KRITIKAKOU, Angeliki and GOUTIS, Costas (2015). A methodology for speeding up loop kernels by exploiting the software information and the memory architecture. Computer Languages Systems and Structures, 41, 21-41.

Kelefouras-MethodologyForSpeedingUpLoopKernals(AM).pdf - Accepted Version
All rights reserved.

Download (3MB) | Preview
Official URL: https://www.sciencedirect.com/science/article/pii/...
Link to published version:: https://doi.org/10.1016/j.cl.2015.01.003


It is well-known that today׳s compilers and state of the art libraries have three major drawbacks. First, the compiler sub-problems are optimized separately; this is not efficient because the separate sub-problems optimization gives a different schedule for each sub-problem and these schedules cannot coexist as the refining of one, causes the degradation of another. Second, they take into account only part of the specific algorithm׳s information. Third, they take into account only a few hardware architecture parameters. These approaches cannot give an optimal solution. In this paper, a new methodology/pre-compiler is introduced, which speeds up loop kernels, by overcoming the above problems. This methodology solves four of the major scheduling sub-problems, together as one problem and not separately; these are the sub-problems of finding the schedules with the minimum numbers of (i) L1 data cache accesses, (ii) L2 data cache accesses, (iii) main memory data accesses, (iv) addressing instructions. First, the exploration space (possible solutions) is found according to the algorithm׳s information, e.g. array subscripts. Then, the exploration space is decreased by orders of magnitude, by applying constraint propagation to the software and hardware parameters. We take the C-code and the memory architecture parameters as input and we automatically produce a new faster C-code; this code cannot be obtained by applying the existing compiler transformations to the original code. The proposed methodology has been evaluated for five well-known algorithms in both general and embedded processors; it is compared with gcc and clang compilers and also with iterative compilation.

Item Type: Article
Uncontrolled Keywords: Data locality, Data reuse, Diophantine equations, Loop tiling, Memory hierarchy, Optimization, Register allocation
Departments - Does NOT include content added after October 2018: Faculty of Science, Technology and Arts > Department of Computing
Identification Number: https://doi.org/10.1016/j.cl.2015.01.003
Page Range: 21-41
Depositing User: Vasileios Kelefouras
Date Deposited: 27 Mar 2018 10:47
Last Modified: 18 Mar 2021 15:19
URI: https://shura.shu.ac.uk/id/eprint/18360

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics