A Unified Coded Deep Neural Network Training Strategy Based on Generalized PolyDot Codes for Matrix Multiplication

I Introduction

Ever-increasing data and computing requirements increasingly require massively distributed and parallel processing. However, as the number of parallel processing units are scaling, the expected number of faults, errors or delays in computing are also scaling. Thus, one of the major challenges of large-scale computing today is ensuring “reliability at scale”. Coded computing has emerged as a promising solution to the various problems arising from the unreliability of processing nodes in parallel and distributed computing, such as straggling delays or “soft-errors”. It is, in fact, a significant step in a long line of work on noisy computing started by von Neumann in 1956, that has been followed upon by Algorithm-Based Fault Tolerance (ABFT), the predecessor of coded computing. Recent advances in coded computing have generated significant interest both within and outside information theory.

The problem of distributed matrix-matrix multiplication $\bm{S}=\bm{W}\bm{X}$ under storage constraints, i.e., when each node is allowed to store a fixed $\frac{1}{K}$ fraction of each of the matrices $\bm{W}$ and $\bm{X}$, has been of considerable interest in the coded computing community. In , the authors introduced Product codes that use two different Maximum Distance Separable (MDS) codes to encode the two matrices being multiplied. This work was followed upon by , where the authors proposed Polynomial codes, that use a polynomial-based encoding scheme for the storage-constrained matrix multiplication problem to achieve a lower recovery threshold, i.e., the number of processing nodes to wait for out of a total of $P$ nodes. In our prior work , we first demonstrated that the recovery threshold for the storage-constrained matrix multiplication problem can be reduced further (beyond Polynomial codes ) in scaling sense by using novel constructions called MatDot codes. When a fixed $\frac{1}{K}$ fraction of each matrix can be stored at each node, MatDot achieves a recovery threshold of $2K-1$ as compared to Polynomial codes which achieve a threshold of $K^{2}$, albeit at a higher communication cost. In fact, MatDot codes can be proved to be optimal for storage-constrained matrix-matrix multiplication using fundamental limits in . In the same work , we also proposed the PolyDot codes for matrix-matrix multiplication that interpolate between Polynomial codes (for low communication costs) and MatDot codes (for lowest recovery threshold), trading off recovery threshold and communication costs, as illustrated in Fig. 1.

In this work, we have two main contributions as follows: 1. Generalized PolyDot Codes: First we build upon our prior work on PolyDot codes and propose a new class of codes for distributed matrix-vector and matrix-matrix multiplication called Generalized PolyDot codes. The proposed Generalized PolyDot codes interpolate better between Polynomial codes and MatDot codes, improving the recovery threshold (see Theorems 1 and 2) by introducing the new idea of “garbage alignment” for this problem. Garbage alignment is essentially a clever substitution in the multivariate polynomial introduced in our prior work on PolyDot framework of matrix multiplication that aligns some of the unwanted coefficients and reduces the number of unknowns during polynomial interpolation, as we elaborate in Section III. The recovery threshold of PolyDot codes are improved by a factor of $2$ using Generalized PolyDot codes by replacing the bijection-based substitution with garbage alignment. We note that, a concurrent work , that in fact appeared at the same venue as the original publication of this work , also achieve the same recovery threshold as Generalized PolyDot codes through slightly different routes.

2. Coded DNN Training Strategy: Our next contribution is that we develop a unified coded computing strategy, by appropriately utilizing Generalized PolyDot codes, for the training of model-parallelData parallel and model parallel are two different architectures for DNN training. In data parallelism , different nodes store and train a different replica of the entire DNN on different pieces of data, and a central parameter server combines inputs from all the nodes to train a central replica of the DNN. In model parallelism, different parts of a single DNN are parallelized across multiple nodes. Coding for data parallel training is examined in . Deep Neural Networks in presence of soft-errors. Soft-errors refer to undetected errors, e.g., bit-flips or gate errors in computation, that can corrupt the end resultIgnoring soft-errors entirely during training of DNNs can severely degrade the accuracy of training, as we experimentally observe in .. For this problem, we consider two kinds of error models: an adversarial model and a probabilistic model. Interestingly, as we show in Theorem 3, under the probabilistic model a real number $(P,Q)$ MDS code can theoretically correct $P-Q-1$ errors with probability $1$ as compared to $\lfloor\frac{P-Q}{2}\rfloor$ for the more conventional, adversarial case. While ideas of correcting more errors than $\frac{P-Q}{2}$ have been prevalent in finite fields (see ), to the best of our knowledge this seems to be the first result of this nature for real number error correction using MDS codes (see for similar results on LDPC codes).

The problem of coded DNN training under soft-errors also has several additional challenges (see ), that are all addressed by our proposed unified strategy, as follows:

Prohibitive overhead of encoding matrix $\bm{W}$ at each iteration: Existing works on coded matrix multiplication (e.g. for computing $\bm{W}_{N\times N}\bm{X}_{N\times B}$ where $N\gg B$) require encoding of both the matrices $\bm{W}$ and $\bm{X}$. Because $N\gg B$, encoding $\bm{W}$ is computationally expensive (complexity $\Theta(N^{2}P)$) and in fact can be as expensive as the matrix multiplication itself ($\Theta(N^{2}B)$). Thus, for this problem, the coding techniques in would be helpful if $\bm{W}$ is known in advance and is fixed over a large number of computations so that the encoding cost is amortized. However, when training DNNs, because the parameter matrices update at every iteration, a naive extension of existing techniques would require encoding of parameter matrices at every iteration and thus introduce an undesirable additional overhead of $\Theta(N^{2}P)$ at every iteration that can no longer be amortized. To address this, we carefully weave Generalized PolyDot codes into the operations of DNN training so that an initial encoding of the weight matrices is maintained across the updates at each iteration. To do so, at each iteration each node locally encodes much smaller matrices consisting of $NB$ elements instead of the large matrix $\bm{W}$ of $N^{2}$ elements, adding negligible overhead. In particular, for the case of $B=1$, this simply reduces to encoding vectors instead of matrices which is much cheaper in terms of computational complexity.

Master node acting as a single point of failure: Because of our focus on soft-errors in this work, if we allow the architecture to use a master node, this node can often become a “single point of failure” (considered undesirable in parallel computing literature, e.g., ). Thus, we consider a completely decentralized setting, with no master node. In that spirit, our strategy allows encoding/decoding to be error-prone as well, along with all the other primary steps, namely, matrix multiplication, nonlinear activation, Hadamard product and update. We only introduce two verification steps (that check for decoding errors by exchanging some values among all nodes and comparing) that are extremely low complexityThe longer a computation, the more is the probability of soft-errors . In fact, the number of soft-errors that occur within a time interval is often modelled as a Poisson random variable with mean proportional to the length of the time interval. and hence, may be assumed to be error-free.

Nonlinear activation between layers: The nonlinear activation (e.g. sigmoid, ReLU) between layers also poses a difficulty for coded training because most coding techniques are linear. To circumvent this issue, we code the linear operations (matrix multiplication of complexity $\Theta(N^{2}B)$) at each layer separately. Matrix multiplication and update are the most critical and complexity-intensive steps in the training of DNNs as compared to other operations such as nonlinear activation or Hadamard product which are of complexity $\Theta(NB)$, and hence are also more likely to have errors. Moreover, as our implementation is decentralized, every node acts as a low-complexity functional replica of the master node, performing encoding/decoding/nonlinear activation/Hadamard product and helping us detect (and if possible correct) errors in all the primary steps, including the nonlinear activation step.

Overview of results in coded DNN Training: We show (in Theorems 4 and 6) that under both the adversarial and probabilistic error models, the coded DNN strategy using Generalized PolyDot codes improves the error tolerance in scaling sense over competing replication strategy and a preliminary MDS-code-based DNN training strategy. Moreover, to demonstrate the utility of the DNN training strategy, we also show in Theorems 5 and 7 that the additional overhead due to coding per iteration is negligible as compared to the computational complexity of the local matrix operations at each node as long as the number of processors $P^{4}=o(N)$. Our coding technique also extends to DNN training with regularization as is done more commonly in practice.

For a distributed matrix-matrix multiplication problem $\bm{S}=\bm{W}\bm{X}$, Polynomial codes use a horizontal splitting of the first matrix $\bm{W}$ and vertical splitting of the second matrix $\bm{X}$ into $K$ blocks each, thus satisfying the storage constraint (see Fig. 2). Alternately, MatDot codes use a vertical splitting of the first matrix $\bm{W}$ and a horizontal splitting of the second matrix $\bm{X}$ into $K$ blocks each. PolyDot and Generalized PolyDot codes both incorporate simultaneous vertical and horizontal splitting of both matrices $\bm{W}$ and $\bm{X}$ to interpolate between Polynomial codes and MatDot codes, while satisfying storage constraints. Interestingly, as it turns out, the problem of coded computing by splitting the matrix $\bm{W}$ both vertically and horizontally arises naturally in DNN training.

In the problem of DNN training, at each iteration in any particular layer, the same matrix $\bm{W}$ is required to be multiplied once with another matrix $\bm{X}$ (or vector $\bm{x}$) from the right side in the feedforward stage, i.e., $\bm{W}\bm{X}$, and once with another matrix $\bm{\Delta}^{T}$ (or vector $\bm{\delta}^{T}$) from the left side in the backpropagation stage, i.e., $\bm{\Delta}^{T}\bm{W}$. One would like to use the same encoding on $\bm{W}$ (or sub-matrices of $\bm{W}$) for both the matrix-matrix multiplication because the available storage is limited and storing two encoded sub-matrices of $\bm{W}$ for the two matrix-matrix multiplications is expensive. Now, suppose that we choose to use MatDot codes for $\bm{W}\bm{X}$ and hence stick with vertical partitioning of the first matrix $\bm{W}$. Then, we would have to use Polynomial codes for $\bm{\Delta}^{T}\bm{W}$ as $\bm{W}$ is the second matrix for this multiplication. This is also pictorially illustrated in Fig. 2. Thus, we would like to allow for both horizontal and vertical partitioning of the matrix $\bm{W}$ into a grid of $m\times n$ sub-matrices with $mn=K$ for the storage constraint. This would allow us to be able to interpolate between MatDot and Polynomial codes for the two matrix-matrix multiplications $\bm{W}\bm{X}$ and $\bm{\Delta}^{T}\bm{W}$, so as to achieve a good recovery threshold (and hence error tolerance) for both forward and backward matrix-matrix multiplications.

We note that a concurrent work , that in fact appeared at the same conference as the original publication of this work , proposes the coding scheme “Entangled Polynomial codes” that achieve the same recovery threshold as Generalized PolyDot codes through slightly different routes for the problem of distributed matrix multiplication under storage constraints allowing for both vertical and horizontal splitting. In this expanded version of we show that the Generalized PolyDot codes, that were originally proposed for matrix-vector products in , naturally extend to matrix-matrix products as well. This is because Generalized PolyDot codes are simply a clever substitution in a multivariate polynomial in our prior PolyDot framework for matrix-matrix multiplication (this work precedes both and ), so that some unwanted coefficients of the polynomial align with each other, reducing the degree of the polynomial and hence number of unknowns in polynomial interpolation, thereby improving the recovery threshold by a factor of $2$. More importantly, our work also introduces a novel result in real-number error correction and is also the first line of work that considers the problem of coded DNN training.

I-B Organization.

The rest of the paper is organized as follows. We introduce our two problem formulations, namely, (1) coded matrix multiplication; and (2) coded DNN, in Section II. First, we address Problem $1$, i.e., the coded matrix multiplication problem. For this problem, we introduce some motivating examples in Section III and then describe the Generalized PolyDot codes in detail in Section IV. Then moving on to Problem $2$, we first elaborate upon some modelling assumptions, e.g., the two error models for the coded DNN problem in Section V, which leads to a novel result on real number error correction. This is followed by possible solutions for the coded DNN problem for $B=1$ (existing strategies in Section VI, our proposed strategy in Section VII). We formally analyze the error tolerance and the computation and communication costs of our strategy in Section VIII. Next, we extend the proposed strategy for the case of $B>1$ in Section IX. Finally, in Section X, we discuss an application of our strategy to more recent but closely related neural network architectures, namely, sparse autoencoders.

II System Models and Problem Formulations for the two problems

System Model: We assume that there is a centralized, reliable master node and $P$ memory-constrained worker nodes that may be unreliable. The master node allocates computational tasks to the worker nodes. The worker nodes perform their computations in parallel and send their outputs back to the master node. Outputs of some worker nodes may be modeled as erasures (e.g., because of straggling or faults). The master node gathers the outputs of the worker nodes (possibly a subset), and uses them to compute the final result. It is desirable that the computational overhead of the master node as well as the communication costs should be smaller than the local computational complexity of each worker node after parallelization.

Problem Formulation: Compute distributed matrix multiplication $\bm{S}=\bm{W}\bm{X}$ using $P$ worker nodes prone to erasures such that each node can store only a fixed fraction $\frac{1}{K}$ of matrix $\bm{W}$ and $\frac{1}{K^{\prime}}$ of matrix $\bm{X}$. For this problem, our goal is to minimize the erasure recovery threshold, i.e., the number of nodes that the decoder has to wait for out of the total $P$ nodes, to be able to compute the entire final result. We are also interested in studying tradeoffs between communication costs and recovery threshold.

We assume that both $K$ and $K^{\prime}$ are less than $P$.

When $K=K^{\prime}$, our prior work on MatDot codes achieves the optimal recovery threshold of $2K-1$ under the storage constraint, albeit at a high communication cost. Here, we propose a more general encoding strategy for the problem of coded matrix multiplication under fixed storage constraints that also allows us to tradeoff between recovery threshold and communication costs, with MatDot codes and Polynomial codes being two special cases.

Note that no specific assumptions are made on the relative dimensions of $\bm{W}$ and $\bm{X}$ for this problem formulation. The matrices $\bm{W}$ and $\bm{X}$ do not necessarily have to be square matrices either.

II-B Problem 222 (Coded DNN).

Background: Before introducing our system model and problem formulation, we first introduce the main computational steps at each iteration of classical (error-free) DNN training using Stochastic Gradient Descent (SGD)As a first step in this direction of coded neural networks, we assume that the training is performed using vanilla SGD. As a future work, we plan to extend these coding ideas to other training algorithms such as momentum SGD, Adam etc.. For a more detailed introduction, we refer to the seminal work or Appendix A.

A DNN consists of $L$ weight matrices (also called parameter matrices), $\bm{W}^{l}$, of dimensions $N_{l}\times N_{l-1}$ where $l$ denotes the layer-index and $N_{l}$ denotes the number of neurons at layer $l$, for $l=1,2,\ldots,L$. These weight matrices are updated at each iteration of training based on a “mini-batch” of $B$ data-points and their labels. Because we are primarily interested in large models that require parallelization across multiple nodes, we assume $N_{l}\gg B$ for all $l$. For simplicity of presentation, we also assume $N_{l}=N$ for all $l$, and thus $N\gg B$. DNN training has $3$ stages in each iteration, (i) the feedforward stage, (ii) the backpropagation stage, and (iii) the update stage. As the operations are similar and repeat across all the layers (see Appendix A), we limit our discussion to layer $l$. The operations during feedforward stage (see Fig. 3a) can be summarized as:

$[$Step $O1]$ Compute matrix-matrix product $\bm{S}^{l}=\bm{W}^{l}\bm{X}^{l}$ where $\bm{X}^{l}$ is a matrix of dimension $N\times B$.

$[$Step $C1]$ Compute $\bm{X}^{(l+1)}=f(\bm{S}^{l})$ where $f(\cdot)$ is a nonlinear activation function applied element-wise.

At the last layer ($l=L$), the backpropagated error matrix is generated by accessing the true label matrix from memory and the estimated label matrix as output of last layer (see Fig. 3b). Then, the backpropagated error propagates from layer $L$ to $1$ (see Fig. 3c), also updating the weight matrices at every layer alongside (see Fig. 3d). The operations for the backpropagation stage can be summarized as: From layer $l=L$ to $1$,

$[$Step $O2]$ Compute matrix-matrix product $[\bm{C}^{l}]^{T}=[\bm{\Delta}^{l}]^{T}\bm{W}^{l}$ where $[\bm{\Delta}^{l}]^{T}$ is a matrix of dimensions $B\times N$.

$[$Step $C2]$ Compute Hadamard product $[\bm{\Delta}^{l-1}]^{T}=[\bm{C}^{l}]^{T}\circ g([\bm{X}^{l}]^{T})$ where $g(\cdot)$ is another function applied element-wise (more specifically $\frac{df(u)}{du}=g(f(u))$ for the chosen nonlinear activation function $f(u)$) and the Hadamard product “$\circ$” between two matrices of the same dimensions is another matrix of those dimensions, such that its elements are element-wise products of the corresponding elements of the operands.

Finally, the step in the Update stage is as follows: For all layers $l$,

$[$Step $O3]$ Update matrix $\bm{W}^{l}$ as follows: $\bm{W}^{l}\leftarrow\bm{W}^{l}+\eta\bm{\Delta}^{l}[\bm{X}^{l}]^{T}$ where $\eta$ is the learning rate. Sometimes a regularization term is added with the loss function in DNN training (elaborated in Section A-C). For L2 regularization, the update rule is modified as: $\bm{W}^{l}\leftarrow(1-\eta\lambda)\bm{W}^{l}+\eta\bm{\delta}^{l}[\bm{x}^{l}]^{T}$ where $\eta$ is the learning rate and $\frac{\lambda}{2}$ is the regularization constant.

System model: We assume that there is a decentralized system of $P$ memory-constrained nodes that are prone to soft-errors during computation. Soft-errors cause the node to produce entirely garbage outputs. We introduce two error-models in Section V. Under Error-Model $1$, which is an adversarial model, soft-errors only occur during the most computationally intensive operations, i.e., steps $O1$, $O2$ and $O3$ but the number of erroneous nodes is bounded. Under Error-Model $2$, which is a probabilistic model, soft-errors can occur during the steps $O1$, $O2$, $O3$, $C1$, $C2$ as well as encoding/decoding. There is no upper bound on the number of erroneous nodes or any specific assumption on where they can occur, but when errors occur, the output of that node is assumed to have an additive continuous-valued random noise. We elaborate upon these two models in Section V.

There is no single reliable master node, and all nodes can be unreliable. After an initial error-free setup (a pre-processing stepWe assume that the cost of initial setup or pre-processing before the start of training is amortized across large number of iterations.), all the nodes may begin their computational tasks in parallel, and proceed with the iterations of training. These memory-constrained and unreliable nodes may also communicate with each other, as required by the DNN training algorithm, or even perform some functions of a master node, such as, gathering outputs from other nodes, encoding/decoding etc., while respecting their storage constraints. After completing the required number of iterations, the final computational results (in this case, the $L$ trained parameter matrices) remain stored locally across the multiple nodes in a distributed manner. The data set and their labels are stored in a separate reliable memory unit and are communicated to all the nodes at each iteration when they access it.

Problem formulation: Design an error-resilient DNN training strategy using $P$ nodes, such that:

Each node can store only a $\frac{1}{K}$ fraction of each weight matrix $\bm{W}^{l}$ for each layer. Thus, for each layer, there is a per-node storage of $\frac{N^{2}}{K}+o\left(\frac{N^{2}}{K}\right)$ where the small additional storage of $o\left(\frac{N^{2}}{K}\right)$ is to store additional quantities that are negligible in storage size as compared to the $\frac{1}{K}$ fraction of $\bm{W}^{l}$, e.g., matrices $\bm{S}^{l}$, $\bm{X}^{l}$, $\bm{C}^{l}$ and $\bm{\Delta}^{l}$ which are all of dimensions $N\times B$ where $B\ll N$ by our assumption. In particular, we assume that $B=o\left(\frac{N}{K}\right)$ to satisfy this storage constraint.

All additional overheads per node including the communication complexity as well as the computational complexity of encoding/decoding in an error-free iterationFor error-resilience, some operations such as error detection, encoding etc. are required to be performed at each iteration even though most iterations of training are actually error-free. The purpose of this assumption is only to ensure that the additional overheads introduced for error-resilience in these error-free iterations is negligible. In the few iterations where errors occur and are detected, all error-resilient strategies incur some extra costs, such as, possibly regenerating the erroneous nodes or reverting to the last checkpoint etc, that is not being compared here. should be negligible in scaling sense as compared to the computational complexity of the local matrix multiplications and updates, i.e., steps $O1$, $O2$ and $O3$ at each node after parallelization.

Our goal is to achieve maximum error tolerance in the steps of DNN training, i.e., maximize the number of errors that can be corrected during training in a single iteration under both the error models. Under Error model $1$ (see Section V), the number of erroneous nodes are bounded and we require the number of errors that can be corrected in any step to be higher than the maximum number of errors that can occur in that step in the worst-case. Under Error model $2$ (see Section V), which allows for unbounded number of errors but their values being drawn from a continuous-valued distribution, in addition to maximizing the number of errors we can correct, our goal is also to be able to detect the occurrence of errors even when they are too many to be corrected.

For this problem formulation, we also assume that $N\gg P$, the number of parallel nodes.

In practice, the nodes also perform “checkpointing” at large intervals, i.e., storing the entire DNN (the $L$ parameter matrices) at a reliable disk from which the values can be retrieved when errors cannot be corrected. However, checkpointing is very expensive, even though it is assumed to be error-free, as the nodes have to access the disk, and thus can only be performed at large time intervals.

Existing coded computing techniques require encoding of the matrices being multiplied. If we were to extend them naively to the problem of coded DNN training, then the matrix $\bm{W}^{l}$ has to be encoded afresh in each iteration because the matrix $\bm{W}^{l}$ is updated in each iteration during step $O3$. Encoding matrix $\bm{W}^{l}$ with non-sparse codes in each iteration has a huge computational cost, and is thus a major challenge for the problem of coded DNN training (violates the last criterion in problem formulation). Thus, one key contribution in this work is in proposing a unified strategy such that the matrix $\bm{W}^{l}$, once initially encoded, remains encoded during updates in each iteration, obviating the need to encode afresh.

Matrix Partitioning Notations: Throughout this paper, matrices and vectors are denoted in bold font. When we block-partition a matrix $\bm{A}$ both row-wise and column-wise into $m\times n$ equal-sized blocks for any integers $m$ and $n$, we let $\bm{A}_{i,j}$ denote the block with row index $i$ and column index $j$, where $i=0,1,\dots,m-1$ and $j=0,1,\dots n-1$. Similarly, when we partition a vector $\bm{a}$ into $m$ equal parts for any integer $m$, the sub-vectors are denoted as $\bm{a}_{0},\bm{a}_{1},\dots,\bm{a}_{n-1}$ respectively. E.g., for $m=n=2$, the partitioning is as follows:

Also, note that when a matrix $\bm{A}$ is split only horizontally or only vertically into $m$ blocks, we denote the sub-matrices as $\bm{A}_{i,:}$ or $\bm{A}_{:,i}$ respectively for $i=0,1,\ldots,m-1$.

III Motivating Example for Coded Matrix Multiplication

In this section, we introduce a motivating example to first understand both Polynomial codes and MatDot codes , that have been proposed for distributed matrix-matrix multiplication and then, we introduce the key idea of garbage alignment in the PolyDot framework for matrix-matrix multiplication . We choose $K=K^{\prime}=4$.

The main intuition behind these polynomial-based strategies is to carefully design two polynomials $\widetilde{\bm{W}}(v)$ and $\widetilde{\bm{X}}(v)$ (may also be multivariate) whose coefficients are sub-matrices of $\bm{W}$ and $\bm{X}$ respectively, such that, different sub-matrices of the final result $\bm{S}(=\bm{W}\bm{X})$ show up as coefficients of the product $\widetilde{\bm{W}}(v)\widetilde{\bm{X}}(v)$. The $p$-th processing node stores a unique evaluation of $\widetilde{\bm{W}}(v)$ and $\widetilde{\bm{X}}(v)$ at $v=b_{p}$ for $p=0,1,\ldots,P-1$, and then computes the product $\widetilde{\bm{W}}(b_{p})\widetilde{\bm{X}}(b_{p})$, essentially producing a unique evaluation of the polynomial $\widetilde{\bm{S}}(v):=\widetilde{\bm{W}}(v)\widetilde{\bm{X}}(v)$ at $v=b_{p}$. From a sufficient number of unique evaluations of the polynomial $\widetilde{\bm{S}}(v)$, the decoder is able to interpolate back all its coefficients, which include the different sub-matrices of the result $\bm{S}$. Thus, the recovery threshold, i.e., the number of nodes to wait for out of $P$ is $(1+Degree(\widetilde{\bm{S}}(v)))$, which is the total number of unknowns in the interpolation of the polynomial $\widetilde{\bm{S}}(v)$.

Matrix Multiplication using Polynomial Codes: In Polynomial codes , the first matrix $\bm{W}$ is split horizontally and the second matrix $\bm{X}$ is split vertically into $K(=4)$ blocks each, as follows:

Note that, the resultant matrix $\bm{S}=\bm{W}\bm{X}$ therefore takes the following form:

For this coding strategy, two polynomials are chosen as follows:

The $p$-th processing node stores a unique evaluation of $\widetilde{\bm{W}}(v)$ and $\widetilde{\bm{X}}(v)$ at $v=b_{p}$ for $p=0,1,\ldots,P-1$, and then computes the product $\widetilde{\bm{W}}(b_{p})\widetilde{\bm{X}}(b_{p})=\widetilde{\bm{S}}(b_{p})$, which essentially produces a unique evaluation of the polynomial $\widetilde{\bm{S}}(v)=\widetilde{\bm{W}}(v)\widetilde{\bm{X}}(v)$ at $v=b_{p}$. Observe the coefficients of the polynomial $\widetilde{\bm{S}}(v)$ as follows:

Interestingly, all the different sub-matrices of $\bm{S}$, i.e., $\bm{S}_{i,j}$ show up as coefficients of the polynomial $\widetilde{\bm{S}}(v)$. Because the degree of this polynomial $\widetilde{\bm{S}}(v)$ is $15$ (for $K=4$), the decoder requires $16$ unique evaluations to interpolate the polynomial successfully. Thus, recovery threshold is $16$.

Matrix Multiplication using MatDot Codes: Contrary to Polynomial codes, in MatDot codes the first matrix $\bm{W}$ is split vertically and the second matrix $\bm{X}$ is split horizontally into $K$ blocks each as follows:

Now we carefully choose the two polynomials $\widetilde{\bm{W}}(v)$ and $\widetilde{\bm{X}}(v)$ as follows:

As before, the $p$-th node stores a unique evaluation of $\widetilde{\bm{W}}(v)$ and $\widetilde{\bm{X}}(v)$ at $v=b_{p}$ for $p=0,1,\ldots,P-1$, and then computes the product $\widetilde{\bm{W}}(b_{p})\widetilde{\bm{X}}(b_{p})=\widetilde{\bm{S}}(b_{p})$, essentially producing a unique evaluation of the polynomial $\widetilde{\bm{S}}(v):=\widetilde{\bm{W}}(v)\widetilde{\bm{X}}(v)$. Now observe the coefficients of the polynomial $\widetilde{\bm{S}}(v)$ as follows:

Note that, the coefficient of $v^{K-1}(=v^{3})$ gives the result $\bm{S}$. All the other coefficients are practically of no use, and hence, are referred to as “garbage.” Because the degree of the polynomial $\bm{S}(v)$ is $6$, the decoder would require only $7$ unique evaluations to interpolate the polynomial successfully. Thus, the recovery threshold is $7$.

Matrix Multiplication using Generalized PolyDot Codes (with Garbage Alignment): Before introducing Generalized PolyDot Codes, we review the PolyDot framework for the matrix-matrix multiplication problem. The PolyDot framework splits both the matrices horizontally and vertically into $4$ sub-matrices each, as follows:

The resultant matrix $\bm{S}$ therefore takes the form:

Now the PolyDot framework (see Fig. 4) encodes these sub-matrices of $\bm{W}$ into a polynomial in two variables with each variable corresponding to either the row or column dimension, as follows:

The sub-matrices of $\bm{X}$ are encoded as follows:

Now, observe the coefficients of the product of the two polynomials, i.e., $\widetilde{\bm{S}}(u,v,w)=\widetilde{\bm{W}}(u,v)\widetilde{\bm{X}}(v,w)$ as follows:

The coefficient of $u^{i}vw^{k}$ corresponds to $\bm{S}_{i,k}$. The total number of unknowns or coefficients in this multivariate polynomial is $2\times 3\times 2=12$. If we convert this multivariate polynomial into a polynomial of a single variable, e.g., using substitution $v=u^{2},w=u^{6}$, so that there exists a bijection between the coefficients of the multivariate polynomial and the polynomial of a single variable, then we would require $12$ unique evaluations of the polynomial to be able to interpolate all its $12$ unknown coefficients, including the ones that contribute towards $\bm{S}$.

In this work, one of our key observations is that even though the polynomial has $12$ coefficients, the number of coefficients that are useful to us is only $4$, i.e., only the coefficients of $u^{i}vw^{k}$ for $i,k=0,1$ while the others are garbage. Thus, we instead propose the following variable substitution: $u=v^{2},w=v^{4}$ in our previously proposed PolyDot framework . Observe the product now:

Note that the coefficient of $v^{2i+4k+1}$ in $\widetilde{\bm{S}}(v)$ correspond exactly to the coefficient of $u^{i}vw^{k}$ in $\widetilde{\bm{S}}(u,v,w)$, i.e., $\bm{S}_{i,k}$. However, some of the garbage coefficients have now aligned with each other to reduce the total number of unknown garbage coefficients, e.g., coefficient of both $uv^{2}$ and $w$ in $\widetilde{\bm{S}}(u,v,w)$ now get added up and form the coefficient of $v^{4}$ in $\widetilde{\bm{S}}(v)$. This is the key idea of garbage alignment that lies at the core of the design of Generalized PolyDot codes, as we discuss in details in the next section. The polynomial resulting after substitution is only of degree $8$. Thus it only requires $9$ unique evaluations to be able to interpolate all its coefficients. Thus, garbage alignment reduces the recovery threshold from $12$ to $9$.

IV Generalized PolyDot codes for coded matrix multiplication

In this section, we describe our Generalized PolyDot code construction for the problem of coded matrix multiplication $\bm{W}_{N_{1}\times N_{0}}\bm{X}_{N_{0}\times B}$ using $P$ memory-constrained nodes, as discussed in Section II. We choose integers $m$, $n$ and $d$ such that $mn=K$ and $nd=K^{\prime}$ respectively. Next, we partition the matrix $\bm{W}$ both horizontally and vertically into an $m\times n$ grid of smaller sub-matrices of dimensions $\frac{N_{1}}{m}\times\frac{N_{0}}{n}$ each. Note that, in this type of partitioning, each sub-matrix contains a $\frac{1}{K}$ fraction of $\bm{W}_{N_{1}\times N_{0}}$. Similarly, $\bm{X}$ is also partitioned into an $n\times d$ grid of sub-matrices of dimensions $\frac{N_{0}}{n}\times\frac{B}{d}$ each ($\frac{1}{K^{\prime}}$ of $\bm{X}$). After this, we encode these sub-matrices of $\bm{W}$ and $\bm{X}$ by taking appropriate linear combinations and store encoded sub-matrices of $\bm{W}$ and $\bm{X}$ at each node that satisfy the storage constraints.

Theorem 1 states our achievability result for the problem of matrix-vector products where we are required to perform $\bm{s}=\bm{W}\bm{x}$ using $P$ nodes, such that every node can only store an $\frac{N_{1}}{m}\times\frac{N_{0}}{n}$ sub-matrix ($\frac{1}{K}$ fraction) of $\bm{W}$ and an $\frac{N_{0}}{n}\times 1$ sub-vector of $\bm{x}$.

Generalized PolyDot codes for computing matrix-vector multiplication $\bm{W}_{N_{1}\times N_{0}}\bm{x}_{N_{0}\times 1}$ using $P$ nodes, each storing an $\frac{N_{1}}{m}\times\frac{N_{0}}{n}$ sub-matrix of $\bm{W}$ and an $\frac{N_{0}}{n}\times 1$ sub-vector of $\bm{x}$, has a recovery threshold of $mn+n-1$. Thus, it can tolerate at most $P-mn-n+1$ erasures.

Recall the PolyDot framework for matrix multiplication. We first block-partition $\bm{W}$ into $m\times n$ sub-matrix where $\bm{W}_{i,j}$ denotes the sub-matrix at location $(i,j)$ for $i=0,1,\ldots,m-1$ and $j=0,1,\ldots,n-1$. Let the $p$-th node ($p=0,1,\ldots,P-1$) store an encoded sub-matrix of $\bm{W}$, which is a polynomial in $u$ and $v$, as follows:

evaluated at some $(u,v)=(a_{p},b_{p})$. The choice of these variables will be clarified later. The vector $\bm{x}$ is also partitioned into $n$ equal sub-vector denoted by $\bm{x}_{0},\bm{x}_{1},\ldots,\bm{x}_{n-1}$, each of dimensions $\frac{N_{0}}{n}\times 1$. Each node stores an encoded sub-vector as follows:

evaluated at $v=b_{p}$. Now, each node computes the smaller matrix-vector multiplication $\widetilde{\bm{W}}(a_{p},b_{p})\widetilde{\bm{x}}(b_{p})$ which effectively results in the evaluation, at $(u,v)=(a_{p},b_{p})$, of the following polynomial:

even though the node is not explicitly evaluating it from all its coefficients. Observe that the coefficient of $u^{i}v^{n-1}$ for $i=0,1,\dots,m-1$ turns out to be $\sum_{j=0}^{n-1}\bm{W}_{i,j}\bm{x}_{j}=\bm{s}_{i}$. This is obtained by fixing $j^{\prime}=j$. Thus, these $m$ coefficients constitute the $m$ sub-vectors of $\bm{s}(=\bm{W}\bm{x})$. Therefore, $\bm{s}$ can be recovered by the decoder if it can interpolate these $m$ coefficients of the polynomial $\widetilde{\bm{s}}(u,v)$ in 3 from its evaluations. As an example, consider the case where $m=n=2$.

More generally, we use the substitution $u=v^{n}$ to convert $\widetilde{\bm{s}}(u,v)$ into a polynomial in a single variable. Therefore, $a_{p}=b_{p}^{n}$ and each $b_{p}$ is unique for $p=0,1,\ldots,P-1$. Some of the unwanted, garbage coefficients align with each other (e.g. $u$ and $v^{2}$ in 4), but the coefficients of $u^{i}v^{n-1}$, i.e., $\bm{s}_{i}$ remain unchanged and now correspond to the coefficients of $v^{ni+n-1}$ for $i=0,1,\ldots,m-1$. After the substitution $u=v^{n}$ in $\widetilde{\bm{s}}(u,v)$, the resulting polynomial of single variable $v$ is of degree $mn+n-2$. Thus, the decoder needs to wait for $mn+n-1$ nodes, each providing a unique evaluation, to be able to interpolate all the $mn+n-1$ unknown coefficients. The recovery threshold is thus $mn+n-1$. ∎

Now, we extend the coding strategy to the problem of matrix-matrix multiplication.

Generalized PolyDot codes for computing matrix-matrix multiplication $\bm{W}_{N_{1}\times N_{0}}\bm{X}_{N_{0}\times B}$ using $P$ nodes, each storing an $\frac{N_{1}}{m}\times\frac{N_{0}}{n}$ sub-matrix of $\bm{W}$ and an $\frac{N_{0}}{n}\times\frac{B}{d}$ sub-matrix of $\bm{X}$ has a recovery threshold of $mnd+n-1$. Thus, it can tolerate at most $P-mnd-n+1$ erasures.

The matrix-matrix multiplication strategy is very similar to the matrix-vector case. The $p$-th node ($p=0,1,\ldots,P-1$) stores an encoded sub-matrix of $\bm{W}$ which is the same polynomial in $u$ and $v$, as follows:

evaluated at $(u,v)=(a_{p},b_{p})$. The matrix $\bm{X}$ is also block-partitioned into $n\times d$ sub-matrices, where the sub-matrix at location $(j,k)$ is denoted as $\bm{X}_{j,k}$, for $j=0,1,\ldots,n-1$ and $k=0,1,\ldots,d-1$. As per the PolyDot framework , the $p$-th node also stores an encoded sub-matrix of $\bm{X}$, as a polynomial in $(v,w)$, as follows:

evaluated at $(v,w)=(b_{p},c_{p})$. Next, each node computes the smaller matrix-matrix product: $\widetilde{\bm{S}}(a_{p},b_{p},c_{p})=\widetilde{\bm{W}}(a_{p},b_{p})\widetilde{\bm{X}}(b_{p},c_{p})$ which effectively results in the evaluation, at $(u,v,w)=(a_{p},b_{p},c_{p})$, of the polynomial:

even though the node is not explicitly evaluating it from its coefficients. Now, fixing $j^{\prime}=j$, we observe that the coefficient of $u^{i}v^{n-1}w^{k}$ for $i=0,1,\dots,m-1$ and $k=0,1,\dots,d-1$ turns out to be $\sum_{j=0}^{n-1}\bm{W}_{i,j}\bm{X}_{j,k}=\bm{S}_{i,k}$. These $md$ coefficients constitute the $m\times d$ sub-matrices (or blocks) of $\bm{S}=\bm{W}\bm{X}$. Therefore, $\bm{S}$ can be recovered at the decoder if all these $md$ coefficients of the polynomial $\widetilde{\bm{S}}(u,v,w)$ can be interpolated from its evaluations at different nodes.

For garbage alignment, we propose the substitutions $(u=v^{n},w=v^{mn})$ to convert $\widetilde{\bm{S}}(u,v,w)$ into a polynomial of a single variable $v$. Thus, $a_{p}=b_{p}^{n}$, $c_{p}=b_{p}^{mn}$ and $b_{p}$ is unique for $p=0,1,\ldots,P-1$. The coefficient of $u^{i}v^{n-1}w^{k}$ in $\widetilde{\bm{S}}(u,v,w)$ exactly correspond to the coefficient of $v^{ni+mnk+n-1}$ in $\widetilde{\bm{S}}(v)=\widetilde{\bm{S}}(u,v,w)|_{u=v^{n},w=v^{m}n}$, while some of the garbage terms align with each other, reducing the total number of unknowns. Observe the polynomial:

which is a polynomial in a single variable $v$. Its degree is given by $n(m-1)+mn(d-1)+n-1+n-1=mnd+n-2$. Thus, the decoder needs to wait for $mnd+n-1$ nodes, each producing a unique evaluation, to be able to interpolate all its $mnd+n-1$ coefficients. ∎

Under erasures, the master node only waits for $mnd+n-1$ nodes to finish and the decoding reduces to the problem of solving a linear system of equations (polynomial interpolation). If the outputs are corrupted by errors instead of erasures, the master node gathers outputs from all the $P$ nodes and then solves a sparse reconstruction problem to decode the correct output, using the techniques in , as we also discuss in Appendix B.

Now we discuss the communication and computation costs of Generalized PolyDot Codes (with $mn=K$, $nd=K^{\prime}$) in the centralized setup under erasures.

Computational complexity of encoding the sub-matrices at the master node: $\mathcal{O}(P(N_{1}N_{0}+N_{0}B))$.

Total communication complexity of sending different encoded sub-matrices from the master node to each of the $P$ nodes: $\Theta(\frac{PN_{1}N_{0}}{K}+\frac{PN_{0}B}{K^{\prime}})$.

Computational complexity at each worker node for the matrix multiplication: $\Theta(\frac{N_{1}N_{0}B}{mnd})$.

Total communication complexity of gathering different outputs at the master node from the first $mnd+n-1$ workers: $\Theta((mnd+n-1)\frac{N_{1}B}{md})$.

Computational complexity of decoding at master node: $\mathcal{O}((mnd+n-1)^{3}\frac{N_{1}B}{md})$.

Tradeoff between communication cost and recovery threshold: In Fig. 5 we illustrate the tradeoff between recovery threshold and communication costs for Generalized PolyDot codes by varying $m$, $n$ and $d$. When we choose $n=1,m=K,d=K^{\prime}$, the Generalized PolyDot codes reduce to Polynomial codes with recovery threshold $KK^{\prime}$. On the other hand, in the regime where $K=K^{\prime}$, the Generalized PolyDot codes reduce to MatDot codes when we choose $m=d=1,n=K$, resulting in a recovery threshold of $2K-1$.

Now, we move on to our Problem Formulation $2$, i.e., coded DNNs.

V Modelling Assumptions for coded DNNs with a Result on Real Number Error Correction

In this section, we will elaborate upon a few modeling assumptions for coded DNNs, such as, defining the two error models and communication complexity in decentralized settings. The error models introduced here lead to an interesting theoretical result on real number error correction, as stated in Theorem 3.

Let $\bm{q}$ be a $Q\times 1$ vector consisting of $Q$ real-valued symbols. The received output vector is as follows:

The subset $\mathcal{A}$ satisfies $|\mathcal{A}|\leq\lfloor\frac{P-Q}{2}\rfloor$, with no specific assumptions on the locations or values of the errors and they may be chosen advarsarially.

Under the Probabilistic Error Model for channel coding, the decoder of a $(P,Q)$ MDS Code can perform the following:

It can detect the occurrence of errors with probability $1$, irrespective of the number of errors that occurred.

If the number of errors that occurred is less than or equal to $P-Q-1$, then all those errors can be corrected with probability $1$, even without knowing in advance that how many errors actually occurred.

If the number of errors that occurred is more than $P-Q-1$, then the decoder is able to determine that the errors are too many to be corrected and declare a “decoding failure” with probability $1$.

This result is interesting as it essentially means that in real number error correction, one can theoretically correct $P-Q-1$ errors with probability $1$ which is more than the well-known adversarial error tolerance of $\lfloor\frac{P-Q}{2}\rfloor$ for MDS coding. A detailed proof of this result is provided in Appendix B. Here we provide the main intuition.

Let us first consider the simple case of replication. Replication is essentially a $(P,1)$ MDS Code as one single real-valued symbol is replicated $P$ times. Under an adversarial error model, one could use a majority voting among the $P$ received values and thus correct upto $\lfloor\frac{P-1}{2}\rfloor$ errors. However, under the probabilistic error model, the probability that two replicas are affected by the same value of error is . Thus, as long as not all the $P$ received values are equal, one can detect that errors have occurred. Moreover, if at least two received values match out of $P$, it is most likely the original symbol unaffected by errors. Thus, one can correct $P-2$ errors with probability $1$. If no symbols match, then the decoder is able to declare a decoding failure.

This idea also extends to any $(P,Q)$ MDS Code. For a $(P,Q)$ MDS Code, the minimum Hamming distance between two codewords is $d_{min}=P-Q+1$. Thus, if the number of errors are within $\lfloor\frac{d_{min}-1}{2}\rfloor=\lfloor\frac{P-Q}{2}\rfloor$, the received output vector lies within a Hamming ball of radius $\lfloor\frac{d_{min}-1}{2}\rfloor$ around the original codeword, and is thus closest in Hamming distance to the original codeword as compared to any other codeword. If one allows for more than $\lfloor\frac{d_{min}-1}{2}\rfloor$ errors, the received output might fall within the $\lfloor\frac{d_{min}-1}{2}\rfloor$ Hamming ball of another codeword, and hence may be decoded incorrectly. However, what Theorem 3 says is that if the error values are not adversarially chosen but allowed to be probabilistic, then even if we go slightly beyond $\lfloor\frac{P-Q}{2}\rfloor$, i.e., upto a Hamming radius of $P-Q-1$, the probability of the received output being closer to a different codeword is . In other words, for a given codeword, the set of all possible outputs that are closer to other codewords in a Hamming sense has probability measure in the space of all possible values that the output can take, i.e., the Hamming ball of radius $P-Q-1$.

Let $\bm{H}$ be the $(P-Q)\times P$ sized parity check matrix of the MDS code, such that $\bm{H}\bm{G}^{T}=\bm{0}$. We first propose the following decoding algorithm (see Algorithm 1) to produce $\widehat{\bm{e}}$, as an estimate of $\bm{e}$, for a given channel output $\bm{z}$. If an $\widehat{\bm{e}}$ is obtained, the decoder can uniquely solve for $\widehat{\bm{q}}$ from the linear set of equations $\bm{G}^{T}\widehat{\bm{q}}=\bm{z}-\widehat{\bm{e}}$.

Note that, for $\bm{H}\bm{e}=\bm{H}\bm{e}^{\prime}$ to hold, $\bm{e}=\bm{e}^{\prime}+\bm{h},$ where $\bm{h}\in Null(\bm{H})\backslash\{\bm{0}\}$. Thus $|\mathcal{A}^{\prime}\cup\mathcal{A}|-|\mathcal{A}^{\prime}|$ indices of $\bm{h}$, indexed in the set $(\mathcal{A}^{\prime}\cup\mathcal{A})\backslash\mathcal{A}^{\prime}$ match exactly with $\bm{e}$ (see Fig. 6).

The key intuition behind this proof is that once a certain number of elements of a vector $\bm{h}$ are allowed to be chosen from iid Gaussian distributions, the probability of the vector $\bm{h}$ still lying in $Null(\bm{H})$ becomes . To understand this better, observe that,

While we theoretically show that real number MDS coding can correct $P-Q-1$ errors, our proposed decoding algorithm requires sparse reconstruction for undetermined systems which is NP Hard . For practical purposes, one might consider using an L1-norm relaxation or other kinds of polynomial-time sparse reconstruction algorithms proposed in the compressed sensing literature , which are known to be reasonably accurate under various restrictions on matrix $\bm{H}$.

Let us now understand what these models mean in the context of coded DNNs.

V-B Error Models for the coded DNN problem.

Recall from our problem formulation (Section II) that we are interested in model-parallel architectures that parallelize each layer across $P$ error-prone nodes (that can be reused across layers) because the nodes cannot locally store the entire matrix $\bm{W}^{l}$. As the steps $O1$, $O2$ and $O3$ are the most computationally intensive ($\Theta(N^{2}B)$) steps at each layer, we restrict ourselves to schemes where these three steps for each layer are parallelized across the $P$ nodesThe steps $C1$ and $C2$ are lower in computational complexity, i.e., $\Theta(NB)$ which is lower in scaling sense as compared to $\Theta(N^{2}B)$ and hence may or may not be parallelized across multiple nodes.. In such schemes, communication will be required after steps $O1$ and $O2$ as the partial computation outputs of steps $O1$ and $O2$ at one layer might be required at another node to compute the input $\bm{X}^{(l+1)}$ or backpropagated error $\bm{\Delta}^{(l-1)}$ for another layerNote that there could be alternate parallelization schemes where the different layers of the network are parallelized across different nodes instead of each layer being parallelized across all nodes. These schemes might have lower communication but some of the nodes stay idle and under-utilized, i.e., while computations are being performed in one layer, the nodes containing the other layers stay idle. It will be an interesting future work to explore the computation-communication tradeoffs among these alternate parallelization schemes.. We define Error Models $1$ and $2$, which are essentially realizations of the probabilistic and adversarial models for the coded DNN problem, with some additional assumptions.

Any node can have soft-errors but only during the steps $O1$, $O2$ and $O3$, which are the most computationally intensive operations in DNN training. Encoding, error-detection, decoding, nonlinear activation and Hadamard product are assumed to be error-free. These operations require negligible time and number of operationsThe shorter the computation, the lower is the probability of soft-errors. E.g., a Poisson process of soft errors makes the number of soft-errors have mean proportional to the interval length. because most of the time and resources are spent on steps $O1$, $O2$ and $O3$. There is no specific assumption on the locations of the erroneous nodes and they may be adversarial. However, the total number of erroneous nodes at any layer during $O1$, $O2$ and $O3$ are known to be bounded by $t_{1}$, $t_{2}$ and $t_{3}$ respectively. There is also no assumption on the distribution of the errors for this model, but all the output values of an erroneous node, e.g., all the values of the output matrix or vector are affected by errors.

Any node can have soft-errors during any primary operation such as encoding, decoding, nonlinear activation, Hadamard product as well as steps $O1$, $O2$ and $O3$, and there is no bound on the number of errors. The locations of the erroneous nodes can still be adversarial. The entire output of an erroneous node (all the values of the output matrix or vector) is assumed to be corrupted by additive iid Gaussian noise. However, under Error Model $2$, we use verification steps to check for decoding errors that have very low complexity (compared to the primary steps), and hence those verification steps are assumed to be error-free.

Error Model $1$ is a “worst-case” abstraction, which is useful when it is difficult to place probabilistic priors on errors. It essentially means that the number of errors that can occur in the longer steps is bounded. Hence, if we choose a strategy with higher error tolerance, we can correct all errors. On the other hand, Error Model $2$ allows for errors in all primary operations and also has no upper bound on the number of errors. However, it makes one simplifying assumption. Specifically, the continuous distribution of noise simplifies our analyses by avoiding complicated probability distributions that arise in finite number of bits representations. We acknowledge that this simplification can lead to optimistic conclusions, e.g., it allows us to correct more errors than the adversarial model (see Theorem 3) with probability $1$ and also detect the occurrence of errors (“garbage outputs”) with probability $1$ (because the noise takes any specific value with probability zero; see Appendix B). This model is only accurate in the limit of large number of bits of precision. In practical implementations, our probability $1$ results should be interpreted as holding with high probability (e.g. it is unlikely, but possible, that two erroneous nodes produce the exact same garbage output). Note that because both replication and coding can exploit Error Model $2$ for error-correction and detection, it does not bias our results towards coding relative to replication.

V-C Error Tolerance Goals for the coded DNN Strategy.

We would like to be able to correct as many erroneous nodes as possible after the steps $O1$ and $O2$, because outputs are communicated to other nodes after these two steps.

Under Error Models $1$, for any layer $l$, the error tolerances are $(t_{f},t_{b})$ if $t_{f}$ and $t_{b}$ erroneous node outputs can be detected and corrected in the worst case immediately after steps $O_{1}$ and after step $O_{2}$ respectively. Similarly, under Error Model $2$, the error tolerances are $(t_{f},t_{b})$ if $t_{f}$ and $t_{b}$ erroneous node outputs can be detected and corrected with probability $1$ immediately after steps $O_{1}$ and after step $O_{2}$ respectively.

Our goal is to maximize the values of these error tolerances under both the error models.

For any coding strategy, the achievable $t_{f}$ and $t_{b}$’s depend on the number of nodes available ($P$) and other parameters of the coding strategy, e.g., $m,n$ etc. as derived in Section VIII. Note that, after steps $O1$ and $O2$, we do not necessarily correct only the errors that occur during those steps. Depending on the coding strategy used, errors occurring in other steps could also get corrected after either $O1$ or $O2$. Under Error model $1$, the values of the achievable $t_{f}$ and $t_{b}$’s will be required to be greater than appropriate functions of $t_{1},t_{2}$ and $t_{3}$ based on the coding strategy being used, as we also elaborate in Section VIII.

V-D Communication Complexity.

In this work, we use standard definition of communication complexity for fully distributed and decentralized architectures, as mentioned in .

The communication cost of sending a message of $N$ items between two nodes will be modeled by $\alpha+\beta N$, in the absence of network conflicts. Here $\alpha$ and $\beta$ are two constants representing the message startup time and per data item transmission time respectively.

We assume that each node can communicate simultaneously to at most a constant number (say $2$) of nodes. Thus, when one node has to broadcast the same $N$ values to $P$ other nodes, it usually initiates communication link (or startup) with the other nodes in the form of a spanning-tree in $\log{P}$ rounds and then starts communicating the $N$ values across this tree-like transmission network of the nodes. For more details, the reader is referred to . Following , the communication cost for this type of broadcast is given by: $\alpha\log{P}+\beta N$. Here, the first term arises because the communication link (or startup) between all the nodes is set up in $\Theta(\log_{2}{P})$ rounds, and then the second term denotes the cost of sending the $N$ values across this tree-like network of nodes. When multiple nodes have to communicate with each other, the communication cost can be efficiently managed using collective communication protocols, as suggested in . For instance, when all nodes send their own, unique message of $N$ values to all other nodes, a communication protocol called All-Gather is used whose communication cost is $\alpha\log{P}+2\beta PN$. We will use Broadcast and All-Gather protocols to prove our results on communication complexities in Appendix D.

VI Applying Existing Strategies to the coded DNN Problem

The problem formulation $2$ stated in Section II discusses our goals. Essentially, for $B=1$, we are required to design a coded DNN training strategy, that we denote as $\mathcal{C}(N,K,P)$, which performs distributed “post” and “pre” multiplication of the same matrix $\bm{W}$ with vectors $\bm{x}$ and $\bm{\delta}^{T}$ respectively at each layer and a distributed update ($\bm{W}+\eta\bm{\delta}\bm{x}^{T}$), along with all the other operations using $P$ memory-constrained nodes.

After these computations, all the replicas computing the same sub-vector, i.e., say $\bm{s}_{i}$, exchange their computational outputs for error detection and correction. Note that the communication cost for exchanging outputs is only a function of the number of nodes, $P$, and does not depend on $N$. This is because the nodes can just exchange a single value of their computation result among each other instead of the entire sub-vector. Thus, this communication cost is much lower as compared to the computational cost of matrix multiplication in the regime $N\ll P$.

Under Error Model $1$, any $t=\lfloor\frac{P-mn}{2mn}\rfloor$ errors can be tolerated in the worst case. However under Error Model $2$, the probability of two outputs having exactly same error is . As long as an output occurs at least twice, it is almost surely the correct output. Thus, any $t=\frac{P}{mn}-2$ errors can be detected and corrected. Then, the correct sub-vectors ($\bm{s}_{i}$’s) are communicated to the respective nodes that require it for generating their input for the next layer, and the sub-matrices stored in the erroneous nodes are regenerated by accessing other nodes known to be correct.

Additional Steps: At regular intervals, the system also checkpoints, i.e., sends the entire DNN to a disk for storage. This disk-storage, although time-intensive to retrieve from, can be assumed to be error-free. Under Error Model $2$, if more than $t$ errors occur, then with probability $1$, none of the outputs match. The system detects the occurrence of errors even though it is unable to correct them. So, it retrieves the DNN from the disk and reverts the computation to the last checkpoint.

A similar technique is applied for backpropagation. The the node with index $(i,j)$ accesses $\bm{\delta}^{T}_{i}$ and computes $\bm{\delta}^{T}_{i}\bm{W}_{i,j}$. Finally the last node in every column aggregates and computes $\sum_{i=0}^{m-1}\bm{\delta}^{T}_{i}\bm{W}_{i,j}=\bm{c}^{T}_{j}$ for $j=0,1,\dots,n-1$. Error check occurs similarly. If errors can be corrected, then $\bm{c}^{T}_{j}$’s are communicated to the respective nodes that require it to compute backpropagated error for the next layer, along with $\bm{x}_{j}$. Interestingly, after these operations, the node with index $(i,j)$ has $\bm{x}_{j}$ and $\bm{\delta}^{T}_{i}$, and is thus able to update itself as $\bm{W}_{i,j}\leftarrow\bm{W}_{i,j}+\eta\bm{\delta}_{i}\bm{x}^{T}_{j}$ respectively.

The error tolerances for the replication strategy are $t_{f}=t_{b}=\lfloor\frac{P-mn}{2mn}\rfloor$ under Error Model $1$ and $t_{f}=t_{b}=\frac{P}{mn}-2$ under Error Model $2$, assuming $mn$ divides $P$.

where $\bm{G}_{r}$ and $\bm{G}_{c}$ are the generator matrices of the two systematic MDS codes for the row and column dimensions, $\otimes$ denotes the Kronecker product and $\bm{I}_{N/m}$ and $\bm{I}_{N/n}$ denote identity matrices of the corresponding dimensions.

In step $O1$, only $P_{f}$ nodes corresponding to the $(\frac{P_{f}}{n},m)$ code are active. Similarly, in step $O2$, only $P_{b}$ nodes are active corresponding to the $(\frac{P_{b}}{m},n)$ code. Errors that happen in the update step $O3$ corrupt the updated sub-matrices and are detected and corrected the next time those sub-matrices are used to produce an output to be sent to another node, which could be either after step $O1$ or step $O2$ of the next iteration at that layer. Thus, errors of step $O3$ are corrected either after step $O1$ or step $O2$ at that layer, in the next iteration.

Under Error Model $1$, in the worst case, the strategy thus requires $t_{f}\geq t_{1}+t_{3}$ and $t_{b}\geq t_{2}+t_{3}$ to be able to detect and correct all the errors. Under Error Model $2$, when the number of errors are greater than $t_{f}$ or $t_{b}$, they can only be detected with probability $1$ but cannot be corrected, as elaborated in .

The error tolerances for the MDS-code-based strategy are as follows: $t_{f}=\lfloor\frac{P_{f}-mn}{2n}\rfloor,\ t_{b}=\lfloor\frac{P_{b}-mn}{2m}\rfloor$ under Error Model $1$ and $t_{f}=\frac{P_{f}-mn-n}{n},\ t_{b}=\frac{P_{b}-mn-m}{m}$ under Error Model $2$.

VII Our Proposed coded DNN Training Strategy for mini-batch B=1𝐵1B=1

In this section, we introduce our proposed unified coded DNN training strategy. We propose an initial encoding scheme for $\bm{W}$ at each layer such that the same encoding allows us to perform coded “post” and “pre” multiplication of $\bm{W}$ with vectors $\bm{x}$ and $\bm{\delta}^{T}$ respectively at each layer in every iteration. The key idea is that we encode $\bm{W}$ only for the first iteration. For all subsequent iterations, we encode and decode vectors (hence complexity $o(\frac{N^{2}}{K})$ as we show in Theorem 5) instead of matrices. As we will show, the encoded weight matrix $\bm{W}$ is able to update itself, maintaining its coded structure at very low additional overhead.

Initial Encoding of $\bm{W}$ (Pre-processing Step): Every node stores an $\frac{N}{m}\times\frac{N}{n}$ sub-matrix (or block) of $\bm{W}$ encoded using Generalized PolyDot. Recall from 1) that,

For $p=0,1,\ldots,P-1$, node $p$ stores $\widetilde{\bm{W}}_{p}:=\widetilde{\bm{W}}(u,v)|_{u=a_{p},v=b_{p}}$, i.e., the evaluation of $\widetilde{\bm{W}}(u,v)$ at $(u,v)=(a_{p},b_{p})$, at the beginning of the training. This coded sub-matrix has $\frac{N^{2}}{K}$ entries. Thus every node stores a sub-matrix $\widetilde{\bm{W}}_{p}=\widetilde{\bm{W}}(a_{p},b_{p})$ at the beginning of the training which has $\frac{N^{2}}{K}$ entries.

Encoding of matrix $\bm{W}$ is done only before the first iteration.

Feedforward stage: Assume that the entire input $\bm{x}$ to the layer is made available at every node by the previous layer (this assumption is justified at the end of this paragraph). Also assume that the updated $\widetilde{\bm{W}}_{p}$ of the previous iteration is available at every node (this assumption will be justified when we show that the encoded sub-matrices of $\bm{W}$ are able to update themselves, preserving their coded structure).

For $p=0,1,\ldots,P-1$, node $p$ first block-partitions $\bm{x}$ into $n$ equal parts, and encodes them using the polynomial:

For $p=0,1,\dots,P-1$, the $p$-th node evaluates the polynomial $\widetilde{\bm{x}}(v)$ at $v=b_{p}$, yielding $\widetilde{\bm{x}}_{p}:=\widetilde{\bm{x}}(b_{p})$. E.g., for $n=2$, $\bm{x}$ is encoded as $\widetilde{\bm{x}}(v)=\bm{x}_{0}v+\bm{x}_{1}$.

Next, each node computes the matrix-vector product: $\widetilde{\bm{s}}_{p}:=\widetilde{\bm{W}}_{p}\widetilde{\bm{x}}_{p}$. The computation of $\widetilde{\bm{s}}_{p}$ at node $p$ is equivalent to the evaluation, at $(u,v)=(a_{p},b_{p})$, of the following polynomial:

even though the node is not explicitly evaluating it by accessing all its coefficients separately. Now, fixing $j^{\prime}=j$, observe that the coefficient of $u^{i}v^{n-1}$ for $i=0,1,\dots,m-1$ is $\sum_{j=0}^{n-1}\bm{W}_{i,j}\bm{x}_{j}=\bm{s}_{i}$. Thus, these $m$ coefficients constitute the $m$ sub-vectors of $\bm{s}=\bm{W}\bm{x}$. Therefore, $\bm{s}$ can be recovered at any node if it can reconstruct all the coefficients of the polynomial $\widetilde{\bm{s}}(u,v)$ in 12, or rather just these $m$ coefficients. The matrix-vector product computed at the $p$-th node results in the evaluation of this polynomial at $(u,v)=(a_{p},b_{p})$. Every node then sends this product to every other nodeRecall that there is no single master node, and every node replicates the functioalities of the decoder. Using efficient all-to-all communication protocols popular in parallel computing, the communication cost of all nodes broadcasting its own sub-vector $\widetilde{\bm{s}}_{p}$ of length $\frac{N}{m}$ to all other nodes has a communication cost of $\alpha\log{P}+2\beta\frac{N}{m}P=\Theta(\frac{N}{m}P)$ using All-Gather protocol. We are currently examining strategies to reduce this cost further. where some of these products may be erroneous. Now, if every node can still reconstruct the coefficients of $u^{i}v^{n-1}$ from these evaluations, then it can successfully decode $\bm{s}_{0},\bm{s}_{1},\ldots,\bm{s}_{m-1}$.

We use one of the substitutions $u=v^{n}$ or $v=u^{m}$ (elaborated in Appendix C), to convert $\widetilde{\bm{s}}(u,v)$ into a polynomial in a single variable and then use standard decoding techniques to interpolate the coefficients of a polynomial in one variable from its evaluations at $P$ arbitrary points when some evaluations have an additive error. Once $\bm{s}$ is decoded at each node, the nonlinear function $f(\cdot)$ is applied element-wise to generate the input for the next layer. This also makes $\bm{x}$ available at every node at the start of the next feedforward layer, justifying our assumption.

Regeneration: If the number of errors are few ($\leq$ error tolerance), the nodes are not only able to decode the vectors correctly but also locate which nodes were erroneous (see Appendix C). Thus, the encoded $\bm{W}$ stored at those nodes are regeneratedThe encoded matrix at any node is the evaluation of a polynomial whose coefficients correspond to the original sub-matrices $\bm{W}_{i,j}$. Thus, the number of nodes required by an error-prone node is the degree of this polynomial $+1$. Substituting $u=v^{n}$ (alternatively, $v=u^{m}$), this degree is $mn-1$, and thus an error-prone node needs to access $mn$ correct nodes to regenerate itself. by accessing some of the nodes that are known to be correct and the algorithm proceeds forward.

It might appear that regeneration violates the storage constraint of each node, i.e., a storage of only a $\frac{1}{K}$ fraction of matrix $\bm{W}$. However, note that the coded sub-matrix can also be computed element-wise rather than all at once, while adhering to the storage constraint. E.g. if the stored sub-matrix $\widetilde{\bm{W}}(a_{p},b_{p})$ of size $\frac{N}{m}\times\frac{N}{n}$ is required to be regenerated, the node can access only the first element (location $(0,0)$) of the stored sub-matrix of any $mn$ nodes to regenerate the element $(0,0)$ of $\widetilde{\bm{W}}(a_{p},b_{p})$. Then it deletes all the gathered values, and moves on to location $(0,1)$ and so on. This process only requires an additional storage of $o\left(\frac{N^{2}}{K}\right)$.