Dissertations / Theses: 'Checkpointing'

1

Oliner, Adam Jamison. "Cooperative checkpointing for supercomputing systems." Thesis, Massachusetts Institute of Technology, 2005. http://hdl.handle.net/1721.1/32102.

Full text

Abstract:

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Includes bibliographical references (p. 91-94).
A system-level checkpointing mechanism, with global knowledge of the state and health of the machine, can improve performance and reliability by dynamically deciding when to skip checkpoint requests made by applications. This thesis presents such a technique, called cooperative checkpointing, and models its behavior as an online algorithm. Where C is the checkpoint overhead and I is the request interval, a worst-case analysis proves a lower bound of (2 + [C/I])-competitiveness for deterministic cooperative checkpointing algorithms, and proves that a number of simple algorithms meet this bound. Using an expected-case analysis, this thesis proves that an optimal periodic checkpointing algorithm that assumes an exponential failure distribution may be arbitrarily bad relative to an optimal cooperative checkpointing algorithm that permits a general failure distribution. Calculations suggest that, under realistic conditions, an application using cooperative checkpointing may make progress 4 times faster than one using periodic checkpointing. Finally, the thesis suggests an embodiment of cooperative checkpointing for a large-scale high performance computer system and presents the results of some preliminary simulations. These results show that, in extreme cases, cooperative checkpointing improved system utilization by more than 25%, reduced bounded slowdown by a factor of 9, while simultaneously reducing the amount of work lost due to failures by 30%. This thesis contributes a unique approach to providing large-scale system reliability through cooperative checkpointing, techniques for analyzing the approach, and blueprints for implementing it in practice.
by Adam Jamison Oliner.
M.Eng.

APA, Harvard, Vancouver, ISO, and other styles

2

Kalaiselvi, S. "Checkpointing Algorithms for Parallel Computers." Thesis, Indian Institute of Science, 1997. https://etd.iisc.ac.in/handle/2005/3908.

Full text

Abstract:

Checkpointing is a technique widely used in parallel/distributed computers for rollback error recovery. Checkpointing is defined as the coordinated saving of process state information at specified time instances. Checkpoints help in restoring the computation from the latest saved state, in case of failure. In addition to fault recovery, checkpointing has applications in fault detection, distributed debugging and process migration. Checkpointing in uniprocessor systems is easy due to the fact that there is a single clock and events occur with respect to this clock. There is a clear demarcation of events that happens before a checkpoint and events that happens after a checkpoint. In parallel computers a large number of computers coordinate to solve a single problem. Since there might be multiple streams of execution, checkpoints have to be introduced along all these streams simultaneously. Absence of a global clock necessitates explicit coordination to obtain a consistent global state. Events occurring in a distributed system, can be ordered partially using Lamport's happens before relation. Lamport's happens before relation ->is a partial ordering relation to identify dependent and concurrent events occurring in a distributed system. It is defined as follows: ·If two events a and b happen in the same process, and if a happens before b, then a->b ·If a is the sending event of a message and b is the receiving event of the same message then a -> b ·If neither a à b nor b -> a, then a and b are said to be concurrent. A consistent global state may have concurrent checkpoints. In the first chapter of the thesis we discuss issues regarding ordering of events in a parallel computer, need for coordination among checkpoints and other aspects related to checkpointing. Checkpointing locations can either be identified statically or dynamically. The static approach assumes that a representation of a program to be checkpointed is available with information that enables a programmer to specify the places where checkpoints are to be taken. The dynamic approach identifies the checkpointing locations at run time. In this thesis, we have proposed algorithms for both static and dynamic checkpointing. The main contributions of this thesis are as follows: 1. Parallel computers that are being built now have faster communication and hence more efficient clock synchronisation compared to those built a few years ago. Based on efficient clock synchronisation protocols, the clock drift in current machines can be maintained within a few microseconds. We have proposed a dynamic checkpointing algorithm for parallel computers assuming bounded clock drifts. 2. The shared memory paradigm is convenient for programming while message passing paradigm is easy to scale. Distributed Shared Memory (DSM) systems combine the advantage of both paradigms and can be visualized easily on top of a network of workstations. IEEE has recently proposed an interconnect standard called Scalable Coherent Interface (SCI), to con6gure computers as a Distributed Shared Memory system. A periodic dynamic checkpointing algorithm has been proposed in the thesis for a DSM system which uses the SCI standard. 3. When information about a parallel program is available one can make use of this knowledge to perform efficient checkpointing. A static checkpointing approach based on task graphs is proposed for parallel programs. The proposed task graph based static checkpointing approach has been implemented on a Parallel Virtual Machine (PVM) platform. We now give a gist of various chapters of the thesis. Chapter 2 of the thesis gives a classification of existing checkpointing algorithms. The chapter surveys algorithm that have been reported in literature for checkpointing parallel/distributed systems. A point to be noted is that most of the algorithms published for checkpointing message passing systems are based on the seminal article by Chandy & Lamport. A large number of checkpointing algorithms have been published by relaxing the assumptions made in the above mentioned article and by extending the features to minimise the overheads of coordination and context saving. Checkpointing for shared memory systems primarily extend cache coherence protocols to maintain a consistent memory. All of them assume that the main memory is safe for storing the context. Recently algorithms have been published for distributed shared memory systems, which extend the cache coherence protocols used in shared memory systems. They however also include methods for storing the status of distributed memory in stable storage. Chapter 2 concludes with brief comments on the desirable features of a checkpointing algorithm. In Chapter 3, we develop a dynamic checkpointing algorithm for message passing systems assuming that the clock drift of processors in the system is bounded. Efficient clock synchronisation protocols have been implemented on recent parallel computers owing to the fact that communication between processors is very fast. Based on efficient clock synchronisation protocols, clock skew can be limited to a few microseconds. The algorithm proposed in the thesis uses clocks for checkpoint coordination and vector counts for identifying messages to be logged. The algorithm is a periodic, distributed algorithm. We prove correctness of the algorithm and compare it with similar clock based algorithms. Distributed Shared Memory (DSM) systems provide the benefit of ease of programming in a scalable system. The recently proposed IEEE Scalable Coherent Interface (SCI) standard, facilitates the construction of scalable coherent systems. In Chapter 4 we discuss a checkpointing algorithm for an SCI based DSM system. SCI maintains cache coherence in hardware using a distributed cache directory which scales with the number of processors in the system. SCI recommends a two phase transaction protocol for communication. Our algorithm is a two phase centralised coordinated algorithm. Phase one initiates checkpoints and the checkpointing activity is completed in phase two. The correctness of the algorithm is established theoretically. The chapter concludes with the discussion of the features of SCI exploited by the checkpointing algorithm proposed in the thesis. In Chapter 5, a static checkpointing algorithm is developed assuming that the program to be executed on a parallel computer is given as a directed acyclic task graph. We assume that the estimates of the time to execute each task in the task graph is given. Given the timing at which checkpoints are to be taken, the algorithm identifies a set of edges where checkpointing tasks can be placed ensuring that they form a consistent global checkpoint. The proposed algorithm eliminates coordination overhead at run time. It significantly reduces the context saving overhead by taking checkpoints along edges of the task graph. The algorithm is used as a preprocessing step before scheduling the tasks to processors. The algorithm complexity is O(km) where m is the number of edges in the graph and k the maximum number of global checkpoints to be taken. The static algorithm is implemented on a parallel computer with a PVM environment as it is widely available and portable. The task graph of a program can be constructed manually or through program development tools. Our implementation is a collection of preprocessing and run time routines. The preprocessing routines operate on the task graph information to generate a set of edges to be checkpointed for each global checkpoint and write the information on disk. The run time routines save the context along the marked edges. In case of recovery, the recovery algorithms read the information from stable storage and reconstruct the context. The limitation of our static checkpointing algorithm is that it can operate only on deterministic task graphs. To demonstrate the practical feasibility of the proposed approach, case studies of checkpointing some parallel programs are included in the thesis. We conclude the thesis with a summary of proposed algorithms and possible directions to continue research in the area of checkpointing.

APA, Harvard, Vancouver, ISO, and other styles

3

Kalaiselvi, S. "Checkpointing Algorithms for Parallel Computers." Thesis, Indian Institute of Science, 1997. http://hdl.handle.net/2005/67.

Full text

Abstract:

Checkpointing is a technique widely used in parallel/distributed computers for rollback error recovery. Checkpointing is defined as the coordinated saving of process state information at specified time instances. Checkpoints help in restoring the computation from the latest saved state, in case of failure. In addition to fault recovery, checkpointing has applications in fault detection, distributed debugging and process migration. Checkpointing in uniprocessor systems is easy due to the fact that there is a single clock and events occur with respect to this clock. There is a clear demarcation of events that happens before a checkpoint and events that happens after a checkpoint. In parallel computers a large number of computers coordinate to solve a single problem. Since there might be multiple streams of execution, checkpoints have to be introduced along all these streams simultaneously. Absence of a global clock necessitates explicit coordination to obtain a consistent global state. Events occurring in a distributed system, can be ordered partially using Lamport's happens before relation. Lamport's happens before relation ->is a partial ordering relation to identify dependent and concurrent events occurring in a distributed system. It is defined as follows: ·If two events a and b happen in the same process, and if a happens before b, then a->b ·If a is the sending event of a message and b is the receiving event of the same message then a -> b ·If neither a à b nor b -> a, then a and b are said to be concurrent. A consistent global state may have concurrent checkpoints. In the first chapter of the thesis we discuss issues regarding ordering of events in a parallel computer, need for coordination among checkpoints and other aspects related to checkpointing. Checkpointing locations can either be identified statically or dynamically. The static approach assumes that a representation of a program to be checkpointed is available with information that enables a programmer to specify the places where checkpoints are to be taken. The dynamic approach identifies the checkpointing locations at run time. In this thesis, we have proposed algorithms for both static and dynamic checkpointing. The main contributions of this thesis are as follows: 1. Parallel computers that are being built now have faster communication and hence more efficient clock synchronisation compared to those built a few years ago. Based on efficient clock synchronisation protocols, the clock drift in current machines can be maintained within a few microseconds. We have proposed a dynamic checkpointing algorithm for parallel computers assuming bounded clock drifts. 2. The shared memory paradigm is convenient for programming while message passing paradigm is easy to scale. Distributed Shared Memory (DSM) systems combine the advantage of both paradigms and can be visualized easily on top of a network of workstations. IEEE has recently proposed an interconnect standard called Scalable Coherent Interface (SCI), to con6gure computers as a Distributed Shared Memory system. A periodic dynamic checkpointing algorithm has been proposed in the thesis for a DSM system which uses the SCI standard. 3. When information about a parallel program is available one can make use of this knowledge to perform efficient checkpointing. A static checkpointing approach based on task graphs is proposed for parallel programs. The proposed task graph based static checkpointing approach has been implemented on a Parallel Virtual Machine (PVM) platform. We now give a gist of various chapters of the thesis. Chapter 2 of the thesis gives a classification of existing checkpointing algorithms. The chapter surveys algorithm that have been reported in literature for checkpointing parallel/distributed systems. A point to be noted is that most of the algorithms published for checkpointing message passing systems are based on the seminal article by Chandy & Lamport. A large number of checkpointing algorithms have been published by relaxing the assumptions made in the above mentioned article and by extending the features to minimise the overheads of coordination and context saving. Checkpointing for shared memory systems primarily extend cache coherence protocols to maintain a consistent memory. All of them assume that the main memory is safe for storing the context. Recently algorithms have been published for distributed shared memory systems, which extend the cache coherence protocols used in shared memory systems. They however also include methods for storing the status of distributed memory in stable storage. Chapter 2 concludes with brief comments on the desirable features of a checkpointing algorithm. In Chapter 3, we develop a dynamic checkpointing algorithm for message passing systems assuming that the clock drift of processors in the system is bounded. Efficient clock synchronisation protocols have been implemented on recent parallel computers owing to the fact that communication between processors is very fast. Based on efficient clock synchronisation protocols, clock skew can be limited to a few microseconds. The algorithm proposed in the thesis uses clocks for checkpoint coordination and vector counts for identifying messages to be logged. The algorithm is a periodic, distributed algorithm. We prove correctness of the algorithm and compare it with similar clock based algorithms. Distributed Shared Memory (DSM) systems provide the benefit of ease of programming in a scalable system. The recently proposed IEEE Scalable Coherent Interface (SCI) standard, facilitates the construction of scalable coherent systems. In Chapter 4 we discuss a checkpointing algorithm for an SCI based DSM system. SCI maintains cache coherence in hardware using a distributed cache directory which scales with the number of processors in the system. SCI recommends a two phase transaction protocol for communication. Our algorithm is a two phase centralised coordinated algorithm. Phase one initiates checkpoints and the checkpointing activity is completed in phase two. The correctness of the algorithm is established theoretically. The chapter concludes with the discussion of the features of SCI exploited by the checkpointing algorithm proposed in the thesis. In Chapter 5, a static checkpointing algorithm is developed assuming that the program to be executed on a parallel computer is given as a directed acyclic task graph. We assume that the estimates of the time to execute each task in the task graph is given. Given the timing at which checkpoints are to be taken, the algorithm identifies a set of edges where checkpointing tasks can be placed ensuring that they form a consistent global checkpoint. The proposed algorithm eliminates coordination overhead at run time. It significantly reduces the context saving overhead by taking checkpoints along edges of the task graph. The algorithm is used as a preprocessing step before scheduling the tasks to processors. The algorithm complexity is O(km) where m is the number of edges in the graph and k the maximum number of global checkpoints to be taken. The static algorithm is implemented on a parallel computer with a PVM environment as it is widely available and portable. The task graph of a program can be constructed manually or through program development tools. Our implementation is a collection of preprocessing and run time routines. The preprocessing routines operate on the task graph information to generate a set of edges to be checkpointed for each global checkpoint and write the information on disk. The run time routines save the context along the marked edges. In case of recovery, the recovery algorithms read the information from stable storage and reconstruct the context. The limitation of our static checkpointing algorithm is that it can operate only on deterministic task graphs. To demonstrate the practical feasibility of the proposed approach, case studies of checkpointing some parallel programs are included in the thesis. We conclude the thesis with a summary of proposed algorithms and possible directions to continue research in the area of checkpointing.

APA, Harvard, Vancouver, ISO, and other styles

4

Nilsson, Christoffer, and Sebastian Karlsson. "Adaptive Checkpointing for Emergency Communication Systems." Thesis, Linköpings universitet, Institutionen för datavetenskap, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-130876.

Full text

Abstract:

The purpose of an emergency communication system is to be ready andavailable at all times during an emergency situation. This means that emergencysystems have specic usage characteristics, they experience long idleperiods followed by usage spikes. To achieve high availability it is importantto have a fault-tolerant solution. In this report, warm passive replication isin focus. When using warm passive replication, checkpointing is the procedureof transfering the current state from a primary server to its replicas. Inorder to utilize resources in a more eective manner compared to when usinga xed interval checkpointing method an adaptive checkpointing method isproposed. A simulation-based comparison is carried out using MATLABand Simulink to test both the proposed adaptive method and the xed intervalmethod. Two metrics, response time and time to recover, and fourparameters are used in the simulation. The results show that an adaptivemethod can increase eciency, but in order to make a good adaptive methodit is necessary to have specic information regarding system congurationand usage characteristics.

APA, Harvard, Vancouver, ISO, and other styles

5

Vieira, Gustavo Maciel Dias. "Estudo comparativo de algoritmos para checkpointing." [s.n.], 2001. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276435.

Full text

Abstract:

Orientador : Luiz Eduardo Buzato
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-01T02:33:00Z (GMT). No. of bitstreams: 1 Vieira_GustavoMacielDias_M.pdf: 3096254 bytes, checksum: 30b7155e50de3e9afd753dd40520b771 (MD5) Previous issue date: 2001
Resumo: Esta dissertação fornece um estudo comparativo abrangente de algoritmos quase-síncronos para checkpointing. Para tanto, utilizamos a simulação de sistemas distribuídos que nos oferece liberdade para construirmos modelos de sistemas com grande facilidade. O estudo comparativo avaliou pela primeira vez de forma uniforme o impacto sobre o desempenho dos algoritmos de fatores como a escala do sistema, a freqüência de check points básicos e a diferença na velocidade dos processos da aplicação. Com base nestes dados obtivemos um profundo conhecimento sobre o comportamento destes algoritmos e produzimos um valioso referencial para projetistas de sistemas em busca de algoritmos para check pointing para as suas aplicações distribuídas
Abstract: This dissertation provides a comprehensive comparative study ofthe performance of quase synchronous check pointing algorithms. To do so we used the simulation of distributed systems, which provides freedom to build system models easily. The comparative study assessed for the first time in an uniform environment the impact of the algorithms' performance with respect to factors such as the system's scale, the basic checkpoint rate and the relative processes' speed. By analyzing these data we acquired a deep understanding of the behavior of these algorithms and were able to produce a valuable reference to system architects looking for check pointing algorithms for their distributed applications
Mestrado
Mestre em Ciência da Computação

APA, Harvard, Vancouver, ISO, and other styles

6

Bai, Yunhao. "A Checkpointing Methodology for Android Smartphone." The Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1461171667.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Jeyakumar, Ashwin Raju. "Metamori: A library for Incremental File Checkpointing." Thesis, Virginia Tech, 2004. http://hdl.handle.net/10919/9969.

Full text

Abstract:

The advent of cluster computing has resulted in a thrust towards providing software mechanisms for reliability on clusters. The prevalent model for such mechanisms is to take a snapshot of the state of an application, called a checkpoint and commit it to stable storage. This checkpoint has sufficient meta-data, so that if the application fails, it can be restarted from the checkpoint. This operation is called a restore. In order to record a process' complete state, both its volatile and persistent state must be checkpointed. Several libraries exist for checkpointing volatile state. Some of these libraries feature incremental checkpointing, where only the changes since the last checkpoint are recorded in the next checkpoint. Such incremental checkpointing is advantageous since otherwise, the time taken for each successive checkpoint becomes larger and larger. Also, when checkpointing is done in increments, we can restore state to any of the previous checkpoints; a vital feature for adaptive applications. This thesis presents a user-level incremental checkpointing library for files: Metamori. This brings the advantages of incremental memory checkpointing to files as well, thereby providing a low-overhead approach to checkpoint persistent state. Thus, the complete state of an application can now be incrementally checkpointed, as compared to earlier approaches where volatile state was checkpointed incrementally but persistent state had no such facilities.
Master of Science

APA, Harvard, Vancouver, ISO, and other styles

8

Schmidt, Rodrigo Malta. "Coleta de lixo para protocolos de checkpointing." [s.n.], 2003. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276424.

Full text

Abstract:

Orientadores : Luiz Eduardo Buzato, Islene Calciolari Garcia
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-08-03T19:18:25Z (GMT). No. of bitstreams: 1 Schmidt_RodrigoMalta_M.pdf: 745421 bytes, checksum: c32cef5e0a61fe3580cc8a211902f9fd (MD5) Previous issue date: 2003
Mestrado

APA, Harvard, Vancouver, ISO, and other styles

9

Vasireddy, Rahul. "ASYNCHRONOUS CHECKPOINTING AND RECOVERY APPROACH FOR DISTRIBUTED SYSTEMS." Available to subscribers only, 2009. http://proquest.umi.com/pqdweb?did=1967797571&sid=6&Fmt=2&clientId=1509&RQT=309&VName=PQD.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Montón, i. Macián Màrius. "Checkpointing for virtual platforms and systemC-TLM-2.0." Doctoral thesis, Universitat Autònoma de Barcelona, 2010. http://hdl.handle.net/10803/32099.

Full text

Abstract:

Un dels avantatges d'usar plataformes virtuals o prototipat virtual enlloc del maquinari real pel desenvolupament de programari encastat és la capacitat d'alguns simuladors de fer captures del seu estat. Si el model del sistema complet és prou detallat, pot tardar uns quants minuts (inclús hores) per simular l'engegada d'un Sistema Operatiu. Si es pren una captura just després de que ha acabat d'engegar, cada cop que calgui corre el programari encastat, els dissenyadors poden simplement recuperar la captura i continuar-la. Recuperar una captura normalment porta pocs segons. Aquest guany es trasllada en una major productivitat, especialment quan es treballa amb sistemes encastat, amb programari complex sobre Sistemes Operatius com en els dispositius actuals. En aquesta tesi es presenta en primer lloc el treball realitzat per afegir un llenguatge de descripció de sistemes anomenat SystemC a dues plataformes virtuals diferents. Aquesta tasca es realitzà per una eina comercial i desprès es traslladà a una plataforma de codi obert. També es presenta una sèrie de modificacions al llenguatge SystemC per suportar la captura d'instantànies. Aquestes modificacions faran possible poder agafar l'estat de la simulació en SystemC i salvar-les al disc. Més tard, la simulació es pot recuperar en el mateix estat on es trobava, sense canvis en els seus components. Aquestes millores ajudaran al llenguatge SystemC a ser més àmpliament usat en el món de les Plataformes Virtuals.
One advantage of using a virtual platform or virtual prototype over real hardware for embedded software development and testing is the ability of some simulators to take checkpoints of their state. If the entire system model is detailed enough, it might take several minutes (or even hours) to simulate booting the O.S. If a snapshot of the simulation is saved just after it has finished booting, each time it is necessary to run the embedded software, designers can simply restore the snapshot and go. Restarting a checkpoint typically takes a few seconds. This can translate into a major productivity gain, especially when working with embedded system with complex SW stacks and O.S. like modern embedded devices. In this dissertation we present in firstly our work on adding a description level language as SystemC to two Virtual Platforms. This work was done for a commercial Virtual Platform, and later translated to a open-sourced Platform. This thesis also presents a set of modifications to SystemC language to support checkpointing. These modifications will make it possible to take the state of a SystemC running simulation and save it to disk. Later, the same simulation can be restored to the same point it was before, without any change to the simulated modules. These changes would help SystemC to be suitable for use by Virtual Platforms as a description language.

APA, Harvard, Vancouver, ISO, and other styles

11

Hägglund, Joakim. "Policies and Checkpointing in a Distributed Automotive Middleware." Thesis, Uppsala University, Department of Information Technology, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-103035.

Full text

Abstract:

The goal of this master thesis is to analyze different methods for checkpointing with rollback recovery and evaluate how these would perform in a distributed heterogeneous automotive system. The conclusions from this study lead to a design of a checkpointing system for the Selfconfigurable HighAvailability and Policy based platform for Embedded system (SHAPE) middleware together with an API to use this new functionality. This design has been implemented in SHAPE to prove that it works. The conclusion is that this design should be enough for most applications in SHAPE although it requires some extra work by the application programmer.

This report also covers some aspects of policy based computing and presents adesign which aims to simplify the usage of policies. This results in a system with a policy manager and a context manager which is implemented in SHAPE.This implementation was shown to greatly improve the usability of policies andcontexts without removing any functionalities.

APA, Harvard, Vancouver, ISO, and other styles

12

Thakre, Anupam S. "Asynchronous checkpointing scheme for distributed mobile computing environment /." Available to subscribers only, 2005. http://proquest.umi.com/pqdweb?did=1095439851&sid=1&Fmt=2&clientId=1509&RQT=309&VName=PQD.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Heller, Richard. "Checkpointing without operating system intervention implementing Griewank's algorithm." Ohio : Ohio University, 1998. http://www.ohiolink.edu/etd/view.cgi?ohiou1176494831.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Wu, Jiang. "CHECKPOINTING AND RECOVERY IN DISTRIBUTED AND DATABASE SYSTEMS." UKnowledge, 2011. http://uknowledge.uky.edu/cs_etds/2.

Full text

Abstract:

A transaction-consistent global checkpoint of a database records a state of the database which reflects the effect of only completed transactions and not the re- sults of any partially executed transactions. This thesis establishes the necessary and sufficient conditions for a checkpoint of a data item (or the checkpoints of a set of data items) to be part of a transaction-consistent global checkpoint of the database. This result would be useful for constructing transaction-consistent global checkpoints incrementally from the checkpoints of each individual data item of a database. By applying this condition, we can start from any useful checkpoint of any data item and then incrementally add checkpoints of other data items until we get a transaction- consistent global checkpoint of the database. This result can also help in designing non-intrusive checkpointing protocols for database systems. Based on the intuition gained from the development of the necessary and sufficient conditions, we also de- veloped a non-intrusive low-overhead checkpointing protocol for distributed database systems. Checkpointing and rollback recovery are also established techniques for achiev- ing fault-tolerance in distributed systems. Communication-induced checkpointing algorithms allow processes involved in a distributed computation take checkpoints independently while at the same time force processes to take additional checkpoints to make each checkpoint to be part of a consistent global checkpoint. This thesis develops a low-overhead communication-induced checkpointing protocol and presents a performance evaluation of the protocol.

APA, Harvard, Vancouver, ISO, and other styles

15

周志賢 and Chi-yin Edward Chow. "Adaptive recovery with hierarchical checkpointing on workstation clusters." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1999. http://hub.hku.hk/bib/B29812914.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Chow, Chi-yin Edward. "Adaptive recovery with hierarchical checkpointing on workstation clusters /." Hong Kong : University of Hong Kong, 1999. http://sunzi.lib.hku.hk/hkuto/record.jsp?B20792700.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Bentria, Dounia. "Combining checkpointing and other resilience mechanisms for exascale systems." Thesis, Lyon, École normale supérieure, 2014. http://www.theses.fr/2014ENSL0971/document.

Full text

Abstract:

Dans cette thèse, nous nous sommes intéressés aux problèmes d'ordonnancement et d'optimisation dans des contextes probabilistes. Les contributions de cette thèse se déclinent en deux parties. La première partie est dédiée à l’optimisation de différents mécanismes de tolérance aux pannes pour les machines de très large échelle qui sont sujettes à une probabilité de pannes. La seconde partie est consacrée à l’optimisation du coût d’exécution des arbres d’opérateurs booléens sur des flux de données.Dans la première partie, nous nous sommes intéressés aux problèmes de résilience pour les machines de future génération dites « exascales » (plateformes pouvant effectuer 1018 opérations par secondes).Dans le premier chapitre, nous présentons l’état de l’art des mécanismes les plus utilisés dans la tolérance aux pannes et des résultats généraux liés à la résilience.Dans le second chapitre, nous étudions un modèle d’évaluation des protocoles de sauvegarde de points de reprise (checkpoints) et de redémarrage. Le modèle proposé est suffisamment générique pour contenir les situations extrêmes: d’un côté le checkpoint coordonné, et de l’autre toute une famille de stratégies non-Coordonnées. Nous avons proposé une analyse détaillée de plusieurs scénarios, incluant certaines des plateformes de calcul existantes les plus puissantes, ainsi que des anticipations sur les futures plateformes exascales.Dans les troisième, quatrième et cinquième chapitres, nous étudions l'utilisation conjointe de différents mécanismes de tolérance aux pannes (réplication, prédiction de pannes et détection d'erreurs silencieuses) avec le mécanisme traditionnel de checkpoints et de redémarrage. Nous avons évalué plusieurs modèles au moyen de simulations. Nos résultats montrent que ces modèles sont bénéfiques pour un ensemble de modèles d'applications dans le cadre des futures plateformes exascales.Dans la seconde partie de la thèse, nous étudions le problème de la minimisation du coût de récupération des données par des applications lors du traitement d’une requête exprimée sous forme d'arbres d'opérateurs booléens appliqués à des prédicats sur des flux de données de senseurs. Le problème est de déterminer l'ordre dans lequel les prédicats doivent être évalués afin de minimiser l'espérance du coût du traitement de la requête. Dans le sixième chapitre, nous présentons l'état de l'art de la seconde partie et dans le septième chapitre, nous étudions le problème pour les requêtes exprimées sous forme normale disjonctive. Nous considérons le cas plus général où chaque flux peut apparaître dans plusieurs prédicats et nous étudions deux modèles, le modèle où chaque prédicat peut accéder à un seul flux et le modèle où chaque prédicat peut accéder à plusieurs flux
In this thesis, we are interested in scheduling and optimization problems in probabilistic contexts. The contributions of this thesis come in two parts. The first part is dedicated to the optimization of different fault-Tolerance mechanisms for very large scale machines that are subject to a probability of failure and the second part is devoted to the optimization of the expected sensor data acquisition cost when evaluating a query expressed as a tree of disjunctive Boolean operators applied to Boolean predicates. In the first chapter, we present the related work of the first part and then we introduce some new general results that are useful for resilience on exascale systems.In the second chapter, we study a unified model for several well-Known checkpoint/restart protocols. The proposed model is generic enough to encompass both extremes of the checkpoint/restart space, from coordinated approaches to a variety of uncoordinated checkpoint strategies. We propose a detailed analysis of several scenarios, including some of the most powerful currently available HPC platforms, as well as anticipated exascale designs.In the third, fourth, and fifth chapters, we study the combination of different fault tolerant mechanisms (replication, fault prediction and detection of silent errors) with the traditional checkpoint/restart mechanism. We evaluated several models using simulations. Our results show that these models are useful for a set of models of applications in the context of future exascale systems.In the second part of the thesis, we study the problem of minimizing the expected sensor data acquisition cost when evaluating a query expressed as a tree of disjunctive Boolean operators applied to Boolean predicates. The problem is to determine the order in which predicates should be evaluated so as to shortcut part of the query evaluation and minimize the expected cost.In the sixth chapter, we present the related work of the second part and in the seventh chapter, we study the problem for queries expressed as a disjunctive normal form. We consider the more general case where each data stream can appear in multiple predicates and we consider two models, the model where each predicate can access a single stream and the model where each predicate can access multiple streams

APA, Harvard, Vancouver, ISO, and other styles

18

Jangjaimon, Itthichok. "Effective Checkpointing for Networked Multicore Systems and Cloud Computing." Thesis, University of Louisiana at Lafayette, 2014. http://pqdtopen.proquest.com/#viewpdf?dispub=3615289.

Full text

Abstract:

Checkpointing has been widely adopted in support of fault-tolerance and job migration essential for large-scale networked multicore systems and cloud computing. This dissertation pursues an effective checkpointing mechanism to handle failures and unavailable events in such systems and thus to reduce the expected job turnaround time, the aggregated file size, and the monetary cost involved. To withstand unavailability/failures of local nodes in networked systems, multi-level checkpointing is indispensable, with checkpoint files kept not only locally but also at remote storage. As the number of nodes in such a system grows, I/O bandwidth to remote storage quickly becomes the bottleneck for multi-level checkpointing.

The first part of this work deals with an effective mechanism, dubbed adaptive incremental checkpointing (AIC), which reduces the checkpointing file size considerably to lower its involved overhead and thus to shorten the expected job turnaround time. Given production multicore systems are observed to often have unused cores available, we design AIC to make use of separate, otherwise unused, cores for carrying out delta compression at desirable points of time adaptively. AIC permits multi-level checkpointing effectively, with checkpoint files of execution nodes written to their partner nodes and to remote storage concurrently during job execution. AIC is observed in our implemented testbed to substantially lower the normalized expected turnaround time (by up to 41%) and the aggregated file size (by up to 1,000×) when compared to its static counterpart and a recent multi-level checkpointing scheme with fixed checkpoint intervals.

The second part presents design and implementation of our enhanced adaptive incremental checkpointing (EAIC) for multithreaded applications on the RaaS clouds under spot instance pricing. EAIC model takes into account spot instance revocation events, besides hardware failures, for fast and accurately predicting the desirable points of time to take checkpoints so as to markedly reduce the expected job turnaround time and the monetary cost. The experimental results from our established testbed under real spot instance price traces from Amazon EC2 show that EAIC lowers both the application turnaround time and the monetary cost markedly (by up to 58% and 59%, respectively) in comparison to its recent checkpointing counterpart.

APA, Harvard, Vancouver, ISO, and other styles

19

Komal, Hooria. "An investigation of semantic checkpointing in dynamically reconfigurable applications." Thesis, Massachusetts Institute of Technology, 2008. http://hdl.handle.net/1721.1/46033.

Full text

Abstract:

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
Includes bibliographical references (p. 74-75).
As convergence continues to blur lines between different hardware and software platforms, distributed systems are becoming increasingly important. With this rise in the use of such systems, the ability to provide continuous functionality to the user under varying conditions and across different platforms becomes important.This thesis investigates the issues that must be dealt with in implementing a system performing dynamic reconfiguration by enabling semantic checkpointing: capturing application level state. The reconfiguration under question is not restricted to replacement of a few modules or moving modules from one machine to another. The individual components can be completely changed as long as the configuration provides identical higher-level functionality. As part of this thesis work, I have implemented a model application that supports semantic checkpointing and is capable of functioning even after a reconfiguration. This application will serve as an illustrative example of a system that provides these capabilities and demonstrates various types of reconfigurations. In addition, the application allows easy understanding and investigation of the issues involved in providing application-level checkpointing and reconfiguration support. While the details of the checkpointing and reconfiguration will be application specific, there are many common features that all runtime reconfigurable applications share. The aim of this thesis is to use this application implementation to highlight these common features. Furthermore, I use our approach as a means to derive more general guidelines and strategies that could be combined to create a complete framework for enabling such behavior.
by Hooria Komal.
M.Eng.

APA, Harvard, Vancouver, ISO, and other styles

20

Sánchez, Verdejo Rommel. "HPC memory systems: Implications of system simulation and checkpointing." Doctoral thesis, Universitat Politècnica de Catalunya, 2022. http://hdl.handle.net/10803/673620.

Full text

Abstract:

The memory system is a significant contributor for most of the current challenges in computer architecture: application performance bottlenecks and operational costs in large data-centers as HPC supercomputers. With the advent of emerging memory technologies, the exploration for novel designs on the memory hierarchy for HPC systems is an open invitation for computer architecture researchers to improve and optimize current designs and deployments. System simulation is the preferred approach to perform architectural explorations due to the low cost to prototype hardware systems, acceptable performance estimates, and accurate energy consumption predictions. Despite the broad presence and extensive usage of system simulators, their validation is not standardized; either because the main purpose of the simulator is not meant to mimic real hardware, or because the design assumptions are too narrow on a particular computer architecture topic. This thesis provides the first steps for a systematic methodology to validate system simulators when compared to real systems. We unveil real-machine´s micro-architectural parameters through a set of specially crafted micro-benchmarks. The unveiled parameters are used to upgrade the simulation infrastructure in order to obtain higher accuracy in the simulation domain. To evaluate the accuracy on the simulation domain, we propose the retirement factor, an extension to a well-known application´s performance methodology. Our proposal provides a new metric to measure the impact simulator´s parameter-tuning when looking for the most accurate configuration. We further present the delay queue, a modification to the memory controller that imposes a configurable delay for all memory transactions that reach the main memory devices; evaluated using the retirement factor, the delay queue allows us to identify the sources of deviations between the simulator infrastructure and the real system. Memory accesses directly affect application performance, both in the real-world machine as well as in the simulation accuracy. From single-read access to a unique memory location up to simultaneous read/write operations to a single or multiple memory locations, HPC applications memory usage differs from workload to workload. A property that allows to glimpse on the application´s memory usage is the workload´s memory footprint. In this work, we found a link between HPC workload´s memory footprint and simulation performance. Actual trends on HPC data-center memory deployments and current HPC application’s memory footprint led us to envision an opportunity for emerging memory technologies to include them as part of the reliability support on HPC systems. Emerging memory technologies such as 3D-stacked DRAM are getting deployed in current HPC systems but in limited quantities in comparison with standard DRAM storage making them suitable to use for low memory footprint HPC applications. We exploit and evaluate this characteristic enabling a Checkpoint-Restart library to support a heterogeneous memory system deployed with an emerging memory technology. Our implementation imposes negligible overhead while offering a simple interface to allocate, manage, and migrate data sets between heterogeneous memory systems. Moreover, we showed that the usage of an emerging memory technology it is not a direct solution to performance bottlenecks; correct data placement and crafted code implementation are critical when comes to obtain the best computing performance. Overall, this thesis provides a technique for validating main memory system simulators when integrated in a simulation infrastructure and compared to real systems. In addition, we explored a link between the workload´s memory footprint and simulation performance on current HPC workloads. Finally, we enabled low memory footprint HPC applications with resilience support while transparently profiting from the usage of emerging memory deployments.
El sistema de memoria es el mayor contribuidor de los desafíos actuales en el campo de la arquitectura de ordenadores como lo son los cuellos de botella en el rendimiento de las aplicaciones, así como los costos operativos en los grandes centros de datos. Con la llegada de tecnologías emergentes de memoria, existe una invitación para que los investigadores mejoren y optimicen las implementaciones actuales con novedosos diseños en la jerarquía de memoria. La simulación de los ordenadores es el enfoque preferido para realizar exploraciones de arquitectura debido al bajo costo que representan frente a la realización de prototipos físicos, arrojando estimaciones de rendimiento aceptables con predicciones precisas. A pesar del amplio uso de simuladores de ordenadores, su validación no está estandarizada ya sea porque el propósito principal del simulador no es imitar al sistema real o porque las suposiciones de diseño son demasiado específicas. Esta tesis proporciona los primeros pasos hacia una metodología sistemática para validar simuladores de ordenadores cuando son comparados con sistemas reales. Primero se descubren los parámetros de microarquitectura en la máquina real a través de un conjunto de micro-pruebas diseñadas para actualizar la infraestructura de simulación con el fin de mejorar la precisión en el dominio de la simulación. Para evaluar la precisión de la simulación, proponemos "el factor de retiro", una extensión a una conocida herramienta para medir el rendimiento de las aplicaciones, pero enfocada al impacto del ajuste de parámetros en el simulador. Además, presentamos "la cola de retardo", una modificación virtual al controlador de memoria que agrega un retraso configurable a todas las transacciones de memoria que alcanzan la memoria principal. Usando el factor de retiro, la cola de retraso nos permite identificar el origen de las desviaciones entre la infraestructura del simulador y el sistema real. Todos los accesos de memoria afectan directamente el rendimiento de la aplicación. Desde el acceso de lectura a una única localidad memoria hasta operaciones simultáneas de lectura/escritura a una o varias localidades de memoria, una propiedad que permite reflejar el uso de memoria de la aplicación es su "huella de memoria". En esta tesis encontramos un vínculo entre la huella de memoria de las aplicaciones de alto desempeño y su rendimiento en simulación. Las tecnologías de memoria emergentes se están implementando en sistemas de alto desempeño en cantidades limitadas en comparación con la memoria principal haciéndolas adecuadas para su uso en aplicaciones con baja huella de memoria. En este trabajo, habilitamos y evaluamos el uso de un sistema de memoria heterogéneo basado en un sistema emergente de memoria. Nuestra implementación agrega una carga despreciable al mismo tiempo que ofrece una interfaz simple para ubicar, administrar y migrar datos entre sistemas de memoria heterogéneos. Además, demostramos que el uso de una tecnología de memoria emergente no es una solución directa a los cuellos de botella en el desempeño. La implementación es fundamental a la hora de obtener el mejor rendimiento ya sea ubicando correctamente los datos, o bien diseñando código especializado. En general, esta tesis proporciona una técnica para validar los simuladores respecto al sistema de memoria principal cuando se integra en una infraestructura de simulación y se compara con sistemas reales. Además, exploramos un vínculo entre la huella de memoria de la carga de trabajo y el rendimiento de la simulación en cargas de trabajo de aplicaciones de alto desempeño. Finalmente, habilitamos aplicaciones de alto desempeño con soporte de resiliencia mientras que se benefician de manera transparente con el uso de un sistema de memoria emergente.
Arquitectura de Computadors

APA, Harvard, Vancouver, ISO, and other styles

21

Berg, Gustaf, and Magnus Brattlöf. "Distributed Checkpointing with Docker Containers in High Performance Computing." Thesis, Högskolan Väst, Avdelningen för data-, elektro- och lantmäteriteknik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:hv:diva-11645.

Full text

Abstract:

Container-virtualisering har blivit mer och mer använt efter att uppdateringar till cgroups och namespace-funktionerna släpptes i Linuxkärnan. Samtidigt så lider industrins högpresterande beräkningskluster av dyra licenskostnader som skulle kunna hanteras av virtualisering. I den här uppsatsen utformades experiment för att ta reda på om Dockers funktion checkpoint, som fortfarande är under utveckling, skulle kunna utnyttjas i industrins beräkningskluster. Genom att demonstrera detta koncept och dess möjligheter att pausa distribuerade containrar, som kör parallella processer inuti, användes den välkända NAS Parallel Benchmarken (NPB) fördelad över två test-maskiner. Sedan så pausades containrar i olika ordningar och Docker lyckas återuppta benchmarken utan problem både lokalt och distribuerat. Om man försiktigt överväger ordningen som man skriver ner containers till disk (checkpoint) så går det utan problem att återuppta benchmarken lokalt på samma maskin. Slutligen så visar vi även att distribuerade containrar kan återupptas på en annan maskin än där den startade med hög framgång. Dockers prestanda, möjligheter och flexibilitet lämpar sig i framtidens industriella högpresterande kluster där man mycket väl kan köra sina applikationer i containrar istället för att köra dom på det traditionella sättet, direkt på hårdvaran. Genom användning av Docker-containers kan man hantera problemet med dyra licenskostnader och prioriteringar.
Lightweight container virtualization has gained widespread adoption in recent years after updates to namespace and cgroups features in the Linux kernel. At the same time the Industrial High Performance community suffers from expensive licensing costs that could be managed with virtualization. To demonstrate that Docker could be used for suspending distributed containers with parallel processes, experiments were designed to find out if the experimental checkpoint feature is ready for this community. We run the well-known NAS Parallel Benchmark (NPB) inside containers spread over two systems under test to prove this concept. Then, pausing containers and unpausing them in different sequence orders we were able resume the benchmark. After that, we further demonstrate that if you carefully consider the order in which you Checkpoint/Restore containers, then the checkpoint feature is also able to resume the benchmark successfully. Finally, the concept of restoring distributed containers, running the benchmark, on a different system from where it started was proven to be working with a high success rate. Our tests demonstrate the performance, possibilities and flexibilities of Dockers future in the industrial HPC community. This might very well tip the community over to running their simulations and virtual engineering-applications inside containers instead of running them on native hardware.

APA, Harvard, Vancouver, ISO, and other styles

22

Manivannan, D. "Quasi-synchronous checkpointing and failure recovery in distributed systems /." The Ohio State University, 1997. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487946776022687.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Sunke, Phani Kanth. "A new asynchronous checkpointing/recovery mechanism for cluster federations /." Available to subscribers only, 2007. http://proquest.umi.com/pqdweb?did=1400971261&sid=4&Fmt=2&clientId=1509&RQT=309&VName=PQD.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Foster, Mark S. "Process forensics the crossroads of checkpointing and intrusion detection /." [Gainesville, Fla.] : University of Florida, 2004. http://purl.fcla.edu/fcla/etd/UFE0008063.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Doudalis, Ioannis. "Hardware assisted memory checkpointing and applications in debugging and reliability." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/42700.

Full text

Abstract:

The problems of software debugging and system reliability/availability are among the most challenging problems the computing industry is facing today, with direct impact on the development and operating costs of computing systems. A promising debugging technique that assists programmers identify and fix the causes of software bugs a lot more efficiently is bidirectional debugging, which enables the user to execute the program in "reverse", and a typical method used to recover a system after a fault is backwards error recovery, which restores the system to the last error-free state. Both reverse execution and backwards error recovery are enabled by creating memory checkpoints, which are used to restore the program/system to a prior point in time and re-execute until the point of interest. The checkpointing frequency is the primary factor that affects both the latency of reverse execution and the recovery time of the system; more frequent checkpoints reduce the necessary re-execution time. Frequent creation of checkpoints poses performance challenges, because of the increased number of memory reads and writes necessary for copying the modified system/program memory, and also because of software interventions, additional synchronization and I/O, etc., needed for creating a checkpoint. In this thesis I examine a number of different hardware accelerators, whose role is to create frequent memory checkpoints in the background, at minimal performance overheads. For the purpose of reverse execution, I propose the HARE and Euripus hardware checkpoint accelerators. HARE and Euripus create different types of checkpoints, and employ different methods for keeping track of the modified memory. As a result, HARE and Euripus have different hardware costs and provide different functionality which directly affects the latency of reverse execution. For improving the availability of the system, I propose the Kyma hardware accelerator. Kyma enables simultaneous creation of checkpoints at different frequencies, which allows the system to recover from multiple types of errors and tolerate variable error-detection latencies. The Kyma and Euripus hardware engines have similar architectures, but the functionality of the Kyma engine is optimized for further reducing the performance overheads and improving the reliability of the system. The functionality of the Kyma and Euripus engines can be combined into a unified accelerator that can serve the needs of both bidirectional debugging and system recovery.

APA, Harvard, Vancouver, ISO, and other styles

26

Silva, Marcelo Pereira da. "Adaptive Remus: replicação de máquinas virtuais Xen com checkpointing adaptável." Universidade do Estado de Santa Catarina, 2015. http://tede.udesc.br/handle/handle/2046.

Full text

Abstract:

Made available in DSpace on 2016-12-12T20:22:53Z (GMT). No. of bitstreams: 1 Marcelo Pereira da Silva.pdf: 1790996 bytes, checksum: 8b61245ad63935d86a70520f22eae9bc (MD5) Previous issue date: 2015-07-03
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
With the ever-increasing dependence on computers and networks, many systems are required to be continuously available in order to fulfill their mission. Virtualization technology enables high availability to be offered in a convenient, cost-effective manner: with the encapsulation provided by virtual machines (VMs), entire systems can be replicated transparently in software, obviating the need for expensive fault-tolerant hardware. Remus is a VM replication mechanism for the Xen hypervisor that provides high availability despite crash failures. Replication is performed by checkpointing the VM at fixed intervals. However, there is an antagonism between processing and communication regarding the optimal checkpointing interval: while longer intervals benefit processorintensive applications, shorter intervals favor network-intensive applications. Thus, any chosen interval may not always be suitable for the hosted applications, limiting Remus usage in many scenarios. This work introduces Adaptive Remus, a proposal for adaptive checkpointing in Remus that dynamically adjusts the replication frequency according to the characteristics of running applications. Experimental results indicate that our proposal improves performance for applications that require both processing and communication, without harming applications that use only one type of resource.
Com a dependência cada vez maior de computadores e redes, muitos sistemas precisam estar continuamente disponíveis para cumprir sua missão. A tecnologia de virtualização permite prover alta disponibilidade de forma conveniente e a um custo razoável: com o encapsulamento oferecido pelas máquinas virtuais (MVs), sistemas inteiros podem ser replicados em software, de forma transparente, eliminando a necessidade de hardware tolerante a faltas dispendioso. Remus é um mecanismo de replicação de MVs que fornece alta disponibilidade diante de faltas de parada. A replicação é realizada através de checkpointing, seguindo um intervalo fixo de tempo predeterminado. Todavia, existe um antagonismo entre processamento e comunicação em relação ao intervalo ideal entre checkpoints: enquanto intervalos maiores beneficiam aplicações com processamento intensivo, intervalos menores favorecem as aplicações cujo desempenho é dominado pela rede. Logo, o intervalo utilizado nem sempre é o adequado para as características de uso de recursos da aplicação em execução na MV, limitando a aplicabilidade de Remus em determinados cenários. Este trabalho apresenta Adaptive Remus, uma proposta de checkpointing adaptativo para Remus, que ajusta dinamicamente a frequência de replicação de acordo com as características das aplicações em execução. Os resultados indicam que a proposta obtém um melhor desempenho de aplicações que utilizam tanto recursos de processamento como de comunicação, sem prejudicar aplicações que usam apenas um dos tipos de recursos.

APA, Harvard, Vancouver, ISO, and other styles

27

Silva, Francisco Assis da. "Recuperação com base em Checkpointing : uma abordagem orientada a objetos." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2002. http://hdl.handle.net/10183/1929.

Full text

Abstract:

Independentemente do modelo de programação adotado, no projeto e implementação de aplicações de alta disponibilidade, faz-se necessário usar procedimentos de tolerância a falhas. Dentre as atividades que trazem consigo interesse de pesquisa na área de Tolerância a Falhas, estão os mecanismos de recuperação em um sistema computacional. Do ponto de vista prático, estes mecanismos buscam manter próximo do mínimo o tempo total de execução de aplicações computacionais de longa duração, ao mesmo tempo em que as preparam para não sofrerem perdas significativas de desempenho, em caso de falhas. Paralelamente à evolução dos sistemas computacionais, foi possível observar também a evolução das linguagens de programação, principalmente as que utilizam o paradigma orientado a objetos. O advento da área de tolerância a falhas na orientação a objetos resultou em novos problemas na atividade de recuperação quanto aos mecanismos de salvamento de estados e retomada da execução, principalmente no que se refere às dificuldades de gerenciamento e controle sobre a alocação de objetos. Entretanto, observa-se que a complexidade de implementação dos mecanismos de recuperação, por parte dos programadores, exige deles conhecimentos mais especializados para o salvamento dos estados da aplicação e para a retomada da execução. Portanto, a simplificação do trabalho do programador, através do uso de uma biblioteca de checkpointing que implemente os mecanismos de salvamento de estados e recuperação é o ponto focal deste trabalho. Diante do contexto exposto, nesta dissertação, são definidas e implementadas as classes de uma biblioteca que provê mecanismos de checkpointing e recuperação. Esta biblioteca, denominada de Libcjp, visa aprimorar o processo de recuperação de aplicações orientadas a objetos escritas na linguagem de programação Java. Esta linguagem foi escolhida para implementação devido à presença dos recursos de persistência e serialização. Para a concepção do trabalho, são considerados ambos os cenários no paradigma orientado a objetos: objetos centralizados e distribuídos. São utilizados os recursos da API de serialização Java e a tecnologia Java RMI para objetos distribuídos. Conclui-se o trabalho com a ilustração de casos de uso através de diversos exemplos desenvolvidos a partir de seus algoritmos originais inicialmente, e incrementados posteriormente com os mecanismos de checkpointing e recuperação. Os componentes desenvolvidos foram testados quanto ao cumprimento dos seus requisitos funcionais. Adicionalmente, foi realizada uma análise preliminar sobre a influência das ações de checkpointing nas características de desempenho das aplicações.

APA, Harvard, Vancouver, ISO, and other styles

28

Chimakurthy, Prasanth. "A new roll-forward checkpointing/recovery mechanism for cluster federation /." Available to subscribers only, 2007. http://proquest.umi.com/pqdweb?did=1464129401&sid=6&Fmt=2&clientId=1509&RQT=309&VName=PQD.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Vemuri, Aditya. "A high performance non-blocking checkpointing/recovery algorithm for ring networks /." Available to subscribers only, 2006. http://proquest.umi.com/pqdweb?did=1203587991&sid=8&Fmt=2&clientId=1509&RQT=309&VName=PQD.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Gad, Ramy Mohamed Aly [Verfasser]. "Enhancing application checkpointing and migration in HPC / Ramy Mohamed Aly Gad." Mainz : Universitätsbibliothek Mainz, 2018. http://d-nb.info/1172105073/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Silva, Ulisses Furquim Freire da. "Arquitetura de software para recuperaçao de falhas utilizando checkpointing quase-sincrono." [s.n.], 2005. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276505.

Full text

Abstract:

Orientadores: Islene Calciolari Garcia
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-06T15:21:09Z (GMT). No. of bitstreams: 1 Silva_UlissesFurquimFreireda_M.pdf: 705102 bytes, checksum: 5b4ebc6853f67fd40696b21c87297f43 (MD5) Previous issue date: 2005
Resumo: Um sistema distribuído tolerante a falhas que utilize recuperação por retrocesso de estado deve selecionar os checkpoints dos seus processos que serão gravados. Além dessa seleção, definida por um protocolo de checkpointing, o sistema precisa realizar uma coleta de lixo, para eliminar os checkpoints que se tornam obsoletos à medida que a aplicação executa. Assim, na ocorrência de uma falha, a computação pode ser retrocedida para um estado consistente salvo anteriormente. Esta dissertação discute os aspectos teóricos e práticos de um sistema distribuído tolerante a falhas que utiliza protocolos de checkpointing quase-síncronos e algoritmos para a coleta de lixo e recuperação por retrocesso. Existem vários protocolos de checkpointing na literatura, e nesta dissertação foram estudados os protocolos de checkpointing quase-síncronos. Esses protocols enviam informações de controle juntamente com as mensagens da aplicação, e podem exigir a gravação de checkpoints forçados, mas não necessitam de sincronização ou troca de mensagens de controle entre os processos. Com base nesse estudo, um framework para protocolos de checkpointing quase-sincronos foi implementado numa biblioteca de troca de mensagens chamada LAM/MPI. Além disso, uma arquitetura de software para recuperação de falhas por retrocesso de estado chamada Curupira também foi estudada e implementada naquela biblioteca. O Curupira_e a primeira arquitetura de software que n~ao precisa de troca de mensagens de controle ou qualquer sincronização entre os processos na execução dos protocolos de checkpointing e de coleta de lixo
Abstract: A fault-tolerant distributed system based on rollback-recovery has to checkpoints of its processes are stored. Besides this selection, that is controlled checkpointing protocol, the system has to do garbage collection, in order to eliminate that become obsolete while the application executes. The garbage collection because checkpoints require the use of storage resources and the storage has limited capacity. So, when some fault occurs, the whole distributed be restored to a consistent global state previously stored. This dissertation practical and theoretical aspects of a fault-tolerant distributed system quasisynchronous checkpointing protocols and also garbage collection and algorithms. There are several checkpointing protocols proposed in the literature, quasisynchronous ones were studied in this dissertation. These protocols information in the application's messages and can induce forced checkpoints, need any synchronization or exchanging of control messages among on that study, a framework for quasi-synchronous checkpointing implemented in a message passing library called LAM/MPI. Moreover, a based on rollback-recovery from faults named Curupira was also implemented in that library. Curupira is the _rst software architecture exchanging of control messages or any synchronization among the execution of the checkpointing and garbage collection protocols
Mestrado
Sistemas Distribuidos
Mestre em Ciência da Computação

APA, Harvard, Vancouver, ISO, and other styles

32

Sakata, Tiemi Christine. "Uma ponte entre as abordagens sincrona e quase-sincrona para checkpointing." [s.n.], 2006. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276255.

Full text

Abstract:

Orientador: Islene Calciolari Garcia
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-08T07:37:22Z (GMT). No. of bitstreams: 1 Sakata_TiemiChristine_D.pdf: 843635 bytes, checksum: 7f950e8bee6e5c7a1dfb19c6212897c2 (MD5) Previous issue date: 2007
Resumo: Protocolos de checkpointing são responsáveis pelo armazenamento de estados dos processos de um sistema distribuído em memória estável para tolerar falhas. Os protocolos síncronos minimais induzem apenas um número minimal de processos a salvarem checkpoints durante uma execução do protocolo bloqueando os processos envolvidos. Uma versão não-bloqueante desta abordagem garante a minimalidade no número de checkpoints salvos em memória estável com o uso de checkpoints mutáveis, checkpoints que podem ser salvos em memória não-estável. Porém, a complexidade deste protocolo e o fato de ele tolerar apenas a presença de uma execução de checkpointing a cada instante nos motivou a procurar soluções para estes problemas na teoria desenvolvida para os protocolos quase-síncronos. A nova abordagem nos permitiu fazer uma revisão de alguns protocolos síncronos bloqueantes existentes na literatura que até então eram considerados minimais. Nesta mesma linha, obtivemos novos resultados na análise de minimalidade dos protocolos síncronos não-bloqueantes, ao considerarmos a aplicação como um todo e também a existência de execuções concorrentes de checkpointing. Ao estabelecermos esta ponte entre as abordagens para checkpointing, conseguimos desenvolver dois novos protocolos síncronos não-bloqueantes. Ambos fazem uso de checkpoints mutáveis, permitem execuções concorrentes de checkpointing e possuem um mecanismo simples de coleta de lixo. No entanto, o fato de cada um dos protocolos derivar de classes diferentes de protocolos quase-síncronos leva a comportamentos distintos, como evidenciado por resultados de simulação
Abstract: Checkpointing protocols are responsible for the selection of checkpoints in fault-tolerant distributed systems. Minimal checkpointing protocols minimize the number of checkpoints blocking processes during checkpointing. A non-blocking version of this approach assures a minimal number of checkpoints saved in stable memory using mutable checkpoints, those checkpoints can be saved in a non-stable storage. However, the complexity of this protocol and the absence of concurrent checkpointing executions have motivated us to find new solutions in the quasi-synchronous theory. The new approach has allowed us to review some blocking synchronous protocols existent in the literature which were, until now, considered as minimals. In the same way, we present new results analysing the minimality on the number of checkpoints in nonblocking synchronous protocols, considering the whole application and also the existence of concurrent checkpointing executions. On bridging the gap between the checkpointing approaches we could develop two new non-blocking synchronous protocols. Both use mutable checkpoints, allow concurrent checkpointing executions and have a simple mechanism of garbage collection. However, since each protocol derives from a diferent class of quasi-synchronous protocols, they present distinct behaviours, which are evident in the simulation results
Doutorado
Sistemas Distribuidos
Doutor em Ciência da Computação

APA, Harvard, Vancouver, ISO, and other styles

33

Aïssaoui, François. "Autonomic Approach based on Semantics and Checkpointing for IoT System Management." Thesis, Toulouse 1, 2018. http://www.theses.fr/2018TOU10061/document.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Kantheti, Vinod. "Design of an efficient checkpointing-recovery algorithm for distributed cluster computing environment /." Available to subscribers only, 2005. http://proquest.umi.com/pqdweb?did=1079672401&sid=2&Fmt=2&clientId=1509&RQT=309&VName=PQD.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Camargo, Raphael Yokoingawa de. "\"Armazenamento distribuído de dados e checkpointing de aplicações paralelas em grades oportunistas\"." Universidade de São Paulo, 2007. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-30082007-115609/.

Full text

Abstract:

Grades computacionais oportunistas utilizam recursos ociosos de máquinas compartilhadas para executar aplicações que necessitam de um alto poder computacional e/ou trabalham com grandes quantidades de dados. Mas a execução de aplicações paralelas computacionalmente intensivas em ambientes dinâmicos e heterogêneos, como grades computacionais oportunistas, é uma tarefa difícil. Máquinas podem falhar, ficar inacessíveis ou passar de ociosas para ocupadas inesperadamente, comprometendo a execução de aplicações. Um mecanismo de tolerância a falhas que dê suporte a arquiteturas heterogêneas é um importante requisito para estes sistemas. Neste trabalho, analisamos, implementamos e avaliamos um mecanismo de tolerância a falhas baseado em checkpointing para aplicações paralelas em grades computacionais oportunistas. Este mecanismo permite o monitoramento de execuções e a migração de aplicações entre nós heterogêneos da grade. Mas além da execução, é preciso gerenciar e armazenar os dados gerados e utilizados por estas aplicações. Desejamos uma infra-estrutura de armazenamento de dados de baixo custo e que utilize o espaço livre em disco de máquinas compartilhadas da grade. Devemos utilizar somente os ciclos ociosos destas máquinas para armazenar e recuperar dados, de modo que um sistema de armazenamento distribuído que as utilize deve ser redundante e tolerante a falhas. Para resolver o problema do armazenamento de dados em grades oportunistas, projetamos, implementamos e avaliamos o middleware OppStore. Este middleware provê armazenamento distribuído e confiável de dados, que podem ser acessados de qualquer máquina da grade. As máquinas são organizadas em aglomerados, que são conectados por uma rede peer-to-peer auto-organizável e tolerante a falhas. Dados são codificados em fragmentos redundantes antes de serem armazenados, de modo que arquivos podem ser reconstruídos utilizando apenas um subconjunto destes fragmentos. Finalmente, para lidar com a heterogeneidade dos recursos, desenvolvemos uma extensão ao protocolo de roteamento em redes peer-to-peer Pastry. Esta extensão adiciona balanceamento de carga e suporte à heterogeneidade de máquinas ao protocolo Pastry.
Opportunistic computational grids use idle resources from shared machines to execute applications that need large amounts of computational power and/or deal with large amounts of data. But executing computationally intensive parallel applications in dynamic and heterogeneous environments, such as opportunistic grids, is a daunting task. Machines may fail, become inaccessible, or change from idle to occupied unexpectedly, compromising the application execution. A fault tolerance mechanism that supports heterogeneous architectures is an important requisite for such systems. In this work, we analyze, implement and evaluate a checkpointing-based fault tolerance mechanism for parallel applications running on opportunistic grids. The mechanism monitors application execution and allows the migration of applications between heterogeneous nodes of the grid. But besides application execution, it is necessary to manage data generated and used by those applications. We want a low cost data storage infrastructure that utilizes the unused disk space of grid shared machines. The system should use the machines to store and recover data only during their idle periods, requiring the system to be redundant and fault-tolerant. To solve the data storage problem in opportunistic grids, we designed, implemented and evaluated the OppStore middleware. This middleware provides reliable distributed storage for application data, which can be accessed from any machine in the grid. The machines are organized in clusters, connected by a self-organizing and fault-tolerant peer-to-peer network. During storage, data is codified into redundant fragments, allowing the reconstruction of the original file using only a subset of those fragments. Finally, to deal with resource heterogeneity, we developed an extension to the Pastry peer-to-peer routing substrate, enabling heterogeneity-aware load-balancing message routing.

APA, Harvard, Vancouver, ISO, and other styles

36

Bhupathi, Raghavendra Kumar. "A fast and efficient non-blocking coordinated checkpointing approach for mobile computing systems /." Available to subscribers only, 2006. http://proquest.umi.com/pqdweb?did=1203588041&sid=22&Fmt=2&clientId=1509&RQT=309&VName=PQD.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Petersen, Karsten. "Management-Elemente für mehrdimensional heterogene Cluster." Master's thesis, Universitätsbibliothek Chemnitz, 2003. http://nbn-resolving.de/urn:nbn:de:swb:ch1-200300851.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Vutukuru, Ashwin. "A sender based message logging and independent checkpointing approach for recovery in mobile computing environment /." Available to subscribers only, 2009. http://proquest.umi.com/pqdweb?did=1797219881&sid=3&Fmt=2&clientId=1509&RQT=309&VName=PQD.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Vutukuru, Ashwin. "A Sender Based Message Logging and Independent Checkpointing Approach for Recovery in Mobile Computing Environment." OpenSIUC, 2008. https://opensiuc.lib.siu.edu/theses/426.

Full text

Abstract:

In this thesis, we have proposed an efficient recovery mechanism for the mobile computing environment. The recovery is based on message logging and uses asynchronous checkpointing and has no domino effect .The proposed work takes care of orphan and lost message along with the duplicate and delayed messages and ensures correct computation after the system recovers from a failure. The salient feature of this scheme is that after recovering from a failure, only the failed process (MH) rolls back to its recent checkpoint and the messages required for recovery are replayed to the MH by the MSS to which it is connected. The effect of failure does not block the working of fail-free processes. The proposed approach achieves faster, effective and less costly in terms of bandwidth, battery power, storage requirements and time.

APA, Harvard, Vancouver, ISO, and other styles

40

Tran, Van Long. "Optimization of checkpointing and execution model for an implementation of OpenMP on distributed memory architectures." Thesis, Evry, Institut national des télécommunications, 2018. http://www.theses.fr/2018TELE0017/document.

Full text

Abstract:

OpenMP et MPI sont devenus les outils standards pour développer des programmes parallèles sur une architecture à mémoire partagée et à mémoire distribuée respectivement. Comparé à MPI, OpenMP est plus facile à utiliser. Ceci est dû au fait qu’OpenMP génère automatiquement le code parallèle et synchronise les résultats à l’aide de directives, clauses et fonctions d’exécution, tandis que MPI exige que les programmeurs fassent ce travail manuellement. Par conséquent, des efforts ont été faits pour porter OpenMP sur les architectures à mémoire distribuée. Cependant, à l’exclusion de CAPE, aucune solution ne satisfait les deux exigences suivantes: 1) être totalement conforme à la norme OpenMP et 2) être hautement performant. CAPE (Checkpointing-Aided Parallel Execution) est un framework qui traduit et fournit automatiquement des fonctions d’exécution pour exécuter un programme OpenMP sur une architecture à mémoire distribuée basé sur des techniques de checkpoint. Afin d’exécuter un programme OpenMP sur un système à mémoire distribuée, CAPE utilise un ensemble de modèles pour traduire le code source OpenMP en code source CAPE, puis le code source CAPE est compilé par un compilateur C/C++ classique. Fondamentalement, l’idée de CAPE est que le programme s’exécute d’abord sur un ensemble de nœuds du système, chaque nœud fonctionnant comme un processus. Chaque fois que le programme rencontre une section parallèle, le maître distribue les tâches aux processus esclaves en utilisant des checkpoints incrémentaux discontinus (DICKPT). Après l’envoi des checkpoints, le maître attend les résultats renvoyés par les esclaves. L’étape suivante au niveau du maître consiste à recevoir et à fusionner le résultat des checkpoints avant de les injecter dans sa mémoire. Les nœuds esclaves quant à eux reçoivent les différents checkpoints, puis l’injectent dans leur mémoire pour effectuer le travail assigné. Le résultat est ensuite renvoyé au master en utilisant DICKPT. À la fin de la région parallèle, le maître envoie le résultat du checkpoint à chaque esclave pour synchroniser l’espace mémoire du programme. Dans certaines expériences, CAPE a montré des performances élevées sur les systèmes à mémoire distribuée et constitue une solution viable entièrement compatible avec OpenMP. Cependant, CAPE reste en phase de développement, ses checkpoints et son modèle d’exécution devant être optimisés pour améliorer les performances, les capacités et la fiabilité. Cette thèse vise à présenter les approches proposées pour optimiser et améliorer la capacité des checkpoints, concevoir et mettre en œuvre un nouveau modèle d’exécution, et améliorer la capacité de CAPE. Tout d’abord, nous avons proposé une arithmétique sur les checkpoints qui modélise la structure de leurs données et ses opérations. Cette modélisation contribue à optimiser leur taille et à réduire le temps nécessaire à la fusion, tout en améliorant leur capacité. Deuxièmement, nous avons développé TICKPT (Time-Stamp Incremental Checkpointing) une implémentation de l’arithmétique sur les checkpoints. TICKPT est une amélioration de DICKPT, il a ajouté l’horodatage aux checkpoints pour en identifier l’ordre. L’analyse et les expériences comparées montrent TICKPT sont non seulement plus petites, mais qu’ils ont également moins d’impact sur les performances du programme. Troisièmement, nous avons conçu et implémenté un nouveau modèle d’exécution et de nouveaux prototypes pour CAPE basés sur TICKPT. Le nouveau modèle d’exécution permet à CAPE d’utiliser les ressources efficacement, d’éviter les risques de goulots d’étranglement et de satisfaire à l’exigence des les conditions de Bernstein. Au final, ces approches améliorent significativement les performances de CAPE, ses capacités et sa fiabilité. Le partage des données implémenté sur CAPE et basé sur l’arithmétique sur des checkpoints est ouvert et basé sur TICKPT. Cela démontre également la bonne direction que nous avons prise et rend CAPE plus complet
OpenMP and MPI have become the standard tools to develop parallel programs on shared-memory and distributed-memory architectures respectively. As compared to MPI, OpenMP is easier to use. This is due to the ability of OpenMP to automatically execute code in parallel and synchronize results using its directives, clauses, and runtime functions while MPI requires programmers do all this manually. Therefore, some efforts have been made to port OpenMP on distributed-memory architectures. However, excluding CAPE, no solution has successfully met both requirements: 1) to be fully compliant with the OpenMP standard and 2) high performance. CAPE stands for Checkpointing-Aided Parallel Execution. It is a framework that automatically translates and provides runtime functions to execute OpenMP program on distributed-memory architectures based on checkpointing techniques. In order to execute an OpenMP program on distributed-memory system, CAPE uses a set of templates to translate OpenMP source code to CAPE source code, and then, the CAPE source code is compiled by a C/C++ compiler. This code can be executed on distributed-memory systems under the support of the CAPE framework. Basically, the idea of CAPE is the following: the program first run on a set of nodes on the system, each node being executed as a process. Whenever the program meets a parallel section, the master distributes the jobs to the slave processes by using a Discontinuous Incremental Checkpoint (DICKPT). After sending the checkpoints, the master waits for the returned results from the slaves. The next step on the master is the reception and merging of the resulting checkpoints before injecting them into the memory. For slave nodes, they receive different checkpoints, and then, they inject it into their memory to compute the divided job. The result is sent back to the master using DICKPTs. At the end of the parallel region, the master sends the result of the checkpoint to every slaves to synchronize the memory space of the program as a whole. In some experiments, CAPE has shown very high-performance on distributed-memory systems and is a viable and fully compatible with OpenMP solution. However, CAPE is in the development stage. Its checkpoint mechanism and execution model need to be optimized in order to improve the performance, ability, and reliability. This thesis aims at presenting the approaches that were proposed to optimize and improve checkpoints, design and implement a new execution model, and improve the ability for CAPE. First, we proposed arithmetics on checkpoints, which aims at modeling checkpoint’s data structure and its operations. This modeling contributes to optimize checkpoint size and reduces the time when merging, as well as improve checkpoints capability. Second, we developed TICKPT which stands for Time-stamp Incremental Checkpointing as an instance of arithmetics on checkpoints. TICKPT is an improvement of DICKPT. It adds a timestamp to checkpoints to identify the checkpoints order. The analysis and experiments to compare it to DICKPT show that TICKPT do not only provide smaller in checkpoint size, but also has less impact on the performance of the program using checkpointing. Third, we designed and implemented a new execution model and new prototypes for CAPE based on TICKPT. The new execution model allows CAPE to use resources efficiently, avoid the risk of bottlenecks, overcome the requirement of matching the Bernstein’s conditions. As a result, these approaches make CAPE improving the performance, ability as well as reliability. Four, Open Data-sharing attributes are implemented on CAPE based on arithmetics on checkpoints and TICKPT. This also demonstrates the right direction that we took, and makes CAPE more complete

APA, Harvard, Vancouver, ISO, and other styles

41

Tran, Van Long. "Optimization of checkpointing and execution model for an implementation of OpenMP on distributed memory architectures." Electronic Thesis or Diss., Evry, Institut national des télécommunications, 2018. http://www.theses.fr/2018TELE0017.

Full text

Abstract:

OpenMP et MPI sont devenus les outils standards pour développer des programmes parallèles sur une architecture à mémoire partagée et à mémoire distribuée respectivement. Comparé à MPI, OpenMP est plus facile à utiliser. Ceci est dû au fait qu’OpenMP génère automatiquement le code parallèle et synchronise les résultats à l’aide de directives, clauses et fonctions d’exécution, tandis que MPI exige que les programmeurs fassent ce travail manuellement. Par conséquent, des efforts ont été faits pour porter OpenMP sur les architectures à mémoire distribuée. Cependant, à l’exclusion de CAPE, aucune solution ne satisfait les deux exigences suivantes: 1) être totalement conforme à la norme OpenMP et 2) être hautement performant. CAPE (Checkpointing-Aided Parallel Execution) est un framework qui traduit et fournit automatiquement des fonctions d’exécution pour exécuter un programme OpenMP sur une architecture à mémoire distribuée basé sur des techniques de checkpoint. Afin d’exécuter un programme OpenMP sur un système à mémoire distribuée, CAPE utilise un ensemble de modèles pour traduire le code source OpenMP en code source CAPE, puis le code source CAPE est compilé par un compilateur C/C++ classique. Fondamentalement, l’idée de CAPE est que le programme s’exécute d’abord sur un ensemble de nœuds du système, chaque nœud fonctionnant comme un processus. Chaque fois que le programme rencontre une section parallèle, le maître distribue les tâches aux processus esclaves en utilisant des checkpoints incrémentaux discontinus (DICKPT). Après l’envoi des checkpoints, le maître attend les résultats renvoyés par les esclaves. L’étape suivante au niveau du maître consiste à recevoir et à fusionner le résultat des checkpoints avant de les injecter dans sa mémoire. Les nœuds esclaves quant à eux reçoivent les différents checkpoints, puis l’injectent dans leur mémoire pour effectuer le travail assigné. Le résultat est ensuite renvoyé au master en utilisant DICKPT. À la fin de la région parallèle, le maître envoie le résultat du checkpoint à chaque esclave pour synchroniser l’espace mémoire du programme. Dans certaines expériences, CAPE a montré des performances élevées sur les systèmes à mémoire distribuée et constitue une solution viable entièrement compatible avec OpenMP. Cependant, CAPE reste en phase de développement, ses checkpoints et son modèle d’exécution devant être optimisés pour améliorer les performances, les capacités et la fiabilité. Cette thèse vise à présenter les approches proposées pour optimiser et améliorer la capacité des checkpoints, concevoir et mettre en œuvre un nouveau modèle d’exécution, et améliorer la capacité de CAPE. Tout d’abord, nous avons proposé une arithmétique sur les checkpoints qui modélise la structure de leurs données et ses opérations. Cette modélisation contribue à optimiser leur taille et à réduire le temps nécessaire à la fusion, tout en améliorant leur capacité. Deuxièmement, nous avons développé TICKPT (Time-Stamp Incremental Checkpointing) une implémentation de l’arithmétique sur les checkpoints. TICKPT est une amélioration de DICKPT, il a ajouté l’horodatage aux checkpoints pour en identifier l’ordre. L’analyse et les expériences comparées montrent TICKPT sont non seulement plus petites, mais qu’ils ont également moins d’impact sur les performances du programme. Troisièmement, nous avons conçu et implémenté un nouveau modèle d’exécution et de nouveaux prototypes pour CAPE basés sur TICKPT. Le nouveau modèle d’exécution permet à CAPE d’utiliser les ressources efficacement, d’éviter les risques de goulots d’étranglement et de satisfaire à l’exigence des les conditions de Bernstein. Au final, ces approches améliorent significativement les performances de CAPE, ses capacités et sa fiabilité. Le partage des données implémenté sur CAPE et basé sur l’arithmétique sur des checkpoints est ouvert et basé sur TICKPT. Cela démontre également la bonne direction que nous avons prise et rend CAPE plus complet
OpenMP and MPI have become the standard tools to develop parallel programs on shared-memory and distributed-memory architectures respectively. As compared to MPI, OpenMP is easier to use. This is due to the ability of OpenMP to automatically execute code in parallel and synchronize results using its directives, clauses, and runtime functions while MPI requires programmers do all this manually. Therefore, some efforts have been made to port OpenMP on distributed-memory architectures. However, excluding CAPE, no solution has successfully met both requirements: 1) to be fully compliant with the OpenMP standard and 2) high performance. CAPE stands for Checkpointing-Aided Parallel Execution. It is a framework that automatically translates and provides runtime functions to execute OpenMP program on distributed-memory architectures based on checkpointing techniques. In order to execute an OpenMP program on distributed-memory system, CAPE uses a set of templates to translate OpenMP source code to CAPE source code, and then, the CAPE source code is compiled by a C/C++ compiler. This code can be executed on distributed-memory systems under the support of the CAPE framework. Basically, the idea of CAPE is the following: the program first run on a set of nodes on the system, each node being executed as a process. Whenever the program meets a parallel section, the master distributes the jobs to the slave processes by using a Discontinuous Incremental Checkpoint (DICKPT). After sending the checkpoints, the master waits for the returned results from the slaves. The next step on the master is the reception and merging of the resulting checkpoints before injecting them into the memory. For slave nodes, they receive different checkpoints, and then, they inject it into their memory to compute the divided job. The result is sent back to the master using DICKPTs. At the end of the parallel region, the master sends the result of the checkpoint to every slaves to synchronize the memory space of the program as a whole. In some experiments, CAPE has shown very high-performance on distributed-memory systems and is a viable and fully compatible with OpenMP solution. However, CAPE is in the development stage. Its checkpoint mechanism and execution model need to be optimized in order to improve the performance, ability, and reliability. This thesis aims at presenting the approaches that were proposed to optimize and improve checkpoints, design and implement a new execution model, and improve the ability for CAPE. First, we proposed arithmetics on checkpoints, which aims at modeling checkpoint’s data structure and its operations. This modeling contributes to optimize checkpoint size and reduces the time when merging, as well as improve checkpoints capability. Second, we developed TICKPT which stands for Time-stamp Incremental Checkpointing as an instance of arithmetics on checkpoints. TICKPT is an improvement of DICKPT. It adds a timestamp to checkpoints to identify the checkpoints order. The analysis and experiments to compare it to DICKPT show that TICKPT do not only provide smaller in checkpoint size, but also has less impact on the performance of the program using checkpointing. Third, we designed and implemented a new execution model and new prototypes for CAPE based on TICKPT. The new execution model allows CAPE to use resources efficiently, avoid the risk of bottlenecks, overcome the requirement of matching the Bernstein’s conditions. As a result, these approaches make CAPE improving the performance, ability as well as reliability. Four, Open Data-sharing attributes are implemented on CAPE based on arithmetics on checkpoints and TICKPT. This also demonstrates the right direction that we took, and makes CAPE more complete

APA, Harvard, Vancouver, ISO, and other styles

42

Walther, Andrea. "Program Reversal Schedules for Single- and Multi-processor Machines." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2002. http://nbn-resolving.de/urn:nbn:de:swb:14-1011612099250-05302.

Full text

Abstract:

Bei der Berechnung von Adjungierten, zum Debuggen und für ähnliche Anwendungen kann man die Umkehr der entsprechenden Programmauswertung verwenden. Der einfachste Ansatz, nämlich das Mitschreiben einer kompletten Mitschrift der Vorwärtsrechnung, welche anschließend rückwärts gelesen wird, verursacht einen enormen Speicherplatzbedarf. Als Alternative dazu kann man die Mitschrift auch stückweise erzeugen, indem die Programmauswertung von passend gewählten Checkpoints wiederholt gestartet wird. Das Ziel der Arbeit ist die Minimierung des von der Programmumkehr verursachten Zeit- und Speicherplatzbedarfs. Dieser wird gemessen in Auswertungswiederholungen bzw. verwendeten Checkpoints. Optimale Umkehrschemata werden für Ein- und Mehr-Schritt-Verfahren entwickelt, welche zum Beispiel bei der Diskretisierung einer gewöhnlichen Differentialgleichung Verwendung finden. Desweiteren erfolgte die Entwicklung von parallelen Umkehrschemata, d. h. mehrere Prozessoren werden für die Umkehrung der Programmauswertung eingesetzt. Diese zusätzlichen Prozessoren dienen dazu, die wiederholten Berechnungen des Programms zu parallelisieren, so daß ein Prozessor die Rückwartsrechnung ohne Unterbrechung durchführen kann. Sowohl für die seriellen als auch für die parallelen Umkehrschemata wurde gezeigt, daß die Länge der umzukehrenden Programmauswertung exponentiell in Abhängigkeit von der Zahl der verwendeten Checkpoints und der Zahl der wiederholten Auswertungen bzw. verwendeten Prozessoren wächst
For adjoint calculations, parameter estimation, and similar purposes one may need to reverse the execution of a computer program. The simplest option is to record a complete execution log and then to read it backwards. This requires massive amounts of storage. Instead one may generate the execution log piecewise by restarting the ``forward'' calculation repeatedly from suitably placed checkpoints. The basic structure of the resulting reversal schedules is illustrated. Various strategies are analysed with respect to the resulting temporal and spatial complexity on serial and parallel machines. For serial machines known optimal compromises between operations count and memory requirement are explained, and they are extended to more general situations. For program execution reversal on multi-processors the new challenges and demands on an optimal reversal schedule are described. We present parallel reversal schedules that are provably optimal with regards to the number of concurrent processes and the total amount of memory required

APA, Harvard, Vancouver, ISO, and other styles

43

Jiang, Qiangfeng. "ALGORITHMS FOR FAULT TOLERANCE IN DISTRIBUTED SYSTEMS AND ROUTING IN AD HOC NETWORKS." UKnowledge, 2013. http://uknowledge.uky.edu/cs_etds/16.

Full text

Abstract:

Checkpointing and rollback recovery are well-known techniques for coping with failures in distributed systems. Future generation Supercomputers will be message passing distributed systems consisting of millions of processors. As the number of processors grow, failure rate also grows. Thus, designing efficient checkpointing and recovery algorithms for coping with failures in such large systems is important for these systems to be fully utilized. We presented a novel communication-induced checkpointing algorithm which helps in reducing contention for accessing stable storage to store checkpoints. Under our algorithm, a process involved in a distributed computation can independently initiate consistent global checkpointing by saving its current state, called a tentative checkpoint. Other processes involved in the computation come to know about the consistent global checkpoint initiation through information piggy-backed with the application messages or limited control messages if necessary. When a process comes to know about a new consistent global checkpoint initiation, it takes a tentative checkpoint after processing the message. The tentative checkpoints taken can be flushed to stable storage when there is no contention for accessing stable storage. The tentative checkpoints together with the message logs stored in the stable storage form a consistent global checkpoint. Ad hoc networks consist of a set of nodes that can form a network for communication with each other without the aid of any infrastructure or human intervention. Nodes are energy-constrained and hence routing algorithm designed for these networks should take this into consideration. We proposed two routing protocols for mobile ad hoc networks which prevent nodes from broadcasting route requests unnecessarily during the route discovery phase and hence conserve energy and prevent contention in the network. One is called Triangle Based Routing (TBR) protocol. The other routing protocol we designed is called Routing Protocol with Selective Forwarding (RPSF). Both of the routing protocols greatly reduce the number of control packets which are needed to establish routes between pairs of source nodes and destination nodes. As a result, they reduce the energy consumed for route discovery. Moreover, these protocols reduce congestion and collision of packets due to limited number of nodes retransmitting the route requests.

APA, Harvard, Vancouver, ISO, and other styles

44

Khan, Salman. "Putting checkpoints to work in thread level speculative execution." Thesis, University of Edinburgh, 2010. http://hdl.handle.net/1842/4676.

Full text

Abstract:

With the advent of Chip Multi Processors (CMPs), improving performance relies on the programmers/compilers to expose thread level parallelism to the underlying hardware. Unfortunately, this is a difficult and error-prone process for the programmers, while state of the art compiler techniques are unable to provide significant benefits for many classes of applications. An interesting alternative is offered by systems that support Thread Level Speculation (TLS), which relieve the programmer and compiler from checking for thread dependencies and instead use the hardware to enforce them. Unfortunately, data misspeculation results in a high cost since all the intermediate results have to be discarded and threads have to roll back to the beginning of the speculative task. For this reason intermediate checkpointing of the state of the TLS threads has been proposed. When the violation does occur, we now have to roll back to a checkpoint before the violating instruction and not to the start of the task. However, previous work omits study of the microarchitectural details and implementation issues that are essential for effective checkpointing. Further, checkpoints have only been proposed and evaluated for a narrow class of benchmarks. This thesis studies checkpoints on a state of the art TLS system running a variety of benchmarks. The mechanisms required for checkpointing and the costs associated are described. Hardware modifications required for making checkpointed execution efficient in time and power are proposed and evaluated. Further, the need for accurately identifying suitable points for placing checkpoints is established. Various techniques for identifying these points are analysed in terms of both effectiveness and viability. This includes an extensive evaluation of data dependence prediction techniques. The results show that checkpointing thread level speculative execution results in consistent power savings, and for many benchmarks leads to speedups as well.

APA, Harvard, Vancouver, ISO, and other styles

45

Aupy, Guillaume. "Resilient and energy-efficient scheduling algorithms at scale." Thesis, Lyon, École normale supérieure, 2014. http://www.theses.fr/2014ENSL0928.

Full text

Abstract:

Dans cette thèse, j'ai considéré d'un point de vue théorique deux problèmes importants pour les futures plateformes dîtes Exascales : les restrictions liées à leur fiabilité ainsi que les contraintes énergétiques. En première partie de cette thèse, je me suis intéressé à l'étude de placements optimal de ces checkpoints dans un but de minimisation de temps total d'exécution. En particulier, j'ai considéré les checkpoints périodiques et coordonnés. J'ai considéré des prédicteurs de fautes capables de prévoir, de manière imparfaite, les fautes arrivant sur la plateforme. Dans ce contexte, j'ai conçu des algorithmes efficaces pour résoudre mes problèmes. Dans un deuxième temps, j'ai considéré des fautes silencieuses. Ces fautes ne peuvent être détectées qu'uniquement par un système de vérification.Dans le cas où une de ces fautes est détectée, l'utilisateur doit retourner au point de sauvegarde le plus récent qui n'a pas été affecté par cette faute, si un tel point existe ! Dans ce contexte, j'ai à nouveau proposé des algorithmes optimaux au premier ordre, mixant points de sauvegarde et points de vérification. Dans la seconde partie de cette thèse, j'ai considéré des problèmes énergétiques liés à ces mêmes plateformes. Ces problèmes critiques doivent être reliés aux problèmes de fiabilité de la partie précédente. Dans ce contexte, j'ai couplé des techniques de baisse de consommation énergétique à des techniques d'augmentation de fiabilité comme la reexécution, la réplication ainsi que le checkpoint. Pour ces différents problèmes, j'ai pu fournir des algorithmes dont l'efficacité a été montrée soit au travers de simulations, soit grâce à des preuves mathématiques
This thesis deals with two issues for future Exascale platforms, namelyresilience and energy.In the first part of this thesis, we focus on the optimal placement ofperiodic coordinated checkpoints to minimize execution time.We consider fault predictors, a software used by system administratorsthat tries to predict (through the study of passed events) where andwhen faults will strike. In this context, we propose efficientalgorithms, and give a first-order optimal formula for the amount ofwork that should be done between two checkpoints.We then focus on silent data corruption errors. Contrarily to fail-stopfailures, such latent errors cannot be detected immediately, and amechanism to detect them must be provided. We compute the optimal periodin order to minimize the waste.In the second part of the thesis we address the energy consumptionchallenge.The speed scaling technique consists in diminishing the voltage of theprocessor, hence diminishing its execution speed. Unfortunately, it waspointed out that DVFS increases the probability of failures. In thiscontext, we consider the speed scaling technique coupled withreliability-increasing techniques such as re-execution, replication orcheckpointing. For these different problems, we propose variousalgorithms whose efficiency is shown either through thoroughsimulations, or approximation results relatively to the optimalsolution. Finally, we consider the different energetic costs involved inperiodic coordinated checkpointing and compute the optimal period tominimize energy consumption, as we did for execution time

APA, Harvard, Vancouver, ISO, and other styles

46

Rough, Justin, and mikewood@deakin edu au. "A Platform for reliable computing on clusters using group communications." Deakin University. School of Computing and Mathematics, 2001. http://tux.lib.deakin.edu.au./adt-VDU/public/adt-VDU20060412.141015.

Full text

Abstract:

Shared clusters represent an excellent platform for the execution of parallel applications given their low price/performance ratio and the presence of cluster infrastructure in many organisations. The focus of recent research efforts are on parallelism management, transport and efficient access to resources, and making clusters easy to use. In this thesis, we examine reliable parallel computing on clusters. The aim of this research is to demonstrate the feasibility of developing an operating system facility providing transport fault tolerance using existing, enhanced and newly built operating system services for supporting parallel applications. In particular, we use existing process duplication and process migration services, and synthesise a group communications facility for use in a transparent checkpointing facility. This research is carried out using the methods of experimental computer science. To provide a foundation for the synthesis of the group communications and checkpointing facilities, we survey and review related work in both fields. For group communications, we examine the V Distributed System, the x-kernel and Psync, the ISIS Toolkit, and Horus. We identify a need for services that consider the placement of processes on computers in the cluster. For Checkpointing, we examine Manetho, KeyKOS, libckpt, and Diskless Checkpointing. We observe the use of remote computer memories for storing checkpoints, and the use of copy-on-write mechanisms to reduce the time to create a checkpoint of a process. We propose a group communications facility providing two sets of services: user-oriented services and system-oriented services. User-oriented services provide transparency and target application. System-oriented services supplement the user-oriented services for supporting other operating systems services and do not provide transparency. Additional flexibility is achieved by providing delivery and ordering semantics independently. An operating system facility providing transparent checkpointing is synthesised using coordinated checkpointing. To ensure a consistent set of checkpoints are generated by the facility, instead of blindly blocking the processes of a parallel application, only non-deterministic events are blocked. This allows the processes of the parallel application to continue execution during the checkpoint operation. Checkpoints are created by adapting process duplication mechanisms, and checkpoint data is transferred to remote computer memories and disk for storage using the mechanisms of process migration. The services of the group communications facility are used to coordinate the checkpoint operation, and to transport checkpoint data to remote computer memories and disk. Both the group communications facility and the checkpointing facility have been implemented in the GENESIS cluster operating system and provide proof-of-concept. GENESIS uses a microkernel and client-server based operating system architecture, and is demonstrated to provide an appropriate environment for the development of these facilities. We design a number of experiments to test the performance of both the group communications facility and checkpointing facility, and to provide proof-of-performance. We present our approach to testing, the challenges raised in testing the facilities, and how we overcome them. For group communications, we examine the performance of a number of delivery semantics. Good speed-ups are observed and system-oriented group communication services are shown to provide significant performance advantages over user-oriented semantics in the presence of packet loss. For checkpointing, we examine the scalability of the facility given different levels of resource usage and a variable number of computers. Low overheads are observed for checkpointing a parallel application. It is made clear by this research that the microkernel and client-server based cluster operating system provide an ideal environment for the development of a high performance group communications facility and a transparent checkpointing facility for generating a platform for reliable parallel computing on clusters.

APA, Harvard, Vancouver, ISO, and other styles

47

Dhoke, Aditya Anil. "On Partial Aborts and Reducing Validation Costs in Fault-tolerant Distributed Transactional Memory." Thesis, Virginia Tech, 2013. http://hdl.handle.net/10919/23890.

Full text

Abstract:

Distributed Transactional Memory (DTM) is an emerging synchronization abstraction thatpromises to alleviate the scalability, programmability, and composability challenges of lock-based distributed synchronization. With DTM, programmers organize code that read/writeshared memory objects, both local and remote, as memory transactions. An underlying DTMframework guarantees atomicity, isolation, and consistency properties for those transactionsthrough speculative concurrency control. In DTM, restarting an aborted transaction from the beginning can degrade performance astransactional conflicts may have occurred in the later part of the transaction, wasting work.The partial abort method alleviates this difficulty by enabling a transaction to be rolled backto the point where objects in the transaction's read-set and write-set are still consistent.In this thesis, we present protocols for supporting partial aborts in QR-DTM, a fault-tolerant DTM that uses quorum protocols for distributed concurrency control in the presence offailures. We focus on two partial abort models: closed nesting, which allows transactions to be nested and inner transactions to be rolled back without rolling back outer transactions;and checkpointing, which allows the transaction state to be saved in checkpoints throughout execution and transactions to be rolled back to those checkpoints. We present protocols that support these partial abort models in QR-DTM, called QR-CN and QR-CHK. We implemented these protocols and conducted experimental studies using macro-benchmarks(e.g., distributed versions of STAMP benchmark), and micro-benchmarks (e.g., distributed data structures). Our studies reveal that QR-CN improves throughput by as much as 101% over flat nesting in specific cases, with an average improvement of 53%. We also develop QR-ACN, a framework that automatically decomposes programmer-writtentransactions into closed nested transactions, at run-time, to improve performance. The composition of a closed nested transaction depends on the contention of objects, which can change at run-time depending upon the workload at hand. Our implementation and experimental studies reveal that QR-ACN consistently outperforms flat nesting by an averageof 51% on benchmarks including TPC-C. False conflicts occur when high-level operations, even though semantically independent, traverse the same set of objects during transaction execution. Such conflicts can lead torepeated aborts, increasing transaction execution time and degrading performance, which can be significant in DTM, since transaction execution also includes network communication. ii We consider the approach of reducing validation cost for resolving false conflicts. We presentthree protocols for reducing validation cost in DTM. Our first protocol, QR-ON, incorporatesthe open nesting model into QR-DTM. Open nesting allows inner-nested transactions tocommit independently of their parent transaction, releasing objects in the transaction read-set and write-set early, minimizing aborts due to false conflicts. We then present QR-OON,in which open-nested transactions commit asynchronously so that subsequent transactionscan proceed without waiting for the commit of previous transactions. Finally, we presentan early release methodology, QR-ER, in which objects that do not affect the final state ofthe shared data are dropped from the transaction's read-set, which avoids false conflicts andreduces communication costs. Our implementation and experimental studies revealed that QR-OON outperforms QR-ON by up to 43%, and that QR-ER outperforms QR-ON and QR-OON by up to 10% on micro- and macro-benchmarks.
Master of Science

APA, Harvard, Vancouver, ISO, and other styles

48

Walther, Andrea. "Program Reversal Schedules for Single- and Multi-processor Machines." Doctoral thesis, Technische Universität Dresden, 1999. https://tud.qucosa.de/id/qucosa%3A24113.

Full text

Abstract:

Bei der Berechnung von Adjungierten, zum Debuggen und für ähnliche Anwendungen kann man die Umkehr der entsprechenden Programmauswertung verwenden. Der einfachste Ansatz, nämlich das Mitschreiben einer kompletten Mitschrift der Vorwärtsrechnung, welche anschließend rückwärts gelesen wird, verursacht einen enormen Speicherplatzbedarf. Als Alternative dazu kann man die Mitschrift auch stückweise erzeugen, indem die Programmauswertung von passend gewählten Checkpoints wiederholt gestartet wird. Das Ziel der Arbeit ist die Minimierung des von der Programmumkehr verursachten Zeit- und Speicherplatzbedarfs. Dieser wird gemessen in Auswertungswiederholungen bzw. verwendeten Checkpoints. Optimale Umkehrschemata werden für Ein- und Mehr-Schritt-Verfahren entwickelt, welche zum Beispiel bei der Diskretisierung einer gewöhnlichen Differentialgleichung Verwendung finden. Desweiteren erfolgte die Entwicklung von parallelen Umkehrschemata, d. h. mehrere Prozessoren werden für die Umkehrung der Programmauswertung eingesetzt. Diese zusätzlichen Prozessoren dienen dazu, die wiederholten Berechnungen des Programms zu parallelisieren, so daß ein Prozessor die Rückwartsrechnung ohne Unterbrechung durchführen kann. Sowohl für die seriellen als auch für die parallelen Umkehrschemata wurde gezeigt, daß die Länge der umzukehrenden Programmauswertung exponentiell in Abhängigkeit von der Zahl der verwendeten Checkpoints und der Zahl der wiederholten Auswertungen bzw. verwendeten Prozessoren wächst.
For adjoint calculations, parameter estimation, and similar purposes one may need to reverse the execution of a computer program. The simplest option is to record a complete execution log and then to read it backwards. This requires massive amounts of storage. Instead one may generate the execution log piecewise by restarting the ``forward'' calculation repeatedly from suitably placed checkpoints. The basic structure of the resulting reversal schedules is illustrated. Various strategies are analysed with respect to the resulting temporal and spatial complexity on serial and parallel machines. For serial machines known optimal compromises between operations count and memory requirement are explained, and they are extended to more general situations. For program execution reversal on multi-processors the new challenges and demands on an optimal reversal schedule are described. We present parallel reversal schedules that are provably optimal with regards to the number of concurrent processes and the total amount of memory required.

APA, Harvard, Vancouver, ISO, and other styles

49

Lu, Peng. "Resilire: Achieving High Availability Through Virtual Machine Live Migration." Diss., Virginia Tech, 2013. http://hdl.handle.net/10919/25434.

Full text

Abstract:

High availability is a critical feature of data centers, cloud, and cluster computing environments. Replication is a classical approach to increase service availability by providing redundancy. However, traditional replication methods are increasingly unattractive for deployment due to several limitations such as application-level non-transparency, non-isolation of applications (causing security vulnerabilities), complex system management, and high cost. Virtualization overcomes these limitations through another layer of abstraction, and provides high availability through virtual machine (VM) live migration: a guest VM image running on a primary host is transparently check-pointed and migrated, usually at a high frequency, to a backup host, without pausing the VM; the VM is resumed from the latest checkpoint on the backup when a failure occurs. A virtual cluster (VC) generalizes the VM concept for distributed applications and systems: a VC is a set of multiple VMs deployed on different physical machines connected by a virtual network. This dissertation presents a set of VM live migration techniques, their implementations in the Xen hypervisor and Linux operating system kernel, and experimental studies conducted using benchmarks (e.g., SPEC, NPB, Sysbench) and production applications (e.g., Apache webserver, SPECweb). We first present a technique for reducing VM migration downtimes called FGBI. FGBI reduces the dirty memory updates that must be migrated during each migration epoch by tracking memory at block granularity. Additionally, it determines memory blocks with identical content and shares them to reduce the increased memory overheads due to block-level tracking granularity, and uses a hybrid compression mechanism on the dirty blocks to reduce the migration traffic. We implement FGBI in the Xen hypervisor and conduct experimental studies, which reveal that the technique reduces the downtime by 77% and 45% over competitors including LLM and Remus, respectively, with a performance overhead of 13%. We then present a lightweight, globally consistent checkpointing mechanism for virtual cluster, called VPC, which checkpoints the VC for immediate restoration after (one or more) VM failures. VPC predicts the checkpoint-caused page faults during each checkpointing interval, in order to implement a lightweight checkpointing approach for the entire VC. Additionally, it uses a globally consistent checkpointing algorithm, which preserves the global consistency of the VMs' execution and communication states, and only saves the updated memory pages during each checkpointing interval. Our Xen-based implementation and experimental studies reveal that VPC reduces the solo VM downtime by as much as 45% and reduces the entire VC downtime by as much as 50% over competitors including VNsnap, with a memory overhead of 9% and performance overhead of 16%. The dissertation's third contribution is a VM resumption mechanism, called VMresume, which restores a VM from a (potentially large) checkpoint on slow-access storage in a fast and efficient way. VMresume predicts and preloads the memory pages that are most likely to be accessed after the VM's resumption, minimizing otherwise potential performance degradation due to cascading page faults that may occur on VM resumption. Our experimental studies reveal that VM resumption time is reduced by an average of 57% and VM's unusable time is reduced by 73.8% over native Xen's resumption mechanism. Traditional VM live migration mechanisms are based on hypervisors. However, hypervisors are increasingly becoming the source of several major security attacks and flaws. We present a mechanism called HSG-LM that does not involve the hypervisor during live migration. HSG-LM is implemented in the guest OS kernel so that the hypervisor is completely bypassed throughout the entire migration process. The mechanism exploits a hybrid strategy that reaps the benefits of both pre-copy and post-copy migration mechanisms, and uses a speculation mechanism that improves the efficiency of handling post-copy page faults. We modify the Linux kernel and develop a new page fault handler inside the guest OS to implement HSG-LM. Our experimental studies reveal that the technique reduces the downtime by as much as 55%, and reduces the total migration time by as much as 27% over competitors including Xen-based pre-copy, post-copy, and self-migration mechanisms. In a virtual cluster environment, one of the main challenges is to ensure equal utilization of all the available resources while avoiding overloading a subset of machines. We propose an efficient load balancing strategy using VM live migration, called DCbalance. Differently from previous work, DCbalance records the history of mappings to inform future placement decisions, and uses a workload-adaptive live migration algorithm to minimize VM downtime. We improve Xen's original live migration mechanism and implement the DCbalance technique, and conduct experimental studies. Our results reveal that DCbalance reduces the decision generating time by 79%, the downtime by 73%, and the total migration time by 38%, over competitors including the OSVD virtual machine load balancing mechanism and the DLB (Xen-based) dynamic load balancing algorithm. The dissertation's final contribution is a technique for VM live migration in Wide Area Networks (WANs), called FDM. In contrast to live migration in Local Area Networks (LANs), VM migration in WANs involve migrating disk data, besides memory state, because the source and the target machines do not share the same disk service. FDM is a fast and storage-adaptive migration mechanism that transmits both memory state and disk data with short downtime and total migration time. FDM uses page cache to identify data that is duplicated between memory and disk, so as to avoid transmitting the same data unnecessarily. We implement FDM in Xen, targeting different disk formats including raw and Qcow2. Our experimental studies reveal that FDM reduces the downtime by as much as 87%, and reduces the total migration time by as much as 58% over competitors including pre-copy or post-copy disk migration mechanisms and the disk migration mechanism implemented in BlobSeer, a widely used large-scale distributed storage service.
Ph. D.

APA, Harvard, Vancouver, ISO, and other styles

50

Väyrynen, Mikael. "Fault-Tolerant Average Execution Time Optimization for General-Purpose Multi-Processor System-On-Chips." Thesis, Linköping University, Linköping University, Linköping University, Department of Computer and Information Science, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-17705.

Full text

Abstract:

Fault tolerance is due to the semiconductor technology development important, not only for safety-critical systems but also for general-purpose (non-safety critical) systems. However, instead of guaranteeing that deadlines always are met, it is for general-purpose systems important to minimize the average execution time (AET) while ensuring fault tolerance. For a given job and a soft (transient) no-error probability, we define mathematical formulas for AET using voting (active replication), rollback-recovery with checkpointing (RRC) and a combination of these (CRV) where bus communication overhead is included. And, for a given multi-processor system-on-chip (MPSoC), we define integer linear programming (ILP) models that minimize the AET including bus communication overhead when: (1) selecting the number of checkpoints when using RRC or a combination where RRC is included, (2) finding the number of processors and job-to-processor assignment when using voting or a combination where voting is used, and (3) defining fault tolerance scheme (voting, RRC or CRV) per job and defining its usage for each job. Experiments demonstrate significant savings in AET.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Checkpointing'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles