Exploitation of Stragglers in Hierarchical Coded Matrix Multiplication
Shahrzad Kianidehkordi · TSpace (University of Toronto) · 2020
In distributed computing systems slow-working nodes, known as stragglers, can greatly extend the finishing time. Coded computing is a technique that enables straggler-resistant computation. This thesis first develops a conceptual framework that unifies existing coded matrix multiplication techniques. In this framework the division of work amongst workers in different coding techniques is presented as a cuboid partitioning problem. Building on this framework, we then propose three methods of hierarchical coded computing: Bit-Interleaved Coded Computing (BICC), Multilevel Coded Computing (MLCC), and Hybrid Hierarchical Coded Computing (HHCC). In hierarchical coding the workers process a sequence (a hierarchy) of ordered subtasks and transmit per-subtask results to the master as they are completed. Such hierarchical design leads to exploit the work of stragglers and allows the fast workers to contribute even more to the overall computation. We prove both theoretically and experimentally that hierarchical coding improves the finishing time when compared with non-hierarchical coding.