The advent of modern DNA sequencing machines has revolutionized genome research and healthcare, enabling fast and cost-effective reading of DNA sequences from a donor's biological sample. The massive data production generated by modern sequencing machines demands high-performance software and hardware accelerators to quickly analyse sequencing data without compromising the accuracy of the results. In particular, sequence alignment is a critical building block in multiple sequencing data analyses and remains a fundamental problem in computer science with diverse applications. Due to its computational complexity, sequence alignment is one of the most time-consuming steps in common genomic analysis pipelines. Classical sequence alignment implementations rely on Dynamic Programming (DP), which ultimately yields solutions with quadratic complexity. To address the demand for faster and more efficient computing for sequence data analysis, heterogeneous architectures have emerged as a promising computational approach, combining general-purpose CPUs with specialized hardware accelerators. Heterogeneous architectures balance the computational needs of different workloads by dynamically allocating tasks between general-purpose CPUs and specialized accelerators. In this context, domain-specific accelerators (DSAs) can significantly improve performance and efficiency by providing specialized hardware optimized for computation-intensive and regular tasks. Meanwhile, general-purpose CPUs can handle complex and irregular workloads while also managing the orchestration of the accelerator. In this thesis, we propose Smough, a heterogeneous architecture designed for large-scale genome sequence alignment. The proposed architecture integrates a general-purpose RISC-V CPU, extended with custom instructions for sequence alignment acceleration, and SmoughEngine, a DSA optimized for DP matrix computations. While the general-purpose CPU orchestrates CPU/DSA computations and executes irregular alignment tasks using the dedicated ISA extension, SmoughEngine performs the heavy DP computations using a tile-based approach and bit-parallel operations. Additionally, we propose a hardware-software co-design that leverages Smough's heterogeneous capabilities to solve the alignment problem efficiently. We implement the complete Smough architecture on the Gem5 simulator and propose an efficient RTL implementation of SmoughEngine's compute tile. We synthesize SmoughEngine's compute tile in a technological node. As a result, SmoughEngine's compute tile synthesis reports an area of 0.17 mm² and an estimated power draw of 588 mW, given a 256x256 elements tile. Moreover, we present a comprehensive experimental evaluation. Our results demonstrate that Smough outperforms state-of-the-art bit-parallel software methods by up to 63.3x aligning long sequences and up to 2.9x aligning short sequences. In addition, our experimental evaluation demonstrates Smough's scalability and efficiency for processing increasingly longer genomic sequences. The high performance of SmoughEngine with the achieved area- and power-efficiency makes Smough a strong candidate for real-world genomic analysis applications.
El auge de las máquinas de secuenciación modernas de ADN ha revolucionado la investigación del genoma y la atención médica, permitiendo la lectura rápida y rentable de secuencias de ADN a partir de una muestra biológica del donante. La enorme producción de datos generada por las máquinas de secuenciación modernas exige software de alto rendimiento y aceleradores de hardware para analizar rápidamente los datos de secuenciación sin comprometer la precisión de los resultados. En particular, el alineamiento de secuencias es un componente crítico en múltiples análisis de datos de secuenciación y sigue siendo un problema fundamental en la informática con diversas aplicaciones. Debido a su complejidad computacional, el alineamiento de secuencias es uno de los pasos más costosos en tiempo dentro de los flujos de trabajo comunes de análisis genómico. Las implementaciones clásicas de alineación de secuencias se basan en la Programación Dinámica (DP, por sus siglas en inglés), que finalmente produce soluciones con complejidad cuadrática. Para abordar la demanda de computación más rápida y eficiente para el análisis de datos de secuencias, las arquitecturas heterogéneas surgen como un enfoque computacional prometedor, combinando CPUs de propósito general con aceleradores de hardware especializados. Las arquitecturas heterogéneas equilibran las necesidades computacionales de diferentes cargas de trabajo al asignar dinámicamente tareas entre las CPUs de propósito general y los aceleradores especializados. En este contexto, los aceleradores específicos de dominio (DSA, por sus siglas en inglés) pueden mejorar significativamente el rendimiento y la eficiencia al proporcionar hardware especializado optimizado para tareas intensivas en cómputo y regulares. Mientras tanto, las CPUs de propósito general pueden manejar cargas de trabajo complejas e irregulares, además de gestionar la orquestación del acelerador. En esta tesis, proponemos Smough, una arquitectura heterogénea diseñada para el alineamiento de secuencias genómicas a gran escala. La arquitectura propuesta integra una CPU RISC-V de propósito general, extendida con instrucciones personalizadas para la aceleración del alineamiento de secuencias, y SmoughEngine, un DSA optimizado para el cómputo de matrices DP. Mientras la CPU de propósito general orquesta las computaciones entre la CPU y el DSA y ejecuta tareas de alineamiento irregulares utilizando la extensión dedicada del ISA, SmoughEngine realiza los cómputos pesados de DP utilizando un enfoque basado en bloques y operaciones de bits en paralelo. Además, proponemos un diseño conjunto de hardware y software que aprovecha las capacidades heterogéneas de Smough para resolver el problema del alineamiento de secuencias de manera eficiente. Implementamos la arquitectura completa de Smough en el simulador Gem5 y proponemos una implementación RTL eficiente del núcleo de cómputo de SmoughEngine. Sintetizamos el núcleo de cómputo de SmoughEngine en un nodo tecnológico. Como resultado, la síntesis del núcleo de cómputo de SmoughEngine informa un área de 0,17 mm² y un consumo de energía estimado de 588 mW, dado un bloque de 256x256 elementos. Además, presentamos una evaluación experimental exhaustiva. Nuestros resultados demuestran que Smough supera a los métodos de software de bits en paralelo de última generación hasta 63,3 veces al alinear secuencias largas y hasta 2,9 veces al alinear secuencias cortas. Además, nuestra evaluación experimental demuestra la escalabilidad y eficiencia de Smough para procesar secuencias genómicas cada vez más largas. El alto rendimiento de SmoughEngine con la eficiencia lograda en área y consumo de energía hace de Smough un fuerte candidato para aplicaciones reales de análisis genómico.
L'apogeu de les màquines de seqüenciació modernes d'ADN ha revolucionat la recerca del genoma i l'atenció sanitària, permetent la lectura ràpida i rendible de les seqüències d'ADN a partir d?una mostra biològica del donant. La massiva producció de dades generada per les màquines de seqüenciació modernes exigeix programari d'alt rendiment i acceleradors de maquinari per analitzar ràpidament les dades de seqüenciació sense comprometre la precisió dels resultats. En particular, l'alineament de seqüències és un component crític en múltiples anàlisis de dades de seqüenciació i continua sent un problema fonamental en la informàtica amb diverses aplicacions. A causa de la seva complexitat computacional, l'alineament de seqüències és un dels passos més costosos en temps dins dels fluxos de treball comuns d'anàlisi genòmica. Les implementacions clàssiques d'alineament de seqüències es basen en la Programació Dinàmica (DP, per les seves sigles en anglès), que finalment produeix solucions amb complexitat quadràtica. Per abordar la demanda d'una computació més ràpida i eficient per a l'anàlisi de dades de seqüències, les arquitectures heterogènies han sorgit com un enfocament computacional prometedor, combinant CPUs de propòsit general amb acceleradors de maquinari especialitzats. Les arquitectures heterogènies equilibren les necessitats computacionals de diferents càrregues de treball assignant dinàmicament tasques entre les CPUs de propòsit general i els acceleradors especialitzats. En aquest context, els acceleradors específics de domini (DSA, per les seves sigles en anglès) poden millorar significativament el rendiment i l'eficiència en proporcionar maquinari especialitzat optimitzat per a tasques intensives en cómput i regulars. Mentrestant, les CPUs de propòsit general poden gestionar càrregues de treball complexes i irregulars, a més de gestionar l'orquestració de l'accelerador. En aquesta tesi, proposem Smough, una arquitectura heterogènia dissenyada per a l'alineament de seqüències genòmiques a gran escala. L'arquitectura proposada integra una CPU RISC-V de propòsit general, ampliada amb instruccions personalitzades per a l'acceleració de l'alineament de seqüències, i SmoughEngine, un DSA optimitzat per el cómput de matrius DP. Mentre que la CPU de propòsit general orquestra el cómput entre la CPU i el DSA i executa tasques d'alineament irregulars utilitzant l'extensió dedicada de l'ISA, SmoughEngine realitza el cómput pesant de DP utilitzant un enfocament basat en blocs i operacions de bits paral·leles . A més, proposem un disseny conjunt de maquinari i programari que aprofita les capacitats heterogènies de Smough per resoldre el problema de l'alineament de manera eficient. Implementem l'arquitectura completa de Smough en el simulador Gem5 i proposem una implementació RTL eficient del núcli de cómput de SmoughEngine. Sintetitzem el núcli de cómput de SmoughEngine en un node tecnològic. Com a resultat, la síntesi de el núcli de cómput de SmoughEngine reporta d'una àrea de 0,17 mm² i un consum d'energia estimat de 588 mW, tenint en compte blocs de 256x256 elements. A més, presentem una avaluació experimental exhaustiva. Els nostres resultats demostren que Smough supera els mètodes de programari basats en operacions de bits paral·leles fins a 63,3 vegades en l'alineament de seqüències llargues i fins a 2,9 vegades en l'alineament de seqüències curtes. A més, la nostra avaluació experimental demostra l'escalabilitat i l'eficiència de Smough per processar seqüències genòmiques cada cop més llargues. L'alt rendiment de SmoughEngine amb l'eficiència aconseguida en àrea i consum d'energia fa de Smough un fort candidat per a aplicacions reals d'anàlisi genòmica.
