Este trabalho aborda alguns conceitos e definições de processamento paralelo, que são aplicados a paralelização automática, e também às análises e condições para as dependências dos dados, de modo a aplicarmos os métodos de paralelização: Hiperplano, Transformação Unimodular, Alocação de Dados Sem Comunicação e Particionamento & Rotulação. Desta forma, transformamos um programa seqüencial em seu equivalente paralelo. Utilizando-os em um sistema de memória distribuída com comunicação através da passagem de mensagem MPI (Message-Passing Interface), e obtemos algumas métricas para efetuarmos as avaliações/comparações entre os métodos. / This work invoke some concepts and definitions about parallel processing, applicable in the automatic parallelization, and also the analysis and conditions for the data dependence, in order to apply the methods for parallelization: Hyperplane, Unimodular Transformation, Communication-Free Data Allocation and Partitioning & Labeling. On this way, transform a sequential program into an equivalent parallel one. Applying these programs on the distributed-memory system with communication through message-passing MPI (Message-Passing Interface), and we obtain some measurements for the evaluations/comparison between those methods.

Empresas estão procurando reduzir seus custos e aumentar seu desempenho e competitividade. Neste cenário de redução de custos, a logística colaborativa pode ser uma aliada. Numa rede complexa, onde embarcadores muitas vezes nem sabem da existência de outros embarcadores com demandas complementares, existe um potencial de sinergia e redução de custos através da diminuição de deslocamentos de veículos sem carga, ou seja, deslocamentos para reposicionar os veículos. Visando essa redução, o Problema de Cobertura de Rotas (PCR), que tem como objetivo cobrir rotas no mínimo custo, une as demandas de frete de vários embarcadores e tenta minimizar os deslocamentos sem cargas (reposicionamentos), reduzindo assim o custo total de toda a rede dos embarcadores envolvidos. Esta pesquisa propõe um modelo e uma heurística para resolver, em grande escala através de programação paralela, uma expansão do PCR. / Companies are looking to reduce costs and improve performance and competitiveness. In this cost-cutting scenario, collaborative logistics can be an ally. In a complex network where shippers often do not know of the existence of other shippers with complementary demands, there is potential for synergy and cost savings by reducing unloaded travelling of vehicles, i.e, the distance and time to reposition the vehicles\'. Towards that reduction, the Lane Covering Problem (LCP), which aims to cover at least cost routeslinks the various shippers\' demands of freight and tries to minimize operations without loads (repositioning), thus reducing the total cost of the entire network for involved shippers. This research proposes a model and an heuristic to solve, in large-scale through parallel programming, an expansion of the PCR.

O Tanque de Provas Numérico (TPN) é um laboratório pioneiro em hidrodinâmica aplicada e fruto de uma colaboração entre a indústria brasileira de petróleo (PETROBRAS S.A.) e as principais instituições de pesquisa do país. Seu principal objetivo é atuar como parceiro da indústria offshore e de petróleo, colaborando para a obtenção da autossuficiência da produção nacional de petróleo como uma poderosa ferramenta para projeto e análise de sistemas flutuantes de produção de óleo e gás. O coração do TPN é um cluster de computadores SMP que é hoje um dos maiores agrupamentos do Brasil para fins de pesquisa. Um dos focos de atenção do TPN é a aplicação do Moving Particles Semi-implicit Method (MPS) na exploração de soluções para muitos problemas de Engenharia. Por trabalhar sem a necessidade do uso de malhas (método tradicional Euleriano), o método tem diversas aplicações na simulação de corpos flutuantes e na hidrodinâmica aplicada, sendo atualmente utilizado para realização de estudos sobre a influência do movimento de ondas em navios; simulações de fenômenos que envolvem fragmentações; superfícies livres; grandes deformações; dinâmica de fluidos em condições extremas, como é o caso em processos prospecção do petróleo onde muitas vezes é difícil e economicamente inviável fazer ensaios físicos. Devido ao grande número de partículas utilizadas na simulação de sistemas complexos pelo método MPS, é necessário aproveitar de forma eficiente os recursos computacionais disponíveis para a análise de modelos com o refinamento adequado às aplicações práticas. Com tera-FLOPS disponíveis na rede cluster do TPN para modelagem computacional, há uma grande necessidade de uma solução computacional paralela altamente escalonável que, além disto, seja fácil de manutenção e extensibilidade. Dentro desta linha de pesquisa, foi desenvolvida uma solução com essas características através do emprego de modernas técnicas de engenharia de software. / The Numerical Offshore Tank (TPN) is a pioneer laboratory in applied hydrodynamics and result of collaboration between the Brazilian oil (Petrobras SA) and the major research institutions in the country. Its main purpose is to act as a partner of industry and offshore oil, contributing to the achievement of self-sufficiency of domestic oil production as a powerful tool for design and analysis of floating production systems for oil and gas. The heart of TPN is a cluster of SMP computers that is now one of the largest groupings of Brazil for research purposes. One focus of attention of TPN is the application of Moving Particles Semi-implicit Method (MPS) in exploring solutions to many engineering problems. By working without the use of mesh (Eulerian traditional method), the method has several applications in the simulation of floating bodies and applied hydrodynamics, currently being used for studies on the influence of the movement of ships in waves; simulations of phenomena involving fragmentation; free surfaces, large deformations; fluid dynamics in extreme conditions, as is the case in processes where petroleum exploration is often difficult and uneconomical to do physical tests. Due to the high number of particles used in the simulation of complex systems by the MPS method, it is necessary to efficiently take advantage of the computational resources available for the analysis of models with the refinement suitable for practical applications. With tera-FLOPS available in the TPN network cluster for computational modeling, there is a great need for a parallel highly scalable solution which, moreover, must be easy maintenance and extensibility. Within this line of research, we developed a solution with these characteristics through the use of modern software engineering techniques.

Com o objetivo de ser portável e eficiente em arquiteturas HPC atuais, a execução de um programa paralelo deve ser adaptável. Este trabalho mostra como isso pode ser atingido utilizando MPI, através de criação dinâmica de processos, integrada com programação Divisão-e-Conquista e uma estratégia Work-Stealing para balancear os processos MPI, em ambientes heterogêneos e/ou dinâmicos, em tempo de execução. Este trabalho explica como implementar uma aplicação segundo o modelo de Divisão-e-Conquista com MPI, bem como a implementação de uma estratégia Work-Stealing. São apresentados resultados experimentais baseados em uma aplicação sintética, o problema das N-Rainhas (N-Queens). Valida-se tanto a adaptabilidade e a eficiência do código. Os resultados mostram que é possível utilizar um padrão amplamente difundido como o MPI, mesmo em plataformas de HPC não tão homogêneas como um cluster. / In order to be portable and efficient on modern HPC architectures, the execution of a parallel program must be adaptable. This work shows how to achieve this in MPI, by the dynamic creation of processes, coupled with Divide-and-Conquer programming and a Work-Stealing strategy to balance the MPI processes, in a heterogeneous and/or dynamic environment, at runtime. The application of Divide and Conquer with MPI is explained, as well as the implementation of a Work-Stealing strategy. Experimental results are provided, based on a synthetic application, the N-Queens computation. Both the adaptability of the code and its efficiency are validated. The results show that it is possible to use widely spread standards such as MPI, even in parallel HPC platforms that are not as homogeneous as a Cluster.

Nos sistemas computacionais atuais, enquanto é necessário explorar a disponibilidade de múltiplos núcleos, também é obrigatório consumir menos energia. Para acelerar o processo de desenvolvimento de aplicações paralelas e o tornar mais transparente ao programador, Interfaces de Programação Paralela (IPPs) são largamente utilizadas. Entretanto, cada IPP implementa diferentes formas para trocar dados usando regiões compartilhadas da memória. Estas regiões são, geralmente, mais distantes do processador do que regiões privadas da memória e, por consequência, possuem maior tempo de acesso e consumo de energia. Ademais, o sistema de memória dos processadores embarcados é diferente em hierarquia, tamanho, tempo de acesso, consumo de energia, etc., quando comparado aos processadores de propósito geral. Assim, considerando o cenário supracitado, com diferentes IPPs sendo utilizadas em sistemas multicore com diferentes requisitos, neste trabalho será mostrado que cada interface possui comportamento diferente em termos de desempenho, consumo de energia e Energy-Delay Product (EDP), e que este comportamento varia de acordo com a característica da aplicação e o processador utilizado (propósito geral ou embarcado). Por exemplo, Pthreads consome 8% menos energia que o melhor caso de OpenMP; 12% menos que MPI-1; e 8% menos que MPI-2, considerando todos os benchmarks no processador Intel Core i7 (propósito geral). Em contrapartida, no processador ARM Cortex-A9 (sistema embarcado), o melhor caso com OpenMP consumiu 2% menos energia que Pthreads; 6% menos que MPI-1; e 15% menos que MPI-2, para o mesmo conjunto de benchmarks. / In current computer systems, while it is necessary to exploit the availability of multiple cores, it is also mandatory to consume less energy. To accelerate the development of parallel applications and to make it more transparent to the programmer, Parallel APIs (Application Programming Interfaces) are widely used. However, each Parallel API implements different ways to exchange data using shared memory regions. These regions are generally more remote than the private ones, and therefore have greater access time and energy consumption. Furthermore, the memory system of embedded processors is different with regard to hierarchy, size, access time, energy consumption, etc., when compared to general purpose processors. Thus, considering the above scenario, with different Parallel APIs being used in multicore systems with different requirements, this work will show that each interface has different behavior in terms of performance, energy consumption and Energy-Delay Product (EDP), and that this behavior varies according to the characteristic of the application and the processor employed (general purpose or embedded). For example, as a result of this work, we have observed that Pthreads consumes 8% less energy than the best case of OpenMP; 12% less than MPI-1; and 8% less than MPI-2, considering all benchmarks on the Intel Core i7 (general purpose). In contrast, in the ARM Cortex-A9 processor (embedded system), the best case with OpenMP consumed 2% less energy than Pthreads; 6% less than MPI-1; and 15% less than MPI-2 for the same benchmarks set.

Esta tese apresenta nossa pesquisa para prover portabilidade de desempenho e escalabilidade para aplicações científicas complexas executadas em plataformas multicore paralelas e hierárquicas. A portabilidade de desempenho é dita como alcançada quando uma pequena ociosidade nas unidades de processamento é obtida para o mapeamento de uma aplicação em diferentes plataformas. A portabilidade de desempenho pode ser afetada por problemas como o desbalanceamento de carga, comunicações custosas e sobrecustos vindos do algoritmo de mapeamento de tarefas. O desbalanceamento de carga é um resultado de comportamentos de cargas de tarefas irregulares e dinâmicas, onde a quantidade de trabalho a ser processado varia dependendo da tarefa e da etapa da simulação. Enquanto isso, comunicações custosas são causadas por uma distribuição de tarefas que não leva em conta os diferentes tempos de comunicações presentes em uma plataforma hierárquica. Isto inclui custos de comunicações não uniformes e assimétricos em níveis de memória e rede. Por fim, os sobrecustos de mapeamento de tarefas vêm do tempo de execução do algoritmo de mapeamento de tarefas tentando mitigar o desbalanceamento de carga e comunicações custosas, além do tempo ligado à migração de tarefas. Nossa abordagem para atingir o objetivo de portabilidade de desempenho é baseada na hipótese de que informações precisas da topologia de máquina podem auxiliar algoritmos de mapeamento em suas decisões. Neste contexto, nós propomos um modelo de topologia de máquina genérico para plataformas paralelas compostas de um ou mais nós de processamento multicore. Ele inclui latências e larguras de banda perfiladas nos níveis de memória e rede, além de salientar assimetrias e não uniformidade em ambos níveis. Estas informações são empregadas pelos nossos três algoritmos de balanceamento de carga cientes da topologia de máquina propostos, chamados NUCOLB, HWTOPOLB e HIERARCHICALLB. Além das informações da topologia, estes algoritmos também utilizam informações da aplicação capturadas durante o tempo de execução. NUCOLB foca nos aspectos não uniformes de plataformas paralelas, enquanto HWTOPOLB considera toda a hierarquia da máquina em suas decisões. HIERARCHICALLB combina estes algoritmos hierarquicamente para reduzir seu sobrecusto de mapeamento de tarefas. Estes algoritmos buscam mitigar o desbalanceamento de carga e comunicações custosas enquanto evitam sobrecustos de migração de tarefas. Resultados experimentais com os balanceadores de carga propostos em diferentes plataformas compostas de um ou mais nós de processamento multicore apresentaram desempenhos superiores a outros algoritmos de balanceamento de carga do estado da arte: NUCOLB apresentou melhorias de até 19% em média; HWTOPOLB demonstrou melhorias de desempenho de 19% em média; e HIERARCHICALLB superou HWTOPOLB em 22% em média em plataformas paralelas com dez ou mais nós de processamento. Estes resultados foram obtidos através da equalização da carga de trabalho entre os recursos disponíveis, redução dos custos de comunicação sentidos pelas aplicações e manutenção de sobrecustos de balanceamento de carga pequenos. Dessa forma, nossos algoritmos de balanceamento de carga proveem portabilidade de desempenho para aplicações científicas enquanto se mantendo independentes de uma aplicação ou arquitetura de sistema específica. / This thesis presents our research to provide performance portability and scalability to complex scientific applications running over hierarchical multicore parallel platforms. Performance portability is said to be attained when a low core idleness is achieved while mapping a given application to different platforms, and can be affected by performance problems such as load imbalance and costly communications, and overheads coming from the task mapping algorithm. Load imbalance is a result of irregular and dynamic load behaviors, where the amount of work to be processed varies depending on the task and the step of the simulation. Meanwhile, costly communications are caused by a task distribution that does not take into account the different communication times present in a hierarchical platform. This includes nonuniform and asymmetric communication costs at memory and network levels. Lastly, task mapping overheads come from the execution time of the task mapping algorithm trying to mitigate load imbalance and costly communications, and from the migration of tasks. Our approach to achieve the goal of performance portability is based on the hypothesis that precise machine topology information can help task mapping algorithms in their decisions. In this context, we proposed a generic machine topology model of parallel platforms composed of one or more multicore compute nodes. It includes profiled latencies and bandwidths at memory and network levels, and highlights asymmetries and nonuniformity at both levels. This information is employed by our three proposed topology-aware load balancing algorithms, named NUCOLB, HWTOPOLB, and HIERARCHICALLB. Besides topology information, these algorithms also employ application information gathered during runtime. NUCOLB focuses on the nonuniform aspects of parallel platforms, while HWTOPOLB considers the whole hierarchy in its decisions, and HIERARCHICALLB combines these algorithms hierarchically to reduce its task mapping overhead. These algorithms seek to mitigate load imbalance and costly communications while averting task migration overheads. Experimental results with the proposed load balancers over different platform composed of one or more multicore compute nodes showed performance improvements over state of the art load balancing algorithms: NUCOLB presented improvements of up to 19% on one compute node; HWTOPOLB experienced performance improvements of 19% on average; and HIERARCHICALLB outperformed HWTOPOLB by 22% on average on parallel platforms with ten or more compute nodes. These results were achieved by equalizing work among the available resources, reducing the communication costs experienced by applications, and by keeping load balancing overheads low. In this sense, our load balancing algorithms provide performance portability to scientific applications while being independent from application and system architecture.

Atualmente, o paradigma multicore é uma tendência fortemente estabelecida também na área de sistemas embarcados. O grau de paralelismo provido por tal arquitetura tem sido a principal causa de avanços de performance na área além de economia de energia e potência. Entretanto, para obter paralelismo eficiente desta arquitetura não é uma tarefa simples. Assim, desenvolvedores propuseram diversos modelos de ambientes de programação tentando prover o máximo de transparência possível. No nível do hardware, este crescente aumento no número de componentes dentro chip cria um problema de gerenciamento a ser tratado. No contexto deste cenário complexo, esta tese propõe o uso de abordagens de gerenciamento de recursos para aumentar a eficiência, levando em consideração tanto performance quanto consumo de energia, de ambientes MPSoC em diferentes níveis. Além disso, estas abordagens tem em comum a noção de clusterização, a qual tenta agregar recursos logicamente de acordo com as demandas da aplicação. Primeiramente no nível do processador/aplicação, é proposto um hardware dinamicamente adaptável para suportar modelos de programação paralelos distintos sem nenhum sobrecusto computacional uma vez que todo o processo é completamente transparente para o programador. Ainda neste ambiente, onde aplicações distintas podem ser executadas, é proposto um mecanismo de escalonamento visando gerenciamento de recursos para aumentar a performance chamado Processor Clustering. São propostas quatro diferentes políticas de mapeamento de recursos que tiram vantagem de aspectos distintos da natureza paralela das aplicações e das restrições arquiteturais do sistema. Entretanto, algumas aplicações tem demandas de memória mais altas do que demandas computacionais. Logo, uma abordagem similar pode ser utilizada no nível da hierarquia de memória. Neste caso, o objetivo é redistribuir recursos de memória de acordo com as demandas da aplicação. Redistribuição de memória é explorada tanto em tempo de projeto quanto em tempo de execução. Um mecanismo de mapeamento de distribuição é proposto baseado na quantidade de requisições de acesso à memória externa. Finalmente, é proposto um mecanismo de tolerância à falhas baseado em gerenciamento de recursos para memórias distribuídas dentro do chip em NoCs. É introduzido um modelo de Reliability Clustering que tira proveito da infraestrutura da NoC. Neste caso, os roteadores tem conhecimento dos blocos com falhas e blocos redundantes. Baseado neste conhecimento, o mecanismo é capaz evitar altas latências de acesso à memória. / The multicore paradigm is a solid trend nowadays, also in the field of embedded systems. The degree of parallelism provided by such architecture has been the foundation of performance advancements in the field as well as for power and energy savings. However, to obtain efficient parallelism of such architecture is not an easy task. Therefore, developers come up with several proposals of programming environments trying to provide as much transparency as possible. On the hardware side, this increasing number of on-chip components creates a management issue to be handled. In the context of this complex scenario this thesis proposes the use of resource management approaches to improve the efficiency, regarding both performance and energy consumption, of MPSoC environments at different levels. Also, these approaches have in common the notion of clustering, which tries to logically aggregate resources according to application demands. First, at the processor/application level, we propose a dynamically adaptable hardware to support distinct parallel programming models at no computational overhead, since the entire process is completely transparent to the programmer. Also, in this environment, where distinct applications can be executed, we propose a resource-aware scheduling mechanism to improve performance named Processor Clustering. We propose four different resource mapping policies that leverage on distinct aspects of the parallel nature of the applications and on architecture constraints. However, some applications have higher memory demands than computational demands. Therefore, a similar approach can be used at the memory level. In this case, we aim at redistributing memory resources according to application demands. We explore memory redistribution at both design time and runtime and propose a distribution mapping mechanism based on the amount of off-chip memory requests. Finally, we propose a resource-aware fault-tolerance mechanism for distributed on-chip memories in NoCs. We introduce a Reliability Clustering model that leverages on the NoC infrastructure. In this case, the routers have knowledge of faulty blocks and redundancy blocks and, based on that, they are able to avoid higher memory access latency.

Made available in DSpace on 2014-06-12T15:57:17Z (GMT). No. of bitstreams: 2 arquivo3157_1.pdf: 3737373 bytes, checksum: 7ca491f9a72f2e9cf51764a7acac3e3c (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Esta dissertação introduz uma estrutura de dados baseada em gride implementada em GPU. Ela foi desenvolvida para pesquisa dos vizinhos mais próximos em nuvens de pontos dinâmicas, de uma forma massivamente paralela. A implementação possui desempenho em tempo real e é executada em GPU, ambas construção do gride e pesquisas dos vizinhos mais próximos (exatos e aproximados). Dessa forma, a transferência de memória entre sistema e dispositivo é minimizada, aumentando o desempenho de uma forma geral. O algoritmo proposto pode ser usado em diferentes aplicações com cenários estáticos ou dinâmicos. Além disso, a estrutura de dados suporta nuvens de pontos tridimensionais e dada sua natureza dinâmica, o usuário pode mudar seus parâmetros em tempo de execução. O mesmo se aplica ao número de vizinhos pesquisados. Uma referência em CPU foi implementada e comparações de desempenho justificam o uso de GPUs como processadores massivamente paralelos. Em adição, o desempenho da estrutura de dados proposta é comparada com implementações em CPU e GPU de trabalhos anteriores. Finalmente, uma aplicação de renderização baseada em pontos foi desenvolvida de forma a verificar o potencial da estrutura de dados

FundaÃÃo de Amparo à Pesquisa do Estado do Cearà / Reduzir a complexidade do software e permitir o desenvolvimento em larga escala de aplicaÃÃes voltados à ComputaÃÃo de Alto Desempenho (CAD) tem exigido o desenvolvimento de ferramentas com potencial capacidade de abstraÃÃo na construÃÃo de sistemas. As tecnologias que envolvem o desenvolvimento de componentes procuram alcanÃar esses requisitos, buscando oferecer suporte a reuso, interoperabilidade, produtividade e maior flexibilidade de manutenÃÃo e desenvolvimento de aplicaÃÃes de alto desempenho. No entanto, conciliar alto poder de abstraÃÃo com alto poder de expressividade na construÃÃo de componentes de aplicaÃÃes nÃo à algo trivial, o que as atuais tecnologias nÃo tÃm conseguido solucionar, uma vez que adotam as tradicionais formas de paralelismo por processos. Diante disso, a plataforma HPE (Hash Programming Environment), baseada no modelo de componentes Hash, tem buscado suportar formas mais gerais de paralelismo, conciliando expressividade com alto poder de abstraÃÃo, uma vez que o modelo Hash à baseado em interesses de software e nÃo em processo, como à feito tradicionalmente. Nesse contexto, esta dissertaÃÃo busca explorar os recursos do HPE, certificando-se de sua viabilidade no contexto de aplicaÃÃes de alto desempenho e validando suas tÃcnicas de programaÃÃo paralela baseadas em componentes. Isso tem resultado em um processo de construÃÃo de aplicaÃÃes cientÃficas sob a abordagem de componentes, tendo como base o conjunto de aplicativos NPB (Nas Parallel Benchmarks), o qual passa por um processo rigoroso de conversÃo para ser suportado pelo HPE. No processo de conversÃo e refatoraÃÃo em componentes, busca-se conservar as estruturas originais do NPB, sem alteraÃÃes significativas nos cÃdigos que declaram e inicializam as estruturas de dados, bem como os que descrevem computaÃÃes, topologia de processos e comunicaÃÃo entre os processos. Para validaÃÃo da plataforma, uma avaliaÃÃo sistemÃtica de desempenho à feita, tendo como princÃpio isolar e mensurar o peso ou o efeito da refatoraÃÃo do NPB em componentes do modelo Hash. / In order to deal with programming-in-the-large requirements in emerging applications of High Performance Computing (HPC), it is still necessary the development of new software development tools for reconciling high level of abstraction, expressiveness and high performance. The technologies behind CBHPC (Component-Based High Performance Computing) target these requirements, looking for reuse of software parts, interoperability across execution platforms, high development productivity and easy maintenance. However, to reconcile high level of abstraction, high performance and high expressiveness for parallel programming models and patterns when building HPC applications is not trivial. For this reason, most of the current technologies fail in this context, since they adopt the traditional process-oriented perspective in the architecture of parallel programs. The HPE platform (Hash Programming Environment) sits on top of the Hash component model to support general forms of parallelism, by combining high expressiveness with high level of abstraction. The Hash component model proposes a concern-oriented perspective to parallel programming, in alternative to the traditional process-oriented approach. In this context, this dissertation is about the efficacy and efficiency of HPE for HPC applications, also validating some of its parallel programming techniques based on components. For that, a set of programs from NPB (NAS Parallel Benchmarks), a widely disseminated collection of benchmarks for evaluating the performance of parallel computing platforms, written in Fortran, C and Java, have been refactored into components aimed at the HPE platform. In such refactoring, the original structure of the benchmarks has been preserved, with minimal changes in the code that declare and initialize data structures, as well as those that describe computations and communication patterns. Using the component-based versions of the benchmarks, a systematic performance evaluation has been performed for quantifying the overheads caused strictly by the component-based structure.

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2018-06-06T18:51:26Z No. of bitstreams: 1 texto completo.pdf: 10760567 bytes, checksum: e11aa8ab3d3f98f215de81a9ce967fcc (MD5) / Approved for entry into archive by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2018-06-06T18:51:49Z (GMT) No. of bitstreams: 1 texto completo.pdf: 10760567 bytes, checksum: e11aa8ab3d3f98f215de81a9ce967fcc (MD5) / Approved for entry into archive by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2018-06-06T18:52:00Z (GMT) No. of bitstreams: 1 texto completo.pdf: 10760567 bytes, checksum: e11aa8ab3d3f98f215de81a9ce967fcc (MD5) / Made available in DSpace on 2018-06-06T18:52:08Z (GMT). No. of bitstreams: 1 texto completo.pdf: 10760567 bytes, checksum: e11aa8ab3d3f98f215de81a9ce967fcc (MD5) Previous issue date: 2017-11 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This thesis presents an exact parallel algorithm for computing the intersection be- tween two 3D triangular meshes, as used in CAD/CAM (Computer Aided De- sign/Computer Aided Manufacturing), CFD (Computational Fluid Dynamics), GIS (Geographical Information Science) and additive manufacturing (also known as 3D Printing). Geometric software packages occasionally fail to compute the correct result because of the algorithm implementation complexity (that usually needs to handle several special cases) and of precision problems caused by floating point arithmetic. A failure in an intersection computation algorithm may propagate to any software using the algorithm as a subroutine. As datasets get bigger (and the chances of failure in an inexact algorithm increase), exact algorithms become even more important. While other methods for exactly intersecting meshes exist, their performance makes them non-suitable for applications where the fast processing of big geometric models is important (such as interactive CAD systems). The key to obtain robustness and performance is a combination of 5 separate techniques: • Multiple precision rational numbers, to exactly represent the coordinates of the objects and completely eliminate roundoff errors during the computations. • Simulation of Simplicity, a symbolic perturbation technique, to ensure that all geometric degeneracies (special cases) are properly handled. • Simple data representations and local information, to simplify the correct pro- cessing of the data and make the algorithm more parallelizable. • A uniform grid, to efficiently index the data, and accelerate some of the steps of the algorithm such as testing pairs of triangles for intersection or locating points in the mesh. / Só foram apresentados título e resumo em inglês.