Timezone: »

Dual Entangled Polynomial Code: Three-Dimensional Coding for Distributed Matrix Multiplication
Pedro Soto · Jun Li · Xiaodi Fan

Tue Jun 11 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #164

Matrix multiplication is a fundamental building block in various machine learning algorithms. When the matrix comes from a large dataset, the multiplication can be split into multiple tasks which calculate the multiplication of submatrices on different nodes. As some nodes may be stragglers, coding schemes have been proposed to tolerate stragglers in such distributed matrix multiplication. However, existing coding schemes typically split the matrices in only one or two dimensions, limiting their capabilities to handle large-scale matrix multiplication. Three-dimensional coding, however, does not have any code construction that achieves the optimal number of tasks required for decoding, with the best result achieved by entangled polynomial (EP) codes. In this paper, we propose dual entangled polynomial (DEP) codes that require around 25% fewer tasks than EP codes by executing two matrix multiplications on each task. With experiments in a real cloud environment, we show that DEP codes can also save the decoding overhead and memory consumption of tasks.

Author Information

Pedro Soto (Florida International University)
Jun Li (Florida International University)
Xiaodi Fan (Florida International University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors

  • 2019 : Poster Session I »
    Stark Draper · Mehmet Aktas · Basak Guler · Hongyi Wang · Venkata Gandikota · Hyegyeong Park · Jinhyun So · Lev Tauz · hema venkata krishna giri Narra · Zhifeng Lin · Mohammadali Maddahali · Yaoqing Yang · Sanghamitra Dutta · Amirhossein Reisizadeh · Jianyu Wang · Eren Balevi · Siddharth Jain · Paul McVay · Michael Rudow · Pedro Soto · Jun Li · Adarsh Subramaniam · Umut Demirhan · Vipul Gupta · Deniz Oktay · Leighton P Barnes · Johannes BallĂ© · Farzin Haddadpour · Haewon Jeong · Rong-Rong Chen · Mohammad Fahim