Adaptive Coding for Matrix Multiplication at Edge Networks

In this section, we provide a short background on existing coded computation mechanisms for matrix multiplication.

Assume a canonical setup, where $A$ and $B$ are $K\times K$ matrices and divided into two sub-matrices $A_{0}$, $A_{1}$, $B_{0}$, and $B_{1}$. The product codes divide matrices column-wise, i.e., $A_{i}$ and $B_{i}$ are $K\times\frac{K}{2}$ matrices, for $i\in\{0,1\}$, and use two-level MDS codes. Considering that $A_{2}=A_{0}+A_{1}$ and $B_{2}=B_{0}+B_{1}$, nine codes are constructed by $A_{i}^{T}B_{i}$, for $i,j\in\{0,1,2\}$. In polynomial codes the master device, by dividing matrices column-wise, creates polynomials $\alpha(n)=A_{0}+A_{1}n$ and $\beta(n)=B_{0}+B_{1}n^{2}$ for worker $w_{n}$, which multiplies $\alpha(n)\beta(n)$. MatDot follows a similar idea of polynomial codes with the following difference: $A$ and $B$ are divided row-wise.

Table I shows the recovery threshold ($k$) [7, 6, 8], computing load per worker ($\gamma$) (this is the simplified analysis presented in Section III-A and further detailed in Appendix A), which shows the number of required multiplications, storage load per worker ($\mu$), which shows the average amount of memory needed to store matrices and their multiplication (as detailed in Section III-B), and probability of successful computation ($\rho$), which is calculated assuming that the failure probability of workers is $\frac{1}{3}$ and independent. As seen, although MDS is the best in terms of recovery threshold ($k$), it introduces more computing load per worker (because of partitioning only one of the matrices). Also, MatDot, MDS and repetition codes perform worse than polynomial and product codes in terms of storage load per worker. Product codes require at least $N=9$ workers due to their very design, and for repetition codes the number of workers should be an even number, but MDS, polynomial and MatDot codes are more flexible. As seen, there is a trade-off among $\{k,\gamma,\mu,\rho\}$, which we aim to explore in this paper by taking into account the limited edge computing resources including computing power and storage. For example, if there is no constraint on the total number of workers, but only on computing load, we will likely select product or polynomial codes. Next, we will provide a computing time and storage analysis of existing codes, and develop ACM² that selects the best code depending on edge constraints.

Assuming a shifted-scaled exponential distribution as a computation delay model with $\lambda$ as the straggling parameter and $\alpha\in\{p_{\text{rep}},p_{\text{mds}},p^{2}_{\text{poly}},p_{\text{matdot}},p^{2}_{\text{pro}}\}$ as the scale parameter for each worker, average computing time for repetition codes $T_{\text{rep}}$ and MDS codes $T_{\text{mds}}$ are expressed [1] as

Proof: The proof is provided in Appendix B. $\Box$

The product codes have different performance in two different regimes. In the first regime the number of workers scales sublinearly with $p_{\text{pro}}^{2}$, i.e., $N=p_{\text{pro}}^{2}+\mathcal{O}(p_{\text{pro}})$, while in the second regime, the number of workers scales linearly with $p_{\text{pro}}^{2}$, i.e., $N=p_{\text{pro}}^{2}+\mathcal{O}(p_{\text{pro}}^{2})$. The computing time analysis of product codes is provided in these two regimes next.

Proof: The proof is provided in Appendix C. $\Box$

In this section, we provide storage requirements of the codes that we explained in Section II-B. These codes have storage requirements both at the master and worker devices. In particular, we assume that each entry of matrices $A$ and $B$ requires a fixed amount of memory. Our analysis, which is provided next, quantifies how many of these entries are needed to be stored at the master and worker devices.

In this section, we present our ACM² algorithm. We consider an iterative process such as gradient descent, where matrix multiplications are required at each iteration. Our goal is to determine the best matrix multiplication code and the optimum number of matrix partitions by taking into account the task completion delay, i.e., computing time, storage requirements and decoding probability of each code. In particular, ACM² solves an optimization problem at each iteration, and determines which code is the best as well as the optimum number of partitions for that code. For example, MDS codes may be good at iteration $i$, while polynomial codes may suit better in later iterations. The optimization problem is formulated as

The objective function selects the best code $\pi$ from the set $\{\text{rep},\text{mds},\text{poly},\text{matdot},\text{pro}\}$ as well as the optimum number of partitions $p_{\pi}$. The first constraint is the storage constraint, which limits the storage usage at master and worker devices with thresholds $S_{\text{thr}}^{m}$ and $S_{\text{thr}}^{w}$. The second constraint is the successful decoding constraint, where successful decoding probability $\rho_{\pi}$ should be larger than the threshold $\rho_{\text{thr}}$. The successful decoding probability is defined as the probability that the master receives all the required results from workers. If we assume that the failure probability of each worker is $(1-\phi)$ and independent, the total number of workers is $N$ and the number of sufficient results is $k_{\pi}$, one may formulate the probability of success for each coding method as a binomial probability $\rho_{\pi}=\sum_{i=k_{\pi}}^{N}\binom{N}{i}(\phi)^{i}(1-\phi)^{N-i}$. The third constraint makes sure that the recovery threshold $k_{\pi}$ is less than the number of workers. The fourth constraint makes the number of partitions larger than or equal to 2, otherwise there is no matrix partitioning, which is a degenerate case.

Recovery threshold is defined as the minimum number of results that the master needs to receive to be able to compute the final result. In product codes the master can finish matrix multiplication calculation if it receives any $k_{\text{pro}}=2(p_{\text{pro}}-1)\sqrt{N}-(p_{\text{pro}}-1)^{2}+1$ results from workers [6]. In the example of Table I, by plugging in $N=9$ and $p_{\text{pro}}=2$, the recovery threshold for product code becomes $k_{\text{pro}}=6$. In polynomial codes, $k_{\text{poly}}=p^{2}_{\text{poly}}=4$. Indeed, there are four unknowns in $\alpha(n)\beta(n)=A_{0}B_{0}+A_{1}B_{0}n+A_{0}B_{1}n^{2}+A_{1}B_{1}n^{3}$, so the master needs to receive at least four results from workers to be able to calculate $C=A^{T}B$. In MatDot codes, $k_{\text{matdot}}=2p_{\text{matdot}}-1=3$. Since there exist three unknowns in $\alpha(n)\beta(n)=(A_{0}+A_{1}n)(B_{0}n+B_{1})=A_{0}B_{1}+(A_{0}B_{0}+A_{1}B_{1})n+A_{1}B_{0}n^{2}$, the master needs to receive at least three results from workers to calculate $C=A^{T}B$. In MDS codes, $k_{\text{mds}}=p_{\text{mds}}=2$ [1], and in repetition codes $k_{\text{rep}}=N-\frac{N}{p_{\text{rep}}}+1$, for $p_{\text{rep}}|N$, since the master can decode the final result when it receives $A_{i}^{T}B$, $\forall i=1,\ldots,p_{\text{rep}}$. Therefore, in the example of Table I, by plugging in $p_{\text{rep}}=2$, the recovery threshold for repetition codes become $\lfloor\frac{N}{2}+1\rfloor$.

We define the computing load as the total number of multiplications (i.e., $a_{i,k}b_{k,j}$, $\forall i,k,j$) to compute $C=A^{T}B$. We note that the computing load could be considered as the static version of the computing time analysis. We assume that each $a_{i,k}b_{k,j}$ multiplication takes a fixed amount of time, so the total computing time will be proportional to the the number of such multiplications . Next, we provide the detailed calculations for computing load per worker.

In product codes, the matrix partitioning is column-wise, so we have $A_{i}\in\mathbb{R}^{K\times\frac{K}{2}}$ and $B_{i}\in\mathbb{R}^{K\times\frac{K}{2}}$, for $i\in\{0,1\}$, after partitioning. Thus, $\frac{K}{2}\times K\times\frac{K}{2}=\frac{K^{3}}{4}$ multiplications are needed to compute $A^{T}_{i}B_{i}\in\mathbb{R}^{\frac{K}{2}\times\frac{K}{2}}$. In polynomial codes, the matrix partitioning is also column-wise, and we have $A_{i}\in\mathbb{R}^{K\times\frac{K}{2}}$ and $B_{i}\in\mathbb{R}^{K\times\frac{K}{2}}$, for $i\in\{0,1\}$ after partitioning, so $\alpha(n)\in\mathbb{R}^{\frac{K}{2}\times K}$ and $\beta(n)\in\mathbb{R}^{K\times\frac{K}{2}}$. Similar to the product codes, $\frac{K}{2}\times K\times\frac{K}{2}=\frac{K^{3}}{4}$ multiplications are needed to compute $\alpha(n)\beta(n)\in\mathbb{R}^{\frac{K}{2}\times\frac{K}{2}}$. In MatDot codes, the matrix partitioning is row-wise. It means that we have $A_{i}\in\mathbb{R}^{\frac{K}{2}\times K}$ and $B_{i}\in\mathbb{R}^{\frac{K}{2}\times K}$, for $i\in\{0,1\}$ after partitioning. Hence, $\alpha(n)\in\mathbb{R}^{K\times\frac{K}{2}}$ and $\beta(n)\in\mathbb{R}^{\frac{K}{2}\times K}$ and $K\times\frac{K}{2}\times K=\frac{K^{3}}{2}$ multiplications are needed to compute $\alpha(n)\beta(n)\in\mathbb{R}^{K\times K}$. In both MDS and repetition codes, one of the matrices, say $A$, is partitioned column-wise, so we have $A_{i}\in\mathbb{R}^{K\times\frac{K}{2}}$, for $i\in\{0,1\}$, after partitioning and $B\in\mathbb{R}^{K\times K}$. Thus, $\frac{K}{2}\times K\times K=\frac{K^{3}}{2}$ multiplications are needed to compute $A^{T}_{i}B\in\mathbb{R}^{\frac{K}{2}\times K}$.

We can compute the storage load per worker of MDS, repetition, product, polynomial and MatDot codes according to (13), (14) and (15). In the example of Table I, assuming $K=L$ and $p_{\text{mds}}=p_{\text{rep}}=p_{\text{poly}}=p_{\text{pro}}=p_{\text{matdot}}=2$, storage load per worker of polynomial and product codes becomes $K^{2}+\frac{K^{2}}{4}$, while it is $2K^{2}$ for MDS, repetition and MatDot codes.

As we discussed in Section III-C, the successful decoding probability can be defined as $\rho_{\pi}=\sum_{i=k_{\pi}}^{N}\binom{N}{i}(\phi)^{i}(1-\phi)^{N-i}$, where $(1-\phi)$ is the failure probability of each worker. By plugging in $(1-\phi)=\frac{1}{3}$, $k_{\text{pro}}=6$, $k_{\text{poly}}=4$, $k_{\text{matdot}}=3$, $k_{\text{mds}}=2$ and $k_{\text{rep}}=\lfloor\frac{N}{2}+1\rfloor$ we can compute the successful decoding probability for different $N\in\{6,7,8,9\}$ for each coding method in Table I.

Reyni’s Representation: The order statistics of an exponential distribution can be shown as linear combinations of independent exponential random variables with a special sequence of coefficients

for $k=1,\dots,n$. Where $\overset{L}{=}$ means equal in distribution and $X_{1},\dots,X_{n}$ are independent exponential random variables with mean $\frac{1}{\lambda}$ [32].

The expected value of the $k^{\text{th}}$ order statistic of exponential distribution with mean $\frac{1}{\lambda}$, is expressed as the following

where $H_{n}\triangleq\sum_{i=1}^{n}\frac{1}{i}$.

The function $f(X)=a+bX$ is a monotone function as its first derivative does not change sign. When a monotone function is applied to an ordered set, it preserves the given order [33]. Now, let us define $Y_{i}=a+bX_{i}$ for $i=1,\dots,n$ where $X_{i}$ are independent exponential random variables with mean $\frac{1}{\lambda}$. By monotonicity, we have $Y_{(k)}=a+bX_{(k)}$ and by considering Reyni’s representation for the $k^{\text{th}}$ order statistic of exponential random variables, we have

The expected value of the $k^{\text{th}}$ order statistic of shifted-scaled exponential distribution with mean $a+\frac{b}{\lambda}$ is expressed as the following

In this paper, we assume shifted exponential distribution for computation time of the original task and shifted-scaled exponential distribution for computation time of each sub-task. Thus, if we assume $X$ as an exponential random variable with mean $\frac{1}{\lambda}$, the computation time of the original task can be expressed as $t=X+1$ and if we assume $X_{i}$, $i=1,\dots,N$ as $N$ independent exponential random variables with mean $\frac{1}{\lambda}$, the computation time of each sub-task can be expressed as $t_{i}=\frac{X_{i}+1}{\alpha},\alpha\in\{p_{\text{rep}},p_{\text{mds}},p^{2}_{\text{poly}},p_{\text{matdot}},p^{2}_{\text{pro}}\}$. Hence, if we replace both $a$ and $b$ with $\frac{1}{\alpha}$ in (20), the expected value of the computation time of each worker for polynomial and MatDot codes can be shown as $\frac{1}{\alpha}+\frac{1}{\alpha\lambda}(H_{N}-H_{(N-k_{i})})$ where, $k_{i}\in\{k_{\text{poly}},k_{\text{matdot}}\}$ and $\alpha\in\{p^{2}_{\text{poly}},p_{\text{matdot}}\}$. Moreover, the $N^{\text{th}}$ harmonic number, $H_{N}$ can be approximated by natural logarithm function, i.e., $H_{N}\approx log(N)$ and $H_{(N-k_{i})}\approx log(N-k_{i})$. Therefore, the expected value of the computation time of each worker for aforementioned coding methods becomes

where $i\in\{\text{poly},\text{matdot}\}$, $k_{i}\in\{k_{\text{poly}},k_{\text{matdot}}\}$ and $\alpha\in\{p^{2}_{\text{poly}},p_{\text{matdot}}\}$. $\Box$

Although we can directly use order statistics to compute the computation time of repetition, MDS, polynomial and MatDot codes, it is challenging for product codes, because the decodability condition of product codes depends on which specific tasks are completed. However, with the help of the idea of edge-removal process in a bipartite graph [30] and order statistics, one can find an asymptotic computation time for product codes in two different regimes. Assuming exponential distribution as a delay model with mean $\frac{1}{\lambda}$ for each worker, the average computing time $T^{{}^{\prime}}_{\text{pro}}$ for products codes in the first regime is as the following [7, 30, 31]

where $c_{\tau/2+1}\approx(1+\tau/2)+\sqrt{(1+\tau/2)\log(1+\tau/2)}$.

Also, the average computation time of $(\sqrt{1+\delta}p_{\text{pro}},p_{\text{pro}})^{2}$ product codes with $(1+\delta)p^{2}_{\text{pro}}$ workers (assuming exponential distribution with mean $\frac{1}{\lambda}$ for the computation time of each worker), for a fixed constant $\delta$, as $p_{\text{pro}}$ grows to infinity, is lower bounded as follows [7]

On the other hand, since we consider the worst case scenario to compute the recovery threshold of product codes [6], the upper bound on the computational time of the product codes in the second regime is the $(k_{\text{pro}})^{\text{th}}$ order statistics of $(1+\delta)p^{2}_{\text{pro}}$ computational times, where $k_{\text{pro}}=N-(\sqrt{N}-p_{\text{pro}}+1)^{2}+1$.

Therefore, based on the above explanations, one can define $T^{\prime\text{up}}_{\text{pro}}:=\frac{2}{\lambda}\log\left(\frac{1+\delta+\sqrt{1+\delta}}{\delta}\right)$ and $T^{\prime\text{low}}_{\text{pro}}:=\frac{1}{\lambda}\log\left(\frac{1+\delta}{\delta}\right)$ as upper bound and lower bound of computational time of product codes, with exponential distribution as delay model of each worker in the second regime.

One can find asymptotic computation time of product codes assuming exponential distribution as a delay model for each worker in the previous section of this Appendix. On the other hand, we assume shifted-scaled exponential distribution for computation time of each worker in this paper. Therefore, according to equation (20), we can compute (5), (6) and (7) using (22), (23) and (24), respectively by replacing both shift and scale parameters, $a$ and $b$, with $\frac{1}{p^{2}_{\text{pro}}}$ in equation (20). $\Box$