Collaborative Research: CCSS: Practical Coded Matrix Computation

Large scale matrix computations are at the heart of several modern technologies that are revolutionizing human life. These include, the now ubiquitous deep learning models, large language models, and scientific computing for supporting research in various domains. The sheer size of the data and models in these domains requires such computations to be performed in a distributed manner over large clusters, whereby an overall job is divided into smaller tasks. Unfortunately, these clusters often suffer from the problem of stragglers (slow or failed workers), especially when they are deployed within cloud computing platforms; this can cause an undesirable increase in the overall job execution time. The overall goal of this project is to research techniques for mitigating the effect of stragglers in the specific context of distributed matrix computations. This project will also provide training for students in the usage of cloud platforms. In addition, the project also involves outreach activities to local schools for mathematics tutoring and the creation of K-12 computer science modules. The field of coded computation uses ideas from coding theory to embed distributed matrix computation into the structure of an erasure code. Specifically, the idea is to create redundant tasks by linearly combining the input submatrices such that as long as a minimum number of workers complete their tasks, the overall job can be completed. The vast majority of prior coded matrix computation approaches are obtained by combining a large number of input submatrices. This is problematic for the practically important case of sparse input matrices as the encoding process results in dense submatrices whose product needs much higher computation time. Furthermore, much of prior work coarsely treats workers as alive or failed and does not leverage partial computations performed by slow workers. The foundational goals of this project are to investigate coded matrix computation techniques that are suitable for sparse input matrices and leverage partial work performed by slow (but not failed) workers. For dealing with sparse input matrices, the research team will adapt ideas from parity-checking in coding theory; this is however non-trivial, as the parities need to respect the computation constraints and the objectives. Moreover, the research team will design schemes that optimize a worst-case combinatorial metric for evaluating different schemes with respect to how well they leverage partial work of the slower nodes within the cluster and provide ideas on the design of schemes that address this metric. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.