Fault Tolerance Configuration for Uncoordinated Checkpoints

Abstract

La tendencia general de los computadores paralelos es crecer en complejidad y en número de componentes. La miniaturización y la concentración de dichos elementos es la principal causa de la aparición y aumento de los fallos en estos computadores. Asimismo, para permitir la ejecución correcta de las aplicaciones paralelas, existe la necesidad de proveer soporte y de tolerar fallos en estos entornos. Una estrategia amplamente utilizada es el rollback-recovery, que consiste en guardar periódicamente el estado de la aplicación y, en caso de fallos, reanudar la aplicación desde el último estado guardado. El uso de estos protocolos añade una sobrecarga al tiempo de ejecución de la aplicación. Con el uso de protocolos de checkpoints no coordinados, es fácil estimar el tiempo total de ejecución de una aplicación, así como también la frecuencia en la cual estos checkpoints deben ser guardados. Actualmente, existen modelos precisos para estimar estos tiempos. Sin embargo, el uso de protocolos de checkpoints coordinados, puede no ser la mejor solución para proveer tolerancia a fallos en los computadores paralelos de próxima generación. En otras palabras, el actual paradigma de tolerancia a fallos para computadores paralelos, no es adecuado para los futuros sistemas. Los protocolos de tolerancia a fallos no coordinados permiten que, cada proceso de la aplicación paralela guarde su estado independientemente de los demás procesos; la combinación de estos protocolos con técnicas de log de eventos eliminan los inconvenientes de los protocolos no coordinados, como el efecto domino y la aparición de mensajes huérfanos. Esta combinación representa el paradigma emergente de tolerancia a fallos para aplicaciones paralelas escalables. Actualmente, no hay modelos adecuados para estimar el tiempo de ejecución de aplicaciones paralelas que están siendo protegidas por checkpoints no coordinados. Así como tampoco existen modelos para calcular la frecuencia en que dichos checkpoints deben ser creados. El objetivo de esta tesis es, definir los modelos específicos para cada uno de los paradigmas: el coordinado y el no coordinado. Los modelos proveen una estimación del tiempo total de ejecución de las aplicaciones cuando están protegidas por cualquiera de los dos paradigmas. Además, se propone una metodología para definir el valor de las variables necesarias para calcular el intervalo de checkpoints. La principal motivación de este trabajo es proveer el conocimiento necesario para enfrentar el paradigma emergente de tolerancia a fallos y hacerlo asequible para los usuarios de las aplicaciones paralelas.

Parallel computers are growing in complexity and in number of components. The components miniaturisation and concentration are the major root causes of the failures increasingly seen on these computers. Thus, in order to achieve the execution end, parallel application should use a fault tolerance strategy. A widely used strategy is the rollback-recovery, which consists of saving the application state periodically. In the event of a fault occurring, the application resumes it execution from the most recent saved state. These fault tolerance protocols include an overhead on the parallel application execution. Using a coordinated checkpointing protocol it becomes easy to estimate the application execution time, as well as to calculate the frequency in which checkpoints should be taken. In fact, there are very precise models to estimate the application execution time and the checkpoint interval nowadays. However, the use of the coordinated checkpointing may not be the best solution to provide fault tolerance on the next-generation parallel computers. In other words, the current paradigm of fault tolerance for parallel applications is not suitable for the future parallel computer. Fault tolerance protocols such as uncoordinated checkpointing permits that each process of the parallel application saves its state independently of other processes. The combination of uncoordinated checkpointing with logging of message-passing events avoids the inconvenience of this sort of protocol, such as the domino effect and orphan messages. This is the emergent paradigm of fault tolerance for scalable parallel applications. For instance, there is no model suitable to estimate the execution time of a parallel application protected by uncoordinated checkpointing. As well as there is no convenient model to calculate the frequency in which those checkpoints should be taken. The objective of this thesis is to define suitable models that can be used with each paradigm: the coordinated and the uncoordinated. These models should provide an estimation of the application wall time clock running under each fault tolerance paradigm, as well a methodology to define the value of the variables used to calculate the checkpointing interval. The main motivation of this work is to provide at the same time the knowledge necessary to face the emergent fault tolerance paradigm and make it suitable to be used by parallel applications users.