Resumo: Considere um sistema formado por nodos interconectados por enlaces. Tanto os nodos quanto os enlaces podem assumir o estado falho ou sem-falha. Os algoritmos de diagnóstico distribuido têm como objetivo a identificação dos estados dos componentes de um sistema a partir de seus nodos sem-falha. O algoritmo NBND (Non-Broadcast Network Diagnosis) permite o diagnóstico distribuido de eventos em redes de topologia arbitrária. Através de testes periódicos, novos eventos são detectados e posteriormente propagados para os demais nodos. Com base no estado dos enlaces da rede, é possível executar, a partir de qualquer ponto da rede, um algoritmo de conectividade para descobrir quais nodos estão acessíveis e quais estão inacessíveis. O SNMP {Simple Network Management Protocolí) é o protocolo padrão utilizado na Internet para gerência de redes. O SNMP trabalha com informações organizadas numa estrutura hierárquica chamada MIB (.Management Information Base). Neste trabalho uma nova versão do algoritmo NBND é proposta e descrita formalmente. Um sistema distribuído de monitoramento de redes com agentes SNMP baseado no algoritmo NBND para diagnóstico de redes de topologia arbitrária é proposto e sua implementação é descrita, incluindo a NBND MIB, utilizada pelos agentes. Este trabalho traz, ainda, resultados experimentais da utilização do sistema de monitoramento na detecção de falhas em enlaces de duas topologías de rede: hipercubo e anel.

A maior parte dos mecanismos em processadores superescalares atuais usam granularidade de instrução para criar ou caracterizar especulações, tais como predição de desvios ou prefetchers. No entanto, muitas das características das instruções podem ser obtidas ao analisar uma granularidade mais grossa, o bloco básico de código, aumentando a quantidade de código coberta em um espaço similar de armazenamento. Adicionalmente, códigos podem ser analisados mais precisamente e prover uma variedade maior de informação ao observar diferentes tipos de instruções e suas relações. Devido a estas vantagens, a análise no nível de blocos pode fornecer mais oportunidades para mecanismos que necessitam desta informação. Por exemplo, é possível integrar informações de desvios mal previstos e acessos a memória para gerar informações mais precisas de quais acessos a memória oferecem melhor desempenho ao serem priorizados. Nesta tese propomos o Block-Level Architecture Profiler (BLAP) (Block Level Architecture Profiler), um mecanismo em hardware que caracteriza gargalos no nível microarquitetural, tal como loads delinquentes, desvios de difícil previsão e contenção nas unidades funcionais. O BLAP trabalha no nível de bloco básico, apenas detectando e fornecendo informações que podem ser usada para otimizar tais gargalos. Um mecanismo para a remoção de prefetches e uma política de controlador de memória DRAM foram criados para usar a informação criada pelo BLAP e demonstrar seu potencial. Juntos, estes mecanismos são capazes de melhorar o desempenho do sistema em até 17.39% (3.9% em média). Nosso método mostrou também ganhos médios de 13.14% quando avaliado com uma pressão na memória mais alta devido a prefetchers mais agressivos. / Most mechanisms in current superscalar processors use instruction granularity information for speculation, such as branch predictors or prefetchers. However, many of these characteristics can be obtained at the basic block level, increasing the amount of code that can be covered while requiring less space to store the data. Moreover, the code can be profiled more accurately and provide a higher variety of information by analyzing different instruction types inside a block. Because of these advantages, block-level analysis can offer more opportunities for mechanisms that use this information. For example, it is possible to integrate information about branch prediction and memory accesses to provide precise information for speculative mechanisms, increasing accuracy and performance. We propose a BLAP, an online mechanism that profiles bottlenecks at the microarchitectural level, such as delinquent memory loads, hard-to-predict branches and contention for functional units. BLAP works at the basic block level, providing information that can be used to reduce the impact of these bottlenecks. A prefetch dropping mechanism and a memory controller policy were developed to use the profiled information provided by BLAP. Together, these mechanisms are able to improve performance by up to 17.39% (3.90% on average). Our technique showed average gains of 13.14% when evaluated under high memory pressure due to highly aggressive prefetch.

Esse trabalho de dissertação está incluído no contexto das pesquisas realizadas no Grupo de Processamento Paralelo e Distribuído da UFRGS. Ele aborda as áreas da computação de alto desempenho, interfaces simples de programação e de sistemas de interconexão de redes velozes. A máquina paralela formada por agregados (clusters) tem se destacado por apresentar os recursos computacionais necessários às aplicações intensivas que necessitam de alto desempenho. Referente a interfaces de programação, Java tem se mostrado uma boa opção para a escrita de aplicações paralelas por oferecer os sistemas de RMI e de soquetes que realizam comunicação entre dois computadores, além de todas as facilidades da orientação a objetos. Na área a respeito de interconexão de rede velozes está emergindo como uma tentativa de padronização a nova tecnologia Infiniband. Ela proporciona uma baixa latência de comunicação e uma alta vazão de dados, além de uma série de vantagens implementadas diretamente no hardware. É neste contexto que se desenvolve o presente trabalho de dissertação de mestrado. O seu tema principal é o sistema Aldeia que reimplementa a interface bastante conhecida de soquetes Java para realizar comunicação assíncrona em agregados formados por redes de sistema. Em especial, o seu foco é redes configuradas com equipamentos Infiniband. O Aldeia objetiva assim preencher a lacuna de desempenho do sistema padrão de soquetes Java, que além de usar TCP/IP possui um caráter síncrono. Além de Infiniband, o Aldeia também procura usufruir dos avanços já realizados na biblioteca DECK, desenvolvida no GPPD da UFRGS. Com a sua adoção, é possível realizar comunicação com uma interface Java sobre redes Myrinet, SCI, além de TCP/IP. Somada a essa vantagem, a utilização do DECK também proporciona a propriedade de geração de rastros para a depuração de programas paralelos escritos com o Aldeia. Uma das grandes vantagens do Aldeia está na sua capacidade de transmitir dados assincronamente. Usando essa técnica, cálculos da aplicação podem ser realizados concorrentemente com as operações pela rede. Por fim, os canais de dados do Aldeia substituem perfeitamente aqueles utilizados para a serialização de objetos. Nesse mesmo caminho, o Aldeia pode ser integrado à sistemas que utilizem a implementação de soquetes Java, agora para operar sobre redes de alta velocidade. Palavras-chave: Arquitetura Infiniband, agregado de computadores, linguagem de programação Java, alto desempenho, interface de programação.

Renovados são os desa os trazidos à computação distribuída pelos recentes desenvolvimentos nas tecnologias de computação móvel. Tais avanços inspiram uma perspectiva na qual a computação tornar-se-á uma entidade ubíqua em um futuro próximo, estando presente nas mais simples atividades do dia-a-dia. Esta perspectiva é motivadora das pesquisas conduzidas no escopo do projeto ISAM, as quais investigam as questões relativas ao uso da computação em ambientes móveis de larga escala. Neste trabalho é apresentado o sistema PRIMOS (PRIMitives for Object Scheduling), o qual busca, pela complementação da plataforma Java, satisfazer as emergentes necessidades do ISAM. Especi camente, o PRIMOS constitui um conjunto de primitivas para instanciação remota e migração de objetos, comunicação e monitoração, direcionadas a um ambiente de computação distribuída de larga escala de características pervasivas. A primitiva de instanciação remota disponibilizada pelo PRIMOS aumenta a plataforma Java padrão com a possibilidade de criar e ativar objetos em nodos remotos do sistema. Por sua vez, a primitiva de migração faculta a relocação de objetos. A consecu- ção de tais semânticas tem como sub-produto a de nição de semânticas para ativação e desativação de objetos, assim como para captura e restauração de contexto de execução. Sob a perspectiva da comunicação, o PRIMOS de ne um esquema de endereçamento independente de protocolo de transporte, assim como uma interface neutra para acesso às facilidades de comunicação. A integração destas funcionalidades ao mecanismo de invocações remotas da plataforma Java, o RMI, permite a desvinculação deste da pilha TCP/IP. Por conseguinte, habilita a adoção de transportes otimizados ao hardware de comunicação disponibilizado pelo sistema. No que se refere à monitoração, o PRIMOS de ne um esquema exível e extensível baseado em sensores. A exibilidade vem principalmente da possibilidade dos sensores terem seus parâmetros de operação recon gurados a qualquer momento em resposta a novas necessidades do sistema. Por outro lado, o sistema é extensível pois o conjunto de sensores básicos, ditos nativos, pode ser aumentado por sensores providos pela aplicação. Com intuito de validar as idéias postuladas, um protótipo foi construído para o sistema. Sobre este, baterias de testes foram realizadas para cada uma das primitivas constituintes do PRIMOS.

A maior parte dos mecanismos em processadores superescalares atuais usam granularidade de instrução para criar ou caracterizar especulações, tais como predição de desvios ou prefetchers. No entanto, muitas das características das instruções podem ser obtidas ao analisar uma granularidade mais grossa, o bloco básico de código, aumentando a quantidade de código coberta em um espaço similar de armazenamento. Adicionalmente, códigos podem ser analisados mais precisamente e prover uma variedade maior de informação ao observar diferentes tipos de instruções e suas relações. Devido a estas vantagens, a análise no nível de blocos pode fornecer mais oportunidades para mecanismos que necessitam desta informação. Por exemplo, é possível integrar informações de desvios mal previstos e acessos a memória para gerar informações mais precisas de quais acessos a memória oferecem melhor desempenho ao serem priorizados. Nesta tese propomos o Block-Level Architecture Profiler (BLAP) (Block Level Architecture Profiler), um mecanismo em hardware que caracteriza gargalos no nível microarquitetural, tal como loads delinquentes, desvios de difícil previsão e contenção nas unidades funcionais. O BLAP trabalha no nível de bloco básico, apenas detectando e fornecendo informações que podem ser usada para otimizar tais gargalos. Um mecanismo para a remoção de prefetches e uma política de controlador de memória DRAM foram criados para usar a informação criada pelo BLAP e demonstrar seu potencial. Juntos, estes mecanismos são capazes de melhorar o desempenho do sistema em até 17.39% (3.9% em média). Nosso método mostrou também ganhos médios de 13.14% quando avaliado com uma pressão na memória mais alta devido a prefetchers mais agressivos. / Most mechanisms in current superscalar processors use instruction granularity information for speculation, such as branch predictors or prefetchers. However, many of these characteristics can be obtained at the basic block level, increasing the amount of code that can be covered while requiring less space to store the data. Moreover, the code can be profiled more accurately and provide a higher variety of information by analyzing different instruction types inside a block. Because of these advantages, block-level analysis can offer more opportunities for mechanisms that use this information. For example, it is possible to integrate information about branch prediction and memory accesses to provide precise information for speculative mechanisms, increasing accuracy and performance. We propose a BLAP, an online mechanism that profiles bottlenecks at the microarchitectural level, such as delinquent memory loads, hard-to-predict branches and contention for functional units. BLAP works at the basic block level, providing information that can be used to reduce the impact of these bottlenecks. A prefetch dropping mechanism and a memory controller policy were developed to use the profiled information provided by BLAP. Together, these mechanisms are able to improve performance by up to 17.39% (3.90% on average). Our technique showed average gains of 13.14% when evaluated under high memory pressure due to highly aggressive prefetch.

[pt] Esta dissertação aborda o problema da recuperação de erros em sistemas distribuídos. Inicialmente, é feita uma breve análise sobre a origem deste problema e as soluções encontradas. Alguns métodos de resolução são então apresentados. Para a simulação do sistema distribuído foi desenvolvido um núcleo multi-tarefa numa máquina compatível com o PC-IBM-XT, utilizando o MS-DOS (versão 3.0 ou acima) como servidor. Finalmente, são apresentadas duas propostas. A primeira visa fornecer a um processo recursos que possibilitem a recuperação por retorno. A segunda utiliza redundância em um conjunto de processos em diferentes estações para garantir que o sistema como um todo continue operativo, mesmo com uma estação de falha / [en] This dissertation deals with the problem of fault tolerance in distributed systems. Initially, a brief analysis on the origins of this problem and its solutions is made. Some of the resolutions methods are then presented. In order to simulate a distributed system, a multi tasking operating system kernel was developed in an IBM PC-XT compatible machine, making use of the MS-DOS (version 3.0 or above) as a server. Finally, two proposals are presented. The first, is intended to supply a process with resources that allow recovery in case of algorithmic faults, making use of the backward error recovery method. The second, uses redundancy in a set of processes over different stations in order to warrant that the system as a whole keeps operative, even with a faulty s

Ingeniero Civil Químico / En los últimos años, la masificación de sistemas embebidos y de computadores de placa reducida (SBC) han permitido el diseño, desarrollo y automatización de hardware de bajo costo para aplicaciones multidisciplinarias tales como impresoras 3D, sistemas de alarmas y climatización. Sin embargo, a nivel de laboratorios y pequeñas industrias su uso se limita a la creación de sensores, es por ello que esta memoria explora el diseño de un sistema de control enfocado en estos segmentos. Este sistema de control está compuesto por un servidor de control que posee una base de datos, un servidor web que actúa como interfaz humano-máquina (HMI), y un elemento de control, conectados mediante una red inalámbrica. El elemento de control corresponde al dispositivo encargado de obtener desde los sensores, datos sobre las variables de entrada, manipular los actuadores a través de los puertos de salida y posee además, la capacidad de implementar una ley de control a través de un controlador en modo de supervisión o como controlador digital directo. Por otro lado, el servidor de control tiene la función de registrar las mediciones de los sensores del equipo conectados al sistema, además, también puede registrar modificaciones hechas al sistema desde el HMI. El sistema de control diseñado se implementó en el equipo HL630, equipo que posee un circuito de calefacción de agua que incluye un radiador con ventilador, calefactor, una bomba de potencia regulable y un sensor de flujo. Para esto, se utilizó como servidor de control el SBC Raspberry Pi B+, y como elemento de control el sistema embebido Arduino Yún. Para conectar el equipo al elemento de control, se utilizó circuitos y dispositivos electrónicos con el fin de enlazar los actuadores y sensores. Asimismo, se observó la presencia de interferencias electromagnéticas (EMI), problema que se solucionó utilizando una jaula de Faraday. Además, se implementó un controlador digital directo de tipo PID con PWM debido a que no es posible utilizar el elemento de control en modo de supervisión. Finalmente, para la sintonización del controlador, se utilizó un modelo empírico basado en la respuesta del sistema a un pulso de 15 seg., y con ello, mediante el ajuste de parámetros de simulaciones para un sistema con una función de transferencia de cierto orden, se determinó que la función de transferencia que mejor representa el sistema es de orden-(3,2). Así, se sintonizó el controlador utilizando algoritmos basados en la minimización de overshoot en función del tiempo de estabilización del sistema para problemas de regulación y servo-control, en base a una simulación del sistema con controlador PID continuo, para obtener parámetros utilizados como base de la ley de control implementada y mediante un análisis de sensibilidad se obtuvo un valor definitivo. Posteriormente, se probó de forma experimental que al aumentar 10 veces el valor destinado a eliminar el windup reset aumenta la amplitud de oscilaciones y el sistema converge a estado estacionario oscilando alrededor del valor del setpoint. De igual manera, también se experimentó aumentar al doble el periodo de la señal de referencia del PWM y se observó que el controlador no cambia la amplitud, ni el tiempo de estabilización, sin embargo, se genera una oscilación de alta frecuencia de amplitud constante. Así, fue posible diseñar una infraestructura de un sistema de control distribuido con las caracteristicas ya mencionadas, que se implementó en un equipo de laboratorio y de forma exitosa fue posible monitorear y controlar el equipo de forma remota a través del HMI. A su vez, este proyecto permitió ver la factibilidad técnica de implementar sistemas de control de bajo costo en algunos procesos de pequeñas escala, a modo de reemplazar la utilización de costosos sistemas industriales.

No description available.

Devido ao contínuo crescimento dos dados científicos nos últimos anos, a análise intensiva de dados nessas quantidades massivas de dados é muito importante para extrair informações valiosas. Por outro lado, o formato de dados científicos GRIB (GRIdded Binary) é amplamente utilizado na comunidade meteorológica para armazenar histórico de dados e previsões meteorológicas. No entanto, as ferramentas atuais disponíveis e métodos para processar arquivos neste formato não realizam o processamento em um ambiente distribuído. Essa situação limita as capacidades de análise dos cientistas que precisam realizar uma avaliação sobre grandes conjuntos de dados com o objetivo de obter informação no menor tempo possível fazendo uso de todos os recursos disponíveis. Neste contexto, este trabalho apresenta uma alternativa ao processamento de dados no formato GRIB usando o padrão Manager-Worker implementado com o modelo de atores fornecido pelo Akka toolkit. Realizamos também uma comparação da nossa proposta com outros mecanismos, como o round-robin, random, balanceamento de carga adaptativo, bem como com um dos principais frameworks para o processamento de grandes quantidades de dados tal como o Apache Spark. A metodologia utilizada considera vários fatores para avaliar o processamento dos arquivos GRIB. Os experimentos foram conduzidos em um cluster na plataforma Microsoft Azure. Os resultados mostram que nossa proposta escala bem à medida que o número de nós aumenta. Assim, nossa proposta atingiu um melhor desempenho em relação aos outros mecanismos utilizados para a comparação, particularmente quando foram utilizadas oito máquinas virtuais para executar as tarefas. Nosso trabalho com o uso de metadados alcançou um ganho de 53.88%, 62.42%, 62.97%, 61.92%, 62.44% e 59.36% em relação aos mecanismos round-robin, random, balanceamento de carga adaptativo que usou métricas CPU, JVM Heap e um combinado de métricas, e o Apache Spark, respectivamente, em um cenário onde um critério de busca é aplicado para selecionar 2 dos 27 parâmetros totais encontrados no conjunto de dados utilizado nos experimentos. / Because of the continuous and overwhelming growth of scientific data in the last few years, data-intensive analysis on this vast amount of scientific data is very important to extract valuable scientific information. The GRIB (GRIdded Binary) scientific data format is widely used within the meteorological community and is used to store historical meteorological data and weather forecast simulation results. However, current libraries to process the GRIB files do not perform the computation in a distributed environment. This situation limits the analytical capabilities of scientists who need to perform analysis on large data sets in order to obtain information in the shortest time possible using of all available resources. In this context, this work presents an alternative to data processing in the GRIB format using the well-know Manager-Worker pattern, which was implemented with the Actor model provided by the Akka toolkit. We also compare our proposal with other mechanisms, such as the round-robin, random and an adaptive load balancing, as well as with one of the main frameworks currently existing for big data processing, Apache Spark. The methodology used considers several factors to evaluate the processing of the GRIB files. The experiments were conducted on a cluster in Microsoft Azure platform. The results show that our proposal scales well as the number of worker nodes increases. Our work reached a better performance in relation to the other mechanisms used for the comparison particularly when eight worker virtual machines were used. Thus, our proposal upon using metadata achieved a gain of 53.88%, 62.42%, 62.97%, 61.92%, 62.44% and 59.36% in relation to the mechanisms: round-robin, random, an adaptive load balancing that used CPU, JVM Heap and mix metrics, and the Apache Spark respectively, in a scenario where a search criteria is applied to select 2 of 27 total parameters found in the dataset used in the experiments.

Um dado por si só não possui valor algum, a menos que ele seja interpretado, contextualizado e agregado com outros dados, para então possuir valor, tornando-o uma informação. Em algumas classes de aplicações o valor não está apenas na informação, mas também na velocidade com que essa informação é obtida. As negociações de alta frequência (NAF) são um bom exemplo onde a lucratividade é diretamente proporcional a latência (LOVELESS; STOIKOV; WAEBER, 2013). Com a evolução do hardware e de ferramentas de processamento de dados diversas aplicações que antes levavam horas para produzir resultados, hoje precisam produzir resultados em questão de minutos ou segundos (BARLOW, 2013). Este tipo de aplicação tem como característica, além da necessidade de processamento em tempo-real ou quase real, a ingestão contínua de grandes e ilimitadas quantidades de dados na forma de tuplas ou eventos. A crescente demanda por aplicações com esses requisitos levou a criação de sistemas que disponibilizam um modelo de programação que abstrai detalhes como escalonamento, tolerância a falhas, processamento e otimização de consultas. Estes sistemas são conhecidos como Stream Processing Systems (SPS), Data Stream Management Systems (DSMS) (CHAKRAVARTHY, 2009) ou Stream Processing Engines (SPE) (ABADI et al., 2005). Ultimamente estes sistemas adotaram uma arquitetura distribuída como forma de lidar com as quantidades cada vez maiores de dados (ZAHARIA et al., 2012). Entre estes sistemas estão S4, Storm, Spark Streaming, Flink Streaming e mais recentemente Samza e Apache Beam. Estes sistemas modelam o processamento de dados através de um grafo de fluxo com vértices representando os operadores e as arestas representando os data streams. Mas as similaridades não vão muito além disso, pois cada sistema possui suas particularidades com relação aos mecanismos de tolerância e recuperação a falhas, escalonamento e paralelismo de operadores, e padrões de comunicação. Neste senário seria útil possuir uma ferramenta para a comparação destes sistemas em diferentes workloads, para auxiliar na seleção da plataforma mais adequada para um trabalho específico. Este trabalho propõe um benchmark composto por aplicações de diferentes áreas, bem como um framework para o desenvolvimento e avaliação de SPSs distribuídos. / Recently a new application domain characterized by the continuous and low-latency processing of large volumes of data has been gaining attention. The growing number of applications of such genre has led to the creation of Stream Processing Systems (SPSs), systems that abstract the details of real-time applications from the developer. More recently, the ever increasing volumes of data to be processed gave rise to distributed SPSs. Currently there are in the market several distributed SPSs, however the existing benchmarks designed for the evaluation this kind of system covers only a few applications and workloads, while these systems have a much wider set of applications. In this work a benchmark for stream processing systems is proposed. Based on a survey of several papers with real-time and stream applications, the most used applications and areas were outlined, as well as the most used metrics in the performance evaluation of such applications. With these information the metrics of the benchmark were selected as well as a list of possible application to be part of the benchmark. Those passed through a workload characterization in order to select a diverse set of applications. To ease the evaluation of SPSs a framework was created with an API to generalize the application development and collect metrics, with the possibility of extending it to support other platforms in the future. To prove the usefulness of the benchmark, a subset of the applications were executed on Storm and Spark using the Azure Platform and the results have demonstrated the usefulness of the benchmark suite in comparing these systems.