2021/08/26 by Stefano Zampini, Boukaram, Wajih, Zampini, Stefano +5
Computer Science · Engineering · Mathematics · Physics and Astronomy · #65F05 #65F08 #65F55 #Distributed #Electromagnetic Scattering and Analysis #FOS: Computer and information sciences #G.4 #Mathematical Software (cs.MS) #Parallel #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2108.11932
openalex publication_date 2021/08/26 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Tile low rank representations of dense matrices partition them into blocks of\nroughly uniform size, where each off-diagonal tile is compressed and stored as\nits own low rank factorization. They offer an attractive representation for\nmany data-sparse dense operators that appear in practical applications, where\nsubstantial compression and a much smaller memory footprint can be achieved.\nTLR matrices are a compromise between the simplicity of a regular\nperfectly-strided data structure and the optimal complexity of the unbalanced\ntrees of hierarchically low rank matrices, and provide a convenient\nperformance-tuning parameter through their tile size that can be proportioned\nto take into account the cache size where the tiles reside in the memory\nhierarchy.\n There are currently no high-performance algorithms that can generate Cholesky\nand LDLT factorizations, particularly on GPUs. The difficulties in achieving\nhigh performance when factoring TLR matrices come from the expensive\ncompression operations that must be performed during the factorization process\nand the adaptive rank distribution of the tiles that causes an irregular work\npattern for the processing cores. In this work, we develop a dynamic batching\noperation and combine it with batched adaptive randomized approximations to\nachieve high performance both on GPUs and CPUs.\n Our implementation attains over 1.2 TFLOP/s in double precision on the V100\nGPU, and is limited by the performance of batched GEMM operations. The Cholesky\nfactorization of covariance matrix of size N = 131K arising in spatial\nstatistics can be factored to an accuracy \ε=10-2 in just a few\nseconds. We believe the proposed GEMM-centric algorithm allows it to be readily\nported to newer hardware such as the tensor cores that are optimized for small\nGEMM operations.\n