La tesis presenta, el desarrollo de una propuesta de arquitectura para el análisis automático de prestaciones de aplicaciones paralelas desarrolladas bajo paradigmas de programación de paso explicito de mensajes.A lo largo de los capítulos que configuran la misma: se han analizado diferentes aspectos que tienen que ver con el ámbito de aplicación, ya sea introduciendo los sistemas paralelos y distribuidos usados como base, así como las métricas base de prestaciones. Dando una visión de diferentes técnicas base para la monitorización, como el tracing y profiling, y como se han usado como primer paso de las herramientas clásicas de análisis de prestaciones, normalmente basadas en técnicas de visualización. Las deficiencias de estas, así como el amplio conocimiento necesario para intepretar correctamente los datos proporcionados, nos llevan a considerar herramientas de un nivel superior, que proporcionen automatismos más allá de la monitorización y nos permitan obtener resultados interpretables y útiles directamente para la mejora de las prestaciones de las aplicaciones.La arquitectura propuesta, mediante diferentes fases de monitorización, detección de problemas, clasificación según su relevancia, análisis de sus causas, y la emisión de sugerencias sobre actuaciones nos permite minimizar y/o hacer desaparecer las ineficiencias causadas por los problemas de prestaciones aparecidos durante la ejecución de las aplicaciones.Entre los objetivos de la arquitectura propuesta, se encuentran: a) La especificación del conocimiento de prestaciones, mediante la introducción de conocimiento en forma de estructura de problemas, y del análisis de sus causas, de forma que permita ampliar el conocimiento que en cada momento pueda disponer la herramienta. b) Independencia de los mecanismos de detección de los problemas concretos definidos. c) Independencia del sistema base de paso de mensajes utilizado. d) Relación de los problemas con el código fuente de la aplicación, para establecer que puntos están relacionados con los problemas. e) La emisión de sugerencias útiles de cara al usuario final para proporcionar actuaciones directas sobre el código de la aplicación para mejorar sus prestaciones.Los resultados experimentales obtenidos sobre un prototipo de herramienta basada en la arquitectura propuesta, demuestran la viabilidad de las de las propuestas formuladas en esta tesis. La herramienta ha sido probada con un amplio conjunto de aplicaciones paralelas y distribuidas para demostrar esta viabilidad, comprobando que la metodología es eficaz, fiable y beneficiosa y que puede ser usada para mejoras reales del rendimiento de las aplicaciones. / The thesis presents, the development of a architectural proposal for the automatic performance analysis of parallel applications developed in programming paradigms of explicit message passing.In the chapters that form the thesis: different aspects have been analyzed that they have to do with the field of application, by introducing the parallel and distributed systems used as base systems, as well the base metrics of performance. Giving a vision of different techniques for monitoring, like tracing and profiling, and since they have used like the first step in the classic tools of performance analysis, normally based on visualization techniques. The deficiencies of these tools, as well as the wide knowledge necessary to interpret the obtained data correctly, takes us to consider tools of a superior level, that provide automatism beyond the monitoring process and they allow us to directly obtain interpretable and useful results for the improvement of the performance of the applications.The architectural proposal, is composed of different phases: from monitoring, detection of problems, classification according to his relevance, analysis of its causes, and the emission of hints on performance that allows us to minimize and/or to make disappear the inefficiencies caused by the performance problems appeared during the execution of the applications.The main goals of the proposed architecture are: a) Ability to specify the performance knowledge, by means of the introduction of knowledge in a form of the structure of the performance problems, and of the analysis of its causes. So, this specification allows us to extend the performance knowledge that every moment can have the tool. b) Independence of the mechanisms of detection of the defined performance problems. c) Independence of environment of message passing used. d) Relation of the problems with the source code of the application, to establish that points are related to the performance problems. e) The emission of useful suggestions/hints facing the end user to provide direct operating points on the code of the application to improve its performance.The experimental results obtained in a tool prototype based on the architecture demonstrate the viability of those of the proposals formulated in this thesis. The tool has been proven with an ample set of parallel and distributed applications to demonstrate this viability, verifying that the methodology is effective, feasible, and profitable and that can be used for a real improvement of the program performance.

Magíster en Ciencias, Mención Computación / Ingeniero Civil en Computación / La proliferación de sistemas con múltiples núcleos de procesamiento ha transformado la aplicación de técnicas de programación paralela en uno de los tópicos más estudiados en los últimos años, ello en pos de mejorar los rendimientos generales de cualquier operación. Una aplicación práctica de dicho enfoque es en el procesamiento de requerimientos DNS, los cuales han evidenciado un gran aumento de la mano del desarrollo de la Internet y la masificación de distintos tipos de dispositivos que demandan conectividad, y que por sus características son un buen candidato a un enfoque de procesamiento paralelo. Sin embargo, distintas investigaciones han revelado que la aplicación de técnicas multithreading per se no son una estrategia que garantice un escalamiento en los resultados. Distintas empresas de carácter global (como Google, Facebook y Toshiba) así como investigaciones locales (de la mano de NIC Chile) han reconocido la existencia de este problema, reiterando responsabilidades a los Internet Sockets provistos por el kernel de Linux, los cuales al ser expuestos a un consumo concurrente degradan su capacidad de consumo de datos y rendimiento general, aún cuando existe poder de cómputo excedente. Así estas empresas y otros trabajos de investigación han planteado varias hipótesis teóricamente razonables para explicar dicho comportamiento pero sin concretar las mismas en términos experimentales que permitan confirmarlas o desmentirlas. La presente investigación plantea un estudio experimental del caso de los Sockets UDP que combina técnicas de profiling y testing de distinto nivel, a fin de verificar las principales sospechas vigentes que den explicación al problema en cuestión, reunidas en 3 líneas de trabajo: Problemas de distribución de carga, degradación del rendimiento por mecanismos de bloqueo y problemas de manejo de caché y defectos de contención de recursos. En la misma línea, se ilustra el impacto de fenómeno de contención de recursos en un escenario concurrente y su repercusión en los canales de comunicación en el procesamiento de datos en arquitecturas modernas multiprocesador como la estudiada. Es fruto de este trabajo un veredicto por cada estudio que concluya explicando las características inherentes a los Internet Sockets que expliquen su mal desempeño, bajo los distintos análisis efectuados. Posteriormente, la investigación se traslada a estudiar la técnica denominada reuseport, un desarrollo de ingenieros de Google que plantea una solución al problema presentado y que promete mitigar el efecto negativo causado por el uso de multithreading en el contexto estudiado. Así también, se repasan aspectos como el rendimiento de este enfoque, y ciertas debilidades del mismo. Finalmente, es producto del presente trabajo el planteamiento e implementación de una solución propia al problema que, inspirado en el diseño de reuseport e implementado como un módulo del kernel, provee un mecanismo de distribución de paquetes que permite optar a mejoras de desempeño en el procesamiento de los mismos usando técnicas de procesamiento paralelo clásicas. Una solución que --en su configuración estándar-- provee un rendimiento competitivo a reuseport, pero que gracias a ser ampliamente configurable permite postular a mejores resultados que reuseport en contextos no uniformes de distribución de paquetes.

En el presente trabajo se estudió y rediseñó una implementación existente del algoritmo Filter-SDP, el cual resuelve problemas de programación semidefinida no lineal de la forma: donde f : Rn → R, h : Rn → Rp y G : Rn → Sm son funciones de clase C2 y Sm denota el espacio lineal de las matrices simétricas de m×m dotado del producto interno A·B = . El algoritmo resuelve en cada iteración una aproximación local representada por un problema de programación semidefinida lineal, y adicionalmente se utiliza un esquema de penalización multi-objetivo, en el cual se minimiza la función objetivo y una función de mérito utilizando un filtro. Se estudió la introducción de cálculo paralelo en partes específicas del algoritmo, con el objetivo de disminuir el tiempo de ejecución. Se reimplementó el algoritmo utilizando el lenguaje C y la librería de cálculo paralelo MPI. Esa nueva implementación se comparó con un desarrollo ya existente, realizado sobre la plataforma MATLAB, y se midió su speedup en los problemas más pesados de una batería de tests escogida. Como apoyo al desarrollo del algoritmo, se diseñaron nuevas fases de restauración sobre la plataforma MATLAB, con el objetivo de mejorar la calidad de las soluciones obtenidas. Se diseñaron 4 nuevos métodos para la fase de restauración del algoritmo, cuyas principales áreas de influencia son la restauración inexacta, el diseño de controladores retroalimentados de salida estática y el posicionamiento de polos. Dentro de los resultados obtenidos, se logró visualizar las ventajas de la nueva implementación con respecto al desarrollo ya existente, así como demostrar el beneficio que se obtiene en el speedup para problemas pesados. También se realizó una comparación entre los métodos diseñados para la fase de restauración, con la cual se llegó a conclusiones que pueden abrir nuevas áreas de investigación y trabajo a futuro. Finalmente, se aprendió a utilizar una herramienta de álgebra lineal que funciona sobre ambientes de cálculo paralelo, ScaLAPACK, y se perfeccionó el proceso de desarrollo de software que ya se tenía sobre este tipo de plataformas.

Magíster en Ciencias, Mención Computación / Esta tesis propone una forma novedosa para introducir características autonómicas de auto-configuración y auto-optimización a Patrones de Paralelismo (o Algorithmic Skeletons en inglés) usando técnicas de la Programación Dirigida por Eventos (o EDP por sus siglas en inglés). Gracias al uso de la programación dirigida por eventos, la solución propuesta en esta tesis presenta las siguientes contribuciones a las soluciones actuales: - No está relacionada a una arquitectura de aplicaciones en particular, por ejemplo la arquitectura de componentes. De esta forma, presenta una solución con un mayor alcance y es independiente de la arquitectura usada para la implementación de los patrones de paralelismo. - Provee un mayor nivel de adaptabilidad por permitir la introducción de cambios estructurales en tiempo de ejecución. A diferencia de otras soluciones que solo permiten la introducción de este tipo de cambios durante la compilación. - Los estimados de trabajo futuro pueden ser calculados en tiempo de ejecución y no hay dependencia a estimados pre-calculados en ejecuciones anteriores. Las características autonómicas presentadas en esta tesis se enfocan principalmente en garantizar un tiempo de ejecución a un patron de paralelismo por medio de la optimización de la cantidad de hilos de ejecución usados. Las calidades de servicio (QoS por sus siglas en inglés) usadas para este fin son: (1) tiempo de ejecución percibido por el usuario y (2) nivel de paralelismo. Otras contribuciones de esta tesis son: - Diseño e implementación de una novedosa solución a la separación de asuntos en los patrones de paralelismo usando técnicas de la programación dirigida por eventos. Esta solución novedosa permite la introducción de asuntos no-funcionales a los patrones de paralelismo sin disminuir sus abstracciones de alto nivel. - Evaluación de diferentes estrategias de estimación de trabajo futuro con el fin de realizar recomendaciones relacionadas a responder a la pregunta ¿Qué estrategia produce mejores estimados bajo qué circunstancias?

El cálculo de la trayectoria de partículas en la atmósfera es una actividad abordada desde hace mucho tiempo, tomando en cuenta un enfoque clásico del uso de los computadores, en el cual se utilizan sus recursos como Procesador Central (CPU) y Memoria RAM. Este enfoque, que ha servido para alcanzar los logros actuales, con predicciones bastante acertadas, aún adolece de problemas claves y en cierta medida irresolubles, que se ven acentuados cuando los procesos se hacen más complejos, ya sea incorporando muchas partículas, o tomando en cuenta modelos de desplazamiento más realistas. El presente trabajo aborda un enfoque totalmente nuevo, el cual hace uso de una componente física de los computadores llamada “Tarjeta Gráfica”, la cual cuenta con su propia unidad de procesamiento gráfico llamada GPU por sus siglas en inglés. Esta componente, gracias a su gran cantidad de núcleos, ofrece la posibilidad de realizar paralelamente entre sí todos, o una parte de los cálculos que le son asignados, de una manera mucho más potente que lo conseguido en la actualidad al hacer uso solamente de CPU. Este problema es abordado mediante la implementación de un programa en dos versiones: una para funcionar exclusivamente en CPU y la otra para hacer uso de GPU en los cálculos. De esta manera se puede contar con un método directo para comparar el desempeño de estos dos enfoques, contrastarlos entre sí, y deducir los casos en que uno supera al otro. El principal insumo en la comparación de estos cálculos es la información del pronóstico del viento. El programa fue aplicado a una situación real: la erupción del Volcán Chaitén, para un día cuyos datos se poseían de antemano. Los resultados obtenidos fueron graficados y comparados con una imagen satelital correspondiente al mismo día simulado, siendo posible comprobar la alta similitud entre ellas. El tiempo de cálculo empleado por la versión que funciona en GPU supera en algunos casos en más de doscientas veces lo que tarda su contraparte CPU, sin afectar en gran medida la exactitud de los cálculos. Esto permite comprobar efectivamente que las GPU superan ampliamente el desempeño de las CPU, cuando el problema abordado es altamente paralelizable. Este es un tema que no está en absoluto cerrado, por cuanto son muchos los caminos donde seguir explorando las ventajas y desventajas del uso de GPU para estos cálculos. Por ejemplo se puede ver cómo funcionan las GPU incorporando procesos físicos más complejos para el cálculo de los desplazamientos de las partículas, o se puede considerar algunas propiedades físicas de estas partículas, como lo es la masa por ejemplo.

Ingeniero Civil Mecánico / 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.

Una de las áreas de mayor interés y crecimiento en los últimos años dentro del procesamiento paralelo es la del tratamiento de grandes volúmenes de datos, tales como las secuencias de ADN. El tipo de procesamiento extensivo de comparación para analizar patrones genéticos requiere un esfuerzo importante en el desarrollo de algoritmos paralelos eficientes. El alineamiento de secuencias de ADN representa una de las operaciones más importantes dentro de la bioinformática. En 1981, Smith y Waterman desarrollaron un método para el alineamiento local de secuencias. Sin embargo, en la práctica se emplean diversas heurísticas en su lugar, debido a los requerimientos de procesamiento y de memoria del algoritmo Smith-Waterman. Si bien son más rápidas, las heurísticas no garantizan que el alineamiento óptimo sea encontrado. Es por ello que resulta interesante estudiar cómo aplicar la potencia de cómputo de plataformas paralelas actuales de manera de acelerar el proceso de alinear secuencias sin perder precisión en los resultados. Los niveles insostenibles de generación de calor y consumo de energía que se presentan al escalar al máximo la velocidad de los procesadores mononúcleos motivaron el surgimiento de los procesadores de múltiples núcleos (multicore). Un procesador multicore integra dos o más núcleos computacionales dentro de un único chip y, si bien estos son más simples y menos veloces, al combinarlos permiten mejorar el rendimiento global del procesador y al mismo tiempo hacerlo más eficiente energéticamente. Al incorporar este tipo de procesadores a los clusters convencionales, se da origen a una arquitectura conocida como cluster de multicores, que combina memoria compartida y distribuida, y donde la comunicación entre las diferentes unidades de procesamiento resulta ser heterogénea. En este trabajo se presenta un algoritmo paralelo distribuido para el alineamiento de secuencias de ADN basado en el método Smith-Waterman para ser ejecutado sobre las arquitecturas de cluster actuales. Además, se realiza un análisis de rendimiento del mismo. Por último, se presentan las conclusiones y las posibles líneas de trabajo futuro.

Esta tesis investiga la implementación hardware eficiente de los sistemas de memoria transaccional (HTM) en un chip multiprocesador escalable (CMP), identificando aspectos que limitan el rendimiento y proponiendo técnicas que solventan dichas patologías. Las contribuciones de la tesis son varios diseños HTM complementarios que alcanzan un rendimiento robusto y evitan comportamientos patológicos, mediante la introducción de flexibilidad y adaptabilidad, sin que dichas técnicas apenas supongan un incremento en la complejidad del sistema global. Esta disertación considera tanto sistemas HTM de política ansiosa como aquellos diseñados bajo el enfoque perezoso, y afrontamos las sobrecargas en el rendimiento que son inherentes a cada política. Quizá la contribución más relevante de esta tesis es ZEBRA, un sistema HTM de política híbrida que adapta su comportamiento en función de las características dinámicas de la carga de trabajo. / This thesis focuses on the hardware mechanisms that provide optimistic concurrency control with guarantees of atomicity and isolation, with the intent of achieving high-performance across a variety of workloads, at a reasonable cost in terms of design complexity. This thesis identifies key inefficiencies that impact the performance of several hardware implementations of TM, and proposes mechanisms to overcome such limitations. In this dissertation we consider both eager and lazy approaches to HTM system design, and address important sources of overhead that are inherent to each policy. This thesis presents a hybrid-policy, adaptable HTM system that combines the advantages of both eager and lazy approaches in a low complexity design. Furthermore, this thesis investigates the overheads of the simpler, fixed-policy HTM designs that leverage a distributed directory-based coherence protocol to detect data races over a scalable interconnect, and develops solutions that address some performance degrading factors.

En esta tesis hemos identificado tres de los mayores cuellos de botella para el rendimiento y escalabilidad de las arquitecturas many-core CMP de memoria compartida. En particular, los mecanismos de sincronización de barrera y cerrojo cuando presentan alta contención, así como los protocolos hardware de coherencia de caché en el mantenimiento de la coherencia del uso de bloques memoria compartidos en una jerarquía de memoria. Para paliar estas deficiencias y aprovechar más el rendimiento de estas arquitecturas, hemos propuesto tres mecanismos hardware: GBarrier, para un mecanismo de barreras eficiente; GLock, para un manejo justo y eficiente de la contención en el acceso a las secciones críticas protegidas por cerrojos; y ECONO, un protocolo de coherencia muy simple que aporta gran eficiencia a bajo costo. La tesis concluye que nuestras propuestas resuelven de manera eficiente los problemas de rendimiento derivados de implementaciones ineficientes para sincronización y coherencia en arquitecturas many-core CMP. / In this thesis we have identified three of the major problems that restrict efficiency and scalability in future shared-memory tiled many-core CMPs. In particular, the synchronization operations of barriers and locks under highly-contended scenarios, and the hardware-based cache coherence protocols when dealing with the maintenance of coherence of all memory blocks across all levels of a memory hierarchy. To alleviate such performance bottlenecks in order to harness the computational power of such systems, we have proposed three hardware-based mechanisms: GBarrier, a very efficient barrier mechanism; GLock, an efficient and fair mechanism to implement highly-contended locks; and ECONO, a simple and efficient hardware coherence protocol. In light of our performance results obtained in this thesis, we can affirm that our proposals represent a step forward towards the resolution of the challenges that many-core CMP architectures will pose to computer architects.

El desarrollo de una herramienta computacional basada en el método de elementos finitos (FEM) para modelar numéricamente el proceso de transporte de pulpas minerales en tuberías circulares horizontales es el tema principal en este trabajo. Las pulpas minerales son consideradas aquí como un fluido monofásico con propiedades reológicas de fluidos no Newtonianos. La herramienta computacional es implementada siguiendo un paradigma de programación orientada a objetos, usando C++ como lenguaje de programación principal, y una metodología de descomposición de dominio para su paralelización. La referida herramienta es validada realizando simulaciones numéricas de múltiples casos de estudio involucrando flujos de fluidos Newtonianos y no Newtonianos. En esta etapa de validación, errores máximos de 3% en tuberías circulares horizontales transportando pulpas minerales reales son obtenidos. Luego de ser validada, la herramienta computacional es utilizada para estudiar parámetros importantes en el diseño de sistemas de transporte de pulpas minerales. Más específicamente, parámetros relativos a la viscosidad, grado de concentración de partículas, velocidad de la fase continua y caída de presión son particularmente analizados. El principal aporte de este trabajo es el desarrollo de una nueva herramienta computacional basada en FEM para modelar adecuadamente flujos viscosos no Newtonianos, permitiendo resolver problemas prácticos de diseño de tuberías circulares horizontales transportando pulpas minerales reales. Además, comparado con otros enfoques paralelos reportados en la literatura, el utilizado aquí es relativamente fácil de implementar en herramientas de dinámica de fluidos computacional. Así, otra de las contribuciones de este trabajo es el desarrollo de un algoritmo en paralelo adecuado para herramientas basadas en FEM que modelen pulpas minerales. Finalmente, otra de las contribuciones de este trabajo está asociada con el estudio numérico por primera vez de pulpas minerales reales recientemente caracterizadas en la literatura.