arrow
Return

Minimum Cost Encoding for Coded Distributed Computing Systems

delete2026-03-25
delete0
PRE
AI
M
Mahyar Karami
M
M. Ardakani
H
Hamid Ebrahimzad
Z
Zhuhong Zhang
DOI:10.1109/TCOMM.2026.3677353delete
deleteOriginal
deleteShare
deleteSave
Abstract

Abstract

En 中文
In large-scale distributed matrix-vector multiplications, e.g., for generative AI, straggling nodes can slow down or even jeopardize the whole operation. Coded distributed computing (CDC) uses erasure codes to create redundant computations and combat stragglers. This requires encoding very large matrices. Moreover, encoding must be repeated whenever system parameters (e.g., weight matrices in AI models) evolve. This paper introduces a general framework for reducing encoding complexity in CDC. We propose the notion of an encoding blueprint, a construction schedule that specifies how each coded symbol is constructed from data and previously computed coded symbols. An optimal blueprint minimizes the number of arithmetic operations required for a given code. We first design blueprints using addition-only operations. We then extend the framework to also allow subtraction, which further decreases the number of required operations. The optimization problem is cast as a mixed-integer program (MIP), and solved. Numerical results on matrix–vector multiplication show that optimized blueprints reduce encoding operations by up to 60 percent compared to standard methods, saving billions of operations in large-scale applications. Our techniques can be used for efficient decoding as well.
Keywords:
Coded distributed computing (CDC)
encoding complexity
binary linear codes
mixed-integer programming (MIP)
encoding blueprint

Journal

IEEE Transactions on Communications cover
IEEE Transactions on Communications
IF:
8.3
Papers:
1.2W
Citations:
4.5W

Organization

H
huawei technologies canada company ltd
Scholars:
5
Papers: 1
Citations: 0
S
synopsys inc
Scholars:
11
Papers: 9
Citations: 88
U
University of Alberta
Scholars:
2.8K
Papers: 1.2K
Citations: 3.2W
researcher View more organizations
Cited Papers

Cited Papers

Speeding Up Distributed Machine Learning Using Codes
err2018-03-01
err0
errOAAI
errKangwook Lee; Maximilian Lam; Ramtin Pedarsani; Dimitris Papailiopoulos; Kannan Ramchandran
errShare
errSave
On the Average Locality of Locally Repairable Codes
err2018-07-01
err6
errOAAI
errShahabinejad, Mostafa; Khabbazian, Majid; Ardakani, Masoud
errShare
errSave
On the Locality of Codeword Symbols
err2012-11-01
err0
errOAAI
errParikshit Gopalan; Cheng Huang; Huseyin Simitci; Sergey Yekhanin
errShare
errSave
Integer and Combinatorial Optimization
err
IF0
err2014-08-22
err0
PREAI
errGeorge Nemhauser; Laurence Wolsey
errShare
errSave
Integer Programming
err
IF0
err2020-09-19
err0
PREAI
errLaurence Wolsey
errShare
errSave
Learning to Branch with Tree MDPs
err2022-01-01
err0
PREAI
errAardal,Karen; Chen,Feng; Chetelat,Didier; Gasse,Maxime; Lodi,Andrea; Scavuzzo,Lara; Yorke-Smith,Neil
errShare
errSave
errShare
errSave
errShare
errSave
researcher View more