Minimum Cost Encoding for Coded Distributed Computing Systems

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.