Date of Degree
Digital Communications and Networking
distributed computing, erasure coding, matrix multiplication
Matrix multiplication is a fundamental building block in many machine learning models. As the input matrices may be too large to be multiplied on a single server, it is common to split input matrices into multiple sub-matrices and execute the multiplications on different servers. However, in a distributed infrastructure, it is common to observe stragglers whose performance is significantly lower than other servers at some time. Compared to replicating each task on multiple servers, coded matrix multiplication, i.e., a combination of coding theoretic techniques and distributed matrix multiplication, can tolerate the same number of stragglers with much fewer servers. The recent years have witnessed the fast development of research in coded matrix multiplication. Coding schemes have been proposed to achieve the optimal recovery threshold, communication, and computation; leverage resource from stragglers; perform secure and private matrix multiplication. Also, coded matrix multiplication is applied in gradient descent and machine learning models.
In this dissertation, we propose a coding scheme for the matrix chain multiplication with a general number of matrices multiplied, which allows completing the chain multiplication in one single round. Then, we present Spinner, a framework for coded distributed matrix multiplication where we exploit the partial results of tasks on stragglers in a heterogeneous cluster. At last, we introduce ε-local coding that can adjust the encoding locality of the parity data sub-tasks, and it can leverage partial results returned by the straggling nodes and has better encoding complexity than existing coding schemes.
Fan, Xiaodi, "Coded Matrix Multiplication" (2022). CUNY Academic Works.
This work is embargoed and will be available for download on Saturday, September 30, 2023
Graduate Center users:
To read this work, log in to your GC ILL account and place a thesis request.
See the GC’s lending policies to learn more.