Hierarchical coded elastic computing

Elasticity is offered by cloud service providers to exploit under-utilized computing resources. The low-cost elastic nodes can leave and join any time during the computation cycle. The possibility of elastic events occurring together with the problem of slow nodes, referred to as stragglers, increases the uncertainty of the system, leading to computation delay. Recent results have shown that coded computing can be used to reduce the negative effect of elasticity and stragglers. In this paper, we propose two hierarchical coded elastic computing schemes that can further speed up the system by exploiting stragglers and effectively allocating tasks among available nodes. In our simulations, our scheme realizes 45% improvement in average finishing time compared to the state-of-the-art coded elastic computing scheme.


INTRODUCTION
Cloud computing services such as Amazon EC2 Spot and Microsoft Azure Batch offer non-dedicated computing nodes at a much lower cost than dedicated nodes. The caveat of nondedicated nodes is that they can be preempted at a short notice. Similarly, additional node may be made available. These two types of events are referred to as elastic events. Elasticity presents novel challenges in allocating tasks within the available nodes. The challenges due to elastic events share a thematic connection to the stragglers' problem, in which response times of nodes are unpredictable. However, there are two major properties that differentiate elastic nodes from stragglers. First, in an elastic setup new nodes can join the computation, while in the case of stragglers there is no newly available nodes that can benefit the system. Secondly, elasticity occurs with short notice which gives the master the opportunity to re-allocate computation among the available nodes. However, nodes can become stragglers without any notice.
Recently, in [1] a coded elastic computing (CEC) scheme was proposed that makes use of coded computing to deal This research was supported in part by a Discovery Research Grant from the Natural Sciences and Engineering Research Council of Canada (NSERC), by DiDi scholarship, by the Ontario graduate scholarship, and by a grant from Huawei Technologies, Inc. This paper was presented at the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Toronto, Canada, June 2021. with elastic events. Coded computing, which employs ideas from coding theory in parallel systems, was initially developed to address the issue of stragglers in distributed machine learning and data analytics [2,3,4]. Coded computing introduces redundancy in computation, so that the distributed system needs only wait for a subset of nodes before recovering the output. While coded computing goes beyond simple and traditional replication that can result extremely high redundancy, the computation overhead of many of the initial coded computing designs was not optimal. To reduce computation overhead, hierarchical coded computing was proposed in [5,6,7,8,9] that enables both fast and slow nodes to contribute to the output recovery. In hierarchical coding, the computation completed by stragglers is exploited rather than being ignored. Building upon [1], in [10] a new performance criterion was introduced called transition waste. This quantifies the total number of subtasks that existing workers must either abandon or take on anew when an elastic event occurs. In [10] a new task allocation scheme is presented that achieves zero transition waste when a worker joins or leaves. These ideas were extended to heterogeneous systems in [11,12].
In this paper, we extend the idea of hierarchical coding to elastic computing. We propose two hierarchical coded elastic computing schemes: multilevel coded elastic computing (MLCEC) and bit-interleaved coded elastic computing (BICEC). The proposed MLCEC method is built upon CEC and MLCC (multilevel coded computing) which is a special case of hierarchical coding [6,7,9]. In MLCEC each worker is tasked by multiple encoded subtasks and available workers select only a subset of their subtasks to work on. The task selection of MLCEC is motivated by the sequential behavior of workers. Workers process their subtasks one-by-one, transmitting each to the master as soon as it is completed. Therefore more workers are expected to finish their first selected subtasks rather than their second, and so forth. With respect to this sequential behavior, in MLCEC fewer workers select their first subtasks to work on and more workers select their last subtasks. This hierarchical selection of subtasks can make the completion time of different subtasks closer to each other and reduces the completion delay in MLCEC compared to CEC. The proposed BICEC method is built upon BICC (bit-interleaved coded computing) which is another special case of hierarchical coding [5,9]. Similar to BICC, in BICEC we jointly encode all subtasks using a single code and assign each worker multiple encoded subtasks. In opposite to CEC and MLCEC, where workers select a subset of their subtasks to work on, in BICEC available workers can work on all their subtasks, starting from the first one, completing subtasks sequentially until enough number of subtasks is completed. This enables a more continuous completion process compared to CEC and MLCEC. When an elastic event occurs, there is no need for task allocation, or in other words, BICEC achieves zero transition waste. We can also view BICEC as a BICC scheme with a higher rate of redundancy. More redundancy in BICEC leads to robustness against more number of preempted workers. The rest of the paper is organized as follows. In Sec. 2 we first provide a motivating example to illustrate the intuition behind our schemes. We then detail our proposed methods. In Sec. 3 we show that our method gains a 45% improvement in average finishing time.

PROPOSED METHOD
Consider a system that consists of a master and N workers, where workers can be preempted or joint within a range N ∈ (N min , N max ). This elasticity occurs with short notice. Each available worker can become a straggler without any prior notice. We aim to parallelize a computation in this system by leveraging ideas from coded computing to reduce the uncertainty due to system elasticity and stragglers. We first describe three illustrative examples. We then propose the generalized MLCEC and BICEC. In the examples the goal is to multiply two matrices A ∈ R u×w and B ∈ R w×v . Computing AB ∈ R u×v requires uwv multiplication and addition operations. In the first example we detail CEC [1]. In the second and third examples we present MLCEC and BICEC. These examples are visualized in Fig. 1 for N ∈ {4, 6, 8}.
Example 1 (CEC) [1]: We first divide the computation of the product AB into K cec = 2 matrix products A 1 B and A 2 B. We accomplish this by partitioning A horizontally into two equal-sized submatrices A 1 , A 2 ∈ R u/2×w . We then encode these submatrices using polynomial codes [3] to generate 8 encoded submatricesÂ n = A 1 + nA 2 , n ∈ [8]. We use the notation [m] to denote the index set {1, . . . , m}. The multiplication ofÂ n and B is assigned to worker n ∈ [N ]. Note that the encoded tasksÂ n B = A 1 B + nA 2 B can be viewed as a polynomial of degree 1. The completion of any 2 of the encoded products is enough to recover the coefficients of the polynomial, i.e., A 1 B and A 2 B products. If N workers are available, then available workers subdivide their task into N equal-sized subtasks. We accomplish this by horizontally dividing encoded matricesÂ n into N equal-sized submatriceŝ A n,m , m ∈ [N ], and assigns the subtasksÂ n,1 B, . . .Â n,N B to worker n ∈ [N ]. To recover A 1 B and A 2 B products, it is required to complete at least 2 computations from each of the following N sets {Â n,1 B} n∈[N ] , . . . , {Â n,N B} n∈ [N ] . In CEC, each worker selects only S cec = 4 of its N subtasks to work on. The value of 4 is selected intentionally to be larger than K cec = 2 to make the system robust to stragglers. As is shown in the first row of Fig. 1, in CEC available workers select their to-do list of subtasks in a cyclic fashion. For example, if N = 8 as it is in the first row of Fig. 1a, worker n subdivides itsÂ n B computation into 8 equal-sized sub-computationsÂ n,1 B, . . . ,Â n,8 B. Worker n works on only 4 subtasks, denoted by A n,m B, where m ≡ (n + i − 1) mod 8 and i ∈ [4]. The cyclic allocation of CEC allows only 4 workers to contribute to the completion of each set {Â n,m } n∈[N ] , m ∈ [8]. In Figures 1b and 1c, it is shown how to continue the computation when workers are gradually preempted reducing the number of workers from N = 8 to N = 6 and to N = 4. CEC uses a fixed rate code (here 2 out of 4) for each set recovery. Since workers complete their subtasks sequentially, the selected subtasks in the set {Â n,1 } n∈[N ] are started to be completed sooner than the selected subtasks in the set {Â n,N } n∈ [N ] . Therefore, the completion of different sets can finish at different times. This may be wasteful of time.
Example 2 (MLCEC): The main difference of MLCEC from CEC is that each worker selects its S mlcec = 4 subtasks in a way that more workers can contribute to the completion of sets {Â n,m } n∈[N ] with a larger m when compared to the sets with a smaller m. While CEC selects a fixed number of workers (i.e., 4) to contribute to the recovery of each set, MLCEC assigns different number of workers to complete each set. For example, Fig. 1a shows that MLCEC assigns d 1 = d 2 = 2 workers to the 1st and 2nd sets. However, it assigns d 3 = 3 workers to the 3rd sets. For 4, 5, 6, 7 and 8th sets, we use d 4 = 4, d 5 = 4, d 6 = 5, d 7 = 6 and d 8 = 6 workers. Note that while different numbers of workers contribute to each set, each worker has still 4 subtasks to do because n∈[N ] d n = 4N . Similar to CEC, to complete each set, we require at least 2 completed subtasks for that set. This makes the decoding cost of MLCEC similar to that of CEC. As the second row of Fig. 1 shows, we set d 1 ≤ d 2 ≤ . . . d N . This setting is expected to improve the computation time since more workers can contribute to the recovery of the sets {Â n,m } n∈[N ] with a larger m, which are started later than the sets with a smaller m.
Example 3 (BICEC): In the 3rd row of Fig. 1 we illustrate how BICEC can be applied to the same example. In contrast to CEC and MLCEC, where the main computational job is divided into 2 tasks, in BICEC we divide the job into K bicec = 600 tiny computations. These computations are then encoded to generate 1200 encoded subtasks. In Fig. 1a, these 1200 encoded subtasks are distributed among N = 8 workers so that each worker is tasked with S bicec = 300 subtasks. The completion of any 600 out of 1200 computations leads to the output recovery. The workers start completing their tasks sequentially from the first to the 300th. In Fig. 1 one can see that when 0 to 4 workers are gradually preempted, on average only the first y percentage, y ∈ {25, 33, 50}, of subtasks by each worker is required to be completed. If stragglers/failures exist, then the fast workers must complete a      The subtasks that are selected by TAS are marked as checks boxes and preempted workers are marks as cross marks. In CEC and MLCEC K ece = K mlcec = 2 and each worker subdivides its computation into N subtasks. In BICEC K bicec = 600 and S bicec = 300.
larger proportion of the overall computation. We can view the completion process of BICEC as a hierarchical process. For example, Fig. 1a shows that 8 workers complete their first subtasks, while only 1 worker completes its 90th subtask.
Generalizing MLCEC and BICEC: We now generalize MLCEC and BICEC. Consider a computing job g(x) where x is the input data and g(.) is a function. For any positive integer k, let's assume that the job g(x) can be decomposed into k computations, i.e., g(x) = f k (g 1 (x), . . . , g k (x)), where the function f k (.) maps the k computations g 1 (x), . . . , g k (x) to g(x). We also assume that the g 1 (x), . . . , g k (x) computations are linear, i.e., for any i, j ∈ [k], ag i (x) + bg j (x) = (ag 1 + bg 2 )(x). One example is a matrix multiplication g(x) = Ax.
The input x is a u × w matrix and A is a w × v matrix. The job Ax can then be partitioned into k computations g i (x) = A i x, i ∈ [k], by horizontally dividing A into k equal-sized submatrices A i . The function f k (.) simply concatenates the A i x results, for all i ∈ [k]. Note that if the total number of computations is not divisible by k, we can use zero-padding. Multilevel coded elastic computing: The master first divides the job g(x) into K mlcec computations g i (x), where i ∈ [K mlcec ]. I.e., g(x) = f K mlcec (g 1 (x), . . . , g K mlcec (x)). These computations are then encoded using an (K mlcec , N max ) MDS code [2] to generate N max encoded tasksĝ n (x), n ∈ [N max ]. Note that the completion of any K mlcec encoded tasks can lead to g(x) recovery. The master then assigns the encoded taskĝ n (x) to the nth worker, for all n ∈ [N max ]. If N workers are available, each worker subdivides its tasks into N equal-sized subtasks. Letĝ 1 n (x), . . . ,ĝ N n (x) be the N subtasks of the nth available worker, n ∈ [N ]. Let's assume that these N 2 encoded subtasksĝ m n (x), n, m ∈ [N ], can be reconstructed differently. The master can first divide the job g(x) into N K mlcec computations g m i (x), where i ∈ [K mlcec ] and m ∈ [N ]. I.e., g(x) = f N K mlcec (g 1 1 (x), . . . , g N K mlcec (x)). The master then groups these computations into N sets . The computations of each set is then encoded using an (K mlcec , N ) MDS code [2] to generate N encoded subtasks. , closer to each other, we set d 1 ≤ . . . ≤ d N . While due to space constraint, we must leave discussion of how to optimize the set {d m } m∈[N ] to future work, in Alg. 1 we describe one method to allocate selected subtasks given {d m } m∈ [N ] .
Data: N, {d 1 , . . . , d N } All workers are initiated with 0 subtasks; for l = N to 1 do n = index of the 1st worker who has the minimum number of subtasks in sets l + 1 to N ; for i = n to n + d l do worker i mod N selects its lth subtask; Algorithm 1: Task allocation in MLCEC Bit-interleaved coded elastic computing: The master divides the job g(x) into K bicec computations g i (x), i.e., g(x) = f K bicec (g 1 (x), . . . , g K bicec (x)). These g i (x) are then encoded using an (K bicec , S bicec N max ) MDS code [2] to generate S bicec N max encoded subtasksĝ i (x), i ∈ [S bicec N max ]. The master then assigns S bicec encoded subtasks to each worker. The completion of any K bicec encoded subtasks can recover all g i (x), i ∈ [K bicec ]. Workers process their subtasks sequentially until enough subtasks are completed.  2400, 960, 6000). In all subfigures, we set K cec = K mlcec = 10, K bicec = 800, S cec = S mlcec = 20, S bicec = 80, and N max = 40.

SIMULATION RESULTS
We now evaluate the performance of MLCEC and BICEC and compare our results with CEC [1]. We conduct our experiments using Python on a machine with an Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz. We simulate the matrix multiplication AB on N working nodes, where N ∈ {20, 22, . . . , 40}. We run the computation assigned to workers sequentially (worker-by-worker). The parallelism among workers' computations is simulated by recording workers' computation times and measuring the final computation times for CEC, MLCEC, and BICEC. To simulate straggling behavior, each available worker becomes straggler with probability 0.5. After computation completes, we implement a decoding process and log the decoding time. We repeat our experiments twice, once for multiplying two square random matrices A ∈ R 2400×2400 and B ∈ R 2400×2400 , and another time for multiplying a tall matrix A ∈ R 2400×960 and a fat matrix B ∈ R 960×6000 . For each case, we run our simulation 20 times. In Fig. 2 we plot the average decoding, computation, and finishing (computation plus decoding) times versus N . We do not report encoding time as it is negligible when compared to computation times. This is because encoding requires many fewer multiplication and addition operations compared to the at least uwv = 2400 3 operations done by workers. We also neglect the time it takes to communicate data between workers and the master.
For CEC and MLCEC, we set K cec = K mlcec = 10. Since N max = 40 , in our experiments we generate 40 random matricesÂ n ∈ R u 10 ×w , n ∈ [40], each of which corresponds to an encoded data input for one worker. We also generate a random matrix B. We then assign theÂ n B multiplication to worker n ∈ [N ]. This multiplication requires 2400 3 10 multiplication and addition operations. Each worker then subdivides its task into N equal-sized subtasks and works on 20 subtasks according to the task allocation schemes in CEC and MLCEC. For each value of N , we set {d n } n∈ [N ] such that d 1 ≤ . . . ≤ d N and n∈[N ] d n = 20N . For BICEC, we set K bicec = 800 and S bicec = 80. Therefore, each worker is tasked by at most 2400 3 10 computations, similar to CEC and MLCEC. In Fig. 2a, we plot the average computation time vs.
N for CEC, MLCEC, and BICEC. The computation time for both matrix dimensions (u, w, v) = (2400, 2400, 2400) and (u, w, v) = (2400, 960, 6000) are the same because uwv = 2400 3 for both cases. In Fig. 2a, MLCEC achieves a lower average computation time compared to CEC as we expected. BICEC has the lowest average computation time and achieves 85% improvement compared to CEC for N = 40.
For decoding, we solve a system of linear equations that involves a Vandermonde matrix of size 10 × 10 in CEC and MLCEC and of size 800 × 800 in BICEC. After we take the inverse of the Vandermonde matrix, in CEC and MLCEC 10uv N multiplication and addition operations are completed. In BICEC 800uv operations are completed. Therefore, as is shown in Fig. 2b, BICEC has the worst decoding time and CEC and MLCEC both have the same (negligible) decoding time. If we change from (u, w, v) = (2400, 2400, 2400) to (u, w, v) = (2400, 960, 6000) the decoding time increases since the decoding process only depends on the dimensions of AB, which is u × v, and v in the first setting is smaller than in the latter. In Fig. 2c and 2d we plot the average computation plus decoding time (denoted "finishing time"). In Fig. 2c BICEC is the best choice and in Fig. 2d MLCEC has the lowest finishing time for N ∈ {32, . . . , 40}. While in both sub-figures computation time is fixed, in Fig. 2d the large decoding time in BICEC is added to the computation time and increases the finishing time of BICEC. For N = 40, the use of BICEC yields a 45% reduction in average finishing time when compared to CEC in Fig. 2c and the use of MLCEC yields a 15% reduction in Fig. 2d. BICEC has two advantages over MLCEC at the cost of larger decoding time. Due to a more continuous completion process of BICEC, its computation time is a lower bound for MLCEC. Besides this, whenever an elastic event occurs, in MLCEC available workers may need to re-allocate their subtasks, while in BICEC workers keep working on their preallocated subtasks, resulting in zero transition waste. As next steps, we would like to implement our schemes on real-world elastic computing frameworks such as Amazon EC2 Spot or Microsoft Azure Batch, and to extend our schemes to a larger class of algorithms rather than linear computations.