2019/11/13 by Yuan Tang, Tang, Yuan, Yuan Yan Tang
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Distributed #FOS: Computer and information sciences #Parallel #Parallel Computing and Optimization Techniques #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1911.05328
openalex publication_date 2019/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Classic cache-oblivious parallel matrix multiplication algorithms achieve\noptimality either in time or space, but not both, which promotes lots of\nresearch on the best possible balance or tradeoff of such algorithms. We study\nmodern processor-oblivious runtime systems and figure out several ways to\nimprove algorithm's time bound while still bounding space and cache\nrequirements to be asymptotically optimal. By our study, we give out sublinear\ntime, optimal work, space and cache algorithms for both general matrix\nmultiplication on a semiring and Strassen-like fast algorithm. Our experiments\nalso show such algorithms have empirical advantages over classic counterparts.\nOur study provides new insights and research angles on how to optimize\ncache-oblivious parallel algorithms from both theoretical and empirical\nperspectives.\n