2020/02/28 by Grace Dinh, Dinh, Grace, James Demmel +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Matrix Theory and Algorithms #Parallel Computing and Optimization Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2003.00119
openalex publication_date 2020/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Reducing communication - either between levels of a memory hierarchy or\nbetween processors over a network - is a key component of performance\noptimization (in both time and energy) for many problems, including dense\nlinear algebra, particle interactions, and machine learning. For these\nproblems, which can be represented as nested-loop computations, previous tiling\nbased approaches have been used to find both lower bounds on the communication\nrequired to execute them and optimal rearrangements, or blockings, to attain\nsuch lower bounds. However, such general approaches have typically assumed the\nproblem sizes are large, an assumption that is often not met in practice. For\ninstance, the classical (# arithmetic operations)/(\cache\nsize)1/2 lower bound for matrix multiplication is not tight for\nmatrix-vector multiplications, which must read in at least O(#\narithmetic operations) words of memory; similar issues occur for almost all\nconvolutions in machine learning applications, which use extremely small filter\nsizes (and therefore, loop bounds).\n In this paper, we provide an efficient way to both find and obtain, via an\nappropriate, efficiently constructible blocking, communication lower bounds and\nmatching tilings which attain these lower bounds for nested loop programs with\narbitrary loop bounds that operate on multidimensional arrays in the projective\ncase, where the array indices are subsets of the loop indices. Our approach\nworks on all such problems, regardless of dimensionality, size, memory access\npatterns, or number of arrays, and directly applies to (among other examples)\nmatrix multiplication and similar dense linear algebra operations, tensor\ncontractions, n-body pairwise interactions, pointwise convolutions, and fully\nconnected layers.\n