Particionamento de domínio e balanceamento de carga no modelo HIDRA

A paralelização de aplicaçõpes envolvendo a solução de problemas definidos sob o escopo da Dinâmica dos Fluidos Computacional normalmente é obtida via paralelismo de dados, onde o domínio da aplicação é dividido entre os diversos processadores, bem como a manutenção do balancecamento durante a execução é um problema complexo e diversas heurísticas têm sido desenvolvidas. Aplicações onde a simulação é dividida em diversas fases sobre partes diferentes do domínio acrescentam uma dificuldade maior ao particionamento, ao se buscar a distirbuição equlibrada das cargas em todas as fases. este trabalho descreve a implementação de mecanismos de particionamento e balanceamento de carga em problemas multi-fase sobre clusters de PCs. Inicialmente é apresentada a aplicação desenvolvida, um modelo de circulação e transporte de susbtâncias sobre corpos hídricos 2D e 3 D, que pode ser utilizado para modelar qualquer corpo hídrico a partir da descrição de sua geometria, batimetria e condições de contorno. Todo o desenvolvimento e testes do modelo foi feito utilizando como caso de estudo o domínio do Lago Guaíba, em Porto Alegre. Após, são descritas as principais heurísticas de particionamento de domínio de aplicações multi-fase em clusters, bem como mecanismos para balanceamento de carga para este tipo de aplicação. Ao final, é apresentada a solução proposta e desenvolvida, bem como os resultados obtidos com a mesma.

ONNIS-GI: uma rede neural oscilatória para segmentação de imagens implementada em arquitetura maciçamente paralela

A presente tese apresenta a concepção de uma rede neural oscilatória e sua realização em arquitetura maciçamente paralela, a qual é adequada à implementação de chips de visão digitais para segmentação de imagens. A rede proposta, em sua versão final, foi denominada ONNIS-GI (Oscillatory Neural Network for Image Segmentation with Global Inhibition) e foi inspirada em uma rede denominada LEGION (Locally Excitatory Globally Inhibitory Oscillator Network), também de concepção recente. Inicialmente, é apresentada uma introdução aos procedimentos de segmentação de imagens, cujo objetivo é o de situar e enfatizar a importância do tema abordado dentro de um contexto abrangente, o qual inclui aplicações de visão artificial em geral. Outro aspecto abordado diz respeito à utilização de redes neurais artificiais em segmentação de imagens, enfatizando as denominadas redes neurais oscilatórias, as quais têm apresentado resultados estimulantes nesta área. A implementação de chips de visão, integrando sensores de imagens e redes maciçamente paralelas de processadores, é também abordada no texto, ressaltando o objetivo prático da nova rede neural proposta. No estudo da rede LEGION, são apresentados resultados de aplicações originais desenvolvidas em segmentação de imagens, nos quais é verificada sua propriedade de separação temporal dos segmentos. A versão contínua da rede, um arranjo paralelo de neurônios baseados em equações diferenciais, apresenta elevada complexidade computacional para implementação em hardware digital e muitos parâmetros, com procedimento de ajuste pouco prático. Por outro lado, sua arquitetura maciçamente paralela apresenta-se particularmente adequada à implementação de chips de visão analógicos com capacidade de segmentação de imagens. Com base nos bons resultados obtidos nas aplicações desenvolvidas, é proposta uma nova rede neural, em duas versões, ONNIS e ONNIS-GI, as quais suplantam a rede LEGION em diversos aspectos relativos à implementação prática. A estrutura dos elementos de processamento das duas versões da rede, sua implementação em arquitetura maciçamente paralela e resultados de simulações e implementações em FPGA são apresentados, demonstrando a viabilidade da proposta. Como resultado final, conclui-se que a rede ONNIS-GI apresenta maior apelo de ordem prática, sendo uma abordagem inovadora e promissora na solução de problemas de segmentação de imagens, possuindo capacidade para separar temporalmente os segmentos encontrados e facilitando a posterior identificação dos mesmos. Sob o ponto de vista prático, a nova rede pode ser utilizada para implementar chips de visão digitais com arquitetura maciçamente paralela, explorando a velocidade de tais topologias e apresentando também flexibilidade para implementação de procedimentos de segmentação de imagens mais sofisticados.

Métodos multigrid paralelos em malhas não estruturadas aplicados à simulação de problemas de dinâmica de fluidos computacional e transferência de calor

Fenômenos naturais, tecnológicos e industriais podem, em geral, ser modelados de modo acurado através de equações diferenciais parciais, definidas sobre domínios contínuos que necessitam ser discretizados para serem resolvidos. Dependendo do esquema de discretização utilizado, pode-se gerar sistemas de equações lineares. Esses sistemas são, de modo geral, esparsos e de grande porte, onde as incógnitas podem ser da ordem de milhares, ou até mesmo de milhões. Levando em consideração essas características, o emprego de métodos iterativos é o mais apropriado para a resolução dos sistemas gerados, devido principalmente a sua potencialidade quanto à otimização de armazenamento e eficiência computacional. Uma forma de incrementar o desempenho dos métodos iterativos é empregar uma técnica multigrid. Multigrid são uma classe de métodos que resolvem eficientemente um grande conjunto de equações algébricas através da aceleração da convergência de métodos iterativos. Considerando que a resolução de sistemas de equações de problemas realísticos pode requerer grande capacidade de processamento e de armazenamento, torna-se imprescindível o uso de ambientes computacionais de alto desempenho. Uma das abordagens encontradas na literatura técnica para a resolução de sistemas de equações em paralelo é aquela que emprega métodos de decomposição de domínio (MDDs). Os MDDs são baseados no particionamento do domínio computacional em subdomínios, de modo que a solução global do problema é obtida pela combinação apropriada das soluções obtidas em cada um dos subdomínios Assim, neste trabalho são disponibilizados diferentes métodos de resolução paralela baseado em decomposição de domínio, utilizando técnicas multigrid para a aceleração da solução de sistemas de equações lineares. Para cada método, são apresentados dois estudos de caso visando a validação das implementações. Os estudos de caso abordados são o problema da difusão de calor e o modelo de hidrodinâmica do modelo UnHIDRA. Os métodos implementados mostraram-se altamente paralelizáveis, apresentando bons ganhos de desempenho. Os métodos multigrid mostraram-se eficiente na aceleração dos métodos iterativos, já que métodos que utilizaram esta técnica apresentaram desempenho superior aos métodos que não utilizaram nenhum método de aceleração.

RST: Reuse through Speculation on Traces

In this thesis, we present a novel approach to combine both reuse and prediction of dynamic sequences of instructions called Reuse through Speculation on Traces (RST). Our technique allows the dynamic identification of instruction traces that are redundant or predictable, and the reuse (speculative or not) of these traces. RST addresses the issue, present on Dynamic Trace Memoization (DTM), of traces not being reused because some of their inputs are not ready for the reuse test. These traces were measured to be 69% of all reusable traces in previous studies. One of the main advantages of RST over just combining a value prediction technique with an unrelated reuse technique is that RST does not require extra tables to store the values to be predicted. Applying reuse and value prediction in unrelated mechanisms but at the same time may require a prohibitive amount of storage in tables. In RST, the values are already stored in the Trace Memoization Table, and there is no extra cost in reading them if compared with a non-speculative trace reuse technique. . The input context of each trace (the input values of all instructions in the trace) already stores the values for the reuse test, which may also be used for prediction. Our main contributions include: (i) a speculative trace reuse framework that can be adapted to different processor architectures; (ii) specification of the modifications in a superscalar, superpipelined processor in order to implement our mechanism; (iii) study of implementation issues related to this architecture; (iv) study of the performance limits of our technique; (v) a performance study of a realistic, constrained implementation of RST; and (vi) simulation tools that can be used in other studies which represent a superscalar, superpipelined processor in detail. In a constrained architecture with realistic confidence, our RST technique is able to achieve average speedups (harmonic means) of 1.29 over the baseline architecture without reuse and 1.09 over a non-speculative trace reuse technique (DTM).

Sistema Aldeia : programação paralela e distribuída em Java sobre Infiniband e DECK

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.

Visualização simultânea e multi-nível de informações de monitoramento de cluster

Clusters de computadores são geralmente utilizados para se obter alto desempenho na execução de aplicações paralelas. Sua utilização tem aumentado significativamente ao longo dos anos e resulta hoje em uma presença de quase 60% entre as 500 máquinas mais rápidas do mundo. Embora a utilização de clusters seja bastante difundida, a tarefa de monitoramento de recursos dessas máquinas é considerada complexa. Essa complexidade advém do fato de existirem diferentes configurações de software e hardware que podem ser caracterizadas como cluster. Diferentes configurações acabam por fazer com que o administrador de um cluster necessite de mais de uma ferramenta de monitoramento para conseguir obter informações suficientes para uma tomada de decisão acerca de eventuais problemas que possam estar acontecendo no seu cluster. Outra situação que demonstra a complexidade da tarefa de monitoramento acontece quando o desenvolvedor de aplicações paralelas necessita de informações relativas ao ambiente de execução da sua aplicação para entender melhor o seu comportamento. A execução de aplicações paralelas em ambientes multi-cluster e grid juntamente com a necessidade de informações externas à aplicação é outra situação que necessita da tarefa de monitoramento. Em todas essas situações, verifica-se a existência de múltiplas fontes de dados independentes e que podem ter informações relacionadas ou complementares. O objetivo deste trabalho é propor um modelo de integração de dados que pode se adaptar a diferentes fontes de informação e gerar como resultado informações integradas que sejam passíveis de uma visualização conjunta por alguma ferramenta. Esse modelo é baseado na depuração offline de aplicações paralelas e é dividido em duas etapas: a coleta de dados e uma posterior integração das informações. Um protótipo baseado nesse modelo de integração é descrito neste trabalho Esse protótipo utiliza como fontes de informação as ferramentas de monitoramento de cluster Ganglia e Performance Co-Pilot, bibliotecas de rastreamento de aplicações DECK e MPI e uma instrumentação do Sistema operacional Linux para registrar as trocas de contexto de um conjunto de processos. Pajé é a ferramenta escolhida para a visualização integrada das informações. Os resultados do processo de integração de dados pelo protótipo apresentado neste trabalho são caracterizados em três tipos: depuração de aplicações DECK, depuração de aplicações MPI e monitoramento de cluster. Ao final do texto, são delineadas algumas conclusões e contribuições desse trabalho, assim como algumas sugestões de trabalhos futuros.

PerDiS : um serviço para descoberta de recursos no ISAM pervasive environment

Estratégias para descoberta de recursos permitem a localização automática de dispositivos e serviços em rede, e seu estudo é motivado pelo elevado enriquecimento computacional dos ambientes com os quais interage-se. Essa situação se deve principalmente à popularização de dispositivos pessoais móveis e de infra-estruturas de comunicação baseadas em redes sem-fio. Associado à rede fixa, esse ambiente computacional proporciona um novo paradigma conhecido como computação pervasiva. No escopo de estudo da computação pervasiva, o Grupo de Processamento Paralelo e Distribuído da Universidade Federal do Rio Grande do Sul desenvolve o projeto ISAM. Este engloba frentes de pesquisa que tratam tanto da programação de aplicações pervasivas como também do suporte à execução dessas. Esse suporte é provido pelo middleware EXEHDA, o qual disponibiliza um conjunto de serviços que podem ser utilizados por essas aplicações ou por outros serviços do ambiente de execução. Essa dissertação aborda especificamente o Pervasive Discovery Service (PerDiS), o qual atua como um mecanismo para descoberta de recursos no ambiente pervasivo proporcionado pelo ISAM. A concepção do PerDiS baseou-se na identificação dos principais requisitos de uma solução para descoberta de recursos apropriada para utilização em um cenário de computação pervasiva Resumidamente, os requisitos identificados nessa pesquisa e considerados pelo PerDiS tratam de questões relacionadas aos seguintes aspectos: a) utilização de informações do contexto de execução, b) utilização de estratégias para manutenção automática da consistência, c) expressividade na descrição de recursos e critérios de pesquisa, d) possibilidade de interoperabilidade com outras estratégias de descoberta, e) suporte à descoberta de recursos em larga-escala, e f) utilização de preferências por usuário. A arquitetura PerDiS para descoberta de recursos utiliza em sua concepção outros serviços disponibilizados pelo ambiente de execução do ISAM para atingir seus objetivos, e ao mesmo tempo provê um serviço que também pode ser utilizado por esses. O modelo proposto é validado através da implementação de um protótipo, integrado à plataforma ISAM. Os resultados obtidos mostram que o PerDiS é apropriado para utilização em ambientes pervasivos, mesmo considerando os desafios impostos por esse paradigma.

Implementação e avaliação de máquinas de comitê em um ambiente com múltiplos processadores embarcados em um único chip

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

Uma implementação paralela híbrida para o problema do caixeiro viajante usando algoritmos genéticos, GRASP e aprendizagem por reforço

The metaheuristics techiniques are known to solve optimization problems classified as NP-complete and are successful in obtaining good quality solutions. They use non-deterministic approaches to generate solutions that are close to the optimal, without the guarantee of finding the global optimum. Motivated by the difficulties in the resolution of these problems, this work proposes the development of parallel hybrid methods using the reinforcement learning, the metaheuristics GRASP and Genetic Algorithms. With the use of these techniques, we aim to contribute to improved efficiency in obtaining efficient solutions. In this case, instead of using the Q-learning algorithm by reinforcement learning, just as a technique for generating the initial solutions of metaheuristics, we use it in a cooperative and competitive approach with the Genetic Algorithm and GRASP, in an parallel implementation. In this context, was possible to verify that the implementations in this study showed satisfactory results, in both strategies, that is, in cooperation and competition between them and the cooperation and competition between groups. In some instances were found the global optimum, in others theses implementations reach close to it. In this sense was an analyze of the performance for this proposed approach was done and it shows a good performance on the requeriments that prove the efficiency and speedup (gain in speed with the parallel processing) of the implementations performed

Contribuição para o estudo do embarque de uma rede neural artificial em field programmable gate array (FPGA)

This study shows the implementation and the embedding of an Artificial Neural Network (ANN) in hardware, or in a programmable device, as a field programmable gate array (FPGA). This work allowed the exploration of different implementations, described in VHDL, of multilayer perceptrons ANN. Due to the parallelism inherent to ANNs, there are disadvantages in software implementations due to the sequential nature of the Von Neumann architectures. As an alternative to this problem, there is a hardware implementation that allows to exploit all the parallelism implicit in this model. Currently, there is an increase in use of FPGAs as a platform to implement neural networks in hardware, exploiting the high processing power, low cost, ease of programming and ability to reconfigure the circuit, allowing the network to adapt to different applications. Given this context, the aim is to develop arrays of neural networks in hardware, a flexible architecture, in which it is possible to add or remove neurons, and mainly, modify the network topology, in order to enable a modular network of fixed-point arithmetic in a FPGA. Five synthesis of VHDL descriptions were produced: two for the neuron with one or two entrances, and three different architectures of ANN. The descriptions of the used architectures became very modular, easily allowing the increase or decrease of the number of neurons. As a result, some complete neural networks were implemented in FPGA, in fixed-point arithmetic, with a high-capacity parallel processing

Estudos de algumas ferramentas de coleta e visualização de dados e desempenho de aplicações paralelas no ambiente MPI

The last years have presented an increase in the acceptance and adoption of the parallel processing, as much for scientific computation of high performance as for applications of general intention. This acceptance has been favored mainly for the development of environments with massive parallel processing (MPP - Massively Parallel Processing) and of the distributed computation. A common point between distributed systems and MPPs architectures is the notion of message exchange, that allows the communication between processes. An environment of message exchange consists basically of a communication library that, acting as an extension of the programming languages that allow to the elaboration of applications parallel, such as C, C++ and Fortran. In the development of applications parallel, a basic aspect is on to the analysis of performance of the same ones. Several can be the metric ones used in this analysis: time of execution, efficiency in the use of the processing elements, scalability of the application with respect to the increase in the number of processors or to the increase of the instance of the treat problem. The establishment of models or mechanisms that allow this analysis can be a task sufficiently complicated considering parameters and involved degrees of freedom in the implementation of the parallel application. An joined alternative has been the use of collection tools and visualization of performance data, that allow the user to identify to points of strangulation and sources of inefficiency in an application. For an efficient visualization one becomes necessary to identify and to collect given relative to the execution of the application, stage this called instrumentation. In this work it is presented, initially, a study of the main techniques used in the collection of the performance data, and after that a detailed analysis of the main available tools is made that can be used in architectures parallel of the type to cluster Beowulf with Linux on X86 platform being used libraries of communication based in applications MPI - Message Passing Interface, such as LAM and MPICH. This analysis is validated on applications parallel bars that deal with the problems of the training of neural nets of the type perceptrons using retro-propagation. The gotten conclusions show to the potentiality and easinesses of the analyzed tools.

Análise de escalabilidade de uma implementação paralela do simulated annealing acoplado

This paper analyzes the performance of a parallel implementation of Coupled Simulated Annealing (CSA) for the unconstrained optimization of continuous variables problems. Parallel processing is an efficient form of information processing with emphasis on exploration of simultaneous events in the execution of software. It arises primarily due to high computational performance demands, and the difficulty in increasing the speed of a single processing core. Despite multicore processors being easily found nowadays, several algorithms are not yet suitable for running on parallel architectures. The algorithm is characterized by a group of Simulated Annealing (SA) optimizers working together on refining the solution. Each SA optimizer runs on a single thread executed by different processors. In the analysis of parallel performance and scalability, these metrics were investigated: the execution time; the speedup of the algorithm with respect to increasing the number of processors; and the efficient use of processing elements with respect to the increasing size of the treated problem. Furthermore, the quality of the final solution was verified. For the study, this paper proposes a parallel version of CSA and its equivalent serial version. Both algorithms were analysed on 14 benchmark functions. For each of these functions, the CSA is evaluated using 2-24 optimizers. The results obtained are shown and discussed observing the analysis of the metrics. The conclusions of the paper characterize the CSA as a good parallel algorithm, both in the quality of the solutions and the parallel scalability and parallel efficiency

Projeto de Sistemas Integrados de Propósito Geral Baseados em Redes em Chip Expandindo as Funcionalidades dos Roteadores para Execução de Operações: A plataforma IPNoSys

It bet on the next generation of computers as architecture with multiple processors and/or multicore processors. In this sense there are challenges related to features interconnection, operating frequency, the area on chip, power dissipation, performance and programmability. The mechanism of interconnection and communication it was considered ideal for this type of architecture are the networks-on-chip, due its scalability, reusability and intrinsic parallelism. The networks-on-chip communication is accomplished by transmitting packets that carry data and instructions that represent requests and responses between the processing elements interconnected by the network. The transmission of packets is accomplished as in a pipeline between the routers in the network, from source to destination of the communication, even allowing simultaneous communications between pairs of different sources and destinations. From this fact, it is proposed to transform the entire infrastructure communication of network-on-chip, using the routing mechanisms, arbitration and storage, in a parallel processing system for high performance. In this proposal, the packages are formed by instructions and data that represent the applications, which are executed on routers as well as they are transmitted, using the pipeline and parallel communication transmissions. In contrast, traditional processors are not used, but only single cores that control the access to memory. An implementation of this idea is called IPNoSys (Integrated Processing NoC System), which has an own programming model and a routing algorithm that guarantees the execution of all instructions in the packets, preventing situations of deadlock, livelock and starvation. This architecture provides mechanisms for input and output, interruption and operating system support. As proof of concept was developed a programming environment and a simulator for this architecture in SystemC, which allows configuration of various parameters and to obtain several results to evaluate it

Programa de remediação fonológica em escolares com dificuldades de aprendizagem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)