Tesis sobre el tema "Paralelización"

La programació d'aplicacions en màquines paral·leles és un tema d'interès quant a que cada vegada són més les màquines d'aquest tipus disponibles comercialment.<br><br/>Per a això l'usuari disposa de dues opcions: (a) Utilització de llenguatges de programació amb primitives específiques que permetin expressar i aprofitar les possibilitats que ofereix la màquina. (b) Utilització de compiladors que de forma automàtica siguin capaces d'extreure el paral·lelisme del programa escrit en un llenguatge de programació convencional.<br> La segona opció presenta certs avantatges, com per exemple, que el programador només deu preocupar se de l'algorisme a resoldre i no de les operacions que poden realitzar-se de forma simultània. D'altra banda són moltes les aplicacions escrites en llenguatges convencionals i que la seva paral·lelització automàtica evitaria la seva reprogramació manual. Aquests compiladors poden extreure paral·lelisme a nivell de procediments ("coarse grain"), bucles ("medium grain") o sentències ("fine grain") existint per a això alguns mètodes proposats en la literatura. En programes numèrics gran part del temps s'empra en l'execució de bucles. Per això, la paral·lelització a nivell de bucles ha estat la més estudiada i es basa en una detallada anàlisi de les dependències entre les sentències que ho componen.<br> Aquesta tesi se centra en l'estudi i proposta de tècniques de reestructuració per a bucles en programes seqüencials. Els principals problemes tractats són l'existència de recurrències i sentències condicionals en aquests bucles. L'avaluació del paral·lelisme d'un bucle és considerada en primer lloc i es realitza a partir del grat de dependències entre sentències obtingut en temps de compilació. El paral·lelisme avaluat és una bona mesura de l'eficiència del procés de reestructuració realitzat. Es proposa un mètode, Graph Traverse Scheduling (GTS) que incorporat en un compilador permet l'extracció del màxim paral·lelisme del bucle. La planificació ("scheduling") realitzada es basa en recorreguts a través d'un cicle del graf de dependències que compleix unes determinades característiques.<br> L'aplicació de GTS per a multiprocessadors amb memòria compartida permet l'obtenció de tasques independents o sincronitzades segons les dependències existents. Un dels temes considerats és la reducció del nombre de sincronitzacions explícites afegides així com el compromís entre paral·lelisme obtingut i sincronització. L'aplicació de GTS per a màquines vectorials permet l'obtenció operacions vectorials de màxima longitud a partir de les operacions incloses en bucles seqüencials. GTS pot ser aplicat a altres arquitectures com multiprocessadors amb memòria distribuïda i màquines VLIW, encara que aquests temes no han estat considerats en aquesta tesi.<br> Es comparen els resultats obtinguts per GTS amb els obtinguts aplicant altres tècniques de reestructuració ja existents, basant-se aquesta comparança en dades obtingudes a partir de grafs de dependència aleatòriament generats.<br>La programación de aplicaciones en máquinas paralelas es un tema de interés en cuanto a que cada vez son más las máquinas de este tipo disponibles comercialmente. Para ello el usuario dispone de dos opciones: (a) Utilización de lenguajes de programación con primitivas específicas que permitan expresar y aprovechar las posibilidades que ofrece la máquina. (br) Utilización de compiladores que de forma automática sean capaces de extraer el paralelismo del programa escrito en un lenguaje de programación convencional.<br><br/>La segunda opción presenta ciertas ventajas, como por ejemplo, que el programador sólo debe de preocuparse del algoritmo a resolver y no de las operaciones que pueden realizarse de forma simultánea. Por otro lado son muchas las aplicaciones escritas en lenguajes convencionales y cuya paralelización automática evitaría su reprogramación manual. Estos compiladores pueden extraer paralelismo a nivel de procedimientos ("coarse grain"), bucles ("medium grain") o sentencias ("fine grain") existiendo para ello algunos métodos propuestos en la literatura. Enprogramas numéricos gran parte del tiempo se emplea en la ejecución de bucles. Por ello, la paralelización a nivel de bucles ha sido la más estudiada y se basa en un detallado análisis de las dependencias entre las sentencias que lo componen.<br> <br/>Esta tesis se centra en el estudio y propuesta de técnicas de restructuración para bucles en programas secuenciales. Los principales problemas tratados son la existencia de recurrencias y sentencias condicionales en estos bucles. La evaluación del paralelismo de un bucle es considerada en primer lugar y se realiza a partir del grato de dependencias entre sentencias obtenido en tiempo de compilación. El paralelismo evaluado es una buena medida de la eficiencia del proceso de reestructuración realizado. Se propone un método, Graph Traverse Scheduling (GTS) que incorporado en un compilador permite la extracción del máximo paralelismo del bucle. El "scheduling' realizado se basa en recorridos a través de un ciclo del grafo de dependencias que cumple unas determinadas características.<br><br/>La aplicación de GTS para multiprocesadores con memoria compartida permite la obtención de tareas independientes o sincronizadas según las dependencias existentes. Uno de los temas considerados es la reducción del número de sincronizaciones explícitas añadidas así como el compromiso entre paralelismo obtenido y sincronización. La aplicación de GTS para máquinas vectoriales permite la obtención operaciones vectoriales de máxima longitud a partir de las operaciones incluidas en bucles secuenciales. GTS puede ser aplicado a otras arquitecturas como multiprocesadores con memoria distribuida y máquinas VLIW, aunque estos temas no han sido considerados en esta tesis. <br><br/>Se comparan los resultados obtenidos por GTS con los obtenidos aplicando otras técnicas de reestructuración ya existentes, basándose esta comparación en datos obtenidos a partir de gráfos de dependencia aleatoriamente generados.<br>Vectorizing and parallelizing compilers exist today for high performance vector and parallel computers in order to execute efficiently sequential programs written in convencional languages such as FORTRAN.<br> In this thesis the author studies and proposes methods for restructuring recurrences as the main problem in such restructuring compilers. The method presented extracts the maximum parallelism or vector operations out of DO loops with tight recurrences including or no conditional statements. The method is named Graph Traverse Scheduling (GTS) and it is devised for producing code for shared memory multiprocessor systems or vector machines. The method is presented for single nested loops including one or several recurrences; the author also shows how parallel and vector code can be generated. <br><br/>Based on the dependence graph, the author first presents its parallelism and vector length evaluation as loop characteristies that will determine the restructuring process. Then the author presentes the application of GTS in order to distribute iterations of a recurrence between tasks or to generate vector operations of a given length. When this methods is applied for parallel code generation, dependences not inciuded in the sequential execution of each task must be explicitely synchronized. Therefore, hardware support for fast synchronization is assumed in the target architecture. When GTS is applied for vector code generation, a sequential loop of vector operations is obtained. <br><br/>Finally the author performs a brief comparison of the resuits btained by the method presentes and other existing methods used restructuring recurrences in sequential loops.

Dados los avances en la tecnología, la astronomía es capaz de recolectar del orden de terabytes de datos por noche. El análisis manual de ésta es prácticamente imposible, por lo que es constante la necesidad de nuevos y mejores algoritmos para realizar análisis automático. Por otro lado, la computación paralela provee herramientas para realizar análisis de datos masivos, las que incrementan la capacidad total de procesamiento y disminuyen el tiempo requerido. Existe un software para la búsqueda de cúmulos de galaxias, el cual funciona de forma secuencial. Hacer que este software funcione en forma paralela sería de gran utilidad, dada la cantidad de datos que existen y existirán para analizar. El objetivo de esta memoria es diseñar e implementar una solución computacional que permita efectuar la detección de cúmulos de galaxias en forma paralela. La paralelización del algoritmo se hizo sobre el framework Hadoop, utilizando la herramienta Streaming con el lenguaje Python para el desarrollo del software. Se construyó una aplicación que divide los datos de entrada de forma inteligente, ejecuta el algoritmo de detección de cúmulos de galaxias en varias máquinas de forma paralela, y re ensambla los resultados parciales obtenidos. Se estudiaron estrategias para el particionamiento de los datos, utilizando celdas con distintas geometrías. También se estudiaron e implementaron estrategias para el re ensamblado de los resultados. En base a conocimientos astronómicos y experimentación se determinó la utilidad, dado el contexto, de cada estrategia, y los valores límites para sus parámetros. Los resultados son los siguientes: (1) un software paralelo para la detección de cúmulos de galaxias; (2) al correr el programa paralelo con dos particiones, el tiempo de ejecución se reduce a la mitad; (3) el software secuencial de detección de cúmulos se observa altamente dependiente de las particiones utilizadas, encontrándose para una partición de 2 celdas sólo un 11% de los cúmulos que se detectaban en la versión secuencial. Como trabajo futuro se propone: (1) modificar el software secuencial de búsqueda de cúmulos de galaxias para que detecte cúmulos sin miembros repetidos; (2) ejecutar este software en un clúster de computadores o con cloud computing, para medir las mejoras en tiempo; (3) la ejecución de este software con sets de datos más grandes, para medir la escalabilidad de éste; (4) crear una partición ad-hoc al set de datos.

Ingeniero Civil Mecánico<br>Dentro de los métodos de simulación numérica para resolución de ecuaciones diferenciales parciales (EDP's), los métodos sin malla han sido desarrollados desde hace aproximadamente veinte años. A diferencia del método de elementos finitos, los métodos sin malla no necesitan una malla definida para la construcción de sus funciones de base, las que se crean únicamente por la distribución de los nodos en el dominio. Esta característica hace a este método más atractivo en problemas donde exista distorsión de la malla, sin embargo, requieren un tiempo extra en su cálculo y un esfuerzo mayor en su programación. El presente trabajo tiene por objetivo realizar un algoritmo numérico eficiente mediante programación en paralelo, para la resolución de problemas en la mecánica de sólidos mediante el método sin malla Galerkiano con funciones de base de máxima entropía. La motivación de este trabajo es suplir uno de los principales defectos de los métodos sin malla, ser computacionalmente costosos. Son abordados los antecedentes del método sin malla, elasticidad lineal y la programación en paralelo. Se utiliza el método sin malla Galerkiano basado en la forma débil, con funciones de base de máxima entropía. Se trabaja con el software computacional MATLAB y la librería Parallel Computing Toolbox en la implementación de la programación en paralelo para tres problemas específicos y se analiza el error numérico, convergencia, tiempo de cómputo, e indicadores de desempeño para la programación en paralelo, como lo son Speedup y Eficiencia paralela. Se obtienen errores numéricos aceptables, entregados por las normas relativas L^2 y H^1, obteniendo convergencia en los tres problemas. Los tiempos de cómputo se reducen al implementar la programación paralela en todos los casos. La convergencia del problema es independiente del número de procesadores utilizados. Se obtienen los mejores resultados de Speedup y Eficiencia paralela para problemas por sobre los 5000 grados de libertad. Se recomienda trabajar problemas por sobre esta cifra en la implementación de la programación en paralelo para la resolución de problemas en la mecánica de sólidos mediante el método sin malla Galerkiano. Se cumple objetivo principal, logrando realizar algoritmo numérico mediante programación en paralelo, para la resolución de problemas en la mecánica de sólidos mediante el método sin malla Galerkiano con funciones de base de máxima entropía.

Ingeniero Civil en Computación<br>La simulación de cuerpos que interactúan entre sí por medio de fuerzas y la detección de colisiones entre cuerpos son problemas estudiados en distintas áreas, como astrofísica, fisicoquímica y videojuegos. Un campo en particular corresponde al estudio de los coloides, partículas microscópicas suspendidas sobre otra sustancia y que tienen aplicaciones en distintas industrias. El problema consiste en simular la evolución de un sistema con distintos tipos de partículas coloidales a través del tiempo, cumpliendo las propiedades de volumen excluido, movimiento aleatorio y condiciones de borde periódicas. Además, la interacción de largo alcance entre coloides presenta la particularidad de no cumplir con el principio de acción y reacción. Se desarrolló un algoritmo de simulación completamente paralelo en GPU, implementado en la plataforma CUDA y C++. La solución utiliza una triangulación de Delaunay en memoria de la tarjeta gráfica para conocer eficientemente la vecindad de cada partícula, lo que permite resolver traslapes entre partículas sin tener que evaluar todo el sistema. Se utilizó una implementación reciente del algoritmo de edge-flip para mantener la triangulación actualizada en cada paso de tiempo, extendiendo además el algoritmo para corregir los triángulos invertidos. Para el caso de fuerzas de corto alcance, además se desarrolló un algoritmo paralelo que construye y utiliza listas de Verlet para manejar las vecindades entre partículas de forma más eficiente que la implementación anterior. Los resultados obtenidos con la implementación paralela presentan una mejora de hasta dos órdenes de magnitud con respecto al tiempo de la solución secuencial existente. Por otro lado, el algoritmo para fuerza de corto alcance mejora de igual magnitud con respecto a la solución de largo alcance desarrollada. También se verificó que la corrección de traslapes con triangulación de Delaunay se hace de forma eficiente, y que esta estructura puede ser aplicada para otros problemas relacionados, como implementar el cálculo de fuerzas de corto alcance (y compararlo con la implementación ya existente) o realizar simulaciones aproximadas utilizando triangulaciones.<br>Financiado parcialmente por el Proyecto FONDECYT # 1140778

Ingeniero Civil en Computación<br>La detección de objetos a partir de imágenes se ha convertido en una herramienta muy poderosa para diferentes disciplinas. El Laboratorio de Materia Fuera del Equilibrio del Departamento de Física de la Facultad cuenta con una implementación en C del Método χ^2 usando bibliotecas ad-hoc compatibles con Mac OSX para detectar partículas en sistemas granulares cuasi-bidimensionales compuestos por miles de partículas de acero de 1 mm de diámetro, pudiendo detectar partículas en una imagen de 1 MegaPixel en alrededor de 10 segundos. Sin embargo, estas imágenes provienen de videos que se desean analizar y en una sesión de trabajo se puede requerir analizar alrededor de unas 100.000 imágenes en total, por lo cual el procesamiento y posterior análisis de estas imágenes de video tiene una duración de varios días. Es por esto que fue necesario agilizar de alguna manera este procesamiento de imágenes y generar una solución robusta. El objetivo principal de la memoria consistió en reducir los tiempos de detección de partículas generando un nuevo software basado en el anterior, facilitando extensiones futuras, y utilizando el máximo poder de cómputo disponible en el laboratorio. El alumno ideó como solución un sistema distribuido haciendo uso de todos los computadores disponibles para el procesamiento de imágenes, reimplementando el código del software, en ese entonces utilizado, de C a C++ utilizando patrones de diseño para facilitar futuras extensiones del software y threads con el fin de aumentar el rendimiento de este. También se agregó tecnología CUDA para el procesamiento de datos reduciendo de forma considerable los tiempos de ejecución. Como resultado final de la memoria, se logró obtener un speedup de alrededor de 5x haciendo uso de distribución de carga computacional, uso de procesos en paralelo, hilos de ejecución y tecnología CUDA, además se logró una solución más robusta y extensible para futuros cambios o generación de nuevos algoritmos de procesamiento. Todo el proceso de investigación, desde la obtención de datos hasta la validación de la hipótesis, lleva mucho tiempo, en donde la detección de partículas es solo una parte de todo el calculo computacional que se debe realizar, por lo que se aconseja implementar en lenguajes no interpretados y más rápidos, como por ejemplo C++, otras etapas de cálculo de datos y además, en lo posible, distribuir el computo y usar CUDA.

En este trabajo se ha realizado una simulación numérica detallada del fenómeno de cambio de fase sólido-líquido, por ser esta fenomenología de gran interés en diferentes áreas industriales. <br/>La simulación realizada implica problemas de no linealidad, fuertes acoplamientos y frontera móvil. Como resultado de esto, solo para las configuraciones más simples se pueden utilizar herramientas analíticas, mientras que para resolver la mayoría de problemas de interés se requiere el uso de métodos numéricos. Estos métodos consisten en discretizar las ecuaciones que definen la fenomenología que nos ocupa en pequeñas celdas o volúmenes de control. En este estudio se ha optado por utilizar el Método de Volúmenes Finitos (FVM) para la discretización de las ecuaciones gobernantes utilizando mallas cartesianas. Se utiliza una malla desplazada; esto quiere decir que las componentes del vector velocidad se calculan en las caras de los volúmenes de control, lo que permite un acoplamiento adecuado entre la ecuación de conservación de la masa y momentum. <br/>Tanto el código como las soluciones numéricas han sido convenientemente verificados. La verificación del código consiste en comprobar que éste está libre de errores de programación y que el comportamiento de los esquemas numéricos implementados está acorde con su comportamiento teórico. Para la verificación de la solución numérica se han utilizado métodos de extrapolación de Richardson o realizando un estudio de refinamiento de malla y observando la evolución de algunas magnitudes características del problema como pueden ser la fracción de líquido en el dominio o el número de Nusselt en la pared caliente.<br/>Una vez que el código y las soluciones numéricas han sido convenientemente verificados, la validación final de la simulación del proceso es la que se obtiene de comparar los resultados predecidos con los datos experimentales.<br/>El problema de la fusión del galio en una cavidad rectangular calentada por un lado ha sido ampliamente utilizado por investigadores con el fin de evaluar los métodos numéricos para la resolución del cambio de fase. Si bien comentar que este material tiene las ventajas de que sus propiedades termofísicas están bien establecidas, que tiene una temperatura de cambio de fase cercana a la temperatura ambiente y que es un material con gran interés industrial, también presenta algunas desventajas como es el hecho de que tiene un comportamiento anisotrópico en cuanto a la conductividad térmica de la fase sólida. No obstante, el gran número de trabajos experimentales que se encuentran en la literatura relacionados con este material nos ha conducido a escoger este material para la realización de un estudio detallado del cambio de fase sólido-líquido en este trabajo.<br/>Si bien en la literatura aparece este problema con diferentes configuraciones, en este trabajo nos hemos centrado en el estudio del caso en que la relación de aspecto (alto/ancho) es de 0,5.<br/>Existen diferentes métodos numéricos pararesolver problemas de cambio de fase sólido líquido: métodos que siguen la frontera móvil, métodos que fijan la frontera móvil, etc. En este trabajo utilizaremos el Método Entálpico pues nos permite utilizar una malla fija en todo el dominio, la condición de Stefan queda impuesta de manera implícita, permite la coexistencia de más de un frente de cambio de fase y permite que la interfase tenga un cierto grosor. <br/>El caso que nos ocupa tiene la singularidad de encontrarse en un rango de Prandtl muy bajo. Esto provoca que se alcance el régimen turbulento para números de Rayleigh relativamente bajos. Esto nos ha hecho pensar sobre la conveniencia de realizar un estudio más detallado para determinar para que valor de Rayleigh se produce la transición de régimen permanente a flujo oscilatorio y de éste a un régimen caótico. <br/>Los problemas que han ido surgiendo a lo largo de la realización de este trabajo nos han conducido a la utilización del método multibloc, también conocido como método de descomposición de subdominios. El método se emplea considerando flujos incompresibles y mallas desplazadas. En este trabajo se explicarán las modificaciones que han sido necesarias para la utilización de este método en la fenomenología del cambio de fase sólido líquido. Se han utilizado dos aproximaciones: una conservativa y otra basada en la presión. Para la obtención de la solución de referencia se ha empleado los métodos de subdominios basados en la presión, pues con el método conservativo se han observado discrepancias entre la solución obtenida con un único subdominio y la obtenida con varios subdominios. <br/>Finalmente, se ha realizado un estudio parámetrico del caso, para el cual se han considerado diferentes relaciones de aspecto, diferentes condiciones de contorno y variaciones de ±10% en las propiedades termofísicas con respecto al caso de referencia, con el objetivo de ver como afectan estas modificaciones sobre la fenomenología que nos ocupa.<br>In this thesis a detailed numerical simulation of liquid-solid phase change phenomena has been made, because this phenomenology is of great interest in different industrial areas. <br/>The simulation done implies problems of nonlinearity, strong couplings and movable interphase. Like a result, only for the simplest configurations analytical tools can be used, whereas to solve the most of interest problems numerical methods are needed. These methods consist in the discretisation of the equations that define the phenomenology in small cells or control volumes. In this study the Finite Volume Method (FVM) has been used for the governing equations discretisation using Cartesian meshes. A displaced mesh is used; this means that the components of the speed vector are calculated in the faces of the control volumes, which allows a correct coupling between the continuity and momentum equations. <br/>So the code as the numerical solutions have been properly verified. The code verification consist of verifying that this is free of programming errors and that the behaviour of the numerical schemes is agreed with the theoretical one. For the verification of the numerical solution the Richardson Extrapolation Method or a mesh refinement study have been used. Once the code and the numerical solutions have been properly verified, the final validation of the process simulation is obtained comparing the numerical results with experimental ones.<br/>The Gallium melting problem in a square cavity heated by a side has been widely used by investigators with the objective of evaluatingthe numerical methods used for solving the phase change phenomena. Although this material have the advantages of its thermophysical properties are well established, the phase change temperature is near the room temperature and is a material with a great industrial interest, also presents some disadvantages like having an anisotropic thermal conductivity of the solid phase. However, the great number of experimental works that can been found in the literature, lead us to choose this material for doing a detailed study of the solid liquid phase change in this work. <br/>Although in the literature this problem appears with different configurations, in this thesis we have centered in the study of the case with an aspect ratio (height/width) of 0.5. Different numerical methods exist to solve solid-liquid phase change problems: methods that follow the moving interphase, methods that fix the moving interphase, etc. In this work we have used the Enthalpy Method because it allows us to use a fixed mesh in all the domain, the Stefan condition is imposed implicitly, it allows the coexistence of more than one front of phase change and allows the interphase has a thickness.<br/>This case has the singularity of being in a low Prandtl number range. This causes that a turbulent state has been reached for relatively low Rayleigh numbers. This has made think us on the convenience of making a detailed study to determine the transition of permanent regime to oscillating flow and from oscillating flow to chaotic regime. <br/>The problems than have been found in the accomplishment of this work have lead us to the use of multiblock method. This method is used considering incompressible flows and moved meshes. We will explain the modifications that have been necessary for using this method in the phase change phenomena. Two approaches have been used: a conservative one and a pressure based one. For obtaining the reference solution has been use the pressure based method, because the conservative method presents discrepancies between the obtained solution with an only subdomain and the obtained with several subdomains. <br/>Finally, a parametric study has been done, considering different aspect ratios, boundary conditions and variations of ±10% in the thermophysical properties with respect to the reference case, with the objective to see as these changes affect on the phenomenology that occupies to us.

Los incendios forestales son desastres naturales que todos los años causan cuantiosas pérdidas. Conocer de antemano su evolución resulta de gran importancia para mitigar sus efectos. Existen diversos modelos que proporcionan una predicción de la propagación del incendio. El viento es un parámetro fundamental de estos modelos, pero hay que considerar que se ve modificado por la orografía del terreno, y es necesario acoplar modelos de campo de vientos. Los simuladores de campo de vientos, como es el caso de WidnNinja, discretizan el terreno formando una malla y aplican las ecuaciones correspondientes para establecer un sistema de ecuaciones de la forma Ax=b. En el caso particular de WindNinja, se aplican las ecuaciones de conservación de la masa y las condiciones de contorno de Dirichlet. Cuando el mapa es muy grande, el sistema de ecuaciones llega a tener centenares de millones de incógnitas y no puede ser resuelto por métodos directos, de modo que se aplican métodos iterativos, como es el Gradiente Conjugado con Precondcionador (PCG). Resolver tales sistemas toma un tiempo que no puede ser asumido en situaciones operacionales. Por tanto, es necesario aplicar técnicas de paralelización. En concreto, se han aplicado tres técnicas para acelerar el cálculo del campo de vientos con WindNinja: • Se ha explotado el paralelismo de datos, aplicando partición del mapa. Se ha desarrollado una metodología que determina la partición del mapa, para reducir el tiempo de ejecución sin perder precisión en el cálculo del campo de vientos, más allá de unos límites aceptables. • Se ha aplicado descomposición del dominio que permite paralelizar la resolución del sistema de ecuaciones aplicando métodos con solapamiento (Schwarz) o métodos sin solapamiento (Schur). • Se ha determinado que la operación más costosa del PCG es la multiplicación matriz dispersa-vector y se ha desarrollado un formato de almacenamiento (Vectorizing Diagonal Sparse Matrix VDSpM) que permite acelerar dicha operación. Los tres métodos consiguen reducir los tiempos de ejecución, pero cuando los mapas son muy grandes, ninguno de los tres presenta la escalabilidad necesaria para conseguir reducir el tiempo por debajo de 100 segundos. Sin embargo, los métodos desarrollados pueden ser integrados en una aplicación híbrida MPI-OpenMP, que consigue alcanzar los objetivos de tiempo establecidos para mapas muy grandes.<br>Forest fires are natural disasters that every year cause significant losses. Knowing in advance their evolution is of great importance to mitigate their effects. There are several models that provide a prediction of fire propagation. The wind is a fundamental parameter of these models, but it is modified by the terrain, and it is necessary to couple wind field models. Wind field simulators, such as WidnNinja, discretize the terrain in a mesh of points and apply the corresponding equations to constitute a system of equations of the form Ax = b. In the particular case of WindNinja, mass conservation equations and Dirichlet boundary conditions are applied. When the map is very large, the system of equations has hundreds of millions of unknowns and cannot be solved by direct methods, so that iterative methods are applied, such as Precondcionated Conjugate Gradient (PCG). Solving such systems takes too much time that cannot be taken in operational situations. Therefore, it is necessary to apply parallelization techniques. Specifically, three techniques have been applied to accelerate the calculation of wind field with WindNinja: • Data parallelism has been exploited, using partition map. A methodology that determines the partition map, to reduce the execution time without losing accuracy in the calculation of wind field, beyond acceptable limits, has been developed. • Domain decomposition has been applied. It allows parallelizing the resolution of the system of equations by applying methods with overlaping (Schwarz) or methods without overlaping (Schur). • It has been determined that the most time consuming operation of the PCG is the sparse matrix-vector multiplication and a storage format (Vectorizing Diagonal Sparse Matrix VDSpM) speeding up the operation has been developed. The three methods are able to reduce execution times, but when the maps are very large, none of the three has the scalability to reduce the time to get below 100 seconds. However, the methods developed can be integrated into a hybrid MPI-OpenMP aplication, getting achieve the execution time objectives for very large maps.

Ingeniero Civil en Computación<br>El estudio cuantitativo de estructuras microscópicas 3D requiere de herramientas computacionales, tanto para realizar mediciones como para su visualización, dada su complejidad y gran volumen. Una de las herramientas para medir y visualizar estas estructuras es el skeleton. Un skeleton es la representacion simplificada de la estructura en forma de grafo, compuesta por nodos y segmentos. Si bien existen múltiples algoritmos para su generación, estos buscan generalmente mantener propiedades topológicas y geométricas del objeto de estudio. Actualmente se cuenta con la implementación de un algoritmo de generación de skeletons [2], basado en el algoritmo propuesto por Au et al [3]. Esta implementación, si bien entrega resultados satisfactorios, presenta tiempos de cálculo muy extensos. Dado lo anterior, es que esta memoriam tiene como objetivo analizar y optimizar el tiempo de ejecución de esta implementación. En este trabajo se realizaron optimizaciones seriales y la paralelización del cálculo. La optimización serial incluyó: (1) implementación del algoritmo con una nueva estructura de datos: Halfedge, (2) optimización en la actualización de costos de arcos, (3) optimización en el uso de la cola de costos y (4) optimización de estructuras de datos. La paralelización fue realizada sobre una de las etapas más demandantes del algoritmo usando la unidad de procesamiento gráfico (GPU). Para validar las optimizaciones y paralelización, se realizaron pruebas de la correctitud y speed-up alcanzado en: (1) modelos 3D creados simples, (2) modelos sintéticos de estructuras biológicas y (3) modelos de estructuras biológicas obtenidas de imágenes de microscopía. Con las optimizaciones y paralelización implementados, se logró una mejora sustancial en el tiempo, pasando de días a minutos o incluso segundos. Además, se verificó que estas mejoras mantienen los skeletons resultantes bien definidos, vale decir, mantienen las propiedades que deben cumplir.

The Ph.D. thesis addresses a comprehensive study of the bee colonyoptimization meta-heuristic method (BCO). Theoretical analysis of themethod is conducted with the tools of probability theory. Necessary andsufficient conditions are presented that establish convergence of the BCOmethod towards an optimal solution. Three parallelization strategies and fivecorresponding implementations are proposed for BCO for distributed-memorysystems. The influence of method&rsquo;s parameters on the performance of theBCO algorithm for two combinatorial optimization problems is analyzedthrough the experimental study.<br>Докторска дисертације се бави испитивањем метахеуристичке методеоптимизације колонијом пчела. Извршена је теоријска анализаасимптотске конвергенције методе посматрањем конвергенције низаслучајних променљивих. Установљени су довољни и потребни условиза које метода конвергира ка оптималном решењу. Предложене су тристратегије паралелизације и пет одговарајућих имплементација конст-руктивне варијанте методе за рачунаре са дистрибуираном меморијом.Извршено је експериментално испитивање утицаја параметара методена њене перформансе за два различита комбинаторна проблема:проблем распоређивања и проблем задовољивости.<br>Doktorska disertacije se bavi ispitivanjem metaheurističke metodeoptimizacije kolonijom pčela. Izvršena je teorijska analizaasimptotske konvergencije metode posmatranjem konvergencije nizaslučajnih promenljivih. Ustanovljeni su dovoljni i potrebni usloviza koje metoda konvergira ka optimalnom rešenju. Predložene su tristrategije paralelizacije i pet odgovarajućih implementacija konst-ruktivne varijante metode za računare sa distribuiranom memorijom.Izvršeno je eksperimentalno ispitivanje uticaja parametara metodena njene performanse za dva različita kombinatorna problema:problem raspoređivanja i problem zadovoljivosti.

Ingeniero Civil en Computación<br>La resolución de diversos problemas en ciencia e ingeniería, requiere el apoyo de soluciones y herramientas computacionales que permitan representar, visualizar y modelar sus objetos de estudio, como superficies, terrenos o células. Una forma de representar estos objetos es mediante el uso de mallas geométricas, sobre las cuales se realizan operaciones y simulaciones para modelar los problemas inherentes a cada disciplina. Uno de los principales problemas asociados a trabajar con mallas geométricas, es el tiempo que demoran en ser procesadas. Con el auge de las tarjetas y procesadores gráficos (GPU), se han investigado nuevas técnicas que permitan usar el poder de computo de estas unidades, para desarrollar e implementar estos algoritmos. Actualmente se cuenta con una librería (llamada Cleap), la cual permite realizar la operación de triangulación de Delaunay en Paralelo usando GPU s de marca Nvidia. A ella, se desea integrar otros algoritmos que trabajen con mallas geométricas, como algoritmos de suavizado y simplificación, además de comparar su rendimiento y calidad con otras implementaciones ya existentes. En este trabajo, se investigó sobre algoritmos de suavizado, triangulación y simplificación de mallas geométricas, y luego se implementaron versiones de los dos primeros, los cuales fueron integrados en Cleap, y se comparó el rendimiento y calidad de sus soluciones. Con respecto al algoritmo de simplificación, solo se llegó hasta la fase de investigación teórica, pero se obtuvo la información y conocimientos necesarios para implementar e integrar una versión de este algoritmo. Los resultados muestran que el uso de la GPU permite reducir considerablemente los tiempos de ejecución, cuando se trabaja con mallas de gran tamaño, en comparación a sus contrapartes secuenciales, y que la calidad de sus resultados es similar o incluso mejor a la de las implementaciones conocidas actualmente. Estos resultados también muestran que no siempre lo que se espera teóricamente, ocurre en la práctica, debido a problemas y fallos que ocurren al realizar cálculos con error asociado, y detalles particulares asociados a una arquitectura o plataforma determinada.