MASA-SSE : comparação de sequências biológicas utilizando instruções vetoriais

Abstract

A comparação de sequências biológicas é uma das operações mais básicas e importantes da Bioinformática. Os métodos exatos de comparação de sequências possuem complexidade quadrática de tempo e por isso soluções paralelas são utilizadas para acelerar a produção de resultados. O framework MASA [3] é uma solução paralela flexível e customizável que permite o alinhamento de sequências biológicas em diferentes hardwares e softwares. Ele foi inicialmente pensado para execução paralela da comparação de sequências em GPUs (Graphics Processing Units), porém, atualmente existem duas soluções MASA para CPU: MASA-CPU e MASA-OpenMP. Essas soluções não utilizam instruções vetoriais, deixando de explorar um grande potencial para paralelismo. O presente trabalho de graduação propõe e avalia o MASA-SSE, uma solução em CPU que utiliza as instruções vetoriais SSE da Intel, implementando o algoritmo de Farrar [6], que é considerado o estado da arte em comparação de sequências biológicas com instruções vetoriais. Os resultados obtidos a partir da comparação de várias sequências reais de DNA em duas máquinas distintas mostram que o MASA-SSE, executando em uma thread e, utilizando instruções vetoriais, possui desempenho superior ao do MASA-OpenMP com quatro threads. _____________________________________________________________________________ ABSTRACT

Biological sequence comparison is one of the most basic and important operations in Bioinformatics. The exact methods that compare two biological sequences have quadratic time complexity and, for this reason, parallel solutions are often used to accelerate the execution. The MASA framework [3] is a flexible and customizable parallel solution for biological sequence comparison which was initially designed for GPU (Graphics Processing Unit) execution but nowadays integrates two CPU solutions: MASA-CPU and MASA-OpenMP. These CPU solutions do not use vector instructions and thus miss the opportunity of exploring a high potential for parallelism. This graduation project proposes and evaluates MASA-SSE, a CPU solution that uses the SSE vector instructions from Intel and implements the Farrar algorithm [6], which is the state-of-the-art algorithm for biological sequence comparison with vector instructions. Experimental results obtained with the comparison of real DNA sequences in two different machines show that MASA-SSE, executing with one thread and vector instructions, outperforms MASA-OpemMP, execution with four threads.