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.

[img]
Preview
PDF
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
Related URLs:

    Abstract

    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: 17 Apr 2018 21:43
    URI: http://shura.shu.ac.uk/id/eprint/18360

    Actions (login required)

    View Item View Item

    Downloads

    Downloads per month over past year

    View more statistics