Dissertação

{en_GB=FPGA-Based Accelerator for High-Order Epistasis Detection} {} EVALUATED

{pt=A abordagem clássica aos estudos de associação do genoma completo (GWAS) procura encontrar uma relação entre um ou mais polimorfismo de nucleotídeo único (SNP) contribuírem para manifestação de uma determinada doença ou característica física. No entanto, a maioria das doenças genéricas não dependem dos efeitos individuais de um ou mais SNPs, mas sim da interação entre vários, ao que se dá o nome de epistasia. A deteção de epistasia para interações de ordem elevada resulta numa elevada complexidade computacional, visto que o número de combinações de SNPs a avaliar aumenta exponencialmente com a ordem das interações. Por esta razão, os mais recentes métodos exaustivos para a deteção epistasia são implementados em GPUs e em plataformas FPGA para a obtenção de soluções de alto desempenho para interações de segunda e terceira ordem. No entanto, poucas implementações em FPGAs têm sido desenvolvidas para detetar interações de terceira ordem, e aquelas que existem não são escaláveis para ordens de interações mais elevadas e têm ainda espaço para otimizações ao nível da arquitetura. Esta tese aborda as limitações de escalabilidade e flexibilidade das implementações existentes em FPGA ao propor uma nova arquitetura genérica para qualquer ordem de interações. As implementações resultantes são mais rápidas e eficientes do que as existentes, resultando em ganhos de desempenho de 3x, quando comparados com implementações terceira ordem, e melhorias de eficiência energética de, em média, 79x. Por fim, a arquitetura proposta permitiu a implementação de um acelerador de deteção de epistasia de quarta ordem numa plataforma FPGA. , en=The classic approach to Genome-Wide Association Studies (GWAS) attempts to find a relation between one or more Single Nucleotide Polymorphisms (SNPs) contributing to the manifestation of a certain disease or trait. However, most genetic diseases do not depend on the individual effect of one or more SNPs, but rather on the interactions between several SNPs, also known as epistasis. Detecting epistasis for high-order interactions results in a huge computational complexity, as the number of SNP combinations evaluated exponentially grows with the order of the interactions. For this reason, state-of-the-art exhaustive search-based methods for epistasis detection rely on Graphics Processing Units (GPUs) and Field Programmable Gate Arrays (FPGAs) to provide high-performance solutions for second-order interactions. Nevertheless, only rare attempts are made to tackle third-order interactions, and the ones that exist are not scalable for higher-order interactions and could be further optimized. In this thesis, the flexibility and scalability limitations of the existing FPGA implementations are addressed, while a novel parameterizable architecture is proposed that enables the deployment of FPGA-based accelerators targeting any order of interactions in modern FPGAs. The resulting implementations can target any dataset size and provide higher performance and energy efficiency than the state-of-the-art FPGA-based architectures. In particular, performance gains of up to 80x and 3x are achieved when compared to existing second and third-order implementations, respectively, while also providing average energy efficiency improvements of 79x. Finally, the proposed architecture allowed for the implementation of a fourth-order epistasis detection accelerator in an FPGA platform. }
{pt=Estudo de Associação do Genoma Completo, Deteção de Epistasia, FPGA, Polimorfismo de Nucleotídeo Único, Arquiteturas de Domínio Especifico, Aceleradores baseados em FPGA, en=Genome-Wide Association Studies, Epistasis Detection, FPGA Accelerator, Single Nucleotide Polymorphism, Domain-Specific Architectures}

Janeiro 22, 2021, 16:0

Orientação

ORIENTADOR

Nuno Filipe Simões Santos Moraes Neves

IT

Investigador

ORIENTADOR

Aleksandar Ilic

Departamento de Engenharia Electrotécnica e de Computadores (DEEC)

Professor Auxiliar