LT Codes with Feedback: Accelerate the Distributed Matrix-Vector Multiplication with Stragglers

被引：0
作者：
Yang, Xiao [1 ]
Jiang, Ming [1 ,2 ]
Zhao, Chunming [1 ,2 ]
机构：
[1] Southeast Univ, Natl Mobile Commun Res Lab, Nanjing, Peoples R China
[2] Purple Mt Lab, Nanjing, Peoples R China
来源：
2019 IEEE 38TH INTERNATIONAL PERFORMANCE COMPUTING AND COMMUNICATIONS CONFERENCE (IPCCC) | 2019年
基金：
中国国家自然科学基金;
关键词：
rateless feedback codes; distributed computation; stragglers;
D O I：
10.1109/ipccc47392.2019.8958745
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper, we propose a coding scheme for distributed matrix-vector multiplication that builds upon the Luby transform (LT) codes with feedback. The ideal soliton distribution is utilized in our LT coding scheme to encode the sub-matrices. Besides, the belief propagation (BP) decoding algorithm is modified to cooperate with the feedback information. Compared with other coded distributed computations with straggling servers, our approach achieves lower computation latency when the overall delay incurred by the encoding, mapping and decoding process is considered. Furthermore, we compare the storage loads of different schemes and show that the LT coding with feedback has a strong comparative advantage in these straggler-tolerant computation scenarios.
引用
收藏
页数：6
相关论文
共 17 条
[1]  
Abhinav K., 2006, P SIGCOMM COMPUT COM, V36
[2]  
Andrew H., 2009, P IEEE INFOCOM
[3]  
Arnold BC, 2008, CLASS APPL MATH, V54, P1
[4]   RT oblivious erasure correcting [J].
Beimel, Amos ;
Dolev, Shlomi ;
Singer, Noam .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2007, 15 (06) :1321-1332
[5]   Data-intensive applications, challenges, techniques and technologies: A survey on Big Data [J].
Chen, C. L. Philip ;
Zhang, Chun-Yang .
INFORMATION SCIENCES, 2014, 275 :314-347
[6]   The Tail at Scale [J].
Dean, Jeffrey ;
Barroso, Luiz Andre .
COMMUNICATIONS OF THE ACM, 2013, 56 (02) :74-80
[7]   Speeding Up Distributed Machine Learning Using Codes [J].
Lee, Kangwook ;
Lam, Maximilian ;
Pedarsani, Ramtin ;
Papailiopoulos, Dimitris ;
Ramchandran, Kannan .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2018, 64 (03) :1514-1529
[8]  
Luby M, 2002, ANN IEEE SYMP FOUND, P271, DOI 10.1109/SFCS.2002.1181950
[9]  
Luby M., 2007, 5053 RFC
[10]  
Luby M., 2011, FDN TRENDS COMMUNICA, V6
12