Factored LT and Factored Raptor Codes for Large-Scale Distributed Matrix Multiplication

被引：0
|
作者：
Pradhan, Asit Kumar [1 ]
Heidarzadeh, Anoosheh [1 ]
Narayanan, Krishna R. [1 ]
机构：
[1] Texas A&M Univ, Dept Elect & Comp Engn, College Stn, TX 77843 USA
来源：
2020 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) | 2020年
基金：
美国国家科学基金会;
关键词：
D O I：
10.1109/isit44484.2020.9174314
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We propose two coding schemes for distributed matrix multiplication in the presence of stragglers. These coding schemes are adaptations of LT codes and Raptor codes to distributed matrix multiplication and are termed Factored LT (FLT) codes and Factored Raptor (FR) codes. Empirically, we show that FLT codes have a near-optimal recovery threshold when the number of worker nodes is very large, and that FR codes have an excellent recovery threshold while the number of worker nodes is moderately large. FLT and FR codes have better recovery thresholds when compared to Product codes and they are expected to have better numerical stability when compared to Polynomial codes, while they can also be decoded with a low-complexity decoding algorithm.
引用
收藏
页码：239 / 244
页数：6
相关论文
共 50 条
  • [1] Asymptotic Analysis of Factored LT Codes for Distributed Matrix Multiplication
    Pradhan, Asit Kumar
    Heidarzadeh, Anoosheh
    Narayanan, Krishna R.
    2021 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2021, : 1718 - 1723
  • [2] Factored MCTS for Large Scale Stochastic Planning
    Cui, Hao
    Khardon, Roni
    Fern, Alan
    Tadepalli, Prasad
    PROCEEDINGS OF THE TWENTY-NINTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2015, : 3261 - 3267
  • [3] Fast Compressive Large-Scale Matrix-Matrix Multiplication Using Product Codes
    Ocal, Orhan
    Ramchandran, Kannan
    2020 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2020, : 1426 - 1431
  • [4] On Distributed Multiplication of Large-Scale Matrices
    Glushan, V. M.
    Lozovoy, A. Yu
    2021 IEEE 15TH INTERNATIONAL CONFERENCE ON APPLICATION OF INFORMATION AND COMMUNICATION TECHNOLOGIES (AICT2021), 2021,
  • [5] Hierarchical Parallel Matrix Multiplication on Large-Scale Distributed Memory Platforms
    Quintin, Jean-Noel
    Hasanov, Khalid
    Lastovetsky, Alexey
    2013 42ND ANNUAL INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING (ICPP), 2013, : 754 - 762
  • [6] A Factored MDP Approach to Optimal Mechanism Design for Resilient Large-Scale Interdependent Critical Infrastructures
    Huang, Linan
    Chen, Juntao
    Zhu, Quanyan
    2017 WORKSHOP ON MODELING AND SIMULATION OF CYBER-PHYSICAL ENERGY SYSTEMS (MSCPES), 2017,
  • [7] LT Codes with Feedback: Accelerate the Distributed Matrix-Vector Multiplication with Stragglers
    Yang, Xiao
    Jiang, Ming
    Zhao, Chunming
    2019 IEEE 38TH INTERNATIONAL PERFORMANCE COMPUTING AND COMMUNICATIONS CONFERENCE (IPCCC), 2019,
  • [8] Large-Scale Distributed Second-Order Optimization Using Kronecker-Factored Approximate Curvature for Deep Convolutional Neural Networks
    Osawa, Kazuki
    Tsuji, Yohei
    Ueno, Yuichiro
    Naruse, Akira
    Yokota, Rio
    Matsuoka, Satoshi
    2019 IEEE/CVF CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION (CVPR 2019), 2019, : 12351 - 12359
  • [9] On Large-Scale Matrix-Matrix Multiplication On Compressed Structures
    Krishna, Sudhindra Gopal
    Narasimhan, Aditya
    Radhakrishnan, Sridhar
    Veras, Richard
    2021 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA), 2021, : 2976 - 2985
  • [10] Improving Execution Concurrency of Large-Scale Matrix Multiplication on Distributed Data-Parallel Platforms
    Gu, Rong
    Tang, Yun
    Tian, Chen
    Zhou, Hucheng
    Li, Guanru
    Zheng, Xudong
    Huang, Yihua
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2017, 28 (09) : 2539 - 2552
12345