Durante os últimos anos, a quantidade de dados gerada pelas aplicações cresceu consideravelmente. No entanto, para tornarem-se relevantes estes dados precisam ser processados. Para atender este objetivo, novos modelos de programação para processamento paralelo e distribuído foram propostos. Um exemplo é o modelo MapReduce, o qual foi proposto pela Google. Este modelo, no entanto, possui pontos de falha única (SPOF), os quais podem comprometer a sua execução. Assim, este trabalho apresenta uma nova arquitetura, inspirada pelo Chord, para lidar com os SPOFs do modelo. A avaliação da proposta foi realizada através de modelagem analítica e de testes experimentais. Os resultados mostram a viabilidade de usar a arquitetura proposta para executar o MapReduce. / During the last years, the amount of data generated by applications grew considerably. To become relevant, however, this data should be processed. With this goal, new programming models for parallel and distributed processing were proposed. An example is the MapReduce model, which was proposed by Google. This model, nevertheless, has Single Points of Failure (SPOF), which can compromise the execution of a job. Thus, this work presents a new architecture, inspired by Chord, to avoid the SPOFs on MapReduce. The evaluation was performed through an analytical model and an experimental setup. The results show the feasibility of using the proposed architecture to execute MapReduce jobs.

A constante redução nas dimensões dos transistores foi o principal combustível capaz de manter o crescente desempenho exigido por aplicações. Ao mesmo tempo, as tensões de alimentação dos circuitos também são reduzidas a cada novo nó tecnológico, fazendo com que partículas como nêutrons e partículas alpha, portando quantidades de energia cada vez menores sejam capazes de gerar os chamados soft errors, que impactam diretamente na redução da confiabilidade dos sistemas embarcados atuais. Isto faz com que a implementação de técnicas de tolerância a falhas se tornem praticamente obrigatórias para tecnologias atuais e futuras. Estes mesmos sistemas embarcados, como smartphones, devem apresentar alto poder de processamento, visando atender um crescente conjunto de aplicações de natureza heterogênea, consumindo a mínima potência possível. Nestes sistemas, algumas dessas principais aplicações como codec GSM, cancelamento de eco acústico, processamento de áudio e vídeo apresentam em comum a necessidade de multiplicar matrizes de diferentes dimensões em determinados intervalos de tempo. Pensando nestas demandas, será proposta a arquitetura RA3, cujo objetivo é executar o algoritmo de multiplicação de matrizes em paralelo com a técnica de tolerância a falhas conhecida na literatura como ABFT, visando a aumentar a confiabilidade da mesma. Além disso, a RA3 possui uma estrutura adaptativa que permite que unidades internas como memórias, multiplicadores e somadores sejam ligadas ou desligadas através da aplicação da técnica de power gating em tempo de execução, conforme restrições impostas pela largura da banda de memória, power budgets e deadlines impostos por aplicações de tempo real, visando executar tarefas consumindo a mínima potência possível. Para avaliar as funcionalidades propostas, dois estudos de caso reais são apresentados e o comportamento da arquitetura é avaliado sobre diversos aspectos como desempenho, área, consumo de potência e cobertura de falhas. Finalmente é possível comprovar que a adaptabilidade proposta pela arquitetura RA3 permite que seja encontrada, em diversos cenários, a quantidade exata de recursos necessários para executar determinadas aplicações sem comprometer as restrições impostas principalmente no consumo de potência e por aplicações com deadlines críticos, mantendo ainda altas taxas de cobertura de falhas. / The continuous reduction of transistors’ dimensions was the main drive capable of maintaining the performance increase required by applications. At the same time, supply voltages of the circuits are also reduced with each new technology node, causing particles such as neutrons or alpha particles, even with reduced amounts of energy, to generate so-called soft errors that directly impact on the reliability of embedded systems. This scenario makes the implementation of techniques for fault tolerance mandatory for current and future technologies. Still, embedded systems, such as smartphones, must provide high processing power to execute a growing set of applications of heterogeneous nature, consuming the least possible power. In these systems, applications like GSM codec, acoustic echo cancellation, audio and video processing have in common the need for matrix multiplication operations of different dimensions at certain time intervals. To efficiently support the aforementioned scenario, this dissertation proposes the RA3 architecture whose goal is run the matrix multiplication algorithm in parallel with the fault tolerance technique know in the literature as ABFT, aiming to support software execution with high reliability. Furthermore, the RA3 architecture provides adaptive internal units such as memories, multipliers and adders with adaptive powering on or off by applying power gating at runtime. Runtime power gating enables to meet restrictions imposed by real-time applications or memory bandwidth with minimum power. To evaluate the proposed architecture, two case studies are presented and the behavior of the architecture is evaluated in terms of performance, area, power consumption and fault coverage. Finally, a comprehensive design space exploration shows that the adaptability provided by the RA3 architecture allows the system designer to find, in many scenarios, the exact amount of resources needed to run a set of applications without compromising the restrictions imposed mainly in power consumption and real-time deadlines, while still maintaining a high fault coverage rate.

Hoje em dia, as redes intra chip (NoC) são cada vez mais utilizadas como uma arquitetura de comunicação alternativa para sistemas complexos, pois estas permitem flexibilidade e desempenho da comunicação. Porém, o grande número de interconexões da rede, aliado à diminuição das dimensões dos transistores fabricados nas tecnologias nanométricas, fazem com que a NoC possa ter um grande número de falhas durante sua fabricação, ou por desgaste durante sua vida útil. Sabe-se que, em futuras tecnologias os circuitos integrados terão uma taxa de falhas permanentes de 20 a 30%. Entretanto, mesmo na presença de falhas, é desejável que a NoC permaneça funcionando corretamente. A partir do diagnóstico das falhas, a NoC deve ser capaz de buscar alternativas para manter a comunicação entre os núcleos, evitando os canais e os roteadores com falhas. O objetivo deste trabalho é propor mecanismos adaptativos de proteção contra falhas permanentes. Mesmo quando são adicionados componentes extras para a substituição em SoCs, a ocorrência de falhas permanentes na rede intrachip impede a substituição ou reparo de um componente no sistema intrachip. Portanto a tolerância a falhas na NoC será crucial para reduzir custo de manufatura, e aumentar o rendimento e o tempo de vida do circuito integrado. O mecanismo proposto é capaz de evitar falhas sabendo anteriormente, na fase de teste e diagnóstico, a localização especifica da falha. Portanto, as técnicas se adaptam em cada roteador para evitar as falhas permanentes, sempre buscando manter desempenho, aumentar o rendimento e a confiabilidade do sistema. / Nowadays, networks-on-chip (NoCs) have been used as an alternative communication architecture inside complex system on-chip. They offer better scalability and performance than the traditional bus. However, the growing number of interconnects that have to be inserted using smaller transistors means that NoCs have a growing number of faults, either from manufacturing or due to aging. In future systems-on-chip (SoCs), the fault rate will be around 20 to 30% of the contact and transistors of integrated circuits. Therefore, even in the presence of a fault, it is still desirable that NoCs properly work. The main idea of this work is to implement adaptive mechanisms to protect NoCs against permanent faults. The main advantage of such mechanism is to manage failures based on data from the testing and diagnosing phase. The mechanisms are adapted in each router in order to sustain performance, increasing the system yield and reliability even in the presence of failures. Even if one adds extra blocks for replacement, the occurrence of permanent faults in a NoC might preclude the replacement or repair of a faulty component within the SoC. In such case, fault-tolerant NoCs are able to reduce manufacturing costs, increase yield and the lifetime of the chip.

Orientador: Jacques Wainer / Dissertação (mestrado) - Universidade Estadual de Campinas. Instituto de Computação / Made available in DSpace on 2018-08-04T04:13:24Z (GMT). No. of bitstreams: 1 Aranha_ClausdeCastro_M.pdf: 502058 bytes, checksum: 70f8b4c9b7e6a526ab30528ac5634647 (MD5) Previous issue date: 2004 / Abstract: A planner must be prepared to deal with dynamic characteristics of the system it acts upon. Lack of world knowledge, dynamic changes, actions with non-deterministic results and faults may put the environment in a state different from the one the planner was expecting while performing a task. When this happens, the pre-conditions required for the plan may become false, turning the plan itself invalid and unable to reach the task goals. The problem of recovering from an invalid plan and achieving the task's original goals is called plan repair. Usually, plan repair techniques can be classified as either replanning techniques or conditional/probabilistic planning. Replanning consists of creating a new plan from the point of failure. Replanners are usually robust but too complex for using them in real-time applications. Probabilistic/conditional planners try to generate offline a plan that take into account the system's uncertainties. However, they might be unable to do so if the environment is too complex. In this work we propose a new plan repair technique based on action replacement. Any complex application will usually offer many different ways to achieve the results of any given action, although usually only the most efficient one is taken into account by the planner. In our replacement system, the planner will study the available devices and their relationship to build a replacement table, which lists subplans that can be used to replace a regular action with lessened efficiency (gracious degradation). We analyze the characteristics of the relationship between an action and its replacement subplans, and how to assemble the required table from this information. We describe the algorithm which implements the technique in a general context. We utilize this definition to apply the technique for simulated robots, a biped robot and web services / Mestrado / Inteligencia Artificial / Mestre em Ciência da Computação

[pt] A utilização de tolerância a falhas na construção de aplicações em sistemas distribuídos é, em geral, uma tarefa complexa. Para facilitar esta tarefa, pode-se utilizar um ambiente de desenvolvimento que forneça técnicas padronizadas e ferramentas para o suporte a tolerância a falhas. Com esse objetivo, foi concebido um suporte especializado para a tolerância a falhas. Parte deste suporte foi implementado e adicionado ao ambiente RIO (Reconfigurable interconnectable Objects) O RIO é centrado no conceito de módulos configuráveis que se comunicam por interfaces bem definidas. O suporte a tolerância a falhas é obtido a partir de técnicas baseadas em replicação de módulos de software. Como exemplo, são apresentadas três técnicas de replicação, Replicação Passiva Reserva Quente, Replicação Ativa Competitiva e Replicação Ativa Cíclica, bem como o suporte concebido e implementado para as mesmas. Os detalhes relevantes desta implementação são discutidos e, finalmente, apresenta-se conclusões e sugestões para trabalhos futuros. / [en] The use of fault tolerance in the construction of distributed systems applications is usually a complex task. To make this task easier, a development environment may be used including standard techniques and tools for the support of fault tolerance. With this purpose, a specialized fault tolerance support was concepted. Part of this support was implemented and added to the RIO (Reconfigurable interconnectable Objects) environment. The RIO is based on the concept of configurables modules. Well defined interfaces are used to modules comunication. The fault tolerance support is obtained by software replication based techniques. Three replication techniques examples are presented, Hot Standby Passive Replication, Competitive Active Replication and Ciclic Active Replication, as well as the designed support for them. Important implementation details are discussed and, finally, conclusions and sugestions for future work are presented.

[pt] Este trabalho descreve o projeto e a implementação de um microcomputador tolerante a falhas para aplicação em tempo real. O sistema é baseado em uma estrutura duplex e utiliza o conceito de dissimilaridade como forma de reduzir a influência de falhas de modo comum. Vários mecanismos de detecção de falhas foram incorporados de forma a melhorar a cobertura do sistema. Com o objetivo de reduzir o hardcore, o único elemento central existente é o seletor de saída, sendo que os processadores sincronizam-se através da troca de mensagens. / [en] This work describes the design and implementation of a fault-tolerant microcomputer for real-time control applications. The system consists in a duplex structure and the dissimilarity concept is used in order to minimize the probability of common-mode faults. Several fault detection mecanisms were incorporated to increase the coverage of the system.

[pt] Este trabalho propõe uma nova estrutura de rede de interconexão para o sistema de processamento paralelo MULTIPLUS em desenvolvimento no NCE/UFRJ. A rede é tolerante a falhas, e trabalha com chaves de 4 entradas e 4 saídas. Inicialmente, discutem-se as formas de interconexão de máquinas paralelas. Descrevem-se sucintamente algumas arquiteturas de sistemas paralelos com ênfase no MULTIPLUS. A seguir, comentam-se alguns conceitos básicos a respeito de redes de interconexão. Apresenta-se a árvore genealógica das redes de interconexão multiestágio, acompanhada de um breve histórico do surgimento das mesmas. Destacam-se algumas redes de percurso único relacionadas com esta dissertação. Após uma introdução aprofundada sobre tolerância a falhas, descrevem-se algumas redes tolerantes a falhas. Uma análise bem estruturada sobre tolerância a falhas lança as bases para a proposta da rede de interconexão. Introduz-se o subsistema de interconexão do MULTIPLUS, focalizando a estrutura e os tipos de mensagens existentes. Discutem-se vários aspectos relativos à rede proposta, tais como a topologia, o algoritmo e tipo de roteamento e, principalmente, o mecanismo de tolerância a falhas. Descreve-se detalhadamente o projeto do elemento de chaveamento 4x4, com destaque nas máquinas de estado controladoras da chave, porém sem detrimento do circuito de prioridade, do circuito de contagem de pacotes, do circuito de comparação de tamanho da mensagem, do circuito de chaveamento, e do circuito de realinhamento de endereço. Inclui-se também uma descrição detalhada do funcionamento do elemento de chaveamento. Por fim, apresentam-se as expectativas de desempenho de uma rede com 16 entradas e 16 saídas, onde calculam-se o atraso para percorrer a rede de uma mensagem de leitura (12 pacotes), o atraso médio por pacote, o throughput médio por porta, e o throughput médio total da rede. Compara-se o desenho de três redes - uma de tamanho mínimo (4x4), outra de tamanho máximo (256x256), e outra de tamanho 16x16 - implementadas com chaves 2x2 e 4x4. apresentam-se os resultados do projeto, incluindo-se as EPLDs selecionadas, o custo aproximado de uma rede de 256x256 implementada com as referidas EPLDs, e os tempos de compilação dos blocos componentes da chave. Propõe-se a implementação da chave em VLSI, bem como a inclusão da capacidade de comunicação multicast, como futuros desenvolvimentos. / [en] This work proposes a new structure of interconnection network for the MULTIPLUS, a parallel processing system under development at NCE/UFRJ. The network is fault tolerant, and works with 4 inputs and 4 outputs switches. Initially, some interconnection forms of parallel machines are discussed. Some parallel systems architecture are briefly described with emphasis on MULTIPLUS. Following, some basic concepts of interconnection networks are commented. A family tree of multistage interconnection networks, and a short history of their appearance in the literature, are presented. Some Single Path Networks, wich are related with this dissertation, are briefly described. After a deep introduction of fault tolerance, some fault- tolerant interconnection network are described. A well- structured analysis on fault tolerance gives the basis for the interconnection network proposal. The MULTIPLUS interconnection subsystem is introduced, focusing the messages´ types and structure. Various aspects regarding the proposed network - such as the topology, routing type and algorithm and, mainly, the fault- tolerance mechanism - are discussed. The design of the 4x4 switch is described in details, with emphasis on switch controllers finite state machines, but also including the priority circuit, packet counting circuit, message size compariong circuit. A detailed description of the seitch operation is given. At last, the expectede performance of a 16 inputs and 16 outpus network, where a reading message (12 packets) delay, the packet mean delay, port mean throughput, and overall mean throughput are calculated. The performance of 3 networks - one with minimum size (4x4), other with maximum size (256x256), and another with 16x16 size, each of which implemented with 2x2 and 4x4 switches - are compared. The design results are presented, including the selected EPLDs, apprximated cost of a 256x256 network implemented with the already mentioned EPLDs, and the compiling times of the switch blocks. The switch implementation in VLSI tecnology, as well the multicast communication capability, are proposed as future developments.

[pt] Neste trabalho considera-se um sistema de computação geograficamente localizado, destinado ao controle de processos em tempo real. O trabalho tem como objetivo determinar uma política de tolerância a falhas transientes, bem como uma arquitetura de base para o sistema em questão, assim como dispendido para implementá-la. Abordam-se os pontos chaves necessários a tolerância, os quais são a caracterização das falhas físicas e humanas, as funções de mascaramento, deteção e recuperação após falhas físicas. O conceito de diversificação é considerado como uma alternativa à deteção e tolerância a falhas humanas (projeto), como também no que diz respeito a capacidade de fornecer uma deteção eficaz de falhas físicas em modo comum, pois proporciona uma independência entre os módulos redundantes quando uma mesma falha os atinge de forma idêntica. São apresentados uma arquitetura de base e a forma selecionada de colocar em prática a diversificação: a emulação de um dos microprocessadores. / [en] This work consideres a geographically localized computerized control sustem. The aim is to determine a policy of tolerance to transient faults, a well as a basic architecture for the control system. A discussion of the allocated effort to implement it is included here. They included the characterization of physical and human faults, masking, detection and recovery of physical faults. The concept of distinctness is considered as an alternative to detection and toleranc3e to human faults and also with respect to the capability to provide an effective detection of physical faults of common mode. This approach provides an independing among redundant modules when the same fault affects them in an identical way. This work presents a basic architecture which illustrates the use of the concept of distinctness, through the emulation of a microprocessor.

Unpredictable hardware faults and software bugs lead to application crashes, incorrect computations, unavailability of internet services, data losses, malfunctioning components, and consequently financial losses or even death of people. In particular, faults in microprocessors (CPUs) and memory corruption bugs are among the major unresolved issues of today. CPU faults may result in benign crashes and, more problematically, in silent data corruptions that can lead to catastrophic consequences, silently propagating from component to component and finally shutting down the whole system. Similarly, memory corruption bugs (memory-safety vulnerabilities) may result in a benign application crash but may also be exploited by a malicious hacker to gain control over the system or leak confidential data. Both these classes of errors are notoriously hard to detect and tolerate. Usual mitigation strategy is to apply ad-hoc local patches: checksums to protect specific computations against hardware faults and bug fixes to protect programs against known vulnerabilities. This strategy is unsatisfactory since it is prone to errors, requires significant manual effort, and protects only against anticipated faults. On the other extreme, Byzantine Fault Tolerance solutions defend against all kinds of hardware and software errors, but are inadequately expensive in terms of resources and performance overhead. In this thesis, we examine and propose five techniques to protect against hardware CPU faults and software memory-corruption bugs. All these techniques are hardware-assisted: they use recent advancements in CPU designs and modern CPU extensions. Three of these techniques target hardware CPU faults and rely on specific CPU features: ∆-encoding efficiently utilizes instruction-level parallelism of modern CPUs, Elzar re-purposes Intel AVX extensions, and HAFT builds on Intel TSX instructions. The rest two target software bugs: SGXBounds detects vulnerabilities inside Intel SGX enclaves, and “MPX Explained” analyzes the recent Intel MPX extension to protect against buffer overflow bugs. Our techniques achieve three goals: transparency, practicality, and efficiency. All our systems are implemented as compiler passes which transparently harden unmodified applications against hardware faults and software bugs. They are practical since they rely on commodity CPUs and require no specialized hardware or operating system support. Finally, they are efficient because they use hardware assistance in the form of CPU extensions to lower performance overhead.

While the robots gradually become a part of our daily lives, they already play vital roles in many critical operations. Some of these critical tasks include surgeries, battlefield operations, and tasks that take place in hazardous environments or distant locations such as space missions. In most of these tasks, remotely controlled robots are used instead of autonomous robots. This special area of robotics is called teleoperation. Teleoperation systems must be reliable when used in critical tasks; hence, all of the subsystems must be dependable even under a subsystem or communication line failure. These systems are categorized as unilateral or bilateral teleoperation. A special type of bilateral teleoperation is described as force-reflecting teleoperation, which is further investigated as limited- and unlimited-workspace teleoperation. Teleoperation systems configured in this study are tested both in numerical simulations and experiments. A new method, Virtual Rapid Robot Prototyping, is introduced to create system models rapidly and accurately. This method is then extended to configure experimental setups with actual master systems working with system models of the slave robots accompanied with virtual reality screens as well as the actual slaves. Fault-tolerant design and modeling of the master and slave systems are also addressed at different levels to prevent subsystem failure. Teleoperation controllers are designed to compensate for instabilities due to communication time delays. Modifications to the existing controllers are proposed to configure a controller that is reliable in communication line failures. Position/force controllers are also introduced for master and/or slave robots. Later, controller architecture changes are discussed in order to make these controllers dependable even in systems experiencing communication problems. The customary and proposed controllers for teleoperation systems are tested in numerical simulations on single- and multi-DOF teleoperation systems. Experimental studies are then conducted on seven different systems that included limited- and unlimited-workspace teleoperation to verify and improve simulation studies. Experiments of the proposed controllers were successful relative to the customary controllers. Overall, by employing the fault-tolerance features and the proposed controllers, a more reliable teleoperation system is possible to design and configure which allows these systems to be used in a wider range of critical missions.