Fault Tolerance in Multicore Clusters. Techniques to Balance Performance and Dependability

Abstract

En Computación de Altas Prestaciones (HPC), con el objetivo de aumentar las prestaciones se ha ido incrementando el número de recursos de cómputo. Con el aumento del tamaño de las aplicaciones ejecutadas en computadores de altas prestaciones, también ha aumentado el número de interrupciones como consecuencia de fallos de hardware. La disminución en el tiempo medio entre fallos (MTBF) en los sistemas de cómputo actuales, fomenta la propuesta de soluciones de tolerancia a fallos apropiadas que permitan la finalización correcta de aplicaciones paralelas afectadas por fallos de componentes físicos. Por lo tanto, las técnicas de tolerancia a fallos son cruciales para aumentar la disponibilidad en computadores de altas prestaciones. Cuando son ejecutadas aplicaciones paralelas en computadores de altas prestaciones, los principales objetivos normalmente son: lograr una aceleración (speedup) cercana a la lineal, utilización eficiente de recursos y finalización correcta de las ejecuciones. Por lo tanto, los sistemas paralelos se enfrentan a un problema multiobjetivo que consiste en incrementar las prestaciones mientras se utilizan técnicas de tolerancia a fallos; dicha combinación en la cual se consideran prestaciones y confiabilidad se denomina en la literatura Performability. Las estrategias de tolerancia a fallos basadas en rollback-recovery han sido extensamente utilizadas en computación de altas prestaciones. Estas estrategias se basan en salvar el estado de la aplicación y cuando ocurren fallos las aplicaciones pueden volver atrás y re-ejecutar desde el último estado guardado (checkpoint). Estas estrategias introducen una sobrecarga durante la ejecución de las aplicaciones en aspectos que afectan a las prestaciones, tales como una sobrecarga en el tiempo de cómputo, uso de recursos, etc. Las estrategias de checkpoint no coordinadas permiten a los procesos salvar sus estados independientemente. Cuando estas estrategias se combinan con mecanismos de log de mensajes, se evitan problemas como el efecto dominó o la aparición de mensajes huérfanos. Las técnicas de log de mensajes son responsables de la mayor parte de la sobrecarga introducida durante ejecuciones libre de fallos. En esta tesis nos hemos centrado en disminuir el impacto de las técnicas de log de mensajes considerando tanto el impacto en las ejecuciones libres de fallos así en como en el tiempo de recuperación. Una de las contribuciones de esta tesis es un mecanismo de log denominado Hybrid Message Pessimistic Logging (HMPL). Este protocolo se enfoca en combinar las características de rápida recuperación de los mecanismos de log pesimistas basados en el receptor con la baja sobrecarga que introducen los mecanismos de log basados en el emisor en ejecuciones libres de fallos. Sin perder las ventajas de un sistema de log de mensajes pesimista basado en el receptor, el HMPL permite a las aplicaciones paralelas continuar con su ejecución inclusive cuando un mensaje no ha sido guardado totalmente en el log del receptor, y de esta manera se reducen las sobrecargas en comparación con los mecanismos de log pesimistas basados en el receptor. Para poder garantizar que no se pierde ningún mensaje, un mecanismo de log pesimista basado en el emisor es utilizado para guardar temporalmente mensajes, mientras los receptores se encargan de guardar totalmente el mensaje recibido. Además proponemos otras estrategias que permiten incrementar la performability de aplicaciones paralelas. Una estrategia consiste en evitar la degradación que ocurre como consecuencia de un fallo mediante la utilización automática de nodos de repuesto (Spare Nodes) para reemplazar nodos que han fallado. Teniendo en cuenta que las tareas de tolerancia a fallos son gestionadas por un middleware transparente al usuario, hemos propuesto una metodología que permite determinar configuraciones apropiadas de las tareas de tolerancia a fallos para disminuir la sobrecarga en ejecuciones libres de fallos. Esta metodología se basa en analizar el impacto del mecanismo de log de mensajes utilizado y configurar las ejecuciones paralelas disminuyendo la perturbación introducida. Además, hemos desarrollado una metodología para la ejecución de aplicaciones pertenecientes al paradigma Single Problem Multiple Data (SPMD). Dicha metodología permite obtener el máximo speedup teniendo en cuenta un umbral de eficiencia computacional definida y considerando el impacto de las tareas de un mecanismo de log de mensajes. Los resultados experimentales han mostrado que mediante la caracterización del impacto del log de mensajes en el cómputo y en las comunicaciones, es posible seleccionar un número de procesos o cores de cómputo que permitan hacer un uso eficiente de los recursos mientras se aumenta la performability.

In High Performance Computing (HPC) the demand for more performance is satisfied by increasing the number of components. With the growing scale of HPC applications has came an increase in the number of interruptions as a consequence of hardware failures. The remarkable decrease of Mean Times Between Failures (MTBF) in current systems encourages the research of suitable fault tolerance solutions which makes it possible to guarantee the successful completion of parallel applications. Therefore, fault tolerance mechanisms are a valuable feature to provide high availability in HPC clusters. When running parallel applications on HPC clusters the prior objectives usually are: almost linear speedup, efficient resources utilization, scalability and successful completion. Hence, parallel applications executions are now facing a multiobjective problem which is focused on improving Performance while giving Fault Tolerance (FT) support; this combination is defined as Performability. A widely used strategy to provide FT support is rollback-recovery, which consists in saving the application state periodically. In the presence of failures, applications resume their executions from the most recent saved state. These FT protocols usually introduce overheads during applications' executions. Uncoordinated checkpoint allows processes to save their states independently. By combining this protocol with message logging, problems such as the domino effect and orphan messages are avoided. Message logging techniques are usually responsible for most of the overhead during failure-free executions in uncoordinated solutions. Considering this fact, in this thesis we focus on lowering the impact of message logging techniques taking into account failure-free executions and recovery times. A contribution of this thesis is a Hybrid Message Pessimistic Logging protocol (HMPL). It focuses on combining the fast recovery feature of pessimistic receiver-based message logging with the low overhead introduced by pessimistic sender-based message logging during failure-free executions. The HMPL aims to reduce the overhead introduced by pessimistic receiver-based approaches by allowing applications to continue normally before a received message is properly saved. In order to guarantee that no message is lost, a pessimistic sender-based logging is used to temporarily save messages while the receiver fully saves its received messages. In this thesis we propose strategies to increase the performability of parallel applications. One approach focuses on avoiding performance degradation when failure occurs by using automatic spare node management to replace failed nodes. Taking into account that the fault tolerance tasks are managed by an user-transparent middleware, we propose a methodology that allows us to determine suitable configurations of these tasks in order to lower overheads in failure-free executions. This methodology is based on analyzing the message log impact and configuring the parallel executions decreasing the introduced disturbance. Another contribution of this thesis is a methodology that allows to obtain the maximum speedup under a defined efficiency threshold, considering the impact of message logging tasks for Single Program Multiple Data (SPMD) applications. Experiments have shown that characterizing the message logging effects in computation and communication, allows us to select a better number of processes or computational cores to be used in order to improve resource utilization while increasing performability.