2019/11/15 by Auguste Olivry, Olivry, Auguste, Julien Langou +7 · 1 citation
Computer Science · #Parallel Computing and Optimization Techniques #Distributed and Parallel Computing Systems #Numerical Methods and Algorithms
paper · pdf · doi:10.48550/arxiv.1911.06664
For most relevant computation, the energy and time needed for data movement\ndominates that for performing arithmetic operations on all computing systems\ntoday. Hence it is of critical importance to understand the minimal total data\nmovement achievable during the execution of an algorithm. The achieved total\ndata movement for different schedules of an algorithm can vary widely depending\non how efficiently the cache is used, e.g., untiled versus effectively tiled\nmatrix-matrix multiplication. A significant current challenge is that no\nexisting tool is able to meaningfully quantify the potential reduction to the\ndata movement of a computation that can be achieved by more effective use of\nthe cache through operation rescheduling. Asymptotic parametric expressions of\ndata movement lower bounds have previously been manually derived for a limited\nnumber of algorithms, often without scaling constants. In this paper, we\npresent the first compile-time approach for deriving non-asymptotic parametric\nexpressions of data movement lower bounds for arbitrary affine computations.\nThe approach has been implemented in a fully automatic tool (IOLB) that can\ngenerate these lower bounds for input affine programs.\n IOLB's use is demonstrated by exercising it on all the benchmarks of the\nPolyBench suite. The advantages of IOLB are many: (1) IOLB enables us to derive\nbounds for few dozens of algorithms for which these lower bounds have never\nbeen derived. This reflects an increase of productivity by automation. (2)\nAnyone is able to obtain these lower bounds through IOLB, no expertise is\nrequired. (3) For some of the most well-studied algorithms, the lower bounds\nobtained by tool are higher than any previously reported manually derived\nlower bounds.\n