No description available.

Many problems appearing in scientific computing and other areas can be formulated as a graph partitioning problems. Examples include data distribution for parallel computers, decomposition of sparse matrices and VLSI-design. In this survey we present the graph partitioning problem, describe some applications and introduce many of the algorithms used to solve the problem.

Many problems appearing in scientific computing and other areas can be formulated as a graph partitioning problems. Examples include data distribution for parallel computers, decomposition of sparse matrices and VLSI-design. In this survey we present the graph partitioning problem, describe some applications and introduce many of the algorithms used to solve the problem.

In the field of Computational Fluid Dynamics, several types of mesh adaptation strategies are used to enhance a mesh’s quality, thereby improving simulation speed and accuracy. Mesh smoothing (r-refinement) is a simple and effective technique, where nodes are repositioned to increase or decrease local mesh resolution. Mesh partitioning divides a mesh into sections, for use on distributed-memory parallel machines. As a more abstract form of modeling, graph theory can be used to simulate many real-world problems, and has applications in the fields of computer science, sociology, engineering and transportation, to name a few. One of the more important graph analysis tasks involves moving through the graph to evaluate and calculate nodal connectivity. The basic structures of meshes and graphs are the same, as both rely heavily on connectivity information, representing the relationships between constituent nodes and edges. This research examines the parallelization of these algorithms using commodity graphics hardware; a low-cost tool readily available to the computing community. Not only does this research look at the benefits of the fine-grained parallelism of an individual graphics processor, but the use of Message Passing Interface (MPI) on large-scale GPU-based supercomputers is also studied.

Multi-core architectures are present throughout a large selection of computing devices from cell phones to super-computers. Parallel applications running on these devices solve bigger problems in a shorter time. Writing those applications is a difficult task for programmers. They need to deal with low-level parallel mechanisms such as data distribution, inter-processor communication, and task placement. The goal of the Standard Template Adaptive Parallel Library (STAPL) is to provide a generic high-level framework to develop parallel applications. One of the first steps of a parallel application is to partition and distribute the data throughout the system. An important data structure for parallel applications to store large amounts of data and model many types of relations is the graph. A mesh, which is a special type of graph, is often used to model a spatial domain in scientific applications. Graph and mesh partitioning has many applications such as VLSI circuit design, parallel task scheduling, and data distribution. Data distribution, significantly impacts the performance of a parallel application. In this thesis, we introduce the STAPL Parallel Graph Partitioner Framework. This framework provides a generic infrastructure to partition arbitrary graphs and meshes and to build customized partitioners. It includes the state of the art parallel k-way multilevel scheme to partition arbitrary graphs, a parallel mesh partitioner with parameterized partition shape, and a customized partitioner used for discrete ordinates particle transport computations. This framework is also part of a generic library, STAPL, allowing the partitioning of the data and development of the whole parallel application to be done in the same environment. We show the user-friendly interface of the framework and its scalability for partitioning different mesh and graph benchmarks on a Cray XE6 system. We also highlight the performance of our customized unstructured mesh partitioner for a discrete ordinates particle transport code. The developed columnar decompositions significantly reduce the execution time of simultaneous sweeps on unstructured meshes.

Com a popularização de equipamentos tradicionais de captura de imagens, como câmeras digitais, e o avanço tecnológico dos dispositivos não invasivos, como tomografia e ressonância, cresce também a necessidade e consequente uso de métodos numéricos para simulação de fenômenos físicos em domínios definidos por imagens. Um dos pré-requisitos para a aplicação de tais métodos numéricos consiste na discretização do domínio em questão, num processo denominado geração de malhas. Embora diversos métodos de geração de malha tenham sido propostos para discretizar domínios definidos por primitivas geométricas, pouco tem sido feito no sentido de gerar uma decomposição diretamente a partir de imagens. Neste trabalho, apresentamos uma abordagem de geração de malhas de qualidade a partir de domínios definidos por imagens com textura. Mais especificamente, a pesquisa descrita nesta tese contribui com a melhoria do algoritmo Imesh, ao sanar três de suas principais limitações: tratamento de imagens com texturas; controle do nível de refinamento da malha e suporte a outros tipos de elementos. Estas contribuições flexibilizam o processo de geração da malha, e ainda ampliam o domínio de aplicações do algoritmo Imesh, à medida que são considerados domínios definidos por imagens com textura e o uso de métodos numéricos para elementos não simpliciais torna-se possível. O algoritmo de melhoria da malha gerada utiliza uma abordagem inovadora de remalhamento baseada em templates e guiada por retalhos de Bézier / With the spreading of traditional image capturing devices, such as digital cameras, and the technological advancement of more specific imaging devices such as CT and MRI, also increased the need and the following use of numerical methods for simulation of physical phenomena in domains defined by images. One of the prerequisites for the application of such numerical methods is the discretization of the corresponding domain, in a process called mesh generation. Although several methods of mesh generation have been proposed to discretize domains defined by geometric primitives, little has been done to generate a decomposition directly from images. We present an approach to generate quality meshes from domains defined by images with texture. More specifically, the research described in this thesis contributes to the improvement of the Imesh algorithm, removing three of its main limitations: treatment textured images, control of the level of the mesh refinement and support for other types of non-simplicial elements. These contributions provide flexibility to the mesh generation process, and extend the range of applications of Imesh by both handling textured images and considering the use of numerical methods for non-simplicial elements. The mesh quality improvement algorithm uses a new approach based on mesh templates and it is guided by Bezier patches

Com a popularização de equipamentos tradicionais de captura de imagens, como câmeras digitais, e o avanço tecnológico dos dispositivos não invasivos, como tomografia e ressonância, cresce também a necessidade e consequente uso de métodos numéricos para simulação de fenômenos físicos em domínios definidos por imagens. Um dos pré-requisitos para a aplicação de tais métodos numéricos consiste na discretização do domínio em questão, num processo denominado geração de malhas. Embora diversos métodos de geração de malha tenham sido propostos para discretizar domínios definidos por primitivas geométricas, pouco tem sido feito no sentido de gerar uma decomposição diretamente a partir de imagens. Neste trabalho, apresentamos uma abordagem de geração de malhas de qualidade a partir de domínios definidos por imagens com textura. Mais especificamente, a pesquisa descrita nesta tese contribui com a melhoria do algoritmo Imesh, ao sanar três de suas principais limitações: tratamento de imagens com texturas; controle do nível de refinamento da malha e suporte a outros tipos de elementos. Estas contribuições flexibilizam o processo de geração da malha, e ainda ampliam o domínio de aplicações do algoritmo Imesh, à medida que são considerados domínios definidos por imagens com textura e o uso de métodos numéricos para elementos não simpliciais torna-se possível. O algoritmo de melhoria da malha gerada utiliza uma abordagem inovadora de remalhamento baseada em templates e guiada por retalhos de Bézier / With the spreading of traditional image capturing devices, such as digital cameras, and the technological advancement of more specific imaging devices such as CT and MRI, also increased the need and the following use of numerical methods for simulation of physical phenomena in domains defined by images. One of the prerequisites for the application of such numerical methods is the discretization of the corresponding domain, in a process called mesh generation. Although several methods of mesh generation have been proposed to discretize domains defined by geometric primitives, little has been done to generate a decomposition directly from images. We present an approach to generate quality meshes from domains defined by images with texture. More specifically, the research described in this thesis contributes to the improvement of the Imesh algorithm, removing three of its main limitations: treatment textured images, control of the level of the mesh refinement and support for other types of non-simplicial elements. These contributions provide flexibility to the mesh generation process, and extend the range of applications of Imesh by both handling textured images and considering the use of numerical methods for non-simplicial elements. The mesh quality improvement algorithm uses a new approach based on mesh templates and it is guided by Bezier patches