Parallelizing Population Genetics Applications

Amb la creixent disponibilitat de dades a escala de l'genoma per a la investigació genètica, els genetistes de poblacions moleculars han de treballar amb models més complexos, el que no pot fer-se en un temps determinat utilitzant el mètode coalescent estàndard. Aquest escenari va dur a el desenvolupament de diverses aplicacions alternatives de simulació numèrica. Tot i l'accés cada vegada més gran a les agrupacions de computació d'alt rendiment (HPC) a l'acadèmia, no s'està aprofitant en el camp de la genètica de poblacions. L'establiment de paral·lels entre les aplicacions existents és difícil d'aconseguir pels desenvolupadors sense una comprensió completa de la HPC, i les noves aplicacions només aprofiten les capacitats de multiprocessament d'una sola computadora. En aquesta tesi es proposa una metodologia per establir un paral·lelisme entre les aplicacions coalescents i utilitzar eficaçment tota la potència de processament disponible d'un grup d'HPC. La metodologia introdueix una estratègia per reduir les comunicacions intra-node en el paradigma de pas de missatges. Aquesta solució permet obtenir una millor escalabilitat per a les aplicacions coalescents que requereixen la generació de milions de rèpliques. Com a resultat, els genetistes de poblacions poden utilitzar les eines coalescents estàndard per executar l'anàlisi de Computació Bayesiana Aproximada (ABC) sense dependre d'aplicacions menys precises. Hem avaluat la nostra estratègia establint un paral·lelisme amb l'aplicació coalescent estàndard de facto i executant experiments a escala de l'genoma en un conglomerat HPC real. Afinant diferents aspectes de la nostra metodologia, hem obtingut importants guanys de rendiment, donant lloc a una velocitat de 4x per sobre de la nostra paral·lelització inicial, que representava una velocitat de 50x per sobre de l'aplicació coalescent de referència.Con la creciente disponibilidad de datos a escala del genoma para la investigación genética, los genetistas de poblaciones moleculares tienen que trabajar con modelos más complejos, lo que no puede hacerse en un tiempo determinado utilizando el método coalescente estándar. Este escenario llevó al desarrollo de varias aplicaciones alternativas de simulación numérica. A pesar del acceso cada vez mayor a las agrupaciones de computación de alto rendimiento (HPC) en la academia, no se está aprovechando en el campo de la genética de poblaciones. El establecimiento de paralelos entre las aplicaciones existentes es difícil de lograr por los desarrolladores sin una comprensión completa de la HPC, y las nuevas aplicaciones sólo aprovechan las capacidades de multiprocesamiento de una sola computadora. En esta tesis se propone una metodología para establecer un paralelismo entre las aplicaciones coalescentes y utilizar eficazmente toda la potencia de procesamiento disponible de un grupo de HPC. La metodología introduce una estrategia para reducir las comunicaciones intra-nodo en el paradigma de paso de mensajes. Esta solución permite obtener una mejor escalabilidad para las aplicaciones coalescentes que requieren la generación de millones de réplicas. Como resultado, los genetistas de poblaciones pueden utilizar las herramientas coalescentes estándar para ejecutar el análisis de Computación Bayesiana Aproximada (ABC) sin depender de aplicaciones menos precisas. Hemos evaluado nuestra estrategia estableciendo un paralelismo con la aplicación coalescente estándar de facto y ejecutando experimentos a escala del genoma en un conglomerado HPC real. Afinando diferentes aspectos de nuestra metodología, hemos obtenido importantes ganancias de rendimiento, cuadruplicando el speedup de nuestra paralelización inicial, la cual representaba una mejora de 50x sobre la aplicación coalescente de referencia.With the increasing availability of genome-scale data for genetic research, molecular population geneticists need to work with more complex models, which cannot be done in a time-fashion using the standard coalescent methods. This scenario led to the development of several alternative numerical simulation applications. Despite the ever-increasing access to High Performance Computing (HPC) clusters in the academy, it is not being leveraged in the field of population genetics. Parallelizing existing applications is hard to achieve by developers without a comprehensive understanding of the HPC, and new applications only take advantage of multiprocessing capabilities from a single computer. This thesis proposes a technique to parallelize coalescent applications and effectively use all the available processing power from an HPC cluster. We use a strategy to reduce the intra- node communications in the message-passing paradigm. This solution allows for getting better scalability for coalescent applications that require generating millions of replicas. As a result, population geneticists can use the standard coalescent tools for running Approximate Bayesian Computation (ABC) analysis without relying on less accurate applications. We have evaluated our strategy parallelizing the de facto standard coalescent application and run experiments at genome-scale in a real HPC cluster. We have obtained significant performance gains in tuning different aspects of our approach, leading to a 4x speedup over our initial parallelization, which accounted for a 50x speedup over the reference coalescent application