Generación distribuida con balanceo de carga de mallas octree

Abstract

En este trabajo se presenta un algoritmo paralelo balanceado de manera estática para la generación de mallas geométricas de “octrees”. Este algoritmo es una mejora a una versión serial del mismo, y como tal promete disminuir los tiempos de ejecución y/o mejorar el nivel de refinamiento manteniendo la misma calidad de malla. El objetivo principal de este trabajo es implementar una versión paralela del algoritmo para la generación de “octrees”, basándose en una versión serial del mismo. Asimismo, dentro de los objetivos específicos está la toma de los tiempos de ejecución variando el tamaño de la malla, el nivel de refinamiento, el número de procesadores y el algoritmo de particionamiento, para luego compararlos con la versión serial con el fin de observar las posibles mejoras o empeoramientos de desempeño. Este algoritmo como modelo de paralelismo utiliza “Task-Farm” y memoria distribuida con paso de mensajes como arquitectura paralela. Es independiente del tipo de algoritmo de particionamiento, lo que hace fácil que acepte nuevos algoritmos. Adicionalmente, presenta pocos y bien definidos puntos de comunicación, lo cual conlleva una menor complejidad del algoritmo paralelo, con la posibilidad de ser extendido a otros algoritmos de refinamiento, además de “octrees”. Dentro de los resultados obtenidos de la ejecución se observa una disminución en el tiempo, salvo en algunos casos; un aumento en el nivel de refinamiento, además de mantener la misma calidad de la malla que en el algoritmo serial y una aparente indiferencia con respecto al tamaño de la malla de entrada, pero no a la complejidad de esta. Junto con esto, se puede decir que el nivel de refinamiento, junto con el número de procesadores, aún pueden ser aumentados, y que el código puede ser mejorado.This work presents a statically balanced parallel algorithm which generates octree meshes. This algorithm is an improvement of an existing serial version, and as such it seeks to improve refinement time and/or refinement level while maintaining mesh quality. The work’s main objective is the implementation of a mesh generating parallel algorithm based on a previous serial version. Other objectives include measuring the execution time and comparing it to the serial version of the algorithm, while varying the mesh size, the refinement level, the number of processors, the partitioning algorithm. This will allow to observe possible gain or losses in performance. This algorithm uses Task-Farm as a parallel model as well as a distributed memory with message passing as its parallel architecture. Additionally, the implemented algorithm is independent from the partitioning algorithm, and as such it can accept new partitioning strategies. The algorithm presents few and well defined communication points, and as a result it presents a low parallel complexity while keeping the possibility to extended it to another refinement algorithms. The work’s results present a decrease in the execution time, with very few exceptions. It presents also an increase in the refinement level while maintaining the mesh quality and a certain indifference towards input mesh size, but not complexity. Finally, there is still room for an increase in the refinement level, the number of processors and/or a code overhaul.