Cache-Aided Matrix Multiplication Retrieval

DOI10.1109/TIT.2022.3157835MaRDI QIDQ5088555zbMATH OpenOpenAlexWikidataFDO

Authors Kai Wan, Hua Sun, Mingyue Ji, Daniela Tuninetti, Giuseppe Caire

Publication date 13 July 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.00856

zbMATH Keywords

cache-aided matrix multiplication retrieval problem

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: Coded caching is a promising technique to smooth out network traffic by storing part of the library content at the users' local caches. The seminal work on coded caching for single file retrieval by Maddah-Ali and Niesen (MAN) showed the existence of a global caching gain that scales with the total memory in the system, in addition to the known local caching gain in uncoded systems. This paper formulates a novel cache-aided matrix multiplication retrieval problem, relevant for data analytics and machine learning applications. In the considered problem, each cache-aided user requests the product of two matrices from the library. A structure-agnostic solution is to treat each possible matrix product as an independent file and use the MAN coded caching scheme for single file retrieval. This paper proposes two structure-aware schemes, which partition each matrix in the library by either rows or columns and let a subset of users cache some sub-matrices, that improve on the structure-agnostic scheme. For the case where the library matrices are "fat" matrices, the structure-aware row-partition scheme is shown to be order optimal under some constraint.

Recommendations

• A memetic algorithm to schedule planned maintenance for the national grid
• Cache friendly sparse matrix-vector multiplication
• Cache oblivious sparse matrix multiplication
• The combinatorics of cache misses during matrix multiplication
• Cache-Oblivious Sparse Matrix–Vector Multiplication by Using Sparse Matrix Partitioning Methods
• scientific article; zbMATH DE number 1728267
• Cache oblivious matrix multiplication using an element ordering based on a Peano curve
• On practical algorithms for accelerated matrix multiplication
• Parallel and cache-efficient in-place matrix storage format conversion

Cited in

(4)

• Cache-efficient renumbering for vectorization
• On the Limits of Cache-Oblivious Matrix Transposition
• On the Optimal Load-Memory Tradeoff of Cache-Aided Scalar Linear Function Retrieval
• Parallel Processing and Applied Mathematics

This page was built for publication: Cache-Aided Matrix Multiplication Retrieval

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088555)