Doctor en Ciencias, Mención Computación / La generación y refinamiento de mallas son temas de gran interés en aplicaciones tales como simulación de fenómenos físicos mediante el uso de los métodos de elementos finitos, en aplicaciones CAD, modelado geométrico y mallas geométricas. Una malla es un conjunto de elementos geométricos (polígonos o poliedros) que no se superponen, los cuales están conectados por medio de vértices, aristas y caras, que se usan para aproximar dominios geométricos. Los algoritmos de refinamiento producen mallas cada vez más finas para discretizar dominios complejos, representar objetos con topologías arbitrarias y también superficies con formas complejas.
En esta tesis se estudió la paralelización de algoritmos de refinamiento basados en el concepto de Lepp para sistemas multicore (multinúcleo) y sistemas distribuidos. Se consideraron dos problemas: (1) refinamiento de mallas de buena calidad: aquí dada una malla de entrada de buena calidad, ésta es iterativa y localmente refinada (de acuerdo a un requerimiento externo a la
aplicación) para producir una malla final de calidad análoga a la inicial; (2) refinamiento de
triangulaciones Delaunay de mala calidad, donde dada una triangulación Delaunay de entrada de mala calidad (con una geometría dada), deseamos producir una triangulación Delaunay de buena calidad y de tamaño óptimo.
Algoritmos basados en el concepto de Lepp son algoritmos refinamiento por la arista más larga mejorados donde el refinamiento de cualquier triángulo t tiene asociado un Lepp(t).
En el contexto de los sistemas multicore se desarrollaron algoritmos Lepp-bisección multicore eficientes y escalables para el refinamiento de mallas de 2 y 3 dimensiones. También se desarrolló un algoritmo Lepp-Delaunay multicore para la generación de mallas Delaunay de buena calidad.
En el contexto de los sistemas de memoria distribuida se desarrolló un algoritmo Lepp-bisección distribuido para el refinamiento de mallas de 2 dimensiones donde la malla inicial es subdividida dentro de un conjunto de submallas (o subparticiones), las cuales son distribuidas entre los procesadores. También se desarrolló una estrategia eficiente para garantizar que se obtiene una malla final válida (conforme) en las interfaces de submallas vecinas.
Se realizaron evaluaciones empíricas de los algoritmos paralelos sobre arquitecturas multicore y sistemas de memoria distribuida que muestran que los algoritmos paralelos tienen buen desempeño.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/135082 |
| Date | January 2015 |
| Creators | Rodríguez Moreno, Pedro Ángel |
| Contributors | Rivara Zúñiga, María Cecilia, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ciencias de la Computación, Mateu Brulé, Luis, Bustos Cárdenas, Benjamín, Chrisochoides, Nikos |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | English |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Atribución-NoComercial-SinDerivadas 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0018 seconds