¿Es adecuado un sistema rápido pero poco robusto?¿Es adecuado un sistema disponible pero lento? Estas dos cuestiones representan la importancia de prestaciones y disponibilidad en clusters de computadores. Esta tesis se enmarca en el estudio de la relación entre prestaciones y disponibilidad cuando un cluster de computadores basado en el modelo de paso de mensajes, usa un protocolo de tolerancia a fallos basado en rollback-recovery con log de mensajes pesimista. Esta relación también es conocida como performability. Los principales factores que influyen en la performability cuando se usa la arquitectura de tolerancia a fallos RADIC son identificados y estudiados. Los factores fundamentales son la latencia de envío de mensajes que se incrementa cuando se usa el log pesimista, que implica una perdida de prestaciones, como también la replicación de los datos redundantes (checkpoint y log) necesaria para el incremento de la disponibilidad en RADIC y el cambio de la distribución de procesos por nodo causada por los fallos, que pueden causar degradación de las prestaciones así como las paradas por mantenimiento preventivo. Para tratar estos problemas se proponen alternativas de diseño basadas en análisis de la performability. La pérdida de prestaciones causada por el log y la replicación ha sido mitigada usando la técnica de pipeline. El cambio en la distribución de procesos por nodo puede ser evitado o restaurada usando un mecanismo flexible y transparente de redundancia dinámica que ha sido propuesto, que permite inserción dinámica de nodos spare o de repuesto. Los resultados obtenidos demuestran que las contribuciones presentadas son capaces de mejorar la performability de un cluster de computadores cuando se usa una solución de tolerancia a fallos como RADIC. / Is a fast but fragile system good? Is an available but slow system good? These two questions demonstrate the importance of performance and availability in computer clusters. This thesis addresses issues correlated to performance and availability when a rollback- recovery pessimistic message log based fault tolerance protocol is applied into a computer cluster based on the message-passing model. Such a correlation is also known as performability. The root factors influencing the performability when using the RADIC (Redundant Array of Distributed Independent Fault Tolerance Controllers) fault tolerance architecture are raised and studied. Factors include the message delivery latency, which increases when using pessimistic logging causing performance overhead, as also in the redundant data (logs and checkpoints) replication needed to increase availability in RADIC and the process per node distribution changed by faults, which may cause performance degradation and preventive maintenance stops. In order to face these problems some alternatives are presented based on a performability analysis. Using a pipeline approach the performance overhead of message logging and the redundant data replication were mitigated. Changes in the process per node distribution can be avoided or restored using the flexible and transparent mechanism for dynamic redundancy proposed, or using a dynamic insertion of spare or replacement nodes. The obtained results show that the presented contributions could improve the performability of a computer cluster when using a fault tolerance solution such as RADIC.

Actualmente, los clústeres de PCs están considerados como una alternativa eficiente a la hora de construir supercomputadores en los que miles de nodos de computación se conectan mediante una red de interconexión. La red de interconexión tiene que ser diseñada cuidadosamente, puesto que tiene una gran influencia sobre las prestaciones globales del sistema. Dos de los principales parámetros de diseño de las redes de interconexión son la topología y el encaminamiento. La topología define la interconexión de los elementos de la red entre sí, y entre éstos y los nodos de computación. Por su parte, el encaminamiento define los caminos que siguen los paquetes a través de la red. Las prestaciones han sido tradicionalmente la principal métrica a la hora de evaluar las redes de interconexión. Sin embargo, hoy en día hay que considerar dos métricas adicionales: el coste y la tolerancia a fallos. Las redes de interconexión además de escalar en prestaciones también deben hacerlo en coste. Es decir, no sólo tienen que mantener su productividad conforme aumenta el tamaño de la red, sino que tienen que hacerlo sin incrementar sobremanera su coste. Por otra parte, conforme se incrementa el número de nodos en las máquinas de tipo clúster, la red de interconexión debe crecer en concordancia. Este incremento en el número de elementos de la red de interconexión aumenta la probabilidad de aparición de fallos, y por lo tanto, la tolerancia a fallos es prácticamente obligatoria para las redes de interconexión actuales. Esta tesis se centra en la topología fat-tree, ya que es una de las topologías más comúnmente usadas en los clústeres. El objetivo de esta tesis es aprovechar sus características particulares para proporcionar tolerancia a fallos y un algoritmo de encaminamiento capaz de equilibrar la carga de la red proporcionando una buena solución de compromiso entre las prestaciones y el coste. / Gómez Requena, C. (2010). Low-Memory Techniques for Routing and Fault-Tolerance on the Fat-Tree Topology [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/8856

Los sistemas informáticos se encuentran presentes en muchos ámbitos, desde los relacionados con la industria hasta el hogar. Cada vez con más frecuencia, uno de los requisitos principales a la hora de diseñar sistemas informáticos es que presenten un alto grado de confiabilidad, especialmente aquellos considerados como críticos, ya que su mal funcionamiento puede poner el peligro la integridad de las personas o puede ocasionar grandes pérdidas económicas. Además, la confiabilidad también puede ser un factor importante en su expansión y competitividad en el mercado. La confiabilidad permite al usuario depositar una confianza justificada en el funcionamiento del producto y debe ser evaluada antes de su fase operacional mediante la verificación y validación del comportamiento del sistema según el servicio especificado tanto en condiciones normales como en presencia de fallos. Sin embargo la tasa de fallos en un sistema informático suele ser baja, siendo necesario recurrir a técnicas de validación experimental como la Inyección de Fallos que aceleran la validación mediante la introducción deliberada y controlada de fallos en el sistema. En general, el efecto de los fallos físicos en los semiconductores actuales, donde el incremento de la frecuencia de funcionamiento y la densidad de integración son notables, es más importante que el observado con tecnologías menos avanzadas. Ya no es justificable el asumir que un fallo simple sólo genera un error simple, siendo necesario validar el sistema ante errores múltiples causados no sólo por fallos localizados en memoria, sino también en la lógica combinacional o en soldaduras y metalizaciones, acrecentados estos últimos por la reducción de la distancia entre pistas. Existen diversas técnicas y herramientas de inyección de fallos, entre ellas, la Inyección física a nivel de pin. Una de sus principales ventajas es su aplicación externa, no generando sobrecarga adicional en el sistema o perturbando la ejecución normal de sus tar / Blanc Clavero, S. (2004). Validación de la arquitectura TTA mediante inyección física de fallos a nivel de PIN [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/2344

Para beneficiarse de una reducción en la latencia así como disminuir tanto el consumo como el coste, el número óptimo de puertos de un conmutador ha ido aumentando a lo largo del tiempo. Sin embargo, las arquitecturas tradicionales se han quedado atrás bien por bajo rendimiento o bien por problemas de escalabilidad con el número de puertos. En esta Tesis se propone una nueva arquitectura de conmutador válida para conmutadores de elevado grado llamada Partitioned Crossbar Input Queued (PCIQ). Esta arquitectura resuelve el problema de los excesivos requerimientos de memoria en el diseño de arquitecturas de elevado grado. Además PCIQ define una nueva familia de arquitecturas de conmutador. PCIQ se basa en un particionado inteligente del crossbar, dividiéndolo en sub-crossbars, requiriendo menos recursos de memoria que las otras propuestas para conmutadores de elevado grado y que consigue una mayor eficiencia debido en parte a un incremento en la eficiencia de los árbitros empleados en el diseño. En este sentido, PCIQ emplea dos árbitros con prioridad rotativa (uno para cada sub-crossbar) que presentan un coste lineal y una respuesta en el tiempo logarítmica conforme aumenta el número de puertos del conmutador. Además PCIQ tiene un coste (medido en términos de requerimientos de memoria, complejidad del crossbar y complejidad en el arbitraje) similar o incluso menor que organizaciones básicas como CIOQ. No obstante PCIQ es capaz de conseguir máxima eficiencia para distribuciones de tráfico uniforme. El bloqueo por paquete al principio de cola (o HOL en inglés) reduce dramáticamente el rendimiento del conmutador. Las soluciones tradicionales para eliminar el bloqueo por HOL no son escalables con el número de puertos o requieren arquitecturas complejas. En esta Tesis se propone una técnica de control de la congestión que elimina el bloqueo por HOL llamada RECN-IQ. RECN-IQ está diseñada para conmutadores con memorias sólo a la entrada y es una técnica altamente eficiente / Mora Porta, G. (2009). High-performance architectures for high-radix switches [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/4335

Los procesadores superescalares actuales utilizan un reorder buffer (ROB) para contabilizar las instrucciones en vuelo. El ROB se implementa como una cola FIFO first in first out en la que las instrucciones se insertan en orden de programa después de ser decodificadas, y de la que se extraen también en orden de programa en la etapa commit. El uso de esta estructura proporciona un soporte simple para la especulación, las excepciones precisas y la reclamación de registros. Sin embargo, el hecho de retirar instrucciones en orden puede degradar las prestaciones si una operación de alta latencia está bloqueando la cabecera del ROB. Varias propuestas se han publicado atacando este problema. La mayoría utiliza retirada de instrucciones fuera de orden de forma especulativa, requiriendo almacenar puntos de recuperación (checkpoints) para restaurar un estado válido del procesador ante un fallo de especulación. Normalmente, los checkpoints necesitan implementarse con estructuras hardware costosas, y además requieren un crecimiento de otras estructuras del procesador, lo cual a su vez puede impactar en el tiempo de ciclo de reloj. Este problema afecta a muchos tipos de procesadores actuales, independientemente del número de hilos hardware (threads) y del número de núcleos de cómputo (cores) que incluyan. Esta tesis abarca el estudio de la retirada no especulativa de instrucciones fuera de orden en procesadores superescalares, multithread y multicore. / Ubal Tena, R. (2010). Out-of-Order Retirement of Instructions in Superscalar, Multithreaded, and Multicore Processors [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/8535

Actualmente, los clusters de PC son un alternativa rentable a los computadores paralelos. En estos sistemas, miles de componentes (procesadores y/o discos duros) se conectan a través de redes de interconexión de altas prestaciones. Entre las tecnologías de red actualmente disponibles para construir clusters, InfiniBand (IBA) ha emergido como un nuevo estándar de interconexión para clusters. De hecho, ha sido adoptado por muchos de los sistemas más potentes construidos actualmente (lista top500). A medida que el número de nodos aumenta en estos sistemas, la red de interconexión también crece. Junto con el aumento del número de componentes la probabilidad de averías aumenta dramáticamente, y así, la tolerancia a fallos en el sistema en general, y de la red de interconexión en particular, se convierte en una necesidad. Desafortunadamente, la mayor parte de las estrategias de encaminamiento tolerantes a fallos propuestas para los computadores masivamente paralelos no pueden ser aplicadas porque el encaminamiento y las transiciones de canal virtual son deterministas en IBA, lo que impide que los paquetes eviten los fallos. Por lo tanto, son necesarias nuevas estrategias para tolerar fallos. Por ello, esta tesis se centra en proporcionar los niveles adecuados de tolerancia a fallos a los clusters de PC, y en particular a las redes IBA. En esta tesis proponemos y evaluamos varios mecanismos adecuados para las redes de interconexión para clusters. El primer mecanismo para proporcionar tolerancia a fallos en IBA (al que nos referimos como encaminamiento tolerante a fallos basado en transiciones; TFTR) consiste en usar varias rutas disjuntas entre cada par de nodos origen-destino y seleccionar la ruta apropiada en el nodo fuente usando el mecanismo APM proporcionado por IBA. Consiste en migrar las rutas afectadas por el fallo a las rutas alternativas sin fallos. Sin embargo, con este fin, es necesario un algoritmo eficiente de encaminamiento capaz de proporcionar suficientes / Montañana Aliaga, JM. (2008). Efficient mechanisms to provide fault tolerance in interconnection networks for pc clusters [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/2603

Cache coherence protocols based on tokens can provide low latency without relying on non-scalable interconnects thanks to the use of efficient requests that are unordered. However, when these unordered requests contend for the same memory block, they may cause protocols races. To resolve the races and ensure the completion of all the cache misses, token protocols use a starvation prevention mechanism that is inefficient and non-scalable in terms of required storage structures and generated traffic. Besides, token protocols use non-silent invalidations which increase the latency of write misses proportionally to the system size. All these problems make token protocols non-scalable. To overcome the main problems of token protocols and increase their scalability, we propose a new starvation prevention mechanism named Priority Requests. This mechanism resolves contention by an efficient, elegant, and flexible method based on ordered requests. Furthermore, thanks to Priority Requests, efficient techniques can be applied to limit the storage requirements of the starvation prevention mechanism, to reduce the total traffic generated for managing protocol races, and to reduce the latency of write misses. Thus, the main problems of token protocols can be solved, which, in turn, contributes to wide their efficiency and scalability. / Cuesta Sáez, BA. (2009). Efficient techniques to provide scalability for token-based cache coherence protocols [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/6024

Las Redes Inalámbricas de Sensores (RIS) gozan de un gran auge hoy en día, habiendo sido identificadas como una de las tecnologías más prometedoras por diversos analistas tecnológicos y revistas especializadas, debido a que dan respuesta a las exigencias actuales referentes al establecimiento de redes que cubran necesidades de comunicación de forma flexible -en tiempo y espacio- y autónoma -autoconfiguración e independencia de una estructura fija-. La posibilidad de implementar dispositivos de bajo coste y elevada duración capaces de obtener información del entorno y reenviarla de forma inalámbrica a un centro de coordinación ofrece posibilidades inimaginables en multitud de aplicaciones. En la mayoría de las aplicaciones se pretende que los nodos no requieran mantenimiento, explotando el concepto de nodos de "usar y tirar", puesto que una vez desplegados no son recuperables. En este entorno, los mayores desafíos se encuentran en minimizar dos factores fundamentales: coste y consumo, maximizando el tiempo de servicio. En los últimos años se han propuesto numerosos protocolos para RIS. Sin embargo, la mayoría de estas propuestas, o bien realizan asunciones poco realistas, o bien resultan poco escalables, lo cual se traduce en aproximaciones poco prácticas. Por otro lado, hasta la fecha se han obviado características deseables como tolerancia a fallos, seguridad y acotación de tiempos en las comunicaciones, generalmente no consideradas en la inmensa mayoría de los protocolos existentes, y cuando lo son, se obtienen sacrificando la eficiencia energética. En la presente tesis se ha propuesto una novedosa solución integral orientada principalmente a reducir el consumo de energía. La nueva arquitectura denominada EDETA (Energy-efficient aDaptative hiErarchical and robusT Architecture) es además escalable, apropiada tanto para RIS homogéneas como heterogéneas -cada vez con mayor auge-, auto-configurable, soporta de forma transparente múltiples sumideros, y proporciona características como tolerancia a fallos y tiempos acotados, sin degradar las prestaciones de la red. La arquitectura propuesta está basada en una jerarquía de dos niveles, el nivel inferior basado en clústeres, gobernado por un protocolo interno del clúster denominado Intra- Cluster-Communication y el nivel superior formado por un árbol dinámico de nodos líderes de clúster que ejecutan un protocolo entre clústeres denominado Inter-Cluster-Routing. / Capella Hernández, JV. (2010). Redes inalámbricas de sensores: Una nueva arquitectura eficiente y robusta basada en jerarquía dinámica de grupos [Tesis doctoral]. Editorial Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/8417

Actualmente, las tecnologías CMOS submicrónicas son básicas para el desarrollo de los modernos sistemas basados en computadores, cuyo uso simplifica enormemente nuestra vida diaria en una gran variedad de entornos, como el gobierno, comercio y banca electrónicos, y el transporte terrestre y aeroespacial. La continua reducción del tamaño de los transistores ha permitido reducir su consumo y aumentar su frecuencia de funcionamiento, obteniendo por ello un mayor rendimiento global. Sin embargo, estas mismas características que mejoran el rendimiento del sistema, afectan negativamente a su confiabilidad. El uso de transistores de tamaño reducido, bajo consumo y alta velocidad, está incrementando la diversidad de fallos que pueden afectar al sistema y su probabilidad de aparición. Por lo tanto, existe un gran interés en desarrollar nuevas y eficientes técnicas para evaluar la confiabilidad, en presencia de fallos, de sistemas fabricados mediante tecnologías submicrónicas. Este problema puede abordarse por medio de la introducción deliberada de fallos en el sistema, técnica conocida como inyección de fallos. En este contexto, la inyección basada en modelos resulta muy interesante, ya que permite evaluar la confiabilidad del sistema en las primeras etapas de su ciclo de desarrollo, reduciendo por tanto el coste asociado a la corrección de errores. Sin embargo, el tiempo de simulación de modelos grandes y complejos imposibilita su aplicación en un gran número de ocasiones. Esta tesis se centra en el uso de dispositivos lógicos programables de tipo FPGA (Field-Programmable Gate Arrays) para acelerar los experimentos de inyección de fallos basados en simulación por medio de su implementación en hardware reconfigurable. Para ello, se extiende la investigación existente en inyección de fallos basada en FPGA en dos direcciones distintas: i) se realiza un estudio de las tecnologías submicrónicas existentes para obtener un conjunto representativo de modelos de fallos transitorios / Andrés Martínez, DD. (2007). Speeding-up model-based fault injection of deep-submicron CMOS fault models through dynamic and partially reconfigurable FPGAS [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/1943

La inyección de fallos es una técnica utilizada para la validación experimental de Sistemas Tolerantes a Fallos. Se distinguen tres grandes categorías: inyección de fallos física (denominada también physical fault injection o hardware implemented fault injection), inyección de fallos implementada por software (en inglés software implemented fault injection) e inyección de fallos basada en simulación. Una de las que más auge está teniendo últimamente es la inyección de fallos basada en simulación, y en particular la inyección de fallos basada en VHDL. Las razones del uso de este lenguaje se pueden resumir en: " Es un lenguaje estándar ampliamente utilizado en el diseño digital actual. " Permite describir el sistema en distintos niveles de abstracción. " Algunos elementos de su semántica pueden ser utilizados en la inyección de fallos. Para realizar la inyección de fallos basada en VHDL, diferentes autores han propuesto tres tipos de técnicas. La primera está basada en la utilización de los comandos del simulador para modificar los valores de las señales y variables del modelo. La segunda se basa en la modificación del código, insertando perturbadores en el modelo o creando mutantes de componentes ya existentes. La tercera técnica se basa en la ampliación de los tipos del lenguaje y en la modificación de las funciones del simulador VHDL. Actualmente, ha surgido otra tendencia de la inyección de fallos basada en VHDL, denominada genéricamente emulación de fallos. La emulación añade ciertos componentes al modelo (inyectores, que suelen ser perturbadores o mutantes, disparadores de la inyección, recolectores de datos, etc.). El modelo junto con los nuevos componentes son sintetizados en una FPGA, que es donde se realiza la inyección. Con la introducción cada vez mayor de sistemas tolerantes a fallos en aplicaciones críticas, su validación se está convirtiendo en uno de los puntos clave para su uso. / Gracia Morán, J. (2004). Validación por inyección de fallos en VHDL de la arquitectura TTA [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/7526