All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD6-S6-T1.1
Paper Title Cache-Aided Matrix Multiplication Retrieval
Authors Kai Wan, Technische Universität Berlin, Germany; Hua Sun, University of North Texas, United States; Mingyue Ji, University of Utah, United States; Daniela Tuninetti, University of Illinois at Chicago, United States; Giuseppe Caire, Technische Universität Berlin, Germany
Session D6-S6-T1: Coded Caching for Computing
Chaired Session: Monday, 19 July, 23:40 - 00:00
Engagement Session: Tuesday, 20 July, 00:00 - 00:20
Abstract This paper formulates the shared-link cache-aided matrix multiplication retrieval problem. Matrix multiplication is an essential building block for distributed computing applications. Different from the original coded caching single file retrieval model, in the considered problem each cache-aided user requests the product of two matrices from a library that contains N matrices. A trivial solution, agnostic to the structure of matrix multiplication, is to treat each of the N^2 possible matrix products as a file in the original single file retrieval coded caching problem. Such a solution can be improved by leveraging the correlation among the entries in the matrix product. In this paper, two structure-aware schemes are proposed, which partition each library matrix either by rows or by columns, and let a subset of users cache some sub-matrices; in the delivery, coded multicast messages are created to leverage the cached content and the correlation among the entries in the requested matrix products. These schemes outperform two baseline schemes, where one sends packets without coding and the other lets each user directly recover the two input matrices. Order optimality results are derived in some parameter regimes.