Este trabalho contribui na busca de soluções para o problema de auxílio à programação paralela, apresentando uma abordagem orientada a objetos, como base para a construção de uma ferramenta que dá apoio ao desenvolvimento de programas paralelos. Diversas ferramentas com propostas análogas sac revisadas e suas características principais são destacadas, visando a busca de um modelo adequado para a ferramenta a ser proposta. A ferramenta desenvolvida, implementada e validada neste trabalho (FAPP - Ferramenta de Auxílio à Programação Paralela) baseia-se na tecnologia de orientação a objetos. A teoria dos grafos, modelada segundo a orientação a objetos, serve de base para a criação de modelos tanto para arquiteturas paralelas (hardware) como para programas paralelos (software). Os modelos criados para o hardware e software, permitem ao programador criar o ambiente para a programação, definindo a sua arquitetura paralela, os processos componentes de seu programa e o mapeamento lógico desses processos nos processadores. A ferramenta FAPP gera automaticamente o esqueleto para a aplicação paralela. Todo o desenvolvimento efetuado e validado através de uma implementação básica da ferramenta e são apresentadas às diretrizes para futuras extensões, visando outros ambientes de hardware e software, bem como melhoramentos objetivando futuros trabalhos / This work contributes to the solution of the parallel programming supporting problem, by proposing an object-oriented approach as the basis for building a tool to help the development of parallel programs. Several tools with similar goals are revised and their main features are highlighted aiming the search of an adequate model for the supporting tool to be developed. The tool developed, implemented and validated in this work (FAPP - Parallel Programming Supporting Tool) is based on the object orientation technology. The graph theory was modeled according to the object-orientation and used as the basis for the creation of models for both parallel architectures (hardware) and parallel programs (software). This allows the programmer to create the programming environment by defining his parallel architecture, the program processes and the logical mapping of the processes on the processors. The FAPP tool automatically generates the skeleton for the parallel application. The work is validated by means of a basic implementation of the tool. The guidelines for future extensions aiming other hardware and software environments as well as for future works are presented

Orientador: Celso Pascoli Bottura / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T16:26:46Z (GMT). No. of bitstreams: 1 DelRealTamariz_Annabell_M.pdf: 3597782 bytes, checksum: e6939ad8e71833c059fabea6a51ca5c6 (MD5) Previous issue date: 1999 / Resumo: Uma proposta de metodologia para a solução da Equação Algébrica de Riccati (EAR) em formas Seqüencial e Paralela e Distribuída é apresentada. O método modifica e propõe uma paralelização do Método de Schur. Transformações de Similaridade Elementares Estabilizadas (TSEE) são utilizadas para transformar a matriz simplética/Hamiltoniana, em uma forma simples. Neste trabalho fazemos uma implementação seqüencial do algoritmo proposto para matrizes densas, bem condicionadas e propomos uma implementação paralela do algoritimo num sistema com memória distribuída e estratégia de paralelização síncrona numa rede de estações de trabalho / Abstract: A proposal of methodology for solving the Algebraic Riccati Equation in Sequential and Parallel and Distriuted forms is presented. The method modifies and proposes a parallelization for the Schur Method. To transform the simpletyc/Hamiltonian matrix in a simple form, Elementary Stabilized Similarity Transformations are utilized. In this work a sequential implementation of the proposed algorithm for dense, well conditioned matrices is made and a parallel implementation on a distributed memory system with a synchronous parallelization strategy over a workstation network is proposed. / Mestrado / Mestre em Engenharia Elétrica

Orientadores: Guido Costa Souza de Araújo, Rodolfo Jardim de Azevedo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T12:44:05Z (GMT). No. of bitstreams: 1 Wottrich_RodolfoGuilherme_M.pdf: 2132128 bytes, checksum: b8ac1197909b6cdaf96b95d6097649f3 (MD5) Previous issue date: 2014 / Resumo: A busca por paralelismo sempre foi um importante objetivo no projeto de sistemas computacionais, conduzida principalmente pelo constante interesse na redução de tempos de execução de aplicações. Programação paralela é uma área de pesquisa ativa, na qual o interesse tem crescido devido à emergência de arquiteturas multicore. Por outro lado, aproveitar as grandes capacidades de computação e armazenamento da nuvem e suas características desejáveis de flexibilidade e escalabilidade oferece várias oportunidades interessantes para abordar problemas de pesquisa relevantes em computação científica. Infelizmente, em muitos casos a implementação de aplicações na nuvem demanda conhecimento específico de interfaces de programação paralela e APIs, o que pode se tornar um fardo na programação de aplicações complexas. Para superar tais limitações, neste trabalho propomos OpenMR, um modelo de execução baseado na sintaxe e nos princípios da API OpenMP que facilita a tarefa de programar sistemas distribuídos (isto é, clusters locais ou a nuvem remota). Especificamente, este trabalho aborda o problema de executar a paralelização de laços, usando OpenMR, em um ambiente distribuído, através do mapeamento de iterações do laço para nós MapReduce. Assim, a interface de programação para a nuvem se torna a própria linguagem, livrando o desenvolvedor da tarefa de se preocupar com detalhes da distribuição de cargas de trabalho e dados. Para avaliar a validade da proposta, modificamos benchmarks da suite SPEC OMP2012 para se encaixarem no modelo proposto, desenvolvemos outros toy benchmarks que são I/O-bound e executamo-os em duas configurações: (a) um cluster de computadores disponível localmente através de uma LAN padrão; e (b) clusters disponíveis remotamente através dos serviços Amazon AWS. Comparamos os resultados com a execução utilizando OpenMP em uma arquitetura SMP e mostramos que a técnica de paralelização proposta é factível e demonstra boa escalabilidade / Abstract: The pursuit of parallelism has always been an important goal in the design of computer systems, driven mainly by the constant interest in reducing program execution time. Parallel programming is an active research area, which has grown in interest due to the emergence of multicore architectures. On the other hand, harnessing the large computing and storage capabilities of the cloud and its desirable flexibility and scaling features offers a number of interesting opportunities to address some relevant research problems in scientific computing. Unfortunately, in many cases the implementation of applications on the cloud demands specific knowledge of parallel programming interfaces and APIs, which may become a burden when programming complex applications. To overcome such limitations, in this work we propose OpenMR, an execution model based on the syntax and principles of the OpenMP API which eases the task of programming distributed systems (i.e. local clusters or remote cloud). Specifically, this work addresses the problem of performing loop parallelization, using OpenMR, in a distributed environment, through the mapping of loop iterations to MapReduce nodes. By doing so, the cloud programming interface becomes the programming language itself, freeing the developer from the task of worrying about the details of distributing workload and data. To assess the validity of the proposal, we modified benchmarks from the SPEC OMP2012 suite to fit the proposed model, developed other I/O-bound toy benchmarks and executed them in two settings: (a) a computer cluster locally available through a standard LAN; and (b) clusters remotely available through the Amazon AWS services. We compare the results to the execution using OpenMP in an SMP architecture and show that the proposed parallelization technique is feasible and demonstrates good scalability / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

A computação paralela tem se estabelecido como uma ferramenta indispensável para conseguir o desempenho esperado em aplicações de muitas áreas científicas. É importante avaliar os fatores que limitam o desempenho de uma aplicação paralela. Este trabalho vem apresentar o desenvolvimento e a implementação de uma ferramenta chamada Hierarchical Analyses que permite o levantamento de dados para análise de fatores de desempenho em programas paralelos de forma hierárquica, ou seja, permite coletar as informações acompanhando o nível de abstração usado pelo programador. Essa ferramenta é composta pelos módulos de coleta e transformação dos dados. O módulo de coleta chamado HieraCollector é responsável por coletar e armazenar os dados em arquivos no formato XML, sendo que o usuário não precisa alterar o código fonte de sua aplicação. O módulo de transformação chamado HieraTransform é reponsável por transformar os dados coletados extraindo medidas que permitam a realização da análise do programa paralelo. Para validação dos módulos de coleta e transformação foi utilizada a biblioteca MPI e o framework OOPS que utiliza orientação a objetos. Outra contribuição deste trabalho, foi o desenvolvimento da ferramenta visual chamada HieraOLAP que auxilia o usuário na análise de desempenho de programas paralelos. / Parallel computing has become an essential tool to achieve the performance needed by many scientific applications. The evaluation of performance factors of parallel applications is of utmost significant. This work presents the developement and implementation of a tool called Hierarchical Analyses which facilitates data collection for performance analysis of parallel programs with hierarchical information, i.e. the information is collected in the various abstraction levels used in the application program. The tool consists of a collection and a transformation modules. The collection module (HieraCollector) collects the data and stores it in XML format. The transformation module (HieraTransform) processes the collected data computing measurements to be used in the analysis of parallel code. To validate the tool, implementations adapted to MPI and the OOPS framework have been developed. Another contribution of this work is the development of a visual tool called HieraOLAP to help the user in the analysis of parallel program performance.

Orientador: Geraldo Francisco Donegá Zafalon / Coorientador: Manoel Ferreira Borges Neto / Banca: Mário Luiz Tronco / Banca: Wladimir Seixas / Resumo: O crescente desenvolvimento tecnológico tem trazido a humanidade grandes benefícios, nas mais diversas áreas. De modo a dar continuidade a esse desenvolvimento, novas frentes de pesquisas vêm surgindo, em busca do domínio dessas tecnologias emergentes. Os limites físicos da computação clássica, baseada nos fenômenos eletromagnéticos, estão sendo alcançados e a computação quântica surge como uma possível solução para esses limites, bem como para apresentar um novo panorama para a computação, devido ao seu grande potencial. A fim de buscar um maior entendimento dos fenômenos que envolvem a computação quântica em uma transmissão de dados, em específico o fenômeno do emaranhamento, no presente trabalho apresenta-se um levantamento teórico sobre mecânica quântica, informação, computação e entropias quânticas, bem como computação paralela e MPI, propondo-se uma simulação com implementação em ambiente paralelo sobre o efeito da entropia de emaranhamento dos fótons em uma transmissão de dados. Além disso, realiza-se a comparação com a implementação em um ambiente de um único processador / Abstract: The increasing technological development has brought great bene ts to humanity, in several areas. In order to continue this development, new research areas are emerging to reach new technologies. The physical limits of classical computing, based on electromagnetic phenomena are being achieved and quantum computing emerges as a possible solution to these limits, as well as to introduce a new scenario for computing, due to its great potential. In order to get a better understanding of phenomena involving quantum computing in a data transmission, in particular the phenomenon of entanglement, this work presents a theoretical quantum mechanics, information, computing and quantum entropies, as well as parallel computing and MPI, proposing a simulation with implementation in parallel environment on the e ect of the entropy of entanglement of photons in data transmission and comparison with implementation in a single processor environment / Mestre

O MPS é um método lagrangeano sem malha para simulação de fluidos, que teve origem para estudos de fluxo incompressíveis com superfície livre. Ele possui diversas vantagens se comparado a métodos convencionais baseados no uso de malha, podendo-se citar como principais a facilidade de representação de interfaces e geometrias complexas, assim como a ausência do termo de convecção nas equações algébricas. Este trabalho foca na aplicação de métodos de computação paralela para simulações de escoamento utilizando a variante explícita do método MPS, denominado E-MPS. O objetivo é a diminuição do tempo de processamento das simulações, e o aumento da quantidade de partículas, que possibilita a simulação de casos cada vez mais complexos, e o real emprego do método para solução de problemas de engenharia. O método proposto consiste de dois níveis de paralelismo: um através de uma decomposição de domínio espacial sobre uma arquitetura de memória distribuída, e outra pelo uso de processamento paralelo em uma arquitetura com memória compartilhada, podendo ser pelo uso de dispositivos Graphics Processing Unit (GPU), ou pelo uso de processadores multicore. Os métodos de decomposição de domínio espacial tratados neste trabalho são o estático, ou não adaptativo, o Orthogonal Recursive Bisection (ORB), o ortogonal e uma nova proposta chamada cell transfer. Dentre os métodos já existentes, o ortogonal se mostrou mais atrativo devido à sua simplicidade, conseguindo manter um melhor nível de balanceamento do que o estático no caso estudado. O novo método cell transfer tenta superar as limitações geométricas dos outros métodos citados, ao levar em consideração a natureza do fluxo. Uma das grandes contribuições deste trabalho é um novo método genérico de comunicação entre subdomínios, que evita a reordenação das partículas, e serve para todos os métodos de decomposição investigadas neste trabalho. / MPS is a meshless lagrangian method for computational fluid dynamics that was created to study incompressible free surface flows and has many advantages compared to traditional mesh based methods, such as the ability to represent complex geometries, interface problems, and the absence of the advection term in the algebraic equations. This work focus on the use of parallel computing methods for fluid dynamic simulation, and more specifically, on the explicit variant of the MPS method, namely E-MPS, to decrease the amount of processing needed to perform a simulation and increase the number of particles, which enables the simulation of real and complex engineering problems. The proposed method is composed of two levels of parallelism: a distributed memory parallelism based on spatial domain decomposition, and a shared memory parallelism, using either GPU or multicore CPUs, for fast computation of each subdomain. Static non-adaptive, ORB, orthogonal, and cell transfer spatial decomposition methods are subject of investigations in this work, the latter being originally proposed by this work to overcome the drawbacks found in most of the methods found in the literature. Among the already proposed methods the more attractive was the orthogonal, due to its simplicity, and capability of maintaining a good load balance in the test case. The new cell transfer method was proposed to overcome the geometrical limitations found in all the above methods, by considering the flux while balancing the load among subdomains. One of the main contributions of this work is a new method for the communication of subdomains, which avoids additional sorting steps, and proved to be generic for all the decomposition methods investigated.

O MPS é um método lagrangeano sem malha para simulação de fluidos, que teve origem para estudos de fluxo incompressíveis com superfície livre. Ele possui diversas vantagens se comparado a métodos convencionais baseados no uso de malha, podendo-se citar como principais a facilidade de representação de interfaces e geometrias complexas, assim como a ausência do termo de convecção nas equações algébricas. Este trabalho foca na aplicação de métodos de computação paralela para simulações de escoamento utilizando a variante explícita do método MPS, denominado E-MPS. O objetivo é a diminuição do tempo de processamento das simulações, e o aumento da quantidade de partículas, que possibilita a simulação de casos cada vez mais complexos, e o real emprego do método para solução de problemas de engenharia. O método proposto consiste de dois níveis de paralelismo: um através de uma decomposição de domínio espacial sobre uma arquitetura de memória distribuída, e outra pelo uso de processamento paralelo em uma arquitetura com memória compartilhada, podendo ser pelo uso de dispositivos Graphics Processing Unit (GPU), ou pelo uso de processadores multicore. Os métodos de decomposição de domínio espacial tratados neste trabalho são o estático, ou não adaptativo, o Orthogonal Recursive Bisection (ORB), o ortogonal e uma nova proposta chamada cell transfer. Dentre os métodos já existentes, o ortogonal se mostrou mais atrativo devido à sua simplicidade, conseguindo manter um melhor nível de balanceamento do que o estático no caso estudado. O novo método cell transfer tenta superar as limitações geométricas dos outros métodos citados, ao levar em consideração a natureza do fluxo. Uma das grandes contribuições deste trabalho é um novo método genérico de comunicação entre subdomínios, que evita a reordenação das partículas, e serve para todos os métodos de decomposição investigadas neste trabalho. / MPS is a meshless lagrangian method for computational fluid dynamics that was created to study incompressible free surface flows and has many advantages compared to traditional mesh based methods, such as the ability to represent complex geometries, interface problems, and the absence of the advection term in the algebraic equations. This work focus on the use of parallel computing methods for fluid dynamic simulation, and more specifically, on the explicit variant of the MPS method, namely E-MPS, to decrease the amount of processing needed to perform a simulation and increase the number of particles, which enables the simulation of real and complex engineering problems. The proposed method is composed of two levels of parallelism: a distributed memory parallelism based on spatial domain decomposition, and a shared memory parallelism, using either GPU or multicore CPUs, for fast computation of each subdomain. Static non-adaptive, ORB, orthogonal, and cell transfer spatial decomposition methods are subject of investigations in this work, the latter being originally proposed by this work to overcome the drawbacks found in most of the methods found in the literature. Among the already proposed methods the more attractive was the orthogonal, due to its simplicity, and capability of maintaining a good load balance in the test case. The new cell transfer method was proposed to overcome the geometrical limitations found in all the above methods, by considering the flux while balancing the load among subdomains. One of the main contributions of this work is a new method for the communication of subdomains, which avoids additional sorting steps, and proved to be generic for all the decomposition methods investigated.

Made available in DSpace on 2013-08-07T18:42:14Z (GMT). No. of bitstreams: 1 000439447-Texto+Completo-0.pdf: 12654350 bytes, checksum: 6b1e68a168b4468adf4d1eba9517ad21 (MD5) Previous issue date: 2012 / This work proposes a Domain-Specific Language for Parallel Patterns Oriented Parallel Programming (LED-PPOPP). Its main purpose is to provide a way to decrease the amount of effort necessary to develop parallel programs, offering a way to guide developers through patterns which are implemented by the language interface. The idea is to exploit this approach avoiding large performance losses in the applications. Patterns are specialized solutions, previously studied, and used to solve a frequent problem. Thus, parallel patterns offer a higher abstraction level to organize the algorithms in the exploitation of parallelism. They also can be easily learned by inexperienced programmers and software engineers. This work carried out a case study based on the Master/Slave pattern, focusing on the parallelization of algorithms for multi-core architectures. The implementation was validated through experiments to evaluate the programming effort to write code in LED-PPOPP and the performance achieved by the parallel code automatically generated. The obtained results let us conclude that a significant reduction in the parallel programming effort occurred in comparison to the Pthreads library utilization. Additionally, the final performance of the parallelized algorithms confirms that the parallelization with LED-PPOPP does not bring on significant losses related to parallelization using OpenMP in most of the all experiments carried out. / Este trabalho propôs uma Linguagem Específica de Domínio de Programação Paralela Orientada a Padrões Paralelos (LED-PPOPP). O principal objetivo é reduzir o esforço e induzir o programador a desenvolver algoritmos paralelos guiando-se através de padrões que são implementados pela interface da linguagem, evitando que ocorram grandes perdas de desempenho nas aplicações. Anteriormente estudados, os padrões são soluções especializadas e utilizadas para resolver um problema frequente. Assim, padrões paralelos são descritos em um alto nível de abstração para organizar os algoritmos na exploração do paralelismo, podendo ser facilmente interpretados por programadores inexperientes e engenheiros de software. Como ponto de partida, este trabalho realizou um estudo de caso baseandose no padrão Mestre/Escravo, focando na paralelização de algoritmos para arquiteturas multi-core. Através de experimentos para medição de esforço e desempenho, a implementação de estudo de caso foi avaliada obtendo bons resultados. Os resultados obtidos mostram que houve uma redução no esforço de programação paralela em relação a utilização da biblioteca Pthreads. Já com relação ao desempenho final das aplicações paralelizadas, foi possível comprovar que a paralelização com LED-PPOPP não acarreta perdas significativas com relação a paralelizações com OpenMP na quase totalidade das aplicações testadas.

Made available in DSpace on 2013-08-07T18:42:58Z (GMT). No. of bitstreams: 1 000424004-Texto+Completo-0.pdf: 1341745 bytes, checksum: 512c3632850f9466f0d8d4864c026768 (MD5) Previous issue date: 2010 / The growing advance in computers processing power provides the means to design and run high performance applications. But depending on the application, there is also the need to efficiently store and access large amounts of data. Applications focused on science, engineering, data mining and simulation of natural events are some examples that require high I/O throughput. Linux clusters and distributed file systems are generally used in these scenarios. However, traditional distributed file systems, like NFS, are not suitable for data-intensive applications. The centralized architecture of such systems limits the performance and scalability of the application. Based on this, several parallel file systems were designed with the purpose of alleviating the bottleneck created in data access. Among these systems is Lustre, a parallel file system widely used by the high performance community. In this work, an evaluation of Lustre on a small scale Linux cluster is carried out. The evaluation aims to identify which factors affect the performance of the parallel file system, and how it behaves under typical parallel applications workloads. The results showed that Lustre is a file system suitable for all the evaluated application classes. However, to achieve good performance processes should try to maximize contiguous access to files. In that way, is possible to take advantage of the optimizations provided by Lustre, like the client cache and read-ahead mechanism. / O crescente avanço na capacidade de processamento dos computadores fornece meios para projetar e executar aplicações com demandas cada vez maiores. Contudo, dependendo da aplicação, há também a necessidade de acessar e armazenar grandes porções de dados de forma eficiente. Aplicações voltadas à ciência, engenharia, mineração de dados e simulações de eventos naturais são alguns exemplos de aplicações que requerem alta vazão de dados. Clusters Linux e sistemas de arquivos distribuídos, geralmente são utilizados nestes cenários. Entretanto, sistemas de arquivos distribuídos ditos tradicionais, como NFS, não são adequados para aplicações intensivas em dados. A arquitetura centralizada limita o desempenho e escala da aplicação. Com base nisso, vários sistemas de arquivos paralelos foram concebidos com o objetivo de amenizar o gargalo criado no acesso aos dados. Dentre esses sistemas, destaca-se o Lustre, sistema de arquivos paralelos amplamente utilizado pela comunidade de alto desempenho. Neste trabalho, realiza-se uma avaliação do Lustre sobre um cluster Linux de pequena escala. A avaliação tem por objetivo identificar quais fatores afetam o desempenho do sistema de arquivos, e como o mesmo se comporta sob cargas de trabalho típicas de aplicações paralelas. Os resultados obtidos mostraram que o Lustre é um sistema de arquivos adequado para todas as classes de aplicações avaliadas. Entretanto, para se obter bom desempenho é importante tornar os acessos, realizados pelos processos, contíguos dentro do arquivo. Dessa forma, é possível aproveitar os recursos fornecidos pelo Lustre, como cache cliente e read-ahead.

Made available in DSpace on 2013-08-07T18:43:16Z (GMT). No. of bitstreams: 1 000397342-Texto+Completo-0.pdf: 6244320 bytes, checksum: 1ad9082d42e6883bb7678a8782a81d49 (MD5) Previous issue date: 2007 / During parallel applications development, besides analysis regarding performance aspects, it is also important to analyze the system's functional properties to assure, for example, that the parallel strategy chosen is adequate for the problem being approached, or that it may converge to an expected result, or even to identify the possibility of a deadlock scenario. The correction guarantee over a parallel application model, besides improving the results reliability, also can be an economic factor, since it allows to reduce the time consumed for the application development and debugging. However, once identi ed the problems and corrections into the model analyzed, there is still the need to map the changes needed to the original application. In this sense, modelchecking and automatic code generation can be used as complementary tools during development, allowing the system behavior analysis and a fast generation of the model's corresponding code. This work presents the use of Object-Based Graph Grammars (OBGG) for parallel applications development, through the de nition of a method to translate OBGG models to C code, using MPI as communication platform. / No desenvolvimento de aplicações paralelas, além da análise de aspectos ligados ao desempenho, torna-se também importante a análise das propriedades funcionais do sistema para garantir, por exemplo, que a estratégia de paralelização escolhida é adequada ao problema sendo abordado, ou que ela pode convergir para um resultado esperado, ou mesmo para identificar a possibilidade de um cenário de bloqueio na computação. A garantia de correção sobre o modelo de uma aplicação paralela, além de aumentar o grau de confiança nos resultados, pode também ser um fator de economia, já que possibilita a redução no tempo despendido no desenvolvimento e depuração da aplicação. Porém, uma vez identificados os problemas e correções no modelo analisado, ainda existe a necessidade de se mapear as mudanças necessárias à aplicação original. Nesse sentido, verificação formal e geração automática de código podem ser utilizadas como ferramentas complementares durante o desenvolvimento, possibilitando tanto a análise do comportamento do sistema quanto a rápida geração do código correspondente ao modelo proposto. Este trabalho apresenta o uso de Gramática de Grafos Baseada em Objetos (GGBO) para a construção de aplicações paralelas, a partir da definição de um método de tradução de modelos GGBO para código C, utilizando MPI como plataforma de comunicação.