Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2016-07-14T18:35:22Z No. of bitstreams: 1 EmmanoelMonteiroDeSousaJunior_DISSERT.pdf: 651885 bytes, checksum: 623fad0bd94a86d13b226fb6e7c4969b (MD5) / Made available in DSpace on 2016-07-25T19:03:26Z (GMT). No. of bitstreams: 1 EmmanoelMonteiroDeSousaJunior_DISSERT.pdf: 651885 bytes, checksum: 623fad0bd94a86d13b226fb6e7c4969b (MD5) Previous issue date: 2016-01-20 / Este trabalho prop?e uma arquitetura de software respons?vel pelo escalonamento para processamento de dados com demanda vari?vel em ambientes de nuvem. O sistema constru?do observa vari?veis espec?ficas ao contexto de neg?cio de uma empresa incubada no Instituto Metropole Digital da UFRN. Tal sistema gera uma estrat?gia de identifica??o e utiliza??o de modelos de m?quinas dispon?veis em um ambiente de nuvem, focando no desempenho do processamento, utilizando-se de estrat?gias de balanceamento de carga de dados e paralelismo de atividades no fluxo de execu??o do software. O objetivo ? atender a demanda sazonal dentro de um limite padr?o de tempo definido pela empresa, controlando os custos operacionais com a utiliza??o de servi?os de nuvem na camada de IaaS. / This study proposes a solution responsible for scheduling data processing with variable demand in cloud environments. The system built check specific variables to the business context of a company incubated at Digital Metropole Institute of UFRN. Such a system generates an identification strategy machinery designs available in a cloud environment, focusing on processing performance, using data load balancing strategies and activities of parallelism in the software execution flow. The goal is to meet the seasonal demand within a standard time limit set by the company, controlling operating costs by using cloud services in the IaaS layer.

Os problemas de engenharia cada vez mais exigem grandes necessidades computacionais, principalmente em termos de capacidade de processamento, sendo que o tempo de execução é um dos pontos-chave em toda esta discussção. Neste sentido o processamento paralelo surge como um elemento decisivo, pois possibilita uma redução do tempo de processamento em decorrência da execução paralela das operações. Outro fator importante é a questão da computação reconfigurável que possibilita combinar o desempenho do hardware com a flexibilidade do software, permitindo o desenvolvimento de sistemas extremamente complexos e compactos. Este trabalho tem por objetivo apresentar uma proposta de uma arquitetura paralela reconfigurável baseada em fluxo de dados (dataflow), que aproveita a potencialidade tanto do processamento paralelo quanto da computação reconfigurável, e que proporciona uma rápida adequação da máquina paralela ao problema a ser resolvido, garantindo um alto desempenho e uma grande flexibilidade de adaptar o sistema paralelo à aplicação desejada. Esta arquitetura visa explorar o paralelismo existente entre as operações envolvidas nos cálculos numéricos, baseando-se no grafo de fluxo de dados do problema a ser solucionado. A arquitetura é composta por uma unidade de controle, responsável por todo o controle dos Elementos Processadores (EPs) e o fluxo de dados entre eles, e de vários EPs que efetivamente realizam a execução da operação. Ao contrário da computação sequencial, a computação paralela aproveita a disponibilidade dos EPs presentes na arquitetura, garantindo um maior desempenho. Além disso, a arquitetura pode facilmente ser reorganizada, adaptando-se à aplicação, o que garante uma flexibilidade na classe de problemas computacionais que podem ser executados nesta arquitetura. / Many real-world engineering problems require high computational power, especially concerning to the processing speed. Modern parallel processing techniques play an important role in reducing the processing time as a consequence of the parallel execution of machinelevel operations for a given application software , taking advantage of possible independence between data and operations during processing time. Recently, reconfigurable computation has gained large attention thanks to its ability to combine hardware performance and software flexibility, allowed the developmentof very complex, compact and powerful systems for custom application. Tjis work proposes a new architecturefor parallel reconfigurable computation that associate the power of parallel processing and the flexibility of reconfigurable devices. This architecture allows quick customization of the system for many problems and, particularly, for numerical computation. For instance, this architecture can exploit the inherent parallelism of the numerical computation of differential equations, where several operations can be executed at the same time using a dataflow graph model of the problem. The proposedarchitecture is composed by a Control Unit , responsible for the control of all Processing Elements (PEs) and the data flow between them; and many application-customized PEs, responsible for the executionof operations. Diferrently from sequential computation, the parallel computation takes advantageof the available PEs and theirspecificity for the aplication. Therefore, the proposed architecture can offerhigh performance, scalability and customized solutions for engineering problems.

Made available in DSpace on 2014-12-17T14:54:52Z (GMT). No. of bitstreams: 1 DannielCL.pdf: 4466929 bytes, checksum: a4689db1730e1d1e328761ddef3c47b2 (MD5) Previous issue date: 2009-07-30 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The number of applications based on embedded systems grows significantly every year, even with the fact that embedded systems have restrictions, and simple processing units, the performance of these has improved every day. However the complexity of applications also increase, a better performance will always be necessary. So even such advances, there are cases, which an embedded system with a single unit of processing is not sufficient to achieve the information processing in real time. To improve the performance of these systems, an implementation with parallel processing can be used in more complex applications that require high performance. The idea is to move beyond applications that already use embedded systems, exploring the use of a set of units processing working together to implement an intelligent algorithm. The number of existing works in the areas of parallel processing, systems intelligent and embedded systems is wide. However works that link these three areas to solve any problem are reduced. In this context, this work aimed to use tools available for FPGA architectures, to develop a platform with multiple processors to use in pattern classification with artificial neural networks / O n?mero de aplica??es baseadas em sistemas embarcados cresce significativamente a cada ano. Isso se deve ao fato de que, apesar de sistemas embarcados possu?rem restri??es e unidades de processamento simples, o desempenho desses tem melhorado a cada dia. Entretanto a complexidade das aplica??es tamb?m cresce, fazendo com que sempre exista a necessidade de um desempenho melhor. Portanto, apesar dessa evolu??o, existem casos, nos quais, um sistema embarcado com uma ?nica unidade de processamento n?o ? suficiente para realizar o processamento das informa??es em tempo h?bil. Para melhorar o desempenho destes sistemas, pode-se analisar a implementa??o de solu??es com processamento paralelo e assim utilizar-los em aplica??es mais complexas que exigem um alto desempenho. A id?ia ? avan?ar al?m das aplica??es que j? utilizam sistemas embarcados, explorando a utiliza??o de um conjunto de unidades de processamento cooperando entre si para execu??o de um algoritmo inteligente. O n?mero de trabalhos existentes nas ?reas de processamento paralelo, sistemas inteligentes e sistemas embarcados ? grande. Entretanto, trabalhos que unam essas tr?s ?reas para a solu??o de algum tipo de problema s?o reduzidos. Diante deste contexto, esse trabalho teve como objetivo utilizar ferramentas dispon?veis para arquiteturas FPGA, desenvolvendo uma plataforma com m?ltiplos processadores para utiliza??o em problemas de processamento inteligente com redes neurais artificiais

Nos últimos anos, uma das alternativas adotadas para aumentar o desempenho de sistemas de processamento de alto desempenho têm sido o uso de arquiteturas híbridas. Essas arquiteturas são constituídas de processadores multicore e coprocessadores especializados, como GPUs. Esses coprocessadores atuam como aceleradores em alguns tipos de operações. Por outro lado, as ferramentas e modelos de programação paralela atuais não são adequados para cenários híbridos, produzindo aplicações pouco portáveis. O paralelismo de tarefas considerado um paradigma de programação genérico e de alto nível pode ser adotado neste cenário. Porém, exige o uso de algoritmos de escalonamento dinâmicos, como o algoritmo de roubo de tarefas. Neste contexto, este trabalho apresenta um middleware (WORMS) que oferece suporte ao paralelismo de tarefas com escalonamento por roubo de tarefas em sistemas híbridos multi-CPU e multi-GPU. Esse middleware permite que as tarefas tenham implementação tanto para execução em CPUs quanto em GPUs, decidindo em tempo de execução qual das implementações será executada de acordo com os recursos de hardware disponíveis. Os resultados obtidos com o WORMS mostram ser possível superar, em algumas aplicações, tanto o desempenho de ferramentas de referência para execução em CPU quanto de ferramentas para execução em GPUs. / In the last years, one of alternatives adopted to increase performance in high performance computing systems have been the use of hybrid architectures. These architectures consist of multicore processors and specialized coprocessors, like GPUs. Coprocessors act as accelerators in some types of operations. On the other hand, current parallel programming models and tools are not suitable for hybrid scenarios, generating less portable applications. Task parallelism, considered a generic and high level programming paradigm, can be used in this scenario. However, it requires the use of dynamic scheduling algorithms, such as work stealing. In this context, this work presents a middleware (WORMS) that supports task parallelism with work stealing scheduling in multi-CPU and multi-GPU systems. This middleware allows task implementations for both CPU and GPU, deciding at runtime which implementation will run according to the available hardware resources. The performance results obtained with WORMS showed that is possible to outperform both CPU and GPU reference tools in some applications.

Weather forecasting models are computationally intensive applications and traditionally they are executed in parallel machines. However, some issues prevent these models from fully exploiting the available computing power. One of such issues is load imbalance, i.e., the uneven distribution of load across the processors of the parallel machine. Since weather models are typically synchronous applications, that is, all tasks synchronize at every time-step, the execution time is determined by the slowest task. The causes of such imbalance are either static (e.g. topography) or dynamic (e.g. shortwave radiation, moving thunderstorms). Various techniques, often embedded in the application’s source code, have been used to address both sources. However, these techniques are inflexible and hard to use in legacy codes. In this thesis, we explore the concept of processor virtualization for dynamically balancing the load in weather models. This means that the domain is over-decomposed in more tasks than the available processors. Assuming that many tasks can be safely executed in a single processor, each processor is put in charge of a set of tasks. In addition, the system can migrate some of them from overloaded processors to underloaded ones when it detects load imbalance. This approach has the advantage of decoupling the application from the load balancing strategy. Our objective is to show that processor virtualization can be applied to weather models as long as an appropriate strategy for migrations is used. Our proposal takes into account the communication pattern of the application in addition to the load of each processor. In this text, we present the techniques used to minimize the amount of change needed in order to apply processor virtualization to a real-world application. Furthermore, we analyze the effects caused by the frequency at which the load balancer is invoked and a threshold that activates rebalancing. We propose an automatic strategy to find an optimal threshold to trigger load balancing. These strategies are centralized and work well for moderately large machines. For larger machines, we present a fully distributed algorithm and analyze its performance. As a study case, we demonstrate the effectiveness of our approach for dynamically balancing the load in Brams, a mesoscale weather forecasting model based on MPI parallelization. We choose this model because it presents a considerable load imbalance caused by localized thunderstorms. In addition, we analyze how other effects of processor virtualization can improve performance.

As threads de aplicações paralelas cooperam a fim de cumprir suas tarefas, dessa forma, comunicação é realizada entre elas. A latência de comunicação entre os núcleos em arquiteturas multiprocessadas diferem dependendo da hierarquia de memória e das interconexões. Com o aumento do número de núcleos por chip e número de threads por núcleo, esta diferença entre as latências de comunicação está aumentando. Portanto, é importante mapear as threads de aplicações paralelas levando em conta a comunicação entre elas. Em aplicações paralelas baseadas no paradigma de memória compartilhada, a comunicação é implícita e ocorre através de acessos à variáveis compartilhadas, o que torna difícil a descoberta do padrão de comunicação entre as threads. Mecanismos tradicionais usam simulação para monitorar os acessos à memória realizados pela aplicação, requerendo modificações no código fonte e aumentando drasticamente a sobrecarga. Nesta dissertação de mestrado, são introduzidos dois mecanismos inovadores com uma baixa sobrecarga para se detectar o padrão de comunicação entre threads. O primeiro mecanismo faz uso de informações sobre linhas compartilhadas de caches providas por protocolos de coerência de cache. O segundo mecanismo utiliza a Translation Lookaside Buffer (TLB) para detectar quais páginas de memória cada núcleo está acessando. Ambos os mecanismos dependem totalmente do hardware, o que torna o mapeamento de threads transparente aos programadores e permite que ele seja realizado dinamicamente pelo sistema operacional. Além disto, nenhuma tarefa de alta sobrecarga, como simulação, é requerida. As propostas foram avaliadas com o NAS Parallel Benchmarks (NPB), obtendo representações precisas dos padrões de comunicação. Mapeamentos para as threads foram gerados utilizando os padrões de comunicação descobertos e um algoritmo de mapeamento. O problema do mapeamento é NP-Difícil. Portanto, de forma a se atingir uma complexidade polinomial, o algoritmo empregado é heurístico, baseado no algoritmo de emparelhamento de grafos de Edmonds. Executando as aplicações com o mapeamento resultou em um ganho de desempenho de até 15; 3%. O número de faltas na cache, invalidações em linhas de cache e transações de espionagem foram reduzidos em até 31; 9%, 41% e 65; 4%, respectivamente. / The threads of parallel applications cooperate in order to fulfill their tasks, thereby communication is performed among themselves. The communication latency between the cores in a multiprocessor architecture differs depending on the memory hierarchy and the interconnections. With the increase in the number of cores per chip and the number of threads per core, this difference between the communication latencies is increasing. Therefore, it is important to map the threads of parallel applications taking into account the communication between them. In parallel applications based on the shared memory paradigm, the communication is implicit and occurs through accesses to shared variables, which makes difficult to detect the communication pattern between the threads. Traditional approaches use simulation to monitor the memory accesses performed by the application, requiring modifications to the source code and drastically increasing the overhead. In this master thesis, we introduce two novel light-weight mechanisms to find the communication pattern of threads. The first mechanism makes use of the information about shared cache lines provided by cache coherence protocols. The second mechanism makes use of the Translation Lookaside Buffer (TLB) to detect which memory pages each core is accessing. Both our mechanisms rely entirely on hardware features, which makes the thread mapping transparent to the programmer and allows it to be performed dynamically by the operating system. Moreover, no time consuming task, such as simulation, is required. We evaluated our mechanisms with the NAS Parallel Benchmarks (NPB) and obtained accurate representations of the communication patterns. We generated thread mappings from the detected communication patterns using a mapping algorithm. Mapping is a NP-Hard problem. Therefore, in order to achieve a polynomial complexity, we designed a heuristic method based on the Edmonds graph matching algorithm. Running the applications with these mappings resulted in performance improvements of up to 15.3% compared to the original scheduler of the operating system. The number of cache misses, cache line invalidations and snoop transactions were reduced by up to 31.9%, 41% and 65.4%, respectively.

O modelo a fluxo de dados tem grande destaque em pesquisas em arquiteturas de alto desempenho. Neste modelo, o controle de execução é feito apenas pela disponibilidade dos dados, permitindo que seja explorado o máximo de paralelismo implícito em um programa. As propostas que serão expostas neste trabalho visam solucionar um particular problema da máquina de fluxo de dados de Manchester. Esta arquitetura para tratar código reentrante, impõe que as fichas de dados, além da indicação da instrução destino, possuam um rótulo. Estas informações extras, que formam 70% da ficha de dado, fazem com que a implantação da máquina seja complexa. Assim, o hardware impõe um sério limite a velocidade de processamento, impedindo a plena utilização do modelo. Neste trabalho, serão apresentadas propostas para a redução do número de informações necessárias para o correto funcionamento da máquina, possibilitando uma implementação mais simples e mais eficiente. / The dataflow model is specially relevant you research in high-performance architectures. In this model, the execution control is done by taking into account only the dates availability, thus allowing maximum exploitation of the paralelism implicit in programs. The present work is based on the Manchester dataflow machine, which, in to order you handle the reentran code, imposes the dates token you have, in addition you the destination instruction Field, albel. Additional This information, which corresponds you 70% of the dates token, compounds the machine implementation it substantially bounds the execution speed and prevents the full model utilization. This work presents approaches will be reducing the amount of information needed will be to proper machine operation in to order you achieve to simpler and lives effective implementation.

Neste trabalho é apresentada a arquitetura SEED, proposta a partir das experiências adquiridas com as arquiteturas baseadas no modelo a fluxo de dados que foram estudadas até o presente. A arquitetura SEED utiliza o modelo a fluxo de dados para escalonar e executar blocos de instruções, visando aproveitar a principal qualidade apresentada pelo modelo, que consiste em expor o máximo de paralelismo existente nos programas. No entanto, a arquitetura explora paralelismo de granularidade mais grossa que as arquiteturas a fluxo de dados, a fim de reduzir o trafego de fichas de dados na arquitetura. Esta redução tenta resolver ou amenizar problemas como a excessiva ocupação de memória e a grande complexidade exigida do hardware. Além da especificação da funcionalidade de toda a arquitetura SEED, este trabalho apresenta uma proposta para o particionamento do código. A utilização desta proposta permite a geração de blocos de códigos que podem ser executados corretamente pela arquitetura SEED. Alguns benchmarks foram gerados utilizando essa proposta de particionamento de código. Estes benchmarks foram executados no simulador da arquitetura SEED, visando analisar e avaliar o comportamento da arquitetura com diversas configurações de hardware. / In this work is presented the SEED architecture. This architecture was proposed considering the experiences obtained with existing architectures based on dataflow model. The SEED architecture uses dataflow model to schedule and execute sets of instructions, called code blocks. This approach tries to make use of the main quality of the dataflow model that is to expose the maximum parallelism of the programs. However, this architecture explores coarser granularity than the one usually considered in dataflow architectures in order to reduce the data token traffic in the architecture. This type of reduction tries to solve problems like excessive occupation of memory and high complexity of the hardware. Besides the specification of all units that compose the SEED architecture, this work also proposes a way of partitioning programs, creating code blocks that may be executed by SEED architecture. Some benchmarks were generated using this proposal for partitioning programs. These benchmarks were executed in the SEED architecture simulator, in order to analyze the behavior of the proposed architecture under special configurations.

Neste trabalho, é apresentado um novo modelo de reconstrução tridimensional (3D) para amostras agrícolas com filtragem de Wiener em processamento paralelo, o qual é obtido a partir de reconstruções tomográficas bidimensionais (2D). No desenvolvimento, foram modelados algoritmos paralelos de retroprojeção filtrada e reconstrução tridimensional, baseando-se na inserção de um conjunto de planos virtuais entre pares de planos reais obtidos em ensaios tomográficos de raios X na faixa de energia de 56 keV a 662 keV. No modelo, os planos virtuais gerados em algoritmo paralelo são implementados com base na técnica de interpolação por B-Spline-Wavelet. Para validação do modelo desenvolvido, foi utilizada uma plataforma paralela composta de 4 processadores DSP, a qual possibilitou a troca de dados entre os processadores DSP e o envio de informações para o host, um computador desktop com processador Pentium III operando em 800 MHz. A extração de medidas de eficiência, de ganho e de precisão dos algoritmos paralelos foi realizada com base em um conjunto de amostras agrícolas (solo, vidro e madeiras) e de phantoms de calibração. Nessa avaliação, observou-se que o algoritmo de reconstrução 2D, utilizado como base para o algoritmo de reconstrução 3D, possibilitou uma alta eficiência para imagens de maior resolução, atingindo um pico de 92% de eficiência na resolução de 181X181 pixels. O algoritmo paralelo de reconstrução 3D foi analisado para um conjunto de amostras, sob diferentes configurações de planos reais e virtuais, organizados de forma a possibilitarem a avaliação do impacto causado pelo aumento da granularidade da comunicação e da carga de trabalho. Um melhor desempenho, com ganho médio igual a 3,4, foi obtido na reconstrução de objetos que demandaram o cálculo de um maior número de planos. Também, buscou-se conhecer a adaptabilidade do modelo para uso em arquitetura convencional, sendo que neste caso o uso de MPI permitiu a comunicação entre as tarefas projetadas em cada algoritmo paralelo. Adicionamente, foram incluídas ferramentas de visualização 2D e 3D para que usuários possam analisar as imagens e as características das amostras agrícolas em ambiente tridimensional. Os resultados obtidos indicam que o modelo de reconstrução 3D paralela trouxe contribuições originais para a área de tomografia agrícola aplicada à física de solos, bem como para a criação de ferramentas que viabilizem explorar recursos computacionais disponíveis em arquiteturas paralelas que demandem elevada capacidade de processamento. / This work presents a new method for three dimensional (3D) image reconstruction dedicated to the investigation in soil physics by means of X-ray tomography which is obtained using two-dimensional (2D) tomographic image reconstructed slices. The conception of the 3D model for reconstruction and visualization was based on the filtered back projection algorithm, operating under parallel environment together the insertion of virtual planes between pairs of real planes obtained by X-Ray tomography under energies varying from 56 keV to 662 keV. In this model, the virtual planes were generated by interpolation with the use of B-Spline-Wavelets. The evaluation of the 3D reconstruction model was established by using a set of agricultural samples (i.e., soil, glass, wood and calibration phantoms) having different configuration for the planes. Such configuration was based on setting not only the sizes and the number of the real but also the virtual planes in the volume. This procedure allows the impact measurements as a function of the increasing in workload and the communication granularity. To validate the reconstruction model, a dedicated parallel architecture composed of 4 DSP processors was used. This board enables data exchange between DSP processors and communication with host computer. A measurement of efficiency with a speed up equal to 3.4 was obtained using the same set of samples and a better performance was observed with a higher number of planes. Also, to understand about its adaptability, the model was implemented in conventional architecture, using MPI library to enable communication between designed tasks. Additionally, 2D and 3D visualization tools based on Vizualization ToolKit were included in order to help users to analyze images and their characteristics. Results have shown that the 3D parallel model reconstruction brought original contributions for the soil science diagnosis by X-Ray tomography, as well as to explore the available computational resources in parallel architectures, which demands great processing capacity.

Este trabalho aborda a utilização de computadores paralelos no processamento de problemas de análise estrutural. Inicialmente apresentam-se peculiaridades dos computadores de arquitetura paralela e do desenvolvimento de programas voltados a tais máquinas. Discute-se então a paralelização de duas etapas típicas da aplicação do método dos elementos finitos em análise estrutural: a montagem da matriz de rigidez da estrutura e a resolução do sistema de equações lineares. São propostos algoritmos alternativos para ambas as etapas. Finalmente é abordada a implementação de um programa de análise não linear de treliças tridimensionais com várias etapas paralelas. / This work is about the use of parallel computers on solving structural analysis problems. Initially, the particular features of parallel computers and the related software development are presented. The parallelization of two typical steps of finite method element are discussed: the assembly of global stiffness matrix and the solution of the linear system of equations. Alternative algorithms are proposed for both steps. Finally, the implementation of a program for nonlinear space truss analysis with several parallel steps is presented.