Tesis por compendio / [EN] The work done for this doctorate thesis focuses on error correction of Next Generation Sequencing (NGS) data in the context of High Performance Computing (HPC). Due to the reduction in sequencing cost, the increasing output of the sequencers and the advancements in the biological and medical sciences, the amount of NGS data has increased tremendously. Humans alone are not able to keep pace with this explosion of information, therefore computers must assist them to ease the handle of the deluge of information generated by the sequencing machines. Since NGS is no longer just a research topic (used in clinical routine to detect cancer mutations, for instance), requirements in performance and accuracy are more stringent. For sequencing to be useful outside research, the analysis software must work accurately and fast. This is where HPC comes into play. NGS processing tools should leverage the full potential of multi-core and even distributed computing, as those platforms are extensively available. Moreover, as the performance of the individual core has hit a barrier, current computing tendencies focus on adding more cores and explicitly split the computation to take advantage of them. This thesis starts with a deep analysis of all these problems in a general and comprehensive way (to reach out to a very wide audience), in the form of an exhaustive and objective review of the NGS error correction field. We dedicate a chapter to this topic to introduce the reader gradually and gently into the world of sequencing. It presents real problems and applications of NGS that demonstrate the impact this technology has on science. The review results in the following conclusions: the need of understanding of the specificities of NGS data samples (given the high variety of technologies and features) and the need of flexible, efficient and accurate tools for error correction as a preliminary step of any NGS postprocessing. As a result of the explosion of NGS data, we introduce MuffinInfo. It is a piece of software capable of extracting information from the raw data produced by the sequencer to help the user understand the data. MuffinInfo uses HTML5, therefore it runs in almost any software and hardware environment. It supports custom statistics to mould itself to specific requirements. MuffinInfo can reload the results of a run which are stored in JSON format for easier integration with third party applications. Finally, our application uses threads to perform the calculations, to load the data from the disk and to handle the UI. In continuation to our research and as a result of the single core performance limitation, we leverage the power of multi-core computers to develop a new error correction tool. The error correction of the NGS data is normally the first step of any analysis targeting NGS. As we conclude from the review performed within the frame of this thesis, many projects in different real-life applications have opted for this step before further analysis. In this sense, we propose MuffinEC, a multi-technology (Illumina, Roche 454, Ion Torrent and PacBio -experimental), any-type-of-error handling (mismatches, deletions insertions and unknown values) corrector. It surpasses other similar software by providing higher accuracy (demonstrated by three type of tests) and using less computational resources. It follows a multi-steps approach that starts by grouping all the reads using a k-mers based metric. Next, it employs the powerful Smith-Waterman algorithm to refine the groups and generate Multiple Sequence Alignments (MSAs). These MSAs are corrected by taking each column and looking for the correct base, determined by a user-adjustable percentage. This manuscript is structured in chapters based on material that has been previously published in prestigious journals indexed by the Journal of Citation Reports (on outstanding positions) and relevant congresses. / [ES] El trabajo realizado en el marco de esta tesis doctoral se centra en la corrección de errores en datos provenientes de técnicas NGS utilizando técnicas de computación intensiva. Debido a la reducción de costes y el incremento en las prestaciones de los secuenciadores, la cantidad de datos disponibles en NGS se ha incrementado notablemente. La utilización de computadores en el análisis de estas muestras se hace imprescindible para poder dar respuesta a la avalancha de información generada por estas técnicas. El uso de NGS transciende la investigación con numerosos ejemplos de uso clínico y agronómico, por lo que aparecen nuevas necesidades en cuanto al tiempo de proceso y la fiabilidad de los resultados. Para maximizar su aplicabilidad clínica, las técnicas de proceso de datos de NGS deben acelerarse y producir datos más precisos. En este contexto es en el que las técnicas de comptuación intensiva juegan un papel relevante. En la actualidad, es común disponer de computadores con varios núcleos de proceso e incluso utilizar múltiples computadores mediante técnicas de computación paralela distribuida. Las tendencias actuales hacia arquitecturas con un mayor número de núcleos ponen de manifiesto que es ésta una aproximación relevante. Esta tesis comienza con un análisis de los problemas fundamentales del proceso de datos en NGS de forma general y adaptado para su comprensión por una amplia audiencia, a través de una exhaustiva revisión del estado del arte en la corrección de datos de NGS. Esta revisión introduce gradualmente al lector en las técnicas de secuenciación masiva, presentando problemas y aplicaciones reales de las técnicas de NGS, destacando el impacto de esta tecnología en ciencia. De este estudio se concluyen dos ideas principales: La necesidad de analizar de forma adecuada las características de los datos de NGS, atendiendo a la enorme variedad intrínseca que tienen las diferentes técnicas de NGS; y la necesidad de disponer de una herramienta versátil, eficiente y precisa para la corrección de errores. En el contexto del análisis de datos, la tesis presenta MuffinInfo. La herramienta MuffinInfo es una aplicación software implementada mediante HTML5. MuffinInfo obtiene información relevante de datos crudos de NGS para favorecer el entendimiento de sus características y la aplicación de técnicas de corrección de errores, soportando además la extensión mediante funciones que implementen estadísticos definidos por el usuario. MuffinInfo almacena los resultados del proceso en ficheros JSON. Al usar HTML5, MuffinInfo puede funcionar en casi cualquier entorno hardware y software. La herramienta está implementada aprovechando múltiples hilos de ejecución por la gestión del interfaz. La segunda conclusión del análisis del estado del arte nos lleva a la oportunidad de aplicar de forma extensiva técnicas de computación de altas prestaciones en la corrección de errores para desarrollar una herramienta que soporte múltiples tecnologías (Illumina, Roche 454, Ion Torrent y experimentalmente PacBio). La herramienta propuesta (MuffinEC), soporta diferentes tipos de errores (sustituciones, indels y valores desconocidos). MuffinEC supera los resultados obtenidos por las herramientas existentes en este ámbito. Ofrece una mejor tasa de corrección, en un tiempo muy inferior y utilizando menos recursos, lo que facilita además su aplicación en muestras de mayor tamaño en computadores convencionales. MuffinEC utiliza una aproximación basada en etapas multiples. Primero agrupa todas las secuencias utilizando la métrica de los k-mers. En segundo lugar realiza un refinamiento de los grupos mediante el alineamiento con Smith-Waterman, generando contigs. Estos contigs resultan de la corrección por columnas de atendiendo a la frecuencia individual de cada base. La tesis se estructura por capítulos cuya base ha sido previamente publicada en revistas indexadas en posiciones dest / [CA] El treball realitzat en el marc d'aquesta tesi doctoral se centra en la correcció d'errors en dades provinents de tècniques de NGS utilitzant tècniques de computació intensiva. A causa de la reducció de costos i l'increment en les prestacions dels seqüenciadors, la quantitat de dades disponibles a NGS s'ha incrementat notablement. La utilització de computadors en l'anàlisi d'aquestes mostres es fa imprescindible per poder donar resposta a l'allau d'informació generada per aquestes tècniques. L'ús de NGS transcendeix la investigació amb nombrosos exemples d'ús clínic i agronòmic, per la qual cosa apareixen noves necessitats quant al temps de procés i la fiabilitat dels resultats. Per a maximitzar la seua aplicabilitat clínica, les tècniques de procés de dades de NGS han d'accelerar-se i produir dades més precises. En este context és en el que les tècniques de comptuación intensiva juguen un paper rellevant. En l'actualitat, és comú disposar de computadors amb diversos nuclis de procés i inclús utilitzar múltiples computadors per mitjà de tècniques de computació paral·lela distribuïda. Les tendències actuals cap a arquitectures amb un nombre més gran de nuclis posen de manifest que és esta una aproximació rellevant. Aquesta tesi comença amb una anàlisi dels problemes fonamentals del procés de dades en NGS de forma general i adaptat per a la seua comprensió per una àmplia audiència, a través d'una exhaustiva revisió de l'estat de l'art en la correcció de dades de NGS. Esta revisió introduïx gradualment al lector en les tècniques de seqüenciació massiva, presentant problemes i aplicacions reals de les tècniques de NGS, destacant l'impacte d'esta tecnologia en ciència. D'este estudi es conclouen dos idees principals: La necessitat d'analitzar de forma adequada les característiques de les dades de NGS, atenent a l'enorme varietat intrínseca que tenen les diferents tècniques de NGS; i la necessitat de disposar d'una ferramenta versàtil, eficient i precisa per a la correcció d'errors. En el context de l'anàlisi de dades, la tesi presenta MuffinInfo. La ferramenta MuffinInfo és una aplicació programari implementada per mitjà de HTML5. MuffinInfo obté informació rellevant de dades crues de NGS per a afavorir l'enteniment de les seues característiques i l'aplicació de tècniques de correcció d'errors, suportant a més l'extensió per mitjà de funcions que implementen estadístics definits per l'usuari. MuffinInfo emmagatzema els resultats del procés en fitxers JSON. A l'usar HTML5, MuffinInfo pot funcionar en gairebé qualsevol entorn maquinari i programari. La ferramenta està implementada aprofitant múltiples fils d'execució per la gestió de l'interfície. La segona conclusió de l'anàlisi de l'estat de l'art ens porta a l'oportunitat d'aplicar de forma extensiva tècniques de computació d'altes prestacions en la correcció d'errors per a desenrotllar una ferramenta que suport múltiples tecnologies (Illumina, Roche 454, Ió Torrent i experimentalment PacBio). La ferramenta proposada (MuffinEC), suporta diferents tipus d'errors (substitucions, indels i valors desconeguts). MuffinEC supera els resultats obtinguts per les ferramentes existents en este àmbit. Oferix una millor taxa de correcció, en un temps molt inferior i utilitzant menys recursos, la qual cosa facilita a més la seua aplicació en mostres més gran en computadors convencionals. MuffinEC utilitza una aproximació basada en etapes multiples. Primer agrupa totes les seqüències utilitzant la mètrica dels k-mers. En segon lloc realitza un refinament dels grups per mitjà de l'alineament amb Smith-Waterman, generant contigs. Estos contigs resulten de la correcció per columnes d'atenent a la freqüència individual de cada base. La tesi s'estructura per capítols la base de la qual ha sigut prèviament publicada en revistes indexades en posicions destacades de l'índex del Journal of Citation Repor / Alic, AS. (2016). Improved Error Correction of NGS Data [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/67630 / Compendio

We describe an implementation of a multi-threaded NFFT (nonequispaced fast Fourier transform) software library and present the used parallelization approaches. Besides the NFFT kernel, the NFFT on the two-sphere and the fast summation based on NFFT are also parallelized. Thereby, the parallelization is based on OpenMP and the multi-threaded FFTW library. Furthermore, benchmarks for various cases are performed. The results show that an efficiency higher than 0.50 and up to 0.79 can still be achieved at 12 threads.

Les architectures de calcul haute performance de nos jours sont des architectures hiérarchiques et hétérogènes: hiérarchiques car elles sont composées d'une hiérarchie de mémoire, une mémoire distribuée entre les noeuds et une mémoire partagée entre les coeurs d'un même noeud. Hétérogènes due à l'utilisation des processeurs spécifiques appelés Accélérateurs tel que le processeur CellBE d'IBM et les CPUs de NVIDIA. La complexité de maîtrise de ces architectures est double. D'une part, le problème de programmabilité: la programmation doit rester simple, la plus proche possible de la programmation séquentielle classique et indépendante de l'architecture cible. D'autre part, le problème d'efficacité: les performances doivent êtres proches de celles qu'obtiendrait un expert en écrivant le code à la main en utilisant des outils de bas niveau. Dans cette thèse, nous avons proposé une plateforme de développement pour répondre à ces problèmes. Pour cela, nous proposons deux outils : BSP++ est une bibliothèque générique utilisant des templates C++ et BSPGen est un framework permettant la génération automatique de code hybride à plusieurs niveaux de la hiérarchie (MPI+OpenMP ou MPI + Cell BE). Basée sur un modèle hiérarchique, la bibliothèque BSP++ prend les architectures hybrides comme cibles natives. Utilisant un ensemble réduit de primitives et de concepts intuitifs, BSP++ offre une simplicité d'utilisation et un haut niveau d' abstraction de la machine cible. Utilisant le modèle de coût de BSP++, BSPGen estime et génère le code hybride hiérarchique adéquat pour une application donnée sur une architecture cible. BSPGen génère un code hybride à partir d'une liste de fonctions séquentielles et d'une description de l'algorithme parallèle. Nos outils ont été validés sur différentes applications de différents domaines allant de la vérification et du calcul scientifique au traitement d'images en passant par la bioinformatique. En utilisant une large sélection d'architecture cible allant de simple machines à mémoire partagée au machines Petascale en passant par les architectures hétérogènes équipées d'accélérateurs de type Cell BE.

A two-dimensional numerical model (RiverFLO-2D) has been enhanced to simulate flooding of urban areas by developing an innovative wet and dry surface algorithm, accounting for variable rainfall, and recoding the model computer program for parallel computing. The model formulation is based on the shallow water equations solved with an explicit time-stepping element-by-element finite element method. The dry-wet surface algorithm is based on a local approximation of the continuity and momentum equations for elements that are completely dry. This algorithm achieves global volume conservation in the finite element, even for flows over complex topographic surfaces. A new module was implemented to account for variable rainfall in space and time using NEXRAD precipitation estimates. The resulting computer code was parallelized using OpenMP Application Program Interface, which allows the model to run up to 5 times faster on multiple core computers. The model was verified with analytical solutions and validated with laboratory and field data. Model application to the Malpasset dam break and Sumacarcel flooding event show that the model accurately predicts flood wave travel times and water depths for these numerically demanding real cases. To illustrate the predictive capability of the enhanced model, an application was made of the city of Sweetwater flooding in Miami-Dade County, FL caused by the Hurricane Irene. The simulation starts with dry bed and rainfall is provided by NEXRAD estimates. Integrating NEXRAD rainfall estimates, developing a novel dry-wet area algorithm and parallelizing RiverFLO-2D code, this dissertation presents a proof of concept to accurately and efficiently predict floods in urban areas, identifying future improvements along this line of research.

Nuclear nonproliferation research and forensics have a need for improved software solutions, particularly in the estimates of the transmutation of nuclear fuel during burnup and depletion. At the same time, parallel computers have become effectively sized to enable full core simulations using highly-detailed 3d mesh models. In this work, the capability for modeling 3d reactor models is researched with PENBURN, a burnup/depletion code that couples to the PENTRAN Parallel Sn Transport Solver and also to the Monte Carlo solver MCNP5 using the multigroup option. This research is computationally focused, but will also compare a subset of results of experimental Pressurized Water Reactor (PWR) burnup spectroscopy data available with a designated BR3 PWR burnup benchmark. Also, this research will analyze large-scale Cartesian mesh models that can be feasibly modeled for 3d burnup, as well as investigate the improvement of finite differencing schemes used in parallel discrete ordinates transport with PENTRAN, in order to optimize runtimes for full core transport simulation, and provide comparative results with Monte Carlo simulations. Also, the research will consider improvements to software that will be parallelized, further improving large model simulation using hybrid OpenMP-MPI. The core simulations that form the basis of this research, utilizing discrete ordinates methods and Monte Carlo methods to drive time and space dependent isotopic reactor production using the PENBURN code, will provide more accurate detail of fuel compositions that can benefit nuclear safety, fuel management, non-proliferation, and safeguards applications.

Parmi les différents paradigmes de programmation parallèle, le parallélisme de flux présente l'avantage de conserver la séquentialité des algorithmes et d'être ainsi applicable en présence de dépendances de données. De plus, l'extension de calcul par flux pour OpenMP proposée par Pop et Cohen permet de mettre en œuvre cette forme de parallélisme sans requérir de réécriture complète du code, en y ajoutant simplement des annotations. Cependant, en raison de l'importance de la communication nécessaire entre les cœurs de calcul, les performances obtenues en suivant ce paradigme sont très dépendantes de l'algorithme de communication utilisé. Or l'algorithme de communication utilisé dans cette extension repose sur des files gérant plusieurs producteurs et consommateurs alors que les applications mettant en œuvre le parallélisme de flux fonctionnent principalement avec des chaînes de communication linéaires. Afin d'améliorer les performances du parallélisme de flux mis en œuvre par l'extension de calcul par flux pour OpenMP, cette thèse propose d'utiliser, lorsque cela est possible, un algorithme de communication plus spécialisé nommé BatchQueue. En ne gérant que le cas particulier d'une communication avec un seul producteur et un seul consommateur, BatchQueue atteint des débits jusqu'à deux fois supérieurs à ceux des algorithmes existants. De plus, une fois intégré à l'extension de calcul par flux pour OpenMP, l'évaluation montre que BatchQueue permet d'améliorer l'accélération des applications jusqu'à un facteur 2 également. L'étude montre ainsi qu'utiliser des algorithmes de communication spécialisés plus efficaces peut avoir un impact significatif sur les performances générales des applications mettant en œuvre le parallélisme de flux.

To parallelize a sequential source code, a parallelization strategy must be defined that transforms the sequential source code into an equivalent parallel version. Since parallelizing compilers can sometimes transform sequential loops and other well-structured codes into parallel ones automatically, we are interested in finding a solution to parallelize semi-automatically codes that compilers are not able to parallelize automatically, mostly because of weakness of classical data and control dependence analysis, in order to simplify the process of transforming the codes for programmers.Invasive Interactive Parallelization (IIP) hypothesizes that by using anintelligent system that guides the user through an interactive process one can boost parallelization in the above direction. The intelligent system's guidance relies on a classical code analysis and pre-defined parallelizing transformation sequences. To support its main hypothesis, IIP suggests to encode parallelizing transformation sequences in terms of IIP parallelization strategies that dictate default ways to parallelize various code patterns by using facts which have been obtained both from classical source code analysis and directly from the user.In this project, we investigate how automated reasoning can supportthe IIP method in order to parallelize a sequential code with an acceptable performance but faster than manual parallelization. We have looked at two special problem areas: Divide and conquer algorithms and loops in the source codes. Our focus is on parallelizing four sequential legacy C programs such as: Quick sort, Merge sort, Jacobi method and Matrix multipliation and summation for both OpenMP and MPI environment by developing an interactive parallelizing assistance tool that provides users with the assistanceneeded for parallelizing a sequential source code.

Les architectures des machines multi-coeurs actuelles deviennent de plus en plus complexes à cause du modèle de conception hiérarchique adopté. Par conséquent, assurer une meilleure stabilité, reproductibilité et prédictibilité des performances sur ces machines nécessite une compréhension approfondie des interactions qui existent entre les applications multi-threads et le matériel sous-jacent. Dans cette thèse, nous étudions deux aspects importants pour les performances des applications multi-threads. Nous montrons que la stabilité des performances est un critère important à considérer dans le processus d'évaluation des performances, et que le placement des threads est une technique efficace en termes de stabilité et d'amélioration des performances des programmes. Nous commençons par étudier la variabilité des temps d'exécution des programmes, nous définissons un protocole rigoureux d'évaluation des performances, puis nous analysons les raisons de cette variabilité et ses implications pour la mesure des performances. Ensuite, nous étudions la relation entre le partage des données entre threads et les stratégies de placement des threads sur machines hiérarchiques. Nous considérons plusieurs stratégies où le même placement est appliqué pour toute la durée d'exécution du programme. Alors que certaines reposent sur les caractéristiques des applications, d'autres non. Nous présentons aussi d'autres stratégies de placement des threads autorisant la migration des threads afin d'exploiter le partage des données au cours des différentes phases d'un programme.

Submitted by Marta Toyoda (1144061@mackenzie.br) on 2018-03-09T21:55:15Z No. of bitstreams: 2 Raphael Alonso de Mendonca.pdf: 3718145 bytes, checksum: bddb4107820ad6d2c15010fadb45425c (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Paola Damato (repositorio@mackenzie.br) on 2018-04-04T11:45:47Z (GMT) No. of bitstreams: 2 Raphael Alonso de Mendonca.pdf: 3718145 bytes, checksum: bddb4107820ad6d2c15010fadb45425c (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-04-04T11:45:47Z (GMT). No. of bitstreams: 2 Raphael Alonso de Mendonca.pdf: 3718145 bytes, checksum: bddb4107820ad6d2c15010fadb45425c (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-02-05 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Since the discovery and con rmation of the rst exoplanet in the late 20th century the increasing improvement of methods of planetary detection and the techniques applied to detection and con rmation. make possible to discover several exopalets. One of the most used methods is the Planetary Transit Method, which works with photometric data, a process of observation of the luminous ux of star. The time series of observed uxes is an important object of data analysis called the light curve. Light curves (synthetic) can also be produced through analytical models of planetary transits. With the advent of new missions to study exoplanets such as TESS and PLATO, high-quality light curves and large volumes of data will be generated in the next years. Thus, the development of analytical models and data analysis that are capable of handling the complexity, quality and volume of data is of great interest to Astroinformatics, the interface between Astronomy, Astrophysics and Computation. Within this context, this dissertation proposes a parallel optimization, via the OpenMP architecture, of the photometric-analytical model generator of planetary transits ELLC, aiming at the treatment of future data from missions TESS and PLATO. This generator, in addition to containing complex parameters for planetary transits such as anisotropic limb darkening models , re ection e ects and stellar spots, is a free software source code and can be easily integrated with MCMC. Getting in loop of code that was parallelized, a speedup of 288.36 on a computer with i7 processor and 12 GB of memory and 452.04 on a computer with i5 processor and 16GB of memory and a speedup of 1,275 times in the total execution of the simulation code. This parallelization will be made available on a free software basis to the research community in planetary transits. / Desde o descobrimento e confirmação do primeiro exoplaneta no final do século 20 e a crescente melhoria dos métodos de detecção de planetas e das tecnologia aplicada a detecção e confirmação. Toranram possível o descobrimento de diversos exopalnetas, um dos métodos mais utilizados é o Método de Trânsitos Planetários, que trabalha com dados de fotometria, processo de observação do fluxo luminoso de estrela. A série temporal de fluxos observados configura um objeto importante de análise de dados chamado curva de luz. Curvas de luz (sintéticas) também podem ser produzidas através de modelos analíticos de trânsitos planetários. Com o advento de novas missões para estudo de exoplanetas como a TESS e a PLATO, curvas de luz de alta qualidade e grandes volumes de dados serão geradas nos próximos anos. Assim, o desenvolvimento de modelos analíticos e de análise de dados que sejam capazes de lidar com a complexidade, qualidade e volume de dados é de grande interesse da Astroinformática, área de interface entre Astronomia, Astrofísica e Computação. Dentro deste contexto, esta dissertação propõe uma otimização paralela, utilizando a implementação em C da arquitetura OpenMP presete no compilador em C do pyhon, do gerador de modelos fotométrico-analíticos de trânsitos planetários ELLC, visando ao tratamento de dados de futuras missões com a TESS e a PLATO. Este gerador, além de conter parâmetros complexos para trânsitos planetários como modelos de escurecimento de limbo anisotrópicos, efeitos de reflexão e manchas estelares, possui código-fonte em regime de software livre e pode ser integrado facilmente com esquemas de ajuste de parâmetros de trânsitos via MCMC. Obtendo, no laço do código que foi paralelizado, uma aceleração de 288,36 em um computador com processador i7 e 12 GB de memória e de 452,04 em um computador com processador i5 e 16GB de memória. e uma aceleração de 1,275 vezes na execução total da simulação código. Esta paralelização será disponibilizada em regime de software livre para a comunidade de pesquisa em trânsitos planetários.

The work deals with design and implementation of 2D ultrasound simulation. Applications of the ultrasound simulation can be found in medicine, biophysic or image reconstruction. As an example of using the ultrasound simulation we can mention High Intensity Focused Ultrasound that is used for diagnosing and treating cancer. The program is part of the k-Wave toolbox designed for supercomputer systems, specifically for machines with shared memory architecture. The program is implemented in the C++ language and using OpenMP acceleration.  Using the designed solution, it is possible to solve large-scale simulations in 2D space. The work also deals with merging and unification of the 2D and 3D simulation using modern C++. A realistic example of use is ultrasound simulation in transcranial neuromodulation and neurostimulation in large domains, which have more than 16384x16384 grid points. Simulation of such size may take several days if we use the original MATLAB 2D k-Wave. Speedup of the new implementation is up to 8 on the Anselm and Salomon supercomputers.