A computação paralela permite uma série de vantagens para a execução de aplicações de grande porte, sendo que o uso efetivo dos recursos computacionais paralelos é um aspecto relevante da computação de alto desempenho. Este trabalho apresenta uma metodologia que provê a execução, de forma automatizada, de aplicações paralelas baseadas no modelo BSP com tarefas heterogêneas. É considerado no modelo adotado, que o tempo de computação de cada tarefa secundária não possui uma alta variância entre uma iteração e outra. A metodologia é denominada de ASE e é composta por três etapas: Aquisição (Acquisition), Escalonamento (Scheduling) e Execução (Execution). Na etapa de Aquisição, os tempos de processamento das tarefas são obtidos; na etapa de Escalonamento a metodologia busca encontrar a distribuição de tarefas que maximize a velocidade de execução da aplicação paralela, mas minimizando o uso de recursos, por meio de um algoritmo desenvolvido neste trabalho; e por fim a etapa de Execução executa a aplicação paralela com a distribuição definida na etapa anterior. Ferramentas que são aplicadas na metodologia foram implementadas. Um conjunto de testes aplicando a metodologia foi realizado e os resultados apresentados mostram que os objetivos da proposta foram alcançados. / Parallel computing allows for a series of advantages on the execution of large applications and the effective use of parallel resources is an important aspect in the High Performance Computing. This work presents a methodology to provide the execution, in an automated way, of parallel applications based on BSP model with heterogeneous tasks. In this model it is assumed that the computation time between iterations does not have a high variance. The methodology is entitled ASE and it is composed by three stages: Acquisition, Scheduling and Execution. In the Acquisition step, the tasks\' processing time are obtained; In the Scheduling step, the methodology finds the ideal arrangement to distribute the tasks to maximize the execution speed and, simultaneously, minimize the use of resources. This is made using an algorithm developed in this work; and lastly the Execution step, where the parallel application is executed in the distribution defined in the previous step. The tools used in the methodology were implemented. A set of tests to apply the methodology were made and the results shown that the objectives were reached.

Este trabalho apresenta o desenvolvimento de um gerador de malha de elementos finitos baseado no Algoritmo de Refinamento de Delaunay. O pacote é versátil e pode ser aplicado às malhas seriais e adaptativas ou à decomposição de uma malha inicial grossa ou pré-refinada usando processamento paralelo. O algoritmo desenvolvido trabalha com uma entrada de dados na forma de um gráfico de linhas retas planas. A construção do algoritmo de Delaunay foi baseada na técnica de Watson para a triangulação fronteiriça e nos métodos seqüenciais de Ruppert e Shewchuk para o refinamento com paralelismo. A técnica elaborada produz malhas que mantêm as propriedades de uma triangulação de Delaunay. A metodologia apresentada foi implementada utilizando os conceitos de Programação Orientada a Objetos com o auxílio de bibliotecas de código livre. Aproveitando a flexibilidade de algumas dessas bibliotecas acopladas foi possível parametrizar a dimensão do problema, permitindo gerar malhas seqüenciais bidimensionais e tridimensionais. Os resultados das aplicações em malhas seriais, adaptativas e com programação paralela mostram a eficácia desta ferramenta. Uma versão acadêmica do algoritmo de refinamento de Delaunay bidimensional para o Ambiente Mathematica também foi desenvolvido. / This work presents the development of a finite elements mesh generation based on Delaunay Triangulation Algorithm. The package is versatile and applicable to the serial and adaptable meshes or to either the coarse or pre-refined initial mesh decomposition using parallel computing. The developed algorithm works with data input in the form of Planar Straight Line Graphics. The building of the Delaunay Algorithm was based on the Watson\'s technique for the boundary triangulation and in both Ruppert and Shewchuk sequential methods for the parallel refinement. The proposed technique produces meshes maintaining the properties of the Delaunay triangulation. The presented methodology was implemented using the Programming Object-Oriented concepts, which is supported by open source libraries. Taking advantage of the flexibility of some of those coupled libraries the parametrization of the problem dimension was possible, allowing to generate both two and three-dimensional sequential meshes. The results obtained with the applications in serial, adaptive and in parallel meshes have shown the effectiveness of this tool. An academic version of the twodimensional Delaunay refinement algorithm for the Mathematica Environment was also developed.

Esta Dissertação apresenta um modelo de paralelismo de grão fino para utilização em aplicações baseadas em objetos distribuídos. A pesquisa é desenvolvida sobre o modelo de distribuição de objetos da linguagem DPC++, uma extensão de C++ concebida na Universidade Federal do Rio Grande do Sul. A motivação para o desenvolvimento deste modelo é a crescente disponibilidade de arquiteturas multiprocessadas e de tecnologias de comunicação de alto desempenho, o que permite o aproveitamento eficiente de um nível de concorrência de menor granularidade. O objetivo do trabalho é integrar de forma adequada e eficiente a utilização de tal nível de concorrência no modelo original de distribuição de objetos de DPC++, permitindo que as aplicações desenvolvidas com a linguagem possam explorar ao máximo o poder computacional oferecido pelas arquiteturas citadas. Como principais características, o modelo proposto apresenta a capacidade de concorrência entre os métodos de um mesmo objeto distribuído e a introdução de um mecanismo de sincronização baseado na semântica de monitores. Os resultados obtidos com a implementação de uma aplicação de geração de fractais de Mandelbrot demonstram que, em termos de desempenho, o modelo apresentado efetivamente atinge seus objetivos. Além disso, a extinção a sintaxe original de programação de DPC++ revela importante contribuição no sentido de aumentar o poder de expressão da linguagem para o desenvolvimento de aplicações paralelas. / This Thesis presents a fine-grain concurrency model for applications based on distributed objects. The basis for the development of this research is the model of distribution of objects presented by the language DPC++, an extension of C++ conceived at the Federal University of Rio Grande do Sul. The motivation for the development of this model is the growing availability of multiprocessor architectures and high-performance communication technologies, which allows for the efficient use of a finer grain of concurrency. The purpose of this work is to efficiently integrate such level of concurrency into the original model of distribution of objects of DPC++, making it possible for the applications developed with the language to thoroughly explore the computational power offered by the mentioned architectures. As main features the proposed model presents the possibility of concurrency between the methods of a single distributed object and the introduction of a synchronisation mechanism based on the semantics of monitors. The results obtained with the implementation of aMandelbrot fractal generation application showthat, in relation to performance, the presented model effectively reaches its purposes. In addition, the extension to the original programming sintax of DPC++ reveals an important contribution towards a higher expressivity degree in the development of parallel applications.

Uma metodologia para desenvolvimento de programas paralelos eficientes deve especificar mecanismos capazes de caracterizar o comportamento das aplicações e permitir estudos sobre o desempenho de diferentes modelos de soluções. Nos ambientes distribuídos, em particular, a eficiência da solução também está relacionada a estratégia utilizada na divisão e distribuição do trabalho entre os processos que cooperam na solução do problema. Para abordar estes aspectos, uma metodologia, denominada PEMPIs-Het (Performance Estimation of MPI Programs in Heterogeneous Systems), é especificada e apresentada nesta tese. A metodologia permite a modelagem, avaliação e predição de desempenho de programas paralelos em ambientes homogêneos e heterogêneos. Técnicas de modelagem analítica são utilizadas para representar o comportamento das aplicações no ambiente distribuído. Um modelo gráfico, denominado DP*Graph++, é proposto para ilustrar as principais estruturas do código da aplicação e facilitar análises sobre a complexidade algorítmica do programa. Algumas aplicações são modeladas e a precisão das predições é verificada através de testes experimentais. Os modelos de desempenho permitem uma estimativa pontual para o tempo de execução da aplicação. Entretanto, uma estratégia alternativa, baseada em intervalos de predição, também é discutida e avaliada. Algumas estratégias para balanceamento de carga de aplicações paralelas distribuídas são implementadas e avaliadas. Estasestratégias utilizam informações de um vetor com índices de desempenho (Vector of Relative Performances - VRP), gerados pelos modelos analíticos, para especificar a divisão e distribuição do trabalho. Estes índices caracterizam a capacidade computacional das máquinas. Uma formalização matemática é apresentada para explicar como os índices são determinados. ) Testes experimentais são realizados para verificar a aplicabilidade das estratégias e a eficiência no balanceamento das cargas. / A methodology for developing efficient parallel programs must specify mechanisms capable of characterizing the behavior of applications and allow studies on the performance of different solution models. In distributed environments, in particular, the solution efficiency is also related to strategy adopted in the division and distribution of work among the processes which cooperate in the solution of the problem. To address these issues, a methodology, called PEMPIs-Het (Performance Estimation of MPI Programs in Heterogeneous Systems), is specified and presented in this thesis. The methodology allows performance modeling, evaluation and prediction of parallel programs in homogeneous and heterogeneous environments. Analytical modeling techniques are used to represent the applications behavior in the distributed environment. A graph model, called DP*Graph++, is proposed to illustrate the main structures of the application code and facilitate some analyses about the program algorithmic complexity. Some applications are modeled and the accuracy of predictions is verified by experimental tests. The models allow estimate a punctual performance to the application execution time. Meanwhile, an alternative strategy, based on prediction intervals, is also discussed and evaluated. Some strategies for load balancing of distributed parallel applications are implemented and evaluated. These strategies use information from a vector with performance indexes (Vector of RelativePerformances - VRP), generated by analytical models to specify the division and distribution of work. These indexes characterize the machines computational capacity. A mathematical formalization is presented to explain how the rates are determined. Experimental tests are conducted to verify the applicability and effectiveness of the strategies in load balancing

A computação paralela permite uma série de vantagens para a execução de aplicações de grande porte, sendo que o uso efetivo dos recursos computacionais paralelos é um aspecto relevante da computação de alto desempenho. Este trabalho apresenta uma metodologia que provê a execução, de forma automatizada, de aplicações paralelas baseadas no modelo BSP com tarefas heterogêneas. É considerado no modelo adotado, que o tempo de computação de cada tarefa secundária não possui uma alta variância entre uma iteração e outra. A metodologia é denominada de ASE e é composta por três etapas: Aquisição (Acquisition), Escalonamento (Scheduling) e Execução (Execution). Na etapa de Aquisição, os tempos de processamento das tarefas são obtidos; na etapa de Escalonamento a metodologia busca encontrar a distribuição de tarefas que maximize a velocidade de execução da aplicação paralela, mas minimizando o uso de recursos, por meio de um algoritmo desenvolvido neste trabalho; e por fim a etapa de Execução executa a aplicação paralela com a distribuição definida na etapa anterior. Ferramentas que são aplicadas na metodologia foram implementadas. Um conjunto de testes aplicando a metodologia foi realizado e os resultados apresentados mostram que os objetivos da proposta foram alcançados. / Parallel computing allows for a series of advantages on the execution of large applications and the effective use of parallel resources is an important aspect in the High Performance Computing. This work presents a methodology to provide the execution, in an automated way, of parallel applications based on BSP model with heterogeneous tasks. In this model it is assumed that the computation time between iterations does not have a high variance. The methodology is entitled ASE and it is composed by three stages: Acquisition, Scheduling and Execution. In the Acquisition step, the tasks\' processing time are obtained; In the Scheduling step, the methodology finds the ideal arrangement to distribute the tasks to maximize the execution speed and, simultaneously, minimize the use of resources. This is made using an algorithm developed in this work; and lastly the Execution step, where the parallel application is executed in the distribution defined in the previous step. The tools used in the methodology were implemented. A set of tests to apply the methodology were made and the results shown that the objectives were reached.

A execução de uma aplicação paralela, utilizando grades computacionais, necessita de um ambiente que permita a sua execução, além de realizar o seu gerenciamento, escalonamento e monitoramento. O ambiente de execução deve prover um modelo de processamento, composto pelos modelos de programação e de execução, no qual o objetivo é a exploração adequada das características das grades computacionais. Este trabalho objetiva a proposta de um modelo de processamento paralelo, baseado em variáveis compartilhadas, para grades computacionais, sendo composto por um modelo de execução apropriado para grades e pelo modelo de programação da linguagem paralela CPAR. O ambiente CPAR-Grid foi desenvolvido para executar aplicações paralelas em grades computacionais, abstraindo do usuário todas as características presentes em uma grade computacional. Os resultados obtidos mostram que este ambiente é uma solução eficiente para a execução de aplicações paralelas. / The execution of parallel applications, using grid computing, requires an environment that enables them to be executed, managed, scheduled and monitored. The execution environment must provide a processing model, consisting of programming and execution models, with the objective appropriately exploiting grid computing characteristics. This paper proposes a parallel processing model, based on shared variables for grid computing, consisting of an execution model that is appropriate for the grid and a CPAR parallel language programming model. The CPAR-Grid environment is designed to execute parallel applications in grid computing, where all the characteristics present in grid computing are transparent to users. The results show that this environment is an efficient solution for the execution of parallel applications.

A execução de uma aplicação paralela, utilizando grades computacionais, necessita de um ambiente que permita a sua execução, além de realizar o seu gerenciamento, escalonamento e monitoramento. O ambiente de execução deve prover um modelo de processamento, composto pelos modelos de programação e de execução, no qual o objetivo é a exploração adequada das características das grades computacionais. Este trabalho objetiva a proposta de um modelo de processamento paralelo, baseado em variáveis compartilhadas, para grades computacionais, sendo composto por um modelo de execução apropriado para grades e pelo modelo de programação da linguagem paralela CPAR. O ambiente CPAR-Grid foi desenvolvido para executar aplicações paralelas em grades computacionais, abstraindo do usuário todas as características presentes em uma grade computacional. Os resultados obtidos mostram que este ambiente é uma solução eficiente para a execução de aplicações paralelas. / The execution of parallel applications, using grid computing, requires an environment that enables them to be executed, managed, scheduled and monitored. The execution environment must provide a processing model, consisting of programming and execution models, with the objective appropriately exploiting grid computing characteristics. This paper proposes a parallel processing model, based on shared variables for grid computing, consisting of an execution model that is appropriate for the grid and a CPAR parallel language programming model. The CPAR-Grid environment is designed to execute parallel applications in grid computing, where all the characteristics present in grid computing are transparent to users. The results show that this environment is an efficient solution for the execution of parallel applications.

The Task Scheduling Paradigm is a general technique for leveraging fine and coarse grain parallelism from applications of several domains with minimum impact on code readability, relying on the automatic inference of data dependencies among tasks. The performance of Task Parallel applications is correlated with the speed at which the underlying Task Scheduling System is able to detect such dependencies, something that is critical for fine-granularity workloads, which cannot amortize scheduling overheads with long periods of useful computation. That being the case, several groups have recently been developing FPGA-accelerated Task Scheduling Systems architectures where a software Task Scheduling Runtime is able to offload its bookkeeping computations to an FPGA-based accelerator with the goal of efficiently scheduling fine-grained tasks to CPU cores. Even though these FPGA-accelerated systems offer substantial gains over the software-only baseline, it is also true that FPGA-CPU communication bottlenecks prevent such designs from handling scenarios with either large number of cores or very fine-grained tasks. With that in mind, we proposed the implementation of a Native Task Scheduling System that is, a processor with native support for task scheduling embedded into its architecture with the goal of substantially reducing these overheads. More specifically, this project aimed at embedding the HW logic of Picos, a mature Task Scheduling Accelerator developed by the Barcelona Supercomputing Center (BSC), into Rocket Chip, an open-source, silicon-proven, multi-core implementation of RISC-V. The ISA of the resulting system provides special instructions for Task Applications to interact with this Task Scheduling Logic, ruling out all FPGA-CPU communication latencies. To evaluate the prototype performance, we both (1) adapted Nanos, a mature Task Scheduling runtime, to benefit from the new task-scheduling-accelerating instructions; and (2) developed Phentos, a new HW-accelerated light weight Task Scheduling runtime. Our experiments show that task parallel programs using Nanos-RV the Nanos version ported to our system are on average 2.13 times faster than those being serviced by baseline Nanos, while programs running on Phentos are 13.19 times faster, considering geometric means. Using eight cores, Nanos-RV is able to deliver speedups with respect to serial execution of up to 5.62 times, while Phentos produces speedups of up to 5.72 times. / Paralelismo por Tarefas é uma técnica genérica de extração de paralelismo de granularidade arbitrária aplicável a programas de vários domínios, com mínimo impacto sobre legibilidade de código, baseada na inferência automática de dependências de dados entre tarefas. O desempenho de aplicações paralelas baseadas nesse paradigma depende da velocidade com a qual o runtime de Paralelismo por Tarefas que lhe dá suporte é capaz de detectar tais dependências, fato que é ainda mais crítico para aplicações envolvendo tarefas de granularidade fina, já que nesse cenário o overhead de escalonamento não é amortizado por períodos significativamente maiores de computação útil. Recentemente, diversos grupos têm desenvolvido Sistemas de Suporte a Paralelismo por Tarefas acelerados por FPGAs, os quais são capazes de fazer offload das operações de inferência de dependências para um acelerador em FPGA de modo a melhorar o seu desempenho ao lidar com tarefas de granularidade fina. Por outro lado, ainda que esses sistemas acelerados por FPGA apresentem ganhos substanciais com relação às alternativas baseadas puramente em software, o desempenho dessas soluções é prejudicado por gargalos de comunicação entre a CPU e a FPGA, os quais limitam a capacidade desses sistemas de lidar com cenários envolvendo grande número de núcleos ou tarefas muito finas. Motivados por isso, implementamos um Sistema de Suporte Nativo a Paralelismo por Tarefas isto é, um processador com suporte arquitetural nativo a Paralelismo por Tarefas com o objetivo de reduzir consideravelmente tais overheads de comunicação. Mais especificamente, integramos a lógica em hardware do Picos, um acelerador de Paralelismo por Tarefas desenvolvido pelo Barcelona Supercomputing Center (BSC), ao Rocket Chip, uma implementação multi-core de código livre do RISC-V desenvolvida pela Universidade da Califórnia, Berkeley. O sistema resultante contém em sua ISA (Instruction Set Architecture) as instruções necessárias para que aplicações baseadas em tarefas possam interagir diretamente com essa lógica de escalonamento, minimizando os overheads associados ao uso de runtimes intermediários e eliminando toda a latência de comunicação FPGA-CPU. Para avaliar a performance do protótipo que então se construiu, nós tanto (1) adaptamos o runtime de escalonamento de tarefas Nanos para que ele pudesse ser acelerado pelas novas instruções de escalonamento de tarefas, quanto (2) criamos um novo runtime leve de escalonamento de tarefas a que demos o nome de Phentos. Nossos experimentos mostram que programas baseados em paralelismo por tarefas usando o runtime Nanos-RV a versão do runtime Nanos com suporte ao sistema que produzimos são executados em média 2,13 vezes mais rapidamente do que versões dos mesmos programas utilizando a versão básica do Nanos, enquanto programas executados com o Phentos são em média 13,19 vezes mais rápidos do que suas versões correspondentes baseadas na mesma versão básica do Nanos. Tais valores médios correspondem à média geométrica dos conjuntos de dados pertinentes. Usando oito núcleos, Nanos-RV entrega ganhos de desempenho com relação a execuções seriais de até 5,62 vezes, enquanto Phentos entrega ganhos de até 5,72 vezes.

Este trabalho apresenta o desenvolvimento de um gerador de malha de elementos finitos baseado no Algoritmo de Refinamento de Delaunay. O pacote é versátil e pode ser aplicado às malhas seriais e adaptativas ou à decomposição de uma malha inicial grossa ou pré-refinada usando processamento paralelo. O algoritmo desenvolvido trabalha com uma entrada de dados na forma de um gráfico de linhas retas planas. A construção do algoritmo de Delaunay foi baseada na técnica de Watson para a triangulação fronteiriça e nos métodos seqüenciais de Ruppert e Shewchuk para o refinamento com paralelismo. A técnica elaborada produz malhas que mantêm as propriedades de uma triangulação de Delaunay. A metodologia apresentada foi implementada utilizando os conceitos de Programação Orientada a Objetos com o auxílio de bibliotecas de código livre. Aproveitando a flexibilidade de algumas dessas bibliotecas acopladas foi possível parametrizar a dimensão do problema, permitindo gerar malhas seqüenciais bidimensionais e tridimensionais. Os resultados das aplicações em malhas seriais, adaptativas e com programação paralela mostram a eficácia desta ferramenta. Uma versão acadêmica do algoritmo de refinamento de Delaunay bidimensional para o Ambiente Mathematica também foi desenvolvido. / This work presents the development of a finite elements mesh generation based on Delaunay Triangulation Algorithm. The package is versatile and applicable to the serial and adaptable meshes or to either the coarse or pre-refined initial mesh decomposition using parallel computing. The developed algorithm works with data input in the form of Planar Straight Line Graphics. The building of the Delaunay Algorithm was based on the Watson\'s technique for the boundary triangulation and in both Ruppert and Shewchuk sequential methods for the parallel refinement. The proposed technique produces meshes maintaining the properties of the Delaunay triangulation. The presented methodology was implemented using the Programming Object-Oriented concepts, which is supported by open source libraries. Taking advantage of the flexibility of some of those coupled libraries the parametrization of the problem dimension was possible, allowing to generate both two and three-dimensional sequential meshes. The results obtained with the applications in serial, adaptive and in parallel meshes have shown the effectiveness of this tool. An academic version of the twodimensional Delaunay refinement algorithm for the Mathematica Environment was also developed.

Orientador: Ailton Akira Shinoda / Banca: Sérgio Azevedo de Oliveira / Banca: Carlos Dias Maciel / Resumo: Neste trabalho é revisada a literatura sobre o funcionamento de um sistema de telefonia celular e apresentadas propostas de aplicações de processamento distribuído, baseada em Algoritmos Genéticos na resolução do problema de alocação de canais para o sistema celular. O estudo realizado para a apresentação desta dissertação descreve o modelamento da rede celular em termos de dois operadores genéticos, além disso, são propostas duas técnicas para o problema de alocação de canais em uma rede de telefonia celular. Uma das técnicas trabalha com a compatibilidade eletromagnética, já a outra, trabalha com a mínima relação sinal interferência (SIR). Os resultados das duas técnicas são obtidos de dois algoritmos de processamento distribuído, desenvolvidos em linguagem C e com a biblioteca de programação distribuída (Message Passing Interface - MPI). Os algoritmos propostos, através de uma função objetivo, calculam a alocação sem conflito de canais entre as células, na primeira abordagem satisfazendo a compatibilidade eletromagnética e exigências da demanda de tráfego, e na segunda abordagem satisfazendo a mínima SIR e exigências da demanda de tráfego, ambos otimizando a alocação de canais / Abstract: The literature about the cell phone system functioning and proposals of the distributed processing applications based on Genetic Algorithms in the assigning channels problems resolutions are presented in this study. This dissertation describes the cell phone problems modeling by two genetic operators and proposes two techniques for the telephone network allocation channels problems. One of the techniques works with the electromagnetic compatibility and the other with minimal signal interference ratio (SIR). The results of the two techniques are obtained by two algorithms distributed processing, developed in C language and Message Passing Interface (MPI). The algorithms proposed, by an objective function, calculate the allocation without channels conflict. At first, satisfying the electromagnetic compatibility and traffic demand requirements and then satisfying the minimum SIR and traffic demand requirements, both optimizing the channels allocation / Mestre