In this paper, we propose a new coded computing technique called "substitute decoding" for general iterative distributed computation tasks. In the first part of the paper, we use PageRank as a simple example to show that substitute decoding can make the computation of power iterations solving PageRank on sparse matrices robust to erasures in distributed systems. For these sparse matrices, codes with dense generator matrices can significantly increase storage costs and codes with low-density generator matrices (LDGM) are preferred. Surprisingly, we show through both theoretical analysis and simulations that when substitute decoding is used, coded iterative computing with extremely low-density codes (2 or 3 non-zeros in each row of the generator matrix) can achieve almost the same convergence rate as noiseless techniques, despite the poor error-correction ability of LDGM codes. In the second part of the paper, we discuss applications of substitute decoding beyond solving linear systems and PageRank. These applications include (1) computing eigenvectors, (2) computing the truncated singular value decomposition (SVD), and (3) gradient descent. These examples show that the substitute decoding algorithm is useful in a wide range of applications.
Some concurrent works also focus on coded computing for graph analytics @cite_48 and sparse matrix multiplications @cite_46 @cite_36 @cite_1 . These works focus on single-shot computing instead of iterative computing. For iterative computational tasks, one has to optimize the system performance from the entire convergence process. For example, although the substitute decoding method is not optimal at each iteration (it does not even provide the complete decoding result in a single iteration), it has the desired convergence rate in the entire iterative process. We notice that the multistage coded computation described by a directed acyclic graph has been discussed in an earlier work @cite_26 under the Map-Reduce framework. The importance of the convergence-rate for iterative computing in the context of computing with stragglers has also been well-recognized by recent works @cite_39 @cite_2 .
@cite_26 @cite_36 @cite_48 @cite_1 @cite_39 @cite_2 @cite_46
2620705481 2614091483 1866018165 2143131337
Computationally intensive distributed and parallel computing is often bottlenecked by a small set of slow workers known as stragglers. In this paper, we utilize the emerging idea of "coded computation" to design a novel error-correcting-code inspired technique for solving linear inverse problems under specific iterative methods in a parallelized implementation affected by stragglers. Example applications include inverse problems in machine learning on graphs, such as personalized PageRank and sampling on graphs. We provably show that our coded-computation technique can reduce the mean-squared error under a computational deadline constraint. In fact, the ratio of mean-squared error of replication-based and coded techniques diverges to infinity as the deadline increases. Our experiments for personalized PageRank performed on real systems and real social networks show that this ratio can be as large as @math . Further, unlike coded-computation techniques proposed thus far, our strategy combines outputs of all workers, including the stragglers, to produce more accurate estimates at the computational deadline. This also ensures that the accuracy degrades "gracefully" in the event that the number of stragglers is large. We consider the problem of computing the convolution of two long vectors using parallel processing units in the presence of "stragglers". Stragglers refer to the small fraction of faulty or slow processors that delays the entire computation in time-critical distributed systems. We first show that splitting the vectors into smaller pieces and using a linear code to encode these pieces provides better resilience against stragglers than replication-based schemes under a simple, worst-case straggler analysis. We then demonstrate that under commonly used models of computation time, coding can dramatically improve the probability of finishing the computation within a target "deadline" time. As opposed to the more commonly used technique of expected computation time analysis, we quantify the exponents of the probability of failure in the limit of large deadlines. Our exponent metric captures the probability of failing to finish before a specified deadline time, i.e. , the behavior of the "tail". Moreover, our technique also allows for simple closed form expressions for more general models of computation time, e.g. shifted Weibull models instead of only shifted exponentials. Thus, through this problem of coded convolution, we establish the utility of a novel asymptotic failure exponent analysis for distributed systems. Despite the performance potential of multicomputers, several factors have limited their widespread adoption. Of these, performance variability is among the most significant. Execution of some programs may yield only a small fraction of peak system performance, whereas others approach the system's theoretical performance peak. Moreover, the observed performance may change substantially as application program parameters vary. Data parallel languages, which facilitate the programming of multicomputers, increase the semantic distance between the program's source code and its observable performance, thus aggravating the performance problem. In this thesis, we propose a new methodology to predict the performance scalability of data parallel applications on multicomputers. Our technique represents the execution time of a program as a symbolic expression that is a function of the number of processors (P), problem size (N), and other system-dependent parameters. This methodology is based on information collected at compile time. By extending an existing data parallel compiler (Fortran D95), we derive, during compilation, a symbolic model that represents the cost of each high-level program section and, inductively, of the complete program. These symbolic expressions may be simplified externally with current symbolic tools. Predicting performance of the program for a given pair @math requires simply the evaluation of its corresponding cost expression. We validate our implementation by predicting scalability of a variety of loop nests, with distinct computation and communication patterns. To demonstrate the applicability of our technique, we present a series of concrete performance problems where it was successfully employed: prediction of total execution time, identification and tracking of bottlenecks, cross-system prediction, and evaluation of code transformations. These examples show that the technique would be useful both to users, in optimizing and tuning their programs, and to advanced compilers, which would have a means to evaluate the expected performance of a synthesized code. According to the results of our study, by integrating compilation, performance analysis and symbolic manipulation tools, it is possible to correctly predict, in an automated fashion, the major performance variations of a data parallel program written in a high-level language. In this paper we present a parallel formulation of the multilevel graph partitioning and sparse matrix ordering algorithm. A key feature of our parallel formulation (that distinguishes it from other proposed parallel formulations of multilevel algorithms) is that it partitions the vertices of the graph intopparts while distributing the overall adjacency matrix of the graph among allpprocessors. This mapping results in substantially smaller communication than one-dimensional distribution for graphs with relatively high degree, especially if the graph is randomly distributed among the processors. We also present a parallel algorithm for computing a minimal cover of a bipartite graph which is a key operation for obtaining a small vertex separator that is useful for computing the fill reducing ordering of sparse matrices. Our parallel algorithm achieves a speedup of up to 56 on 128 processors for moderate size problems, further reducing the already moderate serial run time of multilevel schemes. Furthermore, the quality of the produced partitions and orderings are comparable to those produced by the serial multilevel algorithm that has been shown to outperform both spectral partitioning and multiple minimum degree.