[pt] Esse tese apresenta diversas técnicas sobre tecnologia paralela em jogos eletrônicos. A tese inicia apresentando diversas arquiteturas possíveis para um motor de jogos. Uma nova arquitetura é proposta, mais flexível e adequada para processadores do futuro que terão um grau maior de paralelismo. Em seguida, uma nova técnica para processar uma octree, uma estrutura de dados clássica da computação gráfica, é apresentada. As últimas técnicas apresentadas são relacionadas a detecção de colisão. Novas ténicas para processamento de grids hieráquicos e balanceamento de detecção colisãom um conjunto de objetos são apresentadas. / [en] This thesis presents several techniques about parallel technology on electronic games. The thesis begins presenting several possible architectures for a game engine. A new architecture is presented, more flexible and adequate for the processors of the future that will have a higher level of parallelism. Following, a new technique for processing an octree, a classic data structure for computer graphics, is presented. The last techniques presented are related to collision detection. New techniques for processing hierarquical grids and balancing collision detection on a set of objets are presented.

[pt] O objetivo deste trabalho é o de apresentar uma proposta de metodologia para a análise de estruturas pelo Método dos Elementos Finitos, utilizando-se na sua implementação as técnicas de programação orientada a objetos e computação distribuída. A utilização das técnicas de programação orientada a objetos permite a implementação de um código compacto, portável e de fácil adaptação. Para a implementação do código optou-se pela utilização da linguagem C++, que possui os recursos mais importantes da programação orientada a objetos, destacando-se a herança, o polimorfismo e a sobrecarga de operadores, e da biblioteca MPI de computação paralela. Inicialmente serão apresentados os procedimentos necessários à implementação orientada a objetos da análise de estruturas pelo método dos elementos finitos, sendo posteriormente apresentadas às alterações necessárias à inclusão das técnicas de processamento paralelo, empregando-se duas técnicas de paralelização. A grande quantidade de operações matriciais envolvidas na análise de estruturas pelo método dos elementos finitos motivou ainda o desenvolvimento de uma biblioteca de classes para a representação destas operações. Os exemplos apresentados têm a finalidade de verificar a exatidão dos resultados obtidos com o código implementado, e as vantagens de se empregar a programação orientada a objetos e a computação distribuída / [en] This work focuses on a methodology for the analysis of structures based on the Finite Element Method (FEM) using on its implementation object-oriented programming techniques, together with parallel programming. The usage of object-oriented programming techniques allows the implementation of a compact, portable and of easily adaptable source code. The implementation was carried out using C++ language, which has the main features of the object-oriented programming, such as inheritance, polymorphism and operator overloading, and the MPI library for parallel computing. The procedures taken into account on object-oriented implementations for analysis of structures using the Finite Element Method are presented, followed by the modifications needed for including parallel computing, using two strategies. Also, the large amount of matrix operations involved on the structures analysis using Finite Element Method motivated the development of a class library which represents such operations. The examples presented have the purpose of verify the accuracy of the results obtained with the code, and the advantages of the use of object-oriented programming and parallel computing.

[pt] Fluidos são extremamente comuns em nosso mundo e têm papel central em muitos fenômenos naturais. A compreensão de seu comportamento tem importância fundamental em uma vasta gama de aplicações e diversas áreas de pesquisa, da análise de fluxo sanguíneo até o transporte de petróleo, da exploração do fluxo de um rio até a previsão de maremotos, tempestades e furacões. Na simulação de fluidos, a abordagem conhecida como Euleriana é capaz de gerar resultados bastante corretos e precisos, mas as computações envolvidas podem se tornar excessivamente custosas quando há a necessidade de tratar fronteiras curvas e obstáculos com formas complexas. Este trabalho aborda esse problema e apresenta uma técnica Euleriana rápida e direta para simular o escoamento de fluidos em grades estruturadas parametrizadas tridimensionais. O principal objetivo do método é tratar de forma correta e eficiente as interações de fluidos com fronteiras curvas, incluindo paredes externas e obstáculos internos. Para isso, são utilizadas matrizes Jacobianas por célula para relacionar as derivadas de campos escalares e vetoriais nos espaços do mundo e paramétrico, o que permite a resolução das equações de Navier-Stokes diretamente no segundo, onde a discretização do domínio torna-se simplesmente uma grade uniforme. O trabalho parte de um simulador baseado em grades regulares e descreve como adaptá-lo com a aplicação das matrizes Jacobianas em cada passo, incluindo a resolução de equações de Poisson e dos sistemas lineares esparsos associados, utilizando tanto iterações de Jacobi quanto o método do Gradiente Biconjugado Estabilizado. A técnica é implementada na linguagem de programação CUDA e procura explorar ao máximo a arquitetura massivamente paralela das placas gráficas atuais. / [en] Fluids are extremely common in our world and play a central role in many natural phenomena. Understanding their behavior is of great importance to a broad range of applications and several areas of research, from blood flow analysis to oil transportation, from the exploitation of river flows to the prediction of tidal waves, storms and hurricanes. When simulating fluids, the so-called Eulerian approach can generate quite correct and precise results, but the computations involved can become excessively expensive when curved boundaries and obstacles with complex shapes need to be taken into account. This work addresses this problem and presents a fast and straightforward Eulerian technique to simulate fluid flows in three-dimensional parameterized structured grids. The method s primary design goal is the correct and efficient handling of fluid interactions with curved boundary walls and internal obstacles. This is accomplished by the use of per-cell Jacobian matrices to relate field derivatives in the world and parameter spaces, which allows the Navier-Stokes equations to be solved directly in the latter, where the domain discretization becomes a simple uniform grid. The work builds on a regular-grid-based simulator and describes how to apply Jacobian matrices to each step, including the solution of Poisson equations and the related sparse linear systems using both Jacobi iterations and a Biconjugate Gradient Stabilized solver. The technique is implemented efficiently in the CUDA programming language and strives to take full advantage of the massively parallel architecture of today s graphics cards.

[pt] O investimento em infraestrutura computacional para suportar picos de processamento de curta duração ou sazonais pode gerar desperdícios financeiros, em razão de, na maior parte do tempo, estes recursos ficarem ociosos. Além disso, em muitas soluções, o tempo de resposta é crítico para atendimento dos requisitos do negócio, tornando, muitas vezes, a solução economicamente inviável. Neste cenário é fundamental a alocação inteligente de recursos computacionais em função da demanda por processamento, custo desta alocação e requisitos do negócio. A Simulação de Monte Carlo é um método estatístico utilizado para resolver uma ampla gama de problemas científicos e de engenharia. Quando aplicado a problemas reais, muitas vezes apresenta os desafios mencionados. Computação na nuvem surge como uma alternativa para disponibilizar recursos computacionais sob demanda, gerando economia de escala sem precedentes e escalabilidade quase infinita. Ao alinhar uma moderna arquitetura à nuvem é possível encapsular funcionalidades e oferecer um leque de serviços que antes seriam restritos a domínios específicos. Neste trabalho propomos um arcabouço genérico, que permite a disponibilização de um leque de serviços baseados na Simulação de Monte Carlo, fazendo uso racional da elasticidade provida pela nuvem, a fim de alcançar melhores patamares de eficiência e reuso. / [en] The investment in computing infrastructure to attend seasonal demand or processing peak can generate financial waste, because the most of the time these resources are idle. In addition, in many solutions the response time are critical to attend business requirements, which often, turn the solution economically unviable. In this scenario it is essential intelligent allocation of computing resources according to the demand for processing, allocation and cost of business requirements. The Monte Carlo Simulation is a statistical method widely used to solve a wide range of scientific and engineering problems. When applied to real problems usually have the challenges mentioned. Cloud Computing is an alternative to providing on-demand computing resources, generating economies of scale unprecedented and almost infinite scalability. Aligning a modern architecture to the cloud is possible to encapsulate functionality and offer a range of services that would previously have been restricted to specific areas. In this paper we are interested in building a generic framework, that may provide a range of services based on Monte Carlo, make rational use of the elasticity provided by the cloud in order to achieve better levels of efficiency and reuse.

[pt] Sistemas de computação paralelos vêm se tornando pervasivos, sendo usados para interagir com o mundo físico e processar uma grande quantidade de dados de várias fontes. É essencial, portanto, a melhora contínua do desempenho computacional para acompanhar o ritmo crescente da quantidade de informações que precisam ser processadas. Algumas dessas aplicações admitem uma menor qualidade no resultado final em troca do aumento do desempenho de execução. Este trabalho tem por objetivo avaliar a viabilidade de usar métodos de aprendizagem supervisionada para garantir que a técnica de Sincronização Relaxada, utilizada para o aumento do desempenho de execução, forneça resultados dentro de limites aceitáveis de erro. Para isso, criamos uma metodologia que utiliza alguns dados de entrada para montar casos de testes que, ao serem executados, irão fornecer valores representativos de entrada para o treinamento de métodos de aprendizagem supervisionada. Dessa forma, quando o usuário utilizar a sua aplicação (no mesmo ambiente de treinamento) com uma nova entrada, o algoritmo de classificação treinado irá sugerir o fator de relaxamento de sincronização mais adequado à tripla aplicação/entrada/ambiente de execução. Utilizamos essa metodologia em algumas aplicações paralelas bem conhecidas e mostramos que, aliando a Sincronização Relaxada a métodos de aprendizagem supervisionada, foi possível manter a taxa de erro máximo acordada. Além disso, avaliamos o ganho de desempenho obtido com essa técnica para alguns cenários em cada aplicação. / [en] Parallel computing systems have become pervasive, being used to interact with the physical world and process a large amount of data from various sources. It is essential, therefore, the continuous improvement of computational performance to keep up with the increasing rate of the amount of information that needs to be processed. Some of these applications admit lower quality in the final result in exchange for increased execution performance. This work aims to evaluate the feasibility of using supervised learning methods to ensure that the Relaxed Synchronization technique, used to increase execution performance, provides results within acceptable limits of error. To do so, we have created a methodology that uses some input data to assemble test cases that, when executed, will provide input values for the training of supervised learning methods. This way, when the user uses his/her application (in the same training environment) with a new input, the trained classification algorithm will suggest the relax synchronization factor that is best suited to the triple application/input/execution environment. We used this methodology insome well-known parallel applications and showed that, by combining Relaxed Synchronization with supervised learning methods, it was possible to maintain the maximum established error rate. In addition, we evaluated the performance gain obtained with this technique for a number of scenarios in each application.

[pt] A qualidade de vida nos grandes centros urbanos tem sido motivo de preocupação para governantes, empresários e para a população residente em geral. Os serviços de transporte público coletivo exercem papel central nessa discussão, uma vez que determinam, sobretudo para aquela camada da sociedade de menor poder aquisitivo, o tempo desperdiçado diariamente em seus deslocamentos. Nas metrópoles brasileiras, os ônibus municipais são predominantes no transporte coletivo. Os usuários deste serviço – passageiros – não dispõem de informações atualizadas sobre os ônibus e linhas de ônibus em operação. Oferecer essa natureza de informação contribui para uma melhor experiência de uso diário deste modal e, consequentemente, proporciona maior qualidade de vida aos seus usuários. Em uma visão mais abrangente, os ônibus podem ser considerados sensores que viabilizam a compreensão dos padrões e identificação de anomalias no tráfego de veículos nas áreas urbanas, possibilitando galgar benefícios para toda população. O presente trabalho apresenta uma plataforma na nuvem que captura, enriquece, armazena e disponibiliza os dados dos dispositivos de GPS instalados nos ônibus, permitindo a extração de conhecimento a partir deste valioso e volumoso conjunto de informações. Experimentos são realizados com os ônibus do Município do Rio de Janeiro, com aplicações focadas no passageiro e na sociedade. As metodologias, discussões e técnicas empregadas ao longo do trabalho poderão ser reutilizados para diferentes cidades, modais e perspectivas. / [en] The quality of life in urban centers has been a concern for governments, business and the resident population in general. Public transportation services perform a central role in this discussion, since they determine, especially for that layer of lower-income society, the time wasted daily in their movements. In Brazilian cities, city buses are predominant in public transportion. Users of this service - passengers - do not have updated information of buses and lines. Offer this kind of information contributes to a better everyday experience of this modal and therefore provides greater quality of life for its users. In a broader view, the bus can be considered sensors that enable the understanding of the patterns and identify anomalies in vehicle traffic in urban areas, allowing benefits for the whole population. This work presents a platform in the cloud computing environment that captures, enriches, stores and makes available the data from GPS devices installed on buses, allowing the extraction of knowledge from this valuable and voluminous set of information. Experiments are performed with the buses of the Municipality of Rio de Janeiro, with applications focused on passenger and society. The methodologies, discussions and techniques used throughout the work can be reused for different cities, modal and perspectives.

[pt] Métodos computacionais em engenharia são usados na solução de problemas físicos que não possuem solução analítica ou sua perfeita representação matemática é inviável. Técnicas de métodos numéricos, incluindo o amplamente usado método dos elementos finitos, podem exigir a solução de sistemas lineares com centenas de milhares de equações, demandando altos recursos computacionais (memória e tempo). Nesta tese, nós apresentamos um sistema baseado em plugins para análise numérica em larga escala. O sistema é usado como uma ferramenta original na solução de problemas de otimização topológica usando o método dos elementos finitos com milhões de elementos. Nossa estratégia utiliza uma técnica elemento-por-elemento para implementar um código altamente paralelo para um solver iterativo com baixo consumo de memória. Além disso, a abordagem de plugin proporciona um ambiente completamente flexível e fácil de estender, onde diferentes aplicações, exigindo diferentes tipos de elementos finitos, materiais, solvers lineares e formulações podem ser desenvolvidos e melhorados. O kernel do sistema é mínimo, com apenas um módulo gerenciador de plugin, responsável por carregar os plugins desejados em tempo real usando um arquivo de configuração de entrada. Todas as funcionalidades necessárias para uma determinada aplicação são definidas dentro dos plugins, sem a necessidade de mudar o kernel. Plugins podem disponibilizar ou exigir interfaces adicionais especializadas, onde outros plugins podem ser conectados para compor um sistema mais complexo e completo. Nós apresentamos resultados para uma análise estrutural estática linear elástica e para uma análise estrutural de otimização topológica. As simulações utilizam elementos Q4, hexagonal (Brick8) e prisma hexagonal (Honeycomb), com solvers diretos e iterativos usando computação sequencial, paralela e distribuída. Nós investigamos o desempenho com relação ao uso de memória e escalabilidade da solução para problemas com diferentes tamanhos, de exemplos pequenos a muito grandes em apenas uma máquina e em um cluster. Foi simulado um exemplo de análise estática linear elástica com 500 milhões de elementos em 300 máquinas. / [en] Computational methods in engineering are used to solve physical problems that do not have analytical solution or their perfect mathematical representation is unfeasible. Numerical techniques, including the largely used finite element method, require the solution of linear systems with hundreds of thousands equations, demanding high computational resources (memory and time). In this thesis, we present a plugin-based framework for large-scale numerical analysis. The framework is used as an original tool to solve topology optimization problems using the finite element method with millions of elements. Our strategy uses an element-by-element technique to implement a highly parallel code for an iterative solver with low memory consumption. Besides, the plugin approach provides a fully flexible and easy to extend environment, where different types of applications, requiring different types of finite elements, materials, linear solvers, and formulations, can be developed and improved. The kernel of the framework is minimum with only a plugin manager module, responsible to load the desired plugins during runtime using an input configuration file. All the features required for a specific application are defined inside plugins, with no need to change the kernel. Plugins may provide or require additional specialized interfaces, where other plugins may be connected to compose a more complex and complete system. We present results for a structural linear elastic static analysis and for a structural topology optimization analysis. The simulations use elements Q4, hexahedron (Brick8), and hexagonal prism (Honeycomb), with direct and iterative solvers using sequential, parallel and distributed computing. We investigate the performance regarding the use of memory and the scalability of the solution for problems with different sizes, from small to very large examples on a single machine and on a cluster. We simulated a linear elastic static example with 500 million elements on 300 machines.