O crescimento explosivo no número de usuários de Internet levou arquitetos de software a reavaliarem questões relacionadas à escalabilidade de serviços que são disponibilizados em larga escala. Projetar arquiteturas de software que não apresentem degradação no desempenho com o aumento no número de acessos concorrentes ainda é um desafio. Neste trabalho, investigamos o impacto do sistema operacional em questões relacionadas ao desempenho, paralelização e escalabilidade de jogos interativos multi-usuários. Em particular, estudamos e estendemos o jogo interativo, multi-usuário, QuakeWorld, disponibilizado publicamente pela id Software sob a licença GPL. Criamos um modelo de paralelismo para a simulação distribuída realizada pelo jogo e o implementamos no servidor do QuakeWorld com adaptações que permitem que o sistema operacional gerencie de forma adequada a execução da carga de trabalho gerada. / The explosive growth in the number of Internet users made software architects reevaluate issues related to the scalability of services deployed on a large scale. It is still challenging to design software architectures that do not experience performance degradation when the concurrent access increases. In this work, we investigate the impact of the operating system in issues related to performance, parallelization, and scalability of interactive multiplayer games. Particularly, we study and extend the interactive, multiplayer game QuakeWorld, made publicly available by id Software under GPL license. We have created a new parallelization model for Quake\'s distributed simulation and implemented that model in QuakeWorld server with adaptations that allows the operating system to manage the execution of the generated workload in a more convenient way.

A CromoDinâmica Quântica (QCD) é a teoria quântica de campos que descreve as interações fortes entre quarks, que são os constituintes fundamentais das partículas do núcleo atômico. Devido ao caráter peculiar destas interações, o estudo da QCD não pode ser realizado pelos métodos usuais em teorias quânticas de campos, baseados em expansões perturbativas. O estudo não-perturbativo da QCD a partir de primeiros princípios torna-se possível através da formulação de rede da teoria, que equivale a um modelo de mecânica estatística clássica, para o qual podem ser realizadas simulações numéricas através de métodos de Monte Carlo. A área de simulações numéricas da QCD representa uma das maiores aplicações atuais da computação de alto desempenho, sendo realizada nos principais centros computacionais do mundo. As grandes exigências do trabalho de pesquisa nesta área contribuíram inclusive para o desenvolvimento de novas arquiteturas computacionais. O uso de processamento paralelo é vital nessas simulações, principalmente nos casos em que está envolvida a simulação da chamada QCD completa, onde se consideram os efeitos dos quarks dinâmicos. Vários pacotes contendo implementações de algoritmos para o estudo da QCD começam a ser disponibilizados por grupos de pesquisa na área. Nosso foco neste trabalho é voltado para o pacote MILC. Além de fazer uma descrição detalhada da forma de utilização deste pacote, realizamos aqui um acompanhamento da evolução dos métodos empregados, desde o Método de Monte Carlo aplicado no algoritmo de Metropolis até a elaboração do algoritmo RHMC, introduzido recentemente. Fazemos uma comparação de e_ciência entre o RHMC e o algoritmo R, que foi o mais utilizado por décadas. / Quantum ChromoDinamics (QCD) is the quantum field theory that describes the strong interactions between quarks, which are the fundamental constituents of particles in the atomic nucleus. Due to the peculiar characteristic of these interactions, the study of QCD cannot be carried out by usual methods in quantum field theory, which are based on pertubative expansions. The non-pertubative study of QCD from first principles becomes possible through the lattice formulation of the theory, which is equivalent to a classical statistical mechanics model, which in turn can be carried out by numerical simulations using Monte Carlo methods. The field of numerical simulations of QCD is one of the main applications of high performance computing, and is perfomed in most major computational centers around the world. The demanding requirements needed in this field led also to the development of new computational architectures. The use of parallel processing is vital in these types of simulations, especially in cases that involve what is known as full QCD, where the effects of dynamic quarks are taken into account. Several packages with algorithms implemented for the study of QCD have been recently made available by research groups in this field. The focus of this work is the MILC package. Here we make a detailed description of how to use this package and a follow up of the used methods, from the Monte Carlo method applied in the Metropolis algorithm up to the development of the RHMC algorithm, recently introduced. Comparisons are made between the e_ciency of RHMC and the R algorithm, which was the most used in the past decades.

El desarrollo de una herramienta computacional basada en el método de elementos finitos (FEM) para modelar numéricamente el proceso de transporte de pulpas minerales en tuberías circulares horizontales es el tema principal en este trabajo. Las pulpas minerales son consideradas aquí como un fluido monofásico con propiedades reológicas de fluidos no Newtonianos. La herramienta computacional es implementada siguiendo un paradigma de programación orientada a objetos, usando C++ como lenguaje de programación principal, y una metodología de descomposición de dominio para su paralelización. La referida herramienta es validada realizando simulaciones numéricas de múltiples casos de estudio involucrando flujos de fluidos Newtonianos y no Newtonianos. En esta etapa de validación, errores máximos de 3% en tuberías circulares horizontales transportando pulpas minerales reales son obtenidos. Luego de ser validada, la herramienta computacional es utilizada para estudiar parámetros importantes en el diseño de sistemas de transporte de pulpas minerales. Más específicamente, parámetros relativos a la viscosidad, grado de concentración de partículas, velocidad de la fase continua y caída de presión son particularmente analizados. El principal aporte de este trabajo es el desarrollo de una nueva herramienta computacional basada en FEM para modelar adecuadamente flujos viscosos no Newtonianos, permitiendo resolver problemas prácticos de diseño de tuberías circulares horizontales transportando pulpas minerales reales. Además, comparado con otros enfoques paralelos reportados en la literatura, el utilizado aquí es relativamente fácil de implementar en herramientas de dinámica de fluidos computacional. Así, otra de las contribuciones de este trabajo es el desarrollo de un algoritmo en paralelo adecuado para herramientas basadas en FEM que modelen pulpas minerales. Finalmente, otra de las contribuciones de este trabajo está asociada con el estudio numérico por primera vez de pulpas minerales reales recientemente caracterizadas en la literatura.

É notório que o emprego de unidades de processamento gráfico (GPU) pode acelerar significativamente métodos numéricos de aplicações científicas. Para suportar essa nova tecnologia, é necessário que programas sejam readaptados, exigindo flexibilidade do código. Nesse trabalho, é apresentada a arquitetura de um programa de elementos finitos (MEF) para a análise de estruturas, com suporte ao processamento em GPU. A orientação a objetos é usada para guiar o desenvolvimento e modelar o código em uma estrutura flexível. A escalabilidade do programa é dada pela extensão de suas funcionalidades através de componentes carregados em tempo de execução. Para ilustrar a robustez do código, o software é aplicado para o estudo de dinâmica estrutural, considerando aspectos complexos de não linearidade de material (plasticidade) e geometria (grandes deslocamentos). A acurácia do código é verificada através da comparação com problemas conhecidos da literatura e com as soluções MEF comerciais (ABAQUS). As comparações mostraram uma boa concordância nos resultados. O speedup da GPU é analisado em relação aos tempos de CPU do próprio programa, sendo observado ganhos de desempenho de até 10 vezes. / It has been recognized that the adoption of graphics processing units (GPU) can significantly boost numerical methods in scientific applications. In order to support such technology, it is necessary to readapt the program, which requires code flexibility. In this work, it is presented the architecture of a finite element (FEM) analysis program for structural analysis with GPU support. Object-oriented design is used to guide development and to build code into a flexible structure. Program scalability is achieved by extensibility of its features, provided by run-time loaded components. In order to demonstrate code robustness, the software is directed to the study of structural dynamics, considering complex non-linear aspects of material (plasticity) and geometry (large displacements). Code accuracy is checked by comparing with known literature problems and with commercial solver packages (ABAQUS). The comparison shows good agreement in the results. The GPU code speedup is analysed against timings of CPU program code, where it is observed performance gain up to 10 times.

Teste de software desempenha um papel fundamental no processo de produção de um produto de software de qualidade. Com o passar dos anos, diversas técnicas e critérios de teste de software foram desenvolvidos a fim de estabelecer meios e métricas para guiar a criação de casos de teste efetivos, capazes de evidenciar defeitos no produto avaliado. Dentre os principais critérios para teste de software está o Teste de Mutação, que foi amplamente difundido e é tido como uma das abordagens mais eficazes para guiar a criação de conjuntos de casos de teste capazes de revelar defeitos em software. Entretanto, à medida que esse critério possui uma grande efetividade para revelar defeitos, ele peca pelo baixo poder de escalabilidade, o que acaba comprometendo diretamente a sua capacidade de aplicação. Neste sentido, diversos estudos foram desenvolvidos nesta área dedicando-se a aprimorar o seu desempenho e torná-lo uma alternativa viável para aplicação durante a fase de teste de software. Este trabalho apresenta indícios de que a utilização de estruturas complexas de processamento pode apoiar a aplicação do Teste de Mutação. Para tal, foi concebida uma arquitetura que possibilite a aplicação do Teste de Mutação em paralelo. Após a implementação da arquitetura foram avaliados cinco algoritmos de balanceamento de carga responsáveis por controlar a distribuição e execução do Teste de Mutação. Durante a avaliação experimental da arquitetura e dos algoritmos, observou-se que nos piores cenários avaliados foi possível atingir um ganho de desempenho acima de 70% em relação à aplicação sequencial convencional do Teste de Mutação enquanto nos melhores cenários o ganho de desempenho foi acima 95%, contudo, necessitando utilizar-se de uma infraestrutura mais robusta para a execução da arquitetura. / Software testing plays a fundamental role in the development process of quality software systems. Over the years, many software testing techniques and criteria were developed to provide means and metrics to guide the development of effective test cases, able to find defects on the product being assessed. Among major criteria for software testing is the mutation testing, which was broadly broadcast and is likely one of the most effective approaches for creating sets of test cases able to uncover software bugs. However, although mutating testing has a great effectiveness to uncover defects in a product, it suffers from low scalability, which directly compromises its applicability. In this sense, many studies were developed in this area aiming at improving the performance of that criterion and make it a viable alternative for its application throughout the software testing process. This work presents evidence that the use of complex structures of processing can support mutation testing application. For this, it was established an architecture that enables mutation testing to be performed in parallel. After implementing the architecture, five load balance algorithms to controlling the distribution and execution of mutation testing were analyzed. During the experimental evaluation of the architecture and algorithms, it was observed that in the worst evaluated scenarios it was possible to reach a gain in performance of up to 70% in comparison to the conventional application (sequential). In the best scenarios the gain was over 95% in exchange of using a more robust infrastructure for the execution of the architecture.

Aplicações podem apresentar laços perfeitamente aninhados que demandam um alto poder de processamento. Diversas aplicações científicas contêm laços aninhados em suas estruturas. Tais laços podem processar computações heterogêneas. Uma solução para reduzir o tempo de execução desta classe de aplicações é a paralelização destes laços. A heterogeneidade dos tempos de execução de computações presentes nas iterações de laços perfeitamente aninhados demanda uma paralelização adequada visando uma distribuição de carga homogênea entre os recursos computacionais para reduzir a ociosidade de tais recursos. Esta heterogeneidade implica em um número ideal de recursos computacionais a partir do qual, o seu aumento não impactaria no ganho de desempenho, uma vez que, o tempo mínimo possível é o tempo de execução da tarefa que consome o maior tempo de processamento. Neste trabalho é proposta uma metodologia e ferramentas para paralelização de laços perfeitamente aninhados sem dependência de dados e com processamento heterogêneo em sistemas paralelos e distribuídos. A implementação da metodologia proposta em aplicações melhora o desempenho da execução e reduz a ociosidade dos recursos de processamento. Na metodologia proposta, alguns procedimentos são apoiados por ferramentas desenvolvidas para auxiliá-los. O sistema de processamento poderá ser: um computador Multicore, um Cluster real ou virtual alocado na nuvem. Resultados experimentais são apresentados neste trabalho. Tais resultados mostram a viabilidade e eficiência da metodologia proposta. / Applications may have nested perfectly loops that require a high processing power. Various scientific applications contain nested loops in their structures. Such loops can process heterogeneous computations. A solution to reduce the execution time of this class of applications is the parallelization of these loops. The heterogeneity of the execution times of computations present in the iterations of nested perfectly loops demands an adequate parallelization aiming at a homogeneous load distribution among the computational resources to reduce the idleness of such resources. This heterogeneity implies an ideal number of computational resources which, its increase would not impact the performance gain, since the minimum possible time is the execution time of the task that consumes the longest processing time. In this work is proposed a methodology and tools for parallelization of loops perfectly nested with heterogeneous processing in parallel and distributed systems. The implementation of proposed methodology in application improves execution performance and reduce idles of the processing resources. In the methodology proposed, some procedures are supported by tools developed to assist them. The processing system can be: a computer multicore, a cluster real or virtual allocated in cloud. Experimental results are presented in this work. These results show the feasibility and efficiency of the proposed methodology.

No desenvolvimento de códigos paralelos, a biblioteca PETSc se destaca como uma ferramenta prática e útil. Com o uso desta ferramenta, este trabalho apresenta um estudo sobre resolvedores de sistemas lineares aplicados a escoamentos incompressíveis de fluidos em microescala, além de uma análise de seu comportamento em paralelo. Após um estudo dos diversos aspectos dos métodos de fronteira imersa, é apresentado um método de fronteira imersa paralelo de primeira ordem. Na sequência, é apresentada uma proposta de melhoria na precisão do método, baseada na minimização da distância entre a condição de contorno exata e aproximada, no sentido de mínimos quadrados. O desenvolvimento de uma ferramenta paralela eficiente é demonstrado na solução numérica de problemas envolvendo escoamentos incompressíveis de fluidos viscosos com fronteiras imersas / In the development of parallel codes, PETSc library has an important position as a practical and useful tool. With this tool, this work presents a study about linear system solvers applied to incompressible flow in microscale problems, furthermore an analysis of the parallel behavior of these methods is presented. After a study of several aspects of immersed boundary methods, and taking advantage of the flexibility of PETSc, a parallel first order immersed boundary method is presented. Thereafter, an improvement in the accuracy of the method is presented, based on the minimization of the distance between exact and approximated boundary conditions, in the least square sense. The development of a parallel and efficient tool is demonstrated in the numerical solution of incompressible viscous flow problems with immersed boundary

As proteínas são moléculas presentes nos seres vivos e essenciais para a vida deles. Para entender a função de uma proteína, devese conhecer sua estrutura tridimensional (o posicionamento correto de todos os seus átomos no espaço). A partir da estrutura de uma proteína vital de um organismo causador de uma doença é possível desenvolver fármacos para o tratamento da doença. Para encontrar a estrutura de uma proteína, métodos biofísicos, como Cristalografia de Raio-X e Ressonância Nuclear Magnética têm sido empregados. No entanto, o uso desses métodos tem restrições práticas que impedem a determinação de várias estruturas de proteínas. Para contornar essas limitações, métodos computacionais para o problema de predição da estrutura da proteína (PSP, Protein Structure Prediction) têm sido investigados. Várias classes de métodos computacionais têm sido desenvolvidas para o problema de PSP. Entre elas, as abordagens ab initio são muito importantes, pois não utilizam nenhuma informação prévia de outras estruturas de proteínas para fazer o PSP, apenas a sequência de aminoácidos da proteína e o gráfico de Ramachandran são empregados. O PSP ab initio é um problema combinatorial que envolve relativamente grandes instâncias na prática, por exemplo, as proteínas em geral têm centenas ou milhares de variáveis para determinar. Para vencer esse entrave, metaheurísticas como os Algoritmos Genéticos (AGs) têm sido investigados. As soluções geradas por um AG são avaliadas pelo cálculo da energia potencial da proteína. Entre elas, o cálculo da interação da energia de van der Waals é custoso computacionalmente tornando o processo evolutivo do AG muito lento mesmo para proteínas pequenas. Este trabalho investiga técnicas para reduzir significativamente o tempo de execução desse cálculo. Basicamente, foram propostas modificações de técnicas de paralelização utilizando MPI e OpenMP para os algoritmos resultantes. Os resultados mostram que o cálculo pode ser 1.500 vezes mais rápido para proteínas gigantes quando aplicadas as técnicas investigadas neste trabalho / Proteins are molecules present in the living organism and essential for their life. To understand the function of a protein, its threedimensional structure (the correct positions of all its atoms in the space) should be known. From the structure of a vital protein of an organism that causes a human disease, it is possible to develop medicines for treatment of the disease. To find a protein structure, biophysical methods, as Crystallography of X-Ray and Magnetic Nuclear Resonance, have been employed. However, the use of those methods have practical restrictions that impede the determination of several protein structures. Aiming to overcome such limitation, computational methods for the problem of protein structure prediction (PSP) has been investigated. Several classes of computational methods have been developed for PSP. Among them, ab initio approaches are very important since they use no previous information from other protein structure, only the sequence of amino acids of the protein and the Ramachandran graph are employed. The ab initio PSP is a combinatorial problem that involves relatively large instances in practice, i. e. proteins in general have hundreds or thousands of variables to be determined. To deal with such problem, metaheuristics as Genetic Algorithms (GAs) have been investigated. The solutions generated by a GA are evaluated by the calculus of the potencial energies of the protein. Among them, the calculation of the interaction of van der Waals energy is computationally intense making the evolutionary process of a GA very slow even for non-large proteins. This work investigated techniques to significantly reduce the running time for that calculus. Basically, we proposed modifications parallelization of the resultant algorithm using MPI and OpenMP techniques. The results show that such calculus can be 1.500 times faster when applying the techniques investigated in this work for large proteins

[pt] Este trabalho apresenta um novo sistema de renderização distribuída destinado ao uso em agrupamentos de PCs. É feita uma extensão à linha de produção gráfica convencional para uma linha de produção gráfica distribuída, que pelo uso de múltiplas linhas de execução permite paralelizar as operações feitas na CPU, na GPU e na rede que interliga os PCs do agrupamento. Este sistema serviu de base para a implementação e o teste de três arquiteturas para renderização distribuída: uma arquitetura com ordenação no início, uma arquitetura com ordenação no fim para renderização volumétrica e uma arquitetura híbrida que tenta combinar as vantagens da ordenação no início e da ordenação no fim. É apresentado um novo algoritmo de balanceamento de carga baseado nos tempos de renderização do quadro anterior. O algoritmo é de implementação muito simples e funciona bem tanto em aplicações com gargalo na geometria quanto em aplicações com gargalo na rasterização. Este trabalho também propõe uma estratégia de distribuição de trabalho entre os computadores de renderização do agrupamento que usa eficientemente os recursos gráficos disponíveis, melhorando assim o desempenho da renderização. Um novo algoritmo de partição paralela do modelo entre os computadores do agrupamento é proposto para a arquitetura híbrida. / [en] This work presents a new distributed rendering system destined for PC clusters. The conventional graphics pipeline is extended to a distributed pipeline that parallelizes the operations done on the CPU, the GPU and the network by using multiple threads. This system was the base for the implementation of three distributed rendering architectures: a sort-first architecture, a sort-last architecture for volume rendering, and a hybrid architecture that seeks to combine the advantages of both sort-first and sortlast architectures. A new load-balancing algorithm based on the rendering times of the previous frame is proposed. The algorithm is very simple to be implemented and works well for both geometry- and rasterization-bound models. A new strategy to assign tiles to rendering nodes is proposed which effectively uses the available graphics resources, thus improving rendering performance. A new parallel model partition algorithm is proposed for the hybrid architecture.

As proteínas são moléculas presentes nos seres vivos e essenciais para a vida deles. Para entender a função de uma proteína, devese conhecer sua estrutura tridimensional (o posicionamento correto de todos os seus átomos no espaço). A partir da estrutura de uma proteína vital de um organismo causador de uma doença é possível desenvolver fármacos para o tratamento da doença. Para encontrar a estrutura de uma proteína, métodos biofísicos, como Cristalografia de Raio-X e Ressonância Nuclear Magnética têm sido empregados. No entanto, o uso desses métodos tem restrições práticas que impedem a determinação de várias estruturas de proteínas. Para contornar essas limitações, métodos computacionais para o problema de predição da estrutura da proteína (PSP, Protein Structure Prediction) têm sido investigados. Várias classes de métodos computacionais têm sido desenvolvidas para o problema de PSP. Entre elas, as abordagens ab initio são muito importantes, pois não utilizam nenhuma informação prévia de outras estruturas de proteínas para fazer o PSP, apenas a sequência de aminoácidos da proteína e o gráfico de Ramachandran são empregados. O PSP ab initio é um problema combinatorial que envolve relativamente grandes instâncias na prática, por exemplo, as proteínas em geral têm centenas ou milhares de variáveis para determinar. Para vencer esse entrave, metaheurísticas como os Algoritmos Genéticos (AGs) têm sido investigados. As soluções geradas por um AG são avaliadas pelo cálculo da energia potencial da proteína. Entre elas, o cálculo da interação da energia de van der Waals é custoso computacionalmente tornando o processo evolutivo do AG muito lento mesmo para proteínas pequenas. Este trabalho investiga técnicas para reduzir significativamente o tempo de execução desse cálculo. Basicamente, foram propostas modificações de técnicas de paralelização utilizando MPI e OpenMP para os algoritmos resultantes. Os resultados mostram que o cálculo pode ser 1.500 vezes mais rápido para proteínas gigantes quando aplicadas as técnicas investigadas neste trabalho / Proteins are molecules present in the living organism and essential for their life. To understand the function of a protein, its threedimensional structure (the correct positions of all its atoms in the space) should be known. From the structure of a vital protein of an organism that causes a human disease, it is possible to develop medicines for treatment of the disease. To find a protein structure, biophysical methods, as Crystallography of X-Ray and Magnetic Nuclear Resonance, have been employed. However, the use of those methods have practical restrictions that impede the determination of several protein structures. Aiming to overcome such limitation, computational methods for the problem of protein structure prediction (PSP) has been investigated. Several classes of computational methods have been developed for PSP. Among them, ab initio approaches are very important since they use no previous information from other protein structure, only the sequence of amino acids of the protein and the Ramachandran graph are employed. The ab initio PSP is a combinatorial problem that involves relatively large instances in practice, i. e. proteins in general have hundreds or thousands of variables to be determined. To deal with such problem, metaheuristics as Genetic Algorithms (GAs) have been investigated. The solutions generated by a GA are evaluated by the calculus of the potencial energies of the protein. Among them, the calculation of the interaction of van der Waals energy is computationally intense making the evolutionary process of a GA very slow even for non-large proteins. This work investigated techniques to significantly reduce the running time for that calculus. Basically, we proposed modifications parallelization of the resultant algorithm using MPI and OpenMP techniques. The results show that such calculus can be 1.500 times faster when applying the techniques investigated in this work for large proteins