Fault tolerant decentralized deep neural networks

Universidade do Minho Escola de Engenharia Departamento de Inform´ atica Jo˜ ao Carlos Faria Padr˜ ao Fault Tolerant Decentralized Deep Neural Networks October 2020 Universidade do Minho Escola de Engenharia Departamento de Inform´ atica Jo˜ ao Carlos Faria Padr˜ ao Fault Tolerant Decentralized Deep Neural Networks Master dissertation Integrated Master’s in Informatics Engineering Dissertation supervised by Carlos Baquero Vitor Enes October 2020 DIREITOS DE AUTOR E CONDIC¸ ˜ OES DE UTILIZAC¸ ˜ A O D O TRABALHO POR TERCEIROS Este ´ e um trabalho acad ´ emico que pode ser utilizado por terceiros desde que respeitadas as regras e boas pr ´ aticas internacionalmente aceites, no que concerne aos direitos de autor e direitos conexos. Assim, o presente trabalho pode ser utilizado nos termos previstos na licenc¸a abaixo indicada. Caso o utilizador necessite de permiss˜ ao para poder fazer um uso do trabalho em condi c¸ ˜ oes n ˜ ao previstas no licenciamento indicado, dever ´ a contactar o autor, atrav ´ es do Reposit ´ oriUM da Universidade do Minho. Licen c¸ a concedida aos utilizadores deste trabalho Atribuic¸˜ ao CC BY https://creativecommons.org/licenses/by/4.0/ i ACKNOWLEDGEMENTS I would like to thank my family, specially my father, my mother and my sister for supporting my during the last years of my academic path. I would also like to give a special thanks to my friends Carlos, Hugo, Lu ´ ıs, Pedro, Renato and Sequeira for all the knowledge they shared with me and for listening to my thoughts. And last, I would like to give a very special thanks to my supervisors, Vitor Enes and professor Carlos Baquero for always being present and helpful. Without them this thesis would exist, so I thank you from the bottom of my heart. ii STATEMENT OF INTEGRITY I hereby declare having conducted this academic work with integrity. I confirm that I have not used plagiarism or any form of undue use of information or falsification of results along the process leading to its elaboration. I further declare that I have fully acknowledged the Code of Ethical Conduct of the University of Minho iii ABSTRACT Machine Learning is trending in computer science, especially Deep Learning. Training algorithms that follow this approach to Machine Learning routinely deal with vast amounts of data. Processing these enormous quantities of data requires complex computation tasks that can take a long time to produce results. Distributing computation efforts across multiple machines makes sense in this context, as it allows conclusive results to be available in a shorter time frame. Distributing the training of a Deep Neural Network is not a trivial procedure. Various architectures have been proposed, following two different paradigms. The most common one follows a centralized approach, where a centralized entity, broadly named parameter server, synchronizes and coordinates the updates generated by a number of workers. The alternative discards the centralized unit, assuming a decentralized architecture. The synchronization between the multiple workers is assured by communication techniques that average gradients between a node and its peers. High-end clusters are the ideal environment to deploy Deep Learning systems. Low latency between nodes assures low idle times for workers, increasing the overall system performance. These setups, however, are expensive and are only available to a limited number of entities. On the other end, there is a continuous growth of edge devices with potentially vast amounts of available computational resources. In this dissertation, we aim to implement a fault tolerant decentralized Deep Neural Network training framework, capable of handling the high latency and unreliability characteristic of edge networks. To manage communication between nodes, we employ decentralized algorithms capable of estimating parameters globally. Keywords : Distributed Systems, Machine Learning, Artificial Intelligence, Fault Tolerance. iv RESUMO Machine Learning, mais especificamente Deep Learning, ´ e um campo emergente nas ci ˆ encias da computa c¸˜ ao. Algoritmos de treino aplicados em Deep Learning lidam muito frequentemente com vastas quantidades de dados. Processar estas enormes quantidades de dados requer opera c¸ ˜ oes computacionais complexas que demoram demasiado tempo para produzir resultados. Distribuir o esfor c¸ o computacional por m ´ ultiplas m ´ aquinas faz todo o sentido neste contexto e permite um aumento significativo de desempenho. Distribuir o m ´ etodo de treino de uma rede neuronal n ˜ ao ´ e um processo trivial. V ´ arias arquiteturas t ˆ em sido propostas, seguindo dois diferentes paradigmas. O mais comum segue uma abordagem centralizada, onde uma entidade central, normalmente denominada de parameter server, sincroniza e coordena todas as atualiza c¸ ˜ oes produzidas pelos workers. A alternativa passa por descartar a entidade centralizada, assumindo uma arquitetura descentralizada. A sincroniza c¸˜ ao entre workers ´ e assegurada atrav ´ es de estrat ´ egias de comunicac¸˜ ao descentralizadas. Clusters de alta performance s ˜ ao o ambiente ideal para a implementa c¸˜ ao de sistemas de Deep Learning. A baixa lat ˆ encia entre nodos assegura baixos per ´ ıodos de inatividade nos workers, aumentando assim o rendimento do sistema. Estas instala c¸ ˜ oes, contudo, s ˜ ao muito custosas, estando apenas dispon ´ ıveis para um pequeno n ´ umero de entidades. Por outro lado, o n ´ umero de equipamentos nas extremidades da rede, com baixo aproveitamento de poder computacional, continua a crescer, o que torna o seu uso desej´ avel. Nesta disserta c¸˜ ao, visamos implementar um ambiente de treino de redes neuronais descentralizado e tolerante a faltas, apto a lidar com alta lat ˆ encia na comunica c¸ ˜ oes e baixa estabilidade nos nodos, carater ´ ıstica de redes na extremidade. Para coordenar a comunica c¸˜ ao entre os nodos, empregamos algoritmos de agrega c¸˜ ao, capazes de criar uma vis ˜ ao geral de parametros numa topologia. Palavras Chave : Sistemas Distribu ´ ıdos, Machine Learning, Intelig ˆ encia Artificial, Toler ˆ ancia a Faltas. v CONTENTS 1 introduction 1 1.1Context 1 1.2Motivation 1 1.3Main Contributions 2 1.4Dissertation Outline 2 2 machine learning 3 2.1Defenition 3 2.2Deep Learning 4 2.3Summary 5 3 distributed deep learning 7 3.1Vertical Scaling 7 3.2Horizontal Scaling 7 3.3Distributed Deep Learning Architectures 8 3.3.1Model Parallelism 8 3.3.2Data Parallelism 8 3.3.3Summary 9 4 centralized distributed deep learning 10 4.1Parameter Server 10 4.2Federated Learning 11 4.3Summary 11 5 decentralized distributed deep learning 12 5.1allreduce 12 5.2Ring Allreduce 13 5.3Tree-based allreduce 13 5.4GossipGraD 14 5.5Summary 15 6 fault tolerant tree 16 6.1Topology 16 6.2Reduce 17 6.3Broadcast 19 6.4Probabilistic analisys 21 6.5Summary 22 7 evaluation 23 vi contents vii 7.1Experimental Steup 23 7.2Fault tolerance cost 23 7.3Results without failures 24 7.4Results with failures 26 7.5Summary 30 8 conclusions and future work 31 2.3. Summary 5 Input Layer V0 a(0) 1 a(0) 2 1 Hidden Layer V1 a(1) 1 a(1) 2 a(1) 3 1 Output Layer V2 a(2) 1 w(1) 1,1 w(1) 1,2 w(1) 1,3 w(1) 2,1 w(1) 2,2 w(1) 2,3 b(1) 1 b(1) 2 b(1) 3 w(2) 1,1 w(2) 2,1 w(2) 3,1 b(2) 1 Figure 1: Simple feedforward neural network with 3layers ∆=1 n∑n i=1(li−yi)2 The predominant minimization heuristic used to train Neural Networks is Stochastic Gradient Decent (SGD), based on the Gradient Decent method. Gradient Decent is an iterative optimization procedure that, at each iteration, improves the solution by taking a step along the negative gradient of the function to be minimized, at the current point [ 22 ]. Since we do not have access to the full domain, D , of the problem, this procedure is not feasible in this case. SGD bypasses that limitation by allowing the step to be taken along a random gradient, based on a sample of the domain D . This gradient is calculated using the backpropagation algorithm. With the gradient calculated, the network can be optimized. 2.3 summary In this Chapter, we presented a broad definition of Machine Learning and one of its subfields, Deep Learning. We also covered the basic structure of a neural network and how these 2.3. Summary 6 structures are trained. In the next Chapter, we will discuss the need to distribute Deep Learning and various techniques used to achieve that. 3 DISTRIBUTED DEEP LEARNING As we saw in the previous Chapter, most of the computational effort required to train a deep neural network is the result of basic linear algebra transformations. To accelerate the training process, it is necessary to distribute this operation efficiently. As other largescale computational systems, there are two different alternatives to distribute approach this challenge: vertical scaling or horizontal scaling. 3.1 vertical scaling Vertical scaling involves adding more resources to a single machine. The emergence of deep learning has lead vendors such as Nvidia, to develop GPUs with versatile architectures that better accommodate the need for highly parallel tasks. TPUs [ 13 ] also yield high performance while executing highly parallel tasks. These processing units specializes in transformations of multi-dimensional array structures, and are usually used in combination with TensorFlow [1]. 3.2 horizontal scaling Horizontal scaling involves partitioning tasks across multiple machines. To achieve desirable performance, ML algorithms need to be adapted to a distributed setting. This process is not always straightforward and often presents problems that affect most distributed applications. Overcoming these challenges, however, is desirable for several reasons. The first reason is the increase in fault tolerance because, in the event of a failure, the system can continue to operate. Another reason relates to the high I/O demand of deep neural networks. Partitioning data across several machines increases the total I/O bandwidth of the system. In this thesis we will focus on horizontal scaling. 7 3.3. Distributed Deep Learning Architectures 8 3.3 distributed deep learning architectures When we are distributing computation across several machines, it is important to consider all of the alternative ways of accomplishing it. Depending on the available hardware or on the model itself, one might find some techniques more suited to the problem than others. In distributed deep learning, the first decision falls on whether to implement model or data parallelism. 3.3.1Model Parallelism Model parallelism, represented in Figure 2a, dictates that the model must be split across all machines and that all workers process the same data. To get a holistic view of the model it is necessary to aggregate all the portions split across the workers. This approach tends to yield greater performance with models with local connectivity structures [9]. 3.3.2Data Parallelism Data parallelism, represented in Figure 2b, dictates that the data must be split across all machines and that all workers have a copy of the same model. Each worker processes different data batches using the same model. This approach supports all deep learning algorithms. Model Parallelism D m1m2m3 trained model (a) Model Parallelism Data Parallelism d1d2d3 MMM trained model (b) Data Parallelism Figure 2: Two types of parallelism in Distributed Deep Learning. Data is represented by the letter D, or dnif split, and the model is represented by the letter M, or mnif split. 3.3. Distributed Deep Learning Architectures 9 3.3.3Summary As with most distributed systems, the arrangement of the workers is particularly important to ensure good performance and coordination. Topologies fall under two major categories: centralized and decentralized. In the next two Chapters we will study these classes and present several examples that implement these concepts. 4 CENTRALIZED DISTRIBUTED DEEP LEARNING 4.1 parameter server Most relevant distributed Machine Learning frameworks, such as TensorFlow 1 [ 1 ], MXNet 2 [5] or CNTK3, support the centralized parameter server architecture [17]. This architecture, illustrated in Figure 3, is devised to allow workers to calibrate their own parameters according to a portion of the dataset, and then synchronize their variables with the central parameter server (PS), establishing a starting point for the next round. The PS architecture provides a global view of the system, allowing the parameters to be stored on a persistent data store. In the event of a worker failure, the model parameters stored on the PS are used to restore the malfunctioning worker the current state. (a) Parameter Sever architecture with a single Parameter Server (b) Parameter Sever architecture with multiple Parameter Servers Figure 3: Parameter Server architecture With a small number of workers, it is possible to achieve a near-linear boost in performance. However, a further increase in the number of workers can expose the bandwidth limitations of the communication layer due to a large amount of data being sent through the same channels. One solution is to increase the batch size, leading to fewer synchronization steps. A larger global batch, though, can decrease the efficiency of the model [ 14 ]. Additionally, GPUs have limited memory, which diminishes the viability of large batches of data. To further hinder the training performance, current developments in accelerators and networks suggest an ever evident disparity between computation and communication speeds. New 1https://www.tensorflow.org/ 2https://mxnet.apache.orrg/ 3https://www.microsoft.com/en-us/cognitive-toolkit/ 10 4.2. Federated Learning 11 hardware and algorithms continue to reduce the computation time, while network speeds continue getting faster but at a much slower rate. Another solution is to implement sharded parameter servers [ 6 , 9 ] that divide the ownership of the model parameters. This design leads to a waste of potentially expensive computational resources. Synchronous versions of the parameter server concept guarantee the maximum possible convergence, at the potential cost of performance. The presence of slow workers can hurt the system performance since all workers need to communicate their gradients to end the current round. Several techniques mitigate the negative effect of slow workers. Stale Synchronous Parallel (SSP) [ 12 ] allows workers to run at different paces within a certain interval. Faster workers that move too far ahead of the slower workers are paused. This technique maintains a strong model convergence when the number of slow workers is low. Barrierless Asynchronous Parallel (BAP) [ 10 ] removes the synchronization from the system to minimize the effect of slow workers on the system, thus workers communicate with the PS in parallel without waiting. This technique obtains the maximum speedup possible. The presence of slow workers restrains the model convergence though, as slow workers send gradients based on stale model parameters. 4.2 federated learning Federated Learning [ 3 ] is a hybrid approach to distributed neural network training, where each node downloads the model and computes the gradients localy, with its own data, and then sends the resuls to a cloud based server. As a result, only the training coordination is centralized whereas the training and the data are decentralized. This approach is applied on the domain of mobile phones, using the data stored on this devices. Due to its rather specific domain, we will not consider this design on this thesis. 4.3 summary In this Chapter, we covered the main approach to centralized Deep Learning, the parameter server architecture, as well as Federated Learning. We discussed its variations along with its advantages and disadvantages. In the next Chapter, we will analyze the other approach to distributed Deep Learning, Decentralized Deep Learning. 5 DECENTRALIZED DISTRIBUTED DEEP LEARNING Decentralized approaches to distributed Deep Learning remove the parameter server from the system, redirecting the training and coordination to all the worker nodes. Communication between them ensures the organization and correctness of the training process. This technique removes the central server as the single point of failure and potential bottleneck. Most decentralized learning algorithms rely on the allreduce operation which reduces results across all workers in a decentralized manner. 5.1 allreduce Many distributed applications benefit from reducing a set of values and distributing the results across all workers, as illustrated in Figure 4. In distributed Deep Learning this concept is particularly useful to aggregate gradients, reduce them and disseminate the result to all workers. The reduction step, denoted as ⊕ , is performed by an optimization algorithm, typically Stochastic Gradient Descent, or an optimized version of this algorithm. The dissemination of the results varies, depending on the specification of the allreduce algorithm and the topology formed by the workers, as this versatile operation can be applied in various topologies such as rings or trees or. 123 Worker 0 456 Worker 1 789 Worker 2 12 15 18 Worker 1 12 15 18 Worker 0 12 15 18 Worker 2 Figure 4: Example of an allreduce operation with sum function as reduction operation 12 5.2. Ring Allreduce 13 5.2 ring allreduce Decentralized distributed Machine Learning frameworks, like Horovod 1 [ 21 ], have proven to be a feasible and valid alternative to purely centralized systems. Horovod implements the ring allreduce algorithm [ 20 ], illustrated in Figure 5, a realization of the allreduce concept, enabling worker nodes to synchronously average gradients between them, without the need of a parameter server. Ring allreduce organizes workers in a virtual ring topology. This concept is replicated in TensorFlow with MultiWorkerMirroredStrategy. Fault tolerance was not the main concern when developing this algorithms. If a failure occurs, the system will revert to a previous checkpoint and resume the training. 123 Worker 1 456 Worker 2 789 Worker 3 1212 Worker 1 ⊕1 556 Worker 2 ⊕5 713 9 Worker 3 ⊕9 115 12 Worker 1 ⊕12 5518 Worker 2 ⊕5 12 13 9 Worker 3 ⊕13 12 15 12 Worker 1 15 515 18 Worker 2 18 12 13 18 Worker 3 12 12 15 18 Worker 1 12 12 15 18 Worker 2 15 12 15 18 Worker 3 18 12 15 18 Worker 1 12 15 18 Worker 2 12 15 18 Worker 3 Figure 5: Horovod ring allreduce example 5.3 tree-based allreduce Tree-based topologies prove to be advantageous when performing allreduce operations, as they are highly scalable, simple and efficient [ 20 ]. Implementing allreduce on a tree-based topology is also intuitive. In each round, the nodes in the tree aggregate their gradients with the ones received from their children. When the aggregated gradients reach the root of 1https://eng.uber.com/horovod/ 5.4. GossipGraD 14 the tree, the final round gradients are calculated and then broadcasted to all the remaining nodes. Figure 6illustrates this process. 1 2 4 5 3 67 11 16 4 5 7 6 28 28 28 28 28 28 28 28 28 28 28 2828 Figure 6: Tree-based allreduce Variants of this design have already been implemented and tested in distributed Deep Learning. MXNet provides topology-aware allreduce for distributed training [ 5 ]. This approach makes use of binary trees to perform reduce and broadcast operations. Fault tolerance was not one of the aims when designing this algorithm though, so no failure detection or recovery mechanisms were specified. Margolin and Barak [ 18 ] proposes tree-based fault-tolerant collective operations (FTCO), extending existing tree-based algorithms. The FTCO algorithm detects node failures and excludes them from the topology. This approach allows the application to keep running in the event of a node failure with a small latency penalty. FTCO does not tolerate link failures though. In the event of a failure on a link connecting two nodes, there is no guarantee that the application will keep running. Chen et al. [ 4 ] proposes RABIT, a reliable allreduce, and broadcast interface library, specifically designed to distribute Deep Neural Networks training. This library can handle node failures by pausing every node until the malfunctioning node is restarted. After the restart, the failed node receives the latest model parameters from its peers. Once this step is completed, the training can resume. As with FTCO, RABIT does not provide link failure tolerance. 5.4 gossipgrad Another approach to decentralized machine learning is GossipGraD [ 8 ], a gossip comunication protocol designed for scaling machine learning. This protocol ensures the indirect dessemination of gradients through all nodes in log2(nodes) steps, where each step represents a computed batch. GossipGraD also implements a peer rotation mechanism in order to reduce communication inbalance. This approach does not mention faul tolerance mechanism though. In the event of a node or link failure, the algorithm does not specify a recovery mechanism, so it is not suitable for unstable networks. 6.4. Probabilistic analisys 21 6.4 probabilistic analisys The presented algorithm provides a mechanism to continue computation in the advent of a link failure. If multiple failures occur in the network, a node in the graph can become disconnected, which leads to a stop in the computation. An example of such event is illustrated on Figure 10. To determine the impact of this effect on the algorithm, we measure the probability of a node becoming disconnected network. The test was performed by removing random links from the network until a node beacame disconnected. The results are presented on Figure 11. 0 1 3 4 2 56 Figure 10: Example of a tree with a disconnected node (node 3) (a) Average number of failed links until a node is isolated (b) Average percentage of failed links until a node is isolated Figure 11 Figure 11ashows that the average number of tolerated failed links increases with the tree height. This behavior is expected, as the total number of links also increases. Figure 11b shows that the percentage toleranted failed links decreases with the tree height. Since the failure of only two links (links that are connected to the tree root) can halt the all reduce operation, it is expected that the percentage of tolerated failed links decreases. 6.5. Summary 22 6.5 summary In this Chapter, we presented the fault tolerant tree topology. We defined its behavior under numerous failure circumstances and analyzed its resilience to link failures. In the next Chapter, we will test this approach and compare it to other architectures presented in Chapters 4and 5. 7 EVALUATION In this Chapter we evaluate the algorithm proposed on the previous Chapter and compare its performance to other distributed deep learning algorithms. 7.1 experimental steup We evaluated all alternatives on a single server (four Intel E5-4620 8-Core CPUs at 2.2GHz and 126 GB of RAM). This closed environment allows for more precise monitoring and control over the communication between workers. Each node is restricted to one CPU core to emulate a single device. To simulate a disconnected link, we defined firewall rules. We test all alternatives with the MNIST dataset [ 15 ], composed of 60,000 training images and 10,000 test images. These images represent handwritten digits (10 classes), and the goal is to construct an accurate image classifier. For all distributed algorithms we use the same neural network, implemented using the tensorflow framework, with 4layers with a total of 407050 parameters. We batch the data using batch of 100 images per iteration. 7.2 fault tolerance cost In this section, we present the cost tolerating a link failure. In a tree, concurrent failures can be classified as parallel or serial. A parallel failure, Figure 12a, occurs when the failed links are at the same height. Serial failures, Figure 12b, occur when the two links are at consecutive heights. As we can see in tables 1and 2, the cost of one failure and two parallel failures is approximately the same. On the other hand, the cost of two serial failures is approximately double, as the recovery times cannot overlap. No. of nodes No Faults 1Fault 2Parallel Faults 2Serial Faults 7 0.033 1.449 1.495 2.822 15 0.062 1.510 1.513 2.890 31 0.091 1.497 1.494 2.880 Table 1: Allreduce step duration (in seconds) with a 500 millisecond timeout 23 7.3. Results without failures 24 0 1 3 4 2 56 × × (a) Parallel failure 0 1 3 4 2 56 × × (b) Serial failure Figure 12: Types of link failures on a tree No. of nodes No Faults 1Fault 2Parallel Faults 2Serial Faults 7 0.034 2.441 2.473 4.839 15 0.065 2.541 2.498 4.860 31 0.093 2.509 2.541 4.911 Table 2: Allreduce step duration (in seconds) with a 1second timeout 7.3 results without failures In this section we present the results gathered from testing the fault tolerant tree topology in a environment without failures. We also compare it with other topologies presented previously. All abreviantions used in this Chapter are described in table 3 Abreviation Description sync Synchronous parameter server architecture async Asynchronous parameter server architecture keras TensorFlow native distribution technique using the MultiWorkerMirroredStrategy, invoked by the Keras API tree Standard tree-based allreduce ft tree Fault tolerant tree allreduce Table 3: Allreduce step duration (in seconds) with a 1second timeout Figure 13ashows the resulting training accuracy and Figure 13bshows the training time. As we can see in Figure 13a, the best accuracy is achieved using a synchronous parameter server approach, as this architecture guarantees the maximum convergence, at the expense of time. This tradeoff is visible in Figure 13b. On the other hand, the asynchronous parameter server approach trades accuracy for performance. Both centralized approaches show slower training times when compared to decentralized ones. The decentralized topologies show faster training time, while keeping high accuracies. We can see that tree-based allreduce has the edge over ring-based allreduce accuracy wise. 7.3. Results without failures 25 (a) Train accuracy (b) Train time Figure 13: Training accuracy and time using different topologies. This difference, although, isn’t large. Time wise, we can see that the ring based approach has the edge over the tree-based allreduce. It is also important to note that the fault tolerant mechanisms employed on the tree-based allreduce add a time penalty. 7.4. Results with failures 26 7.4 results with failures In this section, we present the results gathered from testing the fault tolerant tree topology in an environment with link failures. For demonstration purposes, we assume that the links fail between the fifth and the tenth training iteration. Figures 14,15,16 and 17 show the results. (a) Time per iteration with a 500 millisecond timeout (b) Time per iteration with a 1second timeout Figure 14: Time per iteration with a fault tolerant tree with 3nodes 7.4. Results with failures 27 (a) Time per iteration with a 500 millisecond timeout (b) Time per iteration with a 1second timeout Figure 15: Time per iteration with a fault tolerant tree with 7nodes 7.4. Results with failures 28 (a) Time per iteration with a 500 millisecond timeout (b) Time per iteration with a 1second timeout Figure 16: Time per iteration with a fault tolerant tree with 15 nodes 7.4. Results with failures 29 (a) Time per iteration with a 500 millisecond timeout (b) Time per iteration with a 1second timeout Figure 17: Time per iteration with a fault tolerant tree with 31 nodes 7.5. Summary 30 7.5 summary In this Chapter, we analyzed the performance of the fault tolerant tree algorithm and compared it to its competitors presented in Chapters 4and 5. We also presented the cost that a link failure introduces in the system.