A diminuição agressiva dos transistores, a qual levou a reduções na tensão de operação, vem proporcionando enormes benefícios em termos de poder computacional, mantendo o consumo de energia em um nível aceitável. No entanto, à medida que o tamanho dos recursos e a tensão diminuem, a susceptibilidade a falhas tende a aumentar e a importância das avaliações com falhas cresce. Os processadores superescalares, que hoje dominam o mercado, são um exemplo significativo de sistemas que se beneficiam destas melhorias tecnológicas e são mais suscetíveis a erros. Juntamente com isso, existem vários métodos para injeção de falhas, que é um meio eficiente para avaliar a resiliência desses processadores. No entanto, os métodos tradicionais de injeção de falhas, como a técnica baseada em hardware, impõem que o processador seja implementado fisicamente antes que os testes possam ser conduzidos, sem fornecer níveis razoáveis de controlabilidade. Por outro lado, as técnicas baseadas em simuladores implementados em software oferecem altos níveis de controlabilidade. No entanto, enquanto os simuladores em SW de alto nível (que são rápidos) podem levar a uma avaliação incompleta, ou mesmo equivocada, da resiliência do sistema, uma vez que não modelam os componentes internos do hardware (como os registradores do pipeline), simuladores em SW de baixo nível são extremamente lentos e dificilmente estão disponíveis em RTL (Register-Transfer Level). Considerando este cenário, propomos uma plataforma que preenche a lacuna entre as abordagens em HW e SW para avaliar falhas em processadores superescalares: é rápida, tem alta controlabilidade, disponível em software, flexível e, o mais importante, modela o processador em RTL. A ferramenta foi implementada sobre a plataforma usada para gerar o processador superescalar The Berkeley Out-of-Order Machine (BOOM), que é um processador altamente escalável e parametrizável. Esta propriedade nos permitiu experimentar três arquiteturas diferentes do processador: single-, dual- e quad-issue, e, ao analisar como a resiliência a falhas é influenciada pela complexidade de diferentes processadores, usamos os processadores para validar nossa ferramenta.

Aplicações paralelas geralmente são executadas com o máximo número de threads de hardware disponíveis no sistema para maximizar o seu desempenho. Contudo, esta abordagem pode não ser a melhor escolha quando se busca eficiência energética e, em alguns casos, pode até mesmo degradar o desempenho. Desta maneira, o presente trabalho aplica a adaptação dinâmica do número de threads para otimizar o Energy-Delay Product (EDP) de aplicações paralelas OpenMP executadas em sistemas embarcados. Ao contrário de soluções anteriores, que focam em processadores de propósito geral (GPP, do inglês General Purpose Processors), o presente trabalho considera as características intrínsecas de sistemas embarcados, os quais geralmente possuem menos núcleos disponíveis, assim como apresentam diferenças significativas em relação à micro-arquitetura e à hierarquia de memória. Por meio de experimentos realizados em um sistema embarcado real com processador octa-core, este trabalho mostrou que a adaptação dinâmica do número de threads permite, em média, economizar 15,35% no consumo de energia com apenas 3,41% de perda de desempenho, gerando assim 12,47% de otimização de EDP em relação à configuração padrão (uso do máximo número de threads disponíveis no sistema). No melhor caso, a adaptação dinâmica foi capaz de economizar 26,97% em energia enquanto promoveu 25,74% de aumento no desempenho, resultando em 45,77% de melhora no EDP. / Parallel applications usually execute using the maximum number of threads allowed by the available hardware at hand to maximize performance. However, this approach may not be the best when it comes to energy efficiency and may even lead to performance decrease in some particular cases. In this way, the present work proposes a new apporach for the dynamic adaptation of the number of threads to optimize Energy-Delay Product (EDP) of OpenMP applications when running on Embedded Systems. Differently from previous solutions, which focus on General Purpose Processors (GPP), the current one takes into account the intrinsic characteristics of embedded systems, which usually have a lower number of cores and significantly different characteristics concerning the microarchitecture and memory hierarchy when compared to GPPs. Through experiments on a real embedded system with an octa-core processor, this work demonstrates that adapting the number of threads at runtime saves energy, on average, by 15,35% with only 3,41% loss performance, improving the EDP by 12,47% over the default configuration (maximum number of threads available in the system). In the best case, the dynamic adaptation saves 26,97 % in energy while promoting a 25,74 % increase in performance, resulting in a 45,77 % improvement in EDP.

Ao se projetar um novo processador, o desempenho não é mais o único objetivo de otimização. Reduzir o consumo de energia também é essencial, pois, enquanto a maior parte dos dispositivos embarcados depende fortemente de bateria, os processadores de propósito geral (GPPs) são restringidos pelos limites da energia térmica de projeto (TDP – thermal design power). Além disso, devido à evolução da tecnologia, a taxa de falhas transientes tem aumentado nos processadores modernos, o que afeta a confiabilidade de sistemas tanto no espaço quanto no nível do mar. Adicionalmente, a maioria dos processadores homogêneos e heterogêneos tem um design fixo, o que limita a adaptação em tempo de execução. Nesse cenário, nós propomos dois designs de processadores que são capazes de realizar o trade-off entre esses eixos de acordo com a aplicação alvo e os requisitos do sistema. Ambos designs baseiam-se em um mecanismo de duplicação de instruções com rollback que detecta e corrige falhas, um módulo de power gating para reduzir o consumo de energia das unidades funcionais. O primeiro é chamado de processador adaptativo e usa thresholds, definidos em tempo de projeto, para adaptar a execução da aplicação Adicionalmente, ele controla o ILP da aplicação para criar mais oportunidade de duplicação e de power gating. O segundo design é chamado processador polimórfico e ele avalia (em tempo de execução) a melhor configuração de hardware a ser usada para cada aplicação. Ele também explora o hardware disponível para maximizar o número de aplicações que são executadas em paralelo. Para a versão adaptativa usando uma configuração orientada a otimização de energia, é possível, em média, economizar 37,2% de energia com um overhead de apenas 8,2% em performance, mantendo baixos níveis de defeito, quando comparado a um design tolerante a falhas. Para a versão polimórfica, os resultados mostram que a reconfiguração dinâmica do processador é capaz de adaptar eficientemente o hardware ao comportamento da aplicação, de acordo com os requisitos especificados pelo designer, chegando a 94.88% do resultado de um processador oráculo quando o trade-off entre os três eixos é considerado. Por outro lado, a melhor configuração estática apenas atinge 28.24% do resultado do oráculo. / Performance is no longer the only optimization goal when designing a new processor. Reducing energy consumption is also mandatory: while most of the embedded devices are heavily dependent on battery power, General-Purpose Processors (GPPs) are being pulled back by the limits of Thermal Design Power (TDP). Moreover, due to technology scaling, soft error rate (i.e., transient faults) has been increasing in modern processors, which affects the reliability of both space and ground-level systems. In addition, most traditional homogeneous and heterogeneous processors have a fixed design, which limits its runtime adaptability. Therefore, they are not able to cope with the changing application behavior when one considers the axes of fault tolerance, performance, and energy consumption altogether. In this context, we propose two processor designs that are able to trade-off these three axes according to the application at hand and system requirements. Both designs rely on an instruction duplication with rollback mechanism that can detect and correct errors and a power gating module to reduce the energy consumption of the functional units The former design, called adaptive processor, uses thresholds defined at design time to allow runtime adaptation of the application’s execution and controls the application’s Instruction-Level Parallelism (ILP) to create more slots for duplication or power gating. The latter design (polymorphic processor) takes the former one step further by dynamically reconfiguring the hardware and evaluating different processor configurations for each application, and it also exploits the available pipelanes to maximize the number of applications that are executed concurrently. For the adaptive processor using an energy-oriented configuration, it is possible, on average, to reduce energy consumption by 37.2% with an overhead of only 8.2% in performance, while maintaining low levels of failure rate, when compared to a fault-tolerant design. For the polymorphic processor, results show that the dynamic reconfiguration of the processor is able to efficiently match the hardware to the behavior of the application, according to the requirements of the designer, achieving 94.88% of the result of an oracle processor when the trade-off between the three axes is considered. On the other hand, the best static configuration only achieves 28.24% of the oracle’s result.

Este trabalho analisa o uso de redes de estações de trabalho como uma única máquina a ser utilizada para permitir o processamento de problemas que não poderiam ser computados, aceitavelmente, em apenas um de seus nodos, seja por causa do tempo dispendido ou de recursos físicos necessários, como memória principal. São enfocados dois algoritmos de redes neurais artificiais - Combinatorial Neural Model e Back Propagation - que apresentam os problemas enunciados acima, e uma proposta de um esquema para distribuição dessa classe de algoritmos, levando em consideração as vantagens disponíveis no ambiente em questão, a apresentada. A implementação do modelo proposto, sob a forma de um simulador distribuído baseado no conceito de servidor está descrita no trabalho, assim como as estratégias de paralelização dos algoritmos. Ao final, são apresentados os resultados obtidos, quantitativa e qualitativamente, e uma avaliação mais detalhada da paralelização do algoritmo Back Propagation a exposta. / The use of workstation networks as distributed multicomputers to solve resource demanding problems that cannot be feasibly solved in one node is the main concern of this work. Two different artificial neural network algorithms, Combinatorial Neural Model and Back Propagation, are faced and a scheme for distributing this class of algorithms is presented. The several advantages of the environment are focused in the proposal along with its disadvantages. This work also presents the implementation of the proposed scheme allowing an in loco performance evaluation. At the end results are shown and a more in depth evaluation of the Back Propagation parallelization is presented.

Submitted by Setor de Tratamento da Informa??o - BC/PUCRS (tede2@pucrs.br) on 2016-06-22T19:44:58Z No. of bitstreams: 1 DIS_DANIEL_COUTO_ADORNES_COMPLETO.pdf: 1894086 bytes, checksum: f87c59fa92f43ed62efaafd9c724ed8d (MD5) / Made available in DSpace on 2016-06-22T19:44:58Z (GMT). No. of bitstreams: 1 DIS_DANIEL_COUTO_ADORNES_COMPLETO.pdf: 1894086 bytes, checksum: f87c59fa92f43ed62efaafd9c724ed8d (MD5) Previous issue date: 2015-03-31 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior - CAPES / In order to improve performance, simplicity and scalability of large datasets processing, Google proposed the MapReduce parallel pattern. This pattern has been implemented in several ways for different architectural levels, achieving significant results for high performance computing. However, developing optimized code with those solutions requires specialized knowledge in each framework?s interface and programming language. Recently, the DSL-POPP was proposed as a framework with a high-level language for patternsoriented parallel programming, aimed at abstracting complexities of parallel and distributed code. Inspired on DSL-POPP, this work proposes the implementation of a unified MapReduce programming interface with rules for code transformation to optimized solutions for shared-memory multi-core and distributed architectures. The evaluation demonstrates that the proposed interface is able to avoid performance losses, while also achieving a code and a development cost reduction from 41.84% to 96.48%. Moreover, the construction of the code generator, the compatibility with other MapReduce solutions and the extension of DSL-POPP with the MapReduce pattern are proposed as future work. / Visando melhoria de performance, simplicidade e escalabilidade no processamento de dados amplos, o Google prop?s o padr?o paralelo MapReduce. Este padr?o tem sido implementado de variadas formas para diferentes n?veis de arquitetura, alcan?ando resultados significativos com respeito a computa??o de alto desempenho. No entanto, desenvolver c?digo otimizado com tais solu??es requer conhecimento especializado na interface e na linguagem de programa??o de cada solu??o. Recentemente, a DSL-POPP foi proposta como uma solu??o de linguagem de programa??o de alto n?vel para programa??o paralela orientada a padr?es, visando abstrair as complexidades envolvidas em programa??o paralela e distribu?da. Inspirado na DSL-POPP, este trabalho prop?e a implementa??o de uma interface unificada de programa??o MapReduce com regras para transforma??o de c?digo para solu??es otimizadas para arquiteturas multi-core de mem?ria compartilhada e distribu?da. A avalia??o demonstra que a interface proposta ? capaz de evitar perdas de performance, enquanto alcan?a uma redu??o de c?digo e esfor?o de programa??o de 41,84% a 96,48%. Ademais, a constru??o do gerador de c?digo, a compatibilidade com outras solu??es MapReduce e a extens?o da DSL-POPP com o padr?o MapReduce s?o propostas para trabalhos futuros.

Este trabalho que envolve matemática aplicada e processamento paralelo: seu objetivo é avaliar uma estratégia de implementação em paralelo para algoritmos de diferenças finitas que aproximam a solução de equações diferenciais de evolução. A alternativa proposta é a substituição dos produtos matriz-vetor efetuados sequencialmente por multiplicações matriz-matriz aceleradas pelo método de Strassen em paralelo. O trabalho desenvolve testes visando verificar o ganho computacional relacionado a essa estratégia de paralelização, pois as aplicacações computacionais, que empregam a estratégia sequencial, possuem como característica o longo período de computação causado pelo grande volume de cálculo. Inclusive como alternativa, nós usamos o algoritmo em paralelo convencional para solução de algoritmos explícitos para solução de equações diferenciais parciais evolutivas no tempo. Portanto, de acordo com os resultados obtidos, nós observamos as características de cada estratégia em paralelo, tendo como principal objetivo diminuir o esforço computacional despendido. / This work involves parallel processing and applied mathematics: Our goal is to evaluate a strategy for implementing parallel algorithms for finite diference approach,it is the solution of diferential equations of evolution. The alternative proposed is the replacement of the matrix-vector products performed sequentially by matrix-matrix multiplication method accelerated by Strassen in parallel. The work develops tests in order to verify the speedup related to the strategy of parallelization because sequential application have characterized for long periods of computation, this is caused by the large amount of calculation. Even alternatively, we use the algorithm in parallel to conventional explicit solution algorithms for solving partial diferential equations. Therefore, according to the results, we observe the characteristics of each strategy in parallel with the main purpose of reducing the computational effort expended.

A Bioinformática tem se desenvolvido de forma intensa nos últimos anos. A necessidade de se processar os grandes conjuntos de sequências, sejam de nucleotídeos ou de aminoácidos, tem estimulado o desenvolvimento de diversas técnicas algorítmicas, de modo a tratar este problema de maneira factível. Os algoritmos de alinhamento de alinhamento múltiplo de sequências assumiram um papel primordial, tornando a execução de alinhamentos de conjuntos com mais de duas sequencias uma tarefa viável computacionalmente. No entanto, com o aumento vertiginoso tanto da quantidade de sequencias em um determinado conjunto, quanto do comprimento dessas sequencias, a utilização desses algoritmos de alinhamento múltiplo, sem o acoplamento de novas estratégias, tornou-se algo impraticável. Consequentemente, a computação de alto desempenho despontou como um dos recursos a serem utilizados, através da paralelização de diversas estratégias para sua execução em grandes sistemas computacionais. Além disso, com a contínua expansão dos conjuntos de sequências, outras estratégias de otimização passaram a ser agregadas aos algoritmos de alinhamento múltiplo paralelos. Com isso, o desenvolvimento de ferramentas para alinhamento múltiplo de sequencias baseadas em abordagens híbridas destaca-se, atualmente, como a solução com melhor aceitação. Assim, no presente trabalho, pode-se verificar o desenvolvimento de uma estratégia híbrida para os algoritmos de alinhamento múltiplo progressivos, cuja utilização e amplamente difundida, em Bioinformática. Nesta abordagem, conjugou-se a paralelização e o particionamento dos conjuntos de sequências, na fase de construção da matriz de pontuação, e a otimização das fases de construção da árvore filogenética e de alinhamento múltiplo, através dos algoritmos de colônia de formigas e simulated annealling paralelo, respectivamente. / Bioinformatics has been developed in a fast way in the last years. The need for processing large sequences sets, either nucleotides or aminoacids, has stimulated the development of many algorithmic techniques, to solve this problem in a feasible way. Multiple sequence alignment algorithms have played an important role, because with the reduced computational complexity provided by them, it is possible to perform alignments with more than two sequences. However, with the fast growing of the amount and length of sequences in a set, the use of multiple alignment algorithms without new optimization strategies became almost impossible. Therefore, high performance computing has emerged as one of the features being used, through the parallelization of many strategies for execution in large computational systems. Moreover, with the continued expansion of sequences sets, other optimization strategies have been coupled with parallel multiple sequence alignments. Thus, the development of multiple sequences alignment tools based on hybrid strategies has been considered the solution with the best results. In this work, we present the development of a hybrid strategy to progressive multiple sequence alignment, where its using is widespread in Bioinformatics. In this approach, we have aggregated the parallelization and the partitioning of sequences sets in the score matrix calculation stage, and the optimization of the stages of the phylogenetic tree reconstruction and multiple alignment through ant colony and parallel simulated annealing algorithms, respectively.

Ray tracing é um algoritmo para a síntese de imagens por computador. Suas características principais são a alta qualidade das imagens que proporciona (incorporando sombras, reflexões e transparências entre outros efeitos) e, por outro lado, a grande demanda em termos de processamento. O ray tracing parametrizado é um algoritmo baseado no ray tracing, que permite a obtenção de imagens com a mesma qualidade a um custo computacional dezenas de vezes menor, porém com restrições. Estas restrições são a necessidade de geração de um arquivo de dados inicial, cujo tempo de processamento é pouco maior que o do ray tracing convencional e a não possibilidade de alteração de qualquer parâmetro geométrico da cena. Por outro lado, a geração de versões da mesma cena com mudanças nos parâmetros ópticos (cores, intensidades de luz, texturas, reflexões, transparências, etc.) é extremamente rápida. Esta tese propõe extensões ao algoritmo de ray tracing parametrizado, procurando aliviar algumas de suas restrições. Estas extensões permitem alterar alguns parâmetros geométricos como a posição das fontes de luz, parâmetros de fontes de luz spot e mapeamento de revelo entre outros, mantendo o bom desempenho do algoritmo original. Também é estudada a paralelização do algoritmo e outras formas de aceleração do processamento. As extensões propostas permitem ampliar o campo de aplicação do algoritmo original incentivando sua adoção mais generalizada. / Ray tracing is an image synthesis computer algorithm. Its main features are the high quality of the generated images (which incorporate shadows, reflections and transparency, among other effects) and, on the other hand, a high processing demand. Parameterized ray tracing is an algorithm based on ray tracing which allows the synthesis of images with the same quality but tens of times faster than ray tracing, although with some restrictions. These restrictions are the requirement of generating a data file (which takes a little longer than standard ray tracing to create) and the fact that no geometric modifications are allowed. On the other side, the processing time for creating new versions of the image with changes only on optical parameters (colors, light intensities, textures, reflections, transparencies, etc.) is extremely fast. This Ph.D. dissertation proposes extensions to the parameterized ray tracing algorithm for diminishing its restrictions. These extensions allow changing some geometric parameters like the light source positions, spotlight parameters and bump-mapping among others, keeping the processing performance of the original algorithm. The parallelization of the algorithm is also focused as well as other performance enhancements. The proposed extensions enlarge the field of application of the original algorithm, encouraging more general adoption.

Esta Dissertação de Mestrado propõe dois novos algoritmos para tornar mais eficiente o escalonamento on-line de tarefas com dependências estritas em agregados de computadores que usam como middleware para troca de mensagens alguma implementação da MPI (até a versão 2.1). Esses algoritmos foram projetados tendo-se em vista programas construídos no modelo de programação fork/join, onde a operação de fork é usada sobre uma chamada recursiva da função. São eles: 1. O algoritmo RatMD, implementado através de uma biblioteca de primitivas do tipo map-reduce, que funciona para qualquer implementação MPI, com qualquer versão da norma. Utilizado para minimizar o tempo de execução de uma computação paralela; e 2. O algoritmo RtMPD, implementado através de um sistema distribuído sobre daemons gerenciadores de processos criados dinamicamente com a implementação MPICH2 (que implementa a MPI-2). Utilizado para permitir execuções de instâncias maiores de programas paralelos dinâmicos. Ambos se baseiam em roubo de tarefas, que é a estratégia de balanceamento de carga mais difundida na literatura. Para ambos os algoritmos apresenta-se modelagem téorica de custos. Resultados experimentais obtidos ficam dentro dos limites teóricos calculados. RatMD provê uma redução no tempo de execução de até 80% em relação ao algoritmo usual (baseado em round-robin), com manutenção do speedup próximo ao linear e complexidade espacial idêntica à popular implementação com round-robin. RtMPD mantém, no mínimo, o mesmo desempenho que a implementação canônica do escalonamento em MPICH2, dobrando-se o limite físico de processos executados simultaneamente por cada nó. / This Master’s Dissertation proposes two new algorithms for improvement on on-line scheduling of dynamic-created tasks with strict dependencies on clusters of computers using MPI (up to version 2.1) as its middleware for message-passing communication. These algorithms were built targeting programs written on the fork-join model, where the fork operation is always called over an recursive function call. They are: 1. RatMD, implemented as a map-reduce library working for any MPI implementation, on whatever norm’s version. Used for performance gain; and 2. RtMPD, implemented as a distributed system over dynamic-generated processes manager daemons with MPICH2 implentation of MPI. Used for executing larger instances of dynamic parallel programs. Both algorithms are based on the (literature consolidated) work stealing technique and have formal guarantees on its execution time and load balancing. Experimental results are within theoretical bounds. RatMD shows an improvement on the performance up to 80% when paired with more usual algorithms (based on round-robin strategy). It also provides near-linear speedup and just about the same space-complexity on similar implementations. RtMPD keeps, at minimum, the very same performance of the canonical MPICH2 implementation, near doubling the physical limit of simultaneous program execution per cluster node.

A Computação Gráfica, área em franco desenvolvimento, têm caminhado em busca da geração, cada vez mais rápida, de imagens mais realísticas. Os algoritmos que permitem a síntese de imagens realísticas demandam alto poder computacional, fazendo com que a geração deste tipo de imagem, de forma rápida, requeira o uso de computadores paralelos. Hoje, a técnica que permite gerar as imagens mais realísticas é o "ray tracing" . Os multicomputadores, por sua vez, são a arquitetura de computadores paralelos mais promissora na busca do desempenho computacional necessário às aplicações modernas. Esta dissertação aborda o problema da implementação do algoritmo de "ray tracing" em multicomputadores. A paralelização desta técnica para uso em computadores paralelos de memória distribuída pode ser feita de muitas formas diferentes, sempre envolvendo um compromisso entre a velocidade de processamento e a memória utilizada. Neste trabalho conceitua-se este problema e introduz-se ferramentas para a avaliação de soluções que levam em consideração a eficiência de processamento e a redundância no uso de memória. Também é apresentada uma nova taxonomia que, além de permitir a classificação de propostas para implementações de "ray tracing" paralelo, orienta a procura de novas soluções para este problema. O desempenho das soluções em cada classe desta taxonomia é avaliado qualitativamente. Por fim, são sugeridas novas alternativas de paralelização do algoritmo de "ray tracing" em multicomputadores. / Computer Graphics is headed today towards the synthesis of more realistic images, in less time. The algorithms used for realistic image synthesis demand high computer power, so that the synthesis of this kind of image, in short periods of time, requires the use of parallel computers. Nowadays, the technique that yields the most realistic images is ray tracing. On its turn, multicomputers are the most promising parallel architecture for reaching the performance needed in modern applications. This dissertation is on the problem of implementing the ray tracing algorithm on multicomputers. The parallelization of this technique on distributed memory parallel computers can take several forms, always involving a compromise between speed and memory. In this work, this problem is conceptualized and tools for evaluation of solutions that account for efficiency and redundancy, are introduced. It is also presented a new taxonomy that can be used for both the classification of parallel ray tracing proposals and for driving the search of new solutions to this problem. The performances of entries in each class of the taxonomy are qualitatively assessed. New alternatives for parallelizing the ray tracing algorithm on multicomputers, are suggested.