IEEE LATIN AMERICA TRANSACTIONS, VOL. 6, NO. 7, DECEMBER 2008
579
FPGA-Based Implementation and
Performance of the Global and Local
Algorithms for the Gens Alignment
Cristiane da Silva Morony, Edward David Moreno
Abstract— The paper has as objective to implement, in
hardware - making use of FPGA technology, the algorithms that
are considered as standard for the comparison and the global
and local alignment of the DNA genetic sequences. These
algorithms use the dynamic programming technique. These
algorithms were implemented in software (C language) and,
later, the hardware implementation (using VHDL and FPGAs).
We compare our obtained software and hardware results, by the
execution time of the algorithms, and it was possible to verify
that our hardware implementation is better than our software
version and others bioinformatics platforms.
Keywords— FPGAs, Gens Alignment, Needleman-Wunsch
Smith-Waterman
Algorithms,
Performance
and
Evaluation, Bioinformatics Platforms.
I. INTRODUÇÃO
Com os avanços da engenharia genética, na tentativa de
estudar e mapear o genoma dos seres vivos e, em especial, o
genoma humano, dados de seqüências genéticas são gerados
em taxas cada vez maiores. Profissionais como biólogos
deparam-se com uma enorme vazão de dados que gostariam
de classificar e comparar com aqueles armazenados nos
diversos bancos de dados.
Estes profissionais necessitam da utilização de
instrumentos computacionais como software e hardware
especializados para realizar de maneira mais eficiente e em
menor tempo as análises dos algoritmos de alinhamento de
seqüências, visto que, em grande parte destas aplicações o
tempo e o resultado são variáveis fundamentais [22].
Neste sentido, a técnica de programação dinâmica aplicada
nos algoritmos de alinhamento global, conhecido como
algoritmo de Needleman-Wunsch [21] tem como finalidade a
similaridade global entre duas seqüências de DNA, onde todas
as bases são alinhadas umas com as outras ou com gaps. Isto
é, os valores globais requerem que o alinhamento comece no
início e se estenda até o final de todo o comprimento da
seqüência [28].
O algoritmo de alinhamento local, como o algoritmo de
Smith-Waterman [25], possui similaridade local entre duas
seqüências, não necessita alinhar todas as bases em todas as
seqüências, ou seja, os valores locais requerem identificação
na região mais similar entre duas seqüências e também a
penalidade por falta atribuída ou não [28].
Com uma pequena mudança da técnica de programação
dinâmica aplicada no alinhamento global torna-se local.
Assim, é visível a importância dos algoritmos de alinhamento
de seqüências na bioinformática, pois ao encontrar o
alinhamento máximo é possível detectar altas similaridades
que existem entre as seqüências de maneira a permitir
encontrar similaridades funcionais e conseqüentemente
estruturais, contribuindo desta forma para os avanços nas
pesquisas dessas áreas.
Existem vários programas que se encontram disponíveis
para fazer a comparação de seqüências biológicas, exemplo o
BLAST [1]. Softwares como o BLAST ou FASTA são
extensivelmente usados para bancos de dados biológicos e têm
sido projetados para executar em computadores padrões, isto
é, máquinas Von Neuman, e incluem técnicas para acelerar os
processos.
Este software somente implementa o algoritmo para
alinhamento local das seqüências e não utiliza a programação
dinâmica e sim heurística. Por este motivo, não têm garantia
de que vai encontrar o melhor alinhamento [1]. Uma vantagem
de sua utilização é a utilização em plataformas com baixo
custo computacional.
Por esse motivo, escolheu-se esse assunto, pois mesmo
existindo algoritmos de programação dinâmica para o
problema da comparação de seqüências genéticas, esses
algoritmos são amplamente usados pela comunidade
acadêmica da área biológica na tentativa de encontrar maiores
soluções para os desafios que estão sempre surgindo nesta
área. Não obstante, o tempo para fazer a varredura nos bancos
de dados, na tentativa de encontrar rápidas soluções, ainda é
muito alto, uma vez que os mesmos estão crescendo
rapidamente.
Motivados pelos avanços tecnológicos e as novas
possibilidades de se projetar hardware, pensou-se na
possibilidade de implementação dos algoritmos de
alinhamento global e local usando a tecnologia FPGA, com o
intuito de analisar mais detalhadamente as partes mais críticas
desses algoritmos e poder amenizar os problemas de
580
IEEE LATIN AMERICA TRANSACTIONS, VOL. 6, NO. 7, DECEMBER 2008
desempenho dos mesmos, com versões específicas desses
algoritmos em hardware.
Assim, o objetivo principal deste artigo é a implementação
em hardware, dispondo da tecnologia de FPGAs, do
algoritmo global (Needleman-Wunsch) e local (SmithWaterman). Importante salientar que esses algoritmos são
considerados ou adotados como um padrão para a comparação
e o alinhamento das seqüências genéticas de DNA utilizando a
técnica de programação dinâmica. Neste artigo são realizadas
considerações sobre o projeto e o desempenho das respectivas
implementações em FPGAs, assim como otimizações em nível
arquitetural e de programação em VHDL, visando obter bons
resultados. Também foram realizadas comparações e
respectivas análises com outras soluções já existentes em
hardware, em especial, aquelas baseadas em FPGAs.
O artigo está organizado em 5 seções. A seção 2 apresenta
algumas soluções específicas em hardware existentes na
literatura, a seção 3 apresenta resultados do trabalho, das
implementações usando linguagem C. A seção 4 apresenta
dados da implementação em hardware, destacando os recursos
espaciais e temporais dos protótipos em FPGAs. Finalmente a
seção 5 apresenta as conclusões e algumas idéias para
trabalhos futuros.
II. HARDWARE PARA COMPARAÇÃO DE
SEQÛÊNCIAS
A versatilidade, a velocidade e o aumento do poder
computacional dos PCs (Computadores Pessoais) em redes
locais, têm guiado os cientistas no trabalho com modelagem
molecular e alinhamento de múltiplas seqüências de DNA
(evolução molecular) independentemente da existência de
supercomputadores [17][18].
A maioria das máquinas (hardwares) que tem sido
projetadas para acelerar a comparação de seqüências
biológicas é baseada em estrutura de arranjos (arrays)
lineares. Entretanto, essas estruturas diferem na flexibilidade
de programação. Dentre essas podem ser destacadas três
categorias [17, 18]:
Arrays Dedicados VLSI (Very Large Scale
Integration): essas máquinas podem conseguir o mais alto
desempenho sob um único algoritmo que foi adaptado dentro
do silício e não pode ser modificado. Alguns exemplos dessas
máquinas são: BioSCAN (Biological Sequence Comparative
Analysis Node) que acelera a identificação de seqüências
similares de DNA ou de proteínas sem permissão de gaps e o
SAMBA (Systolic Accelerator for Molecular Biological
Application) que é um array sistólico dedicado para analisar
os algoritmos envolvidos na comparação de seqüências
biológicas;
Arrays FPGAs (Field Programmable Gate Arrays):
eles incluem sistema com hardware reconfigurável (FPGA).
Eles tendem a ser mais lentos e têm densidade muito mais
baixa do que os arrays (arranjos) VLSI. A criação e
modificação de algoritmos para esses sistemas são possíveis.
Exemplos: Splash-2: sua arquitetura pode facilmente suportar
aplicações paralelas, tais como sistólica ou computações de
dados paralelos. O Splash -2 é um melhoramento da primeira
versão do Splash -1 [10], a qual consistiu de um tamanho fixo
de array linear de chips Xilinx 3090 FPGA [30] e o Hscan: é
um filtro processador dedicado para pesquisa em bancos de
dados de DNA. Foi desenvolvido pela IRISA (Institut de
Recherque en Informatique et Systèmes Aléatories) [11]
[17][18]; e
Arrays Programáveis VLSI: essa última categoria
de máquinas empenha-se para a flexibilidade algorítmica de
sistemas reconfiguráveis e a velocidade e a densidade de
máquinas VLSI de propósito único. Portanto, a principal
vantagem é a facilidade de programação. Exemplo: B-SYS
(Brown SYStolic Array) [13, 14] foi projetado principalmente
para o propósito de comparação de seqüências, ainda que a
flexibilidade de programação possibilite muitas outras
aplicações. Esta máquina foi fabricada pela Brown University
e testada sobre um protótipo de 10 chips, tendo uma
quantidade total de 470 processadores (47 processadores por
chip) [13].
Segundo Morony (2006), os arrays dedicados do tipo
VLSI são vinte vezes mais rápidos do que os FPGAs ou os
arrays programáveis VLSI. Já, os FPGAs e os arrays
programáveis VLSI têm performances comparáveis.
Sabe-se que as pesquisas e os estudos biológicos caminham
numa rápida evolução, assim, esta área precisa de tecnologia
que
realmente
consiga
acompanhar
seu
enorme
desenvolvimento. Diante desse fato, possivelmente,
pesquisadores, cientistas biológicos e projetistas de hardware
são impulsionados a estudar e averiguar as funcionalidades da
arquitetura reconfigurável utilizando a tecnologia FPGA nesta
área.
A seguir apresentam-se, brevemente, dois computadores
maciçamente
paralelos
que
utilizam
arquiteturas
reconfiguráveis: NGEN e POLYP. Destaca-se também o
alinhamento de seqüências sobre a arquitetura Cray MTA-2 e
uma abordagem sistólica em hardware para algoritmos de
comparação de seqüências.
A. Máquinas NGEN (eNGiNE) e POLYP
NGEN (eNGiNE) é uma plataforma de hardware para
computação maciçamente paralela, permitindo sua
configuração, em baixo nível, pelo usuário. Baseado na
tecnologia FPGA é reconfigurável para cada problema nos
níveis elementares de processamento digital e de
comunicação.
A arquitetura NGEN sobressai-se pelo uso de acessos
maciçamente paralelos à memória, em conjunto com variadas
conexões entre FPGAs e a capacidade de configuração
minuciosa da topologia global de interconexão.
MORONY AND MORENO : FPGA-BASED IMPLEMENTATION AND PERFORMANCE
A sigla POLYP (Parallel OnLine PolYmer Processing)
refere-se ao processamento paralelo on-line de polímeros.
POLYP e corresponde à segunda geração de computadores
maciçamente paralelos reconfiguráveis. Sua construção foi
baseada em FPGAs microrreconfiguráveis e alta densidade de
memória distribuída. O projeto do computador POLYP difere
em vários aspectos do projeto do NGEN, permitindo a
microrreconfiguração dinâmica nos seus FPGAs [26].
581
operação foram obtidas a partir de informações fornecidas
pela ferramenta de síntese, ver tabela I.
TABELA I
DESEMPENHO OBTIDO PARA UMA ARQUITETURA SISTÓLICA
EM HARDWARE [8]
Quantidade
de células
do vetor
Quantidade
de elementos
lógicos
Freqüência
Máxima
MHz
Média de
elementos
utilizados por
célula
5
10
15
20
25
30
40
50
146
507
900
1292
1758
2222
3204
4403
122,49
77,54
70,35
64,96
62,63
56,45
56,27
56,1
29,2
50,7
60
64,6
70,32
74,06
80,1
88,06
B. Alinhamento de Seqüências sobre o Cray MTA-2
Segundo Vianna [27] as características da arquitetura Cray
MTA (Multithreaded Architecture) foram relacionadas com as
características da arquitetura híbrida SIMD (Single Instruction
Single Data) e MIMD (Multiple Instruction Multiple Data)
para amenizar a deficiência do limite do tamanho das
seqüências de DNA, na arquitetura híbrida, com a utilização
das placas Systola1024 e Fuzion150 para a componente
SIMD, enquanto que o componente MIMD é estruturado em
um Cluster de 16 PCs.
Algumas variações do algoritmo de programação dinâmica
foram implementadas no Cray com relação a diferentes ordens
de atualização da matriz, devendo, portanto, ter concentração
na implementação que realiza atualização da matriz na ordem
antidiagonal.
Esta especialização foi escolhida devido à facilidade de
relacionamento com a técnica empregada pelas arquiteturas
Systola e Fuzion [27], as quais executam a computação das
células da matriz da mesma forma. As arquiteturas Systola e
Fuzion são melhor descritas em [16].
C. Estrutura Sistólica em Hardware
Um outro trabalho é o de Carvalho [8] que apresentou uma
visão geral de uma estrutura sistólica para algoritmos de
comparação de seqüências genéticas baseados em
programação dinâmica. Foi utilizada a placa APEX PCI
Development Board do fabricante Altera, contendo o FPGA
APEX EP20K400EFC672. Essa placa foi instalada em um
computador da Dell com um processador Pentium IV. A
ferramenta de síntese adotada foi o Quartus II da própria
Altera [8].
A implementação em hardware dessa estrutura sistólica foi
baseada no algoritmo de comparação local de duas seqüências
proposto por Smith-Waterman [25] e se deu apenas em nível
de síntese. Desta maneira os resultados apresentados em [8]
foram obtidos a partir de simulações feitas na ferramenta de
desenvolvimento do fabricante ALTERA que fornece
resultados bastante precisos em termos de velocidade do
circuito, ainda que em nível de simulação uma vez que leva
em consideração caminhos críticos e atrasos dos sinais.
Os testes foram feitos com seqüências fictícias cuja matriz
de similaridade era conhecida ou poderia ser construída
facilmente. Para o teste de desempenho, vetores de diferentes
tamanhos foram sintetizados e suas freqüências máximas de
Como esperado, pode-se perceber que quanto maior a
quantidade de células do vetor, maior a utilização dos recursos
espaciais oferecidos pelos FPGAs e menor sua freqüência
máxima de operação. Este projeto mostrou como um
hardware dedicado, baseado em uma estrutura sistólica, é
capaz de linearizar a complexidade temporal e reduzir o tempo
de processamento desses algoritmos.
As arquiteturas especiais brevemente comentadas neste
artigo (NGEN, POLYP, Cray MTA-2 e estruturas sistólicas
para algoritmos de comparação de seqüências baseados em
programação dinâmica) mostraram a utilização de FPGAs na
computação maciçamente paralela. Esses projetos permitem
antever o potencial de utilização de dispositivos programáveis
como importante bloco de construção de sistemas de
computação que requerem de alto desempenho.
III. ALGORITMOS DE ALINHAMENTOS EM C
Esta seção apresenta dados de desempenho da
implementação dos algoritmos de alinhamento global e local,
implementados em C, aqui denominados respectivamente de
AGM e ALM.
O hardware utilizado na execução desses algoritmos foi
um computador Pentium IV 1.66 GHz, AMD Athlon (tm) XP
2000+, 240 MB de memória RAM, 256 K de cache, com
sistema operacional Microsoft Windows XP. Foi possível
variar o tamanho das seqüências utilizadas na execução dos
algoritmos AGM e ALM, mudando de 10 até 1000 caracteres.
A tabela II mostra o tempo de execução (em segundos) do
seqüenciamento, para vetores de vários tamanhos.
Observando os dados da tabela II é possível verificar que o
algoritmo global executa mais rápido que o algoritmo local,
resultado esperado, pois o algoritmo local além de fazer as
mesmas operações que o algoritmo global uma vez que
precisa de uma operação adicional para obter o maior
seqüenciamento. Interessante observar também que esses
tempos são quase iguais para seqüências de até 50 caracteres e
582
IEEE LATIN AMERICA TRANSACTIONS, VOL. 6, NO. 7, DECEMBER 2008
se tornam maiores para seqüências de tamanhos maiores a 300
caracteres (diferença acima de 5% que pode chegar a 28%).
TABELA II
TEMPO DE EXECUÇÃO DOS ALGORITMOS AGM E ALM EM C
Tamanho
das
Seqüências
10
20
30
40
50
100
150
300
400
500
600
1000
AGM
0.220 (ms)
1
2
4
9
57
227
2664
7999
19354
39704
300184 =
83 horas
Tempo em Segundos
ALM
Diferença
%
0.160 (ms)
1
2
4
9
60
222
2979
10259
21187
43281
328280 =
91 horas
27
0
0
0
0
5.2
2.2
11.8
28.2
9.5
9
12
Conforme esperado, também é possível observar que o
tempo para realizar o alinhamento aumenta conforme o
tamanho da seqüência aumenta, e se torna crítica para as
seqüências maiores de 300 caracteres. Para seqüências de
tamanhos 1000, esse tempo é da ordem de dezenas de horas.
Isso lembra a importância de ter plataformas e/ou algoritmos
específicos que possam diminuir o tempo de execução dessas
operações de alinhamento (global e local), em especial, para
grandes tamanhos de seqüências.
A seguir apresenta-se uma comparação dos dados obtidos
da implementação em C (executando em um Pentium IV 1.66
GHz) com aqueles obtidos na plataforma SAMBA. A
arquitetura SAMBA (Systolic Accelerator for Molecular
Biological Application) [17] [18][20] é um array sistólico
dedicado para a comparação de seqüências biológicas. Esse
hardware acelera uma versão parametrizada do algoritmo de
Smith-Waterman [2] [25] permitindo a computação de
alinhamentos globais e locais com ou sem gap penalty.
Pelo fato da arquitetura SAMBA utilizar o algoritmo de
Smith-Waterman é possível realizar a comparação dos dados
de desempenho desta arquitetura com as performances obtidas
nas implementações dos alinhamentos Global e Local
implementados em C. Na comparação usaram-se as
seqüências definidas na versão 31 do banco SWISS-PROT1
[16], banco de dados de proteínas composto por um conjunto
de 815 proteínas. A versão 31 do banco SWISS-PROT
contém exatamente 43.470 seqüências distribuídas sob
15.335.248 aminoácidos. As 815 seqüências representam um
total de 307.400 aminoácidos. A implementação do SAMBA,
além de permitir plataformas de hardware maciçamente
1
SWISS-PROT: Protein Knowledgebase. Banco de dados de seqüências de
proteínas.
paralelas, usa também diferentes matrizes de substituição2 e
gap penalties.
A arquitetura SAMBA contém uma workstation, um array
sistólico composto de 128 processadores de 12 bits, e uma
interface baseada em FGPA. A interface FPGA é a placa
PerLe-1 desenvolvida em [7] e funcionava como um driver
programável para o array sistólico.
SAMBA pode ser comparado com dois outros sistemas de
hardware: BISP [9] e BioSCAN [29]. O BISP (Biological
Information Signal Processor) fornece uma alta velocidade e
um sistema linearmente extensível que pode localizar
estaticamente subseqüências similares de duas seqüências de
DNA ou de proteínas. Este implementa uma versão
modificada do algoritmo do Smith Waterman e permite que
vários parâmetros sejam estabelecidos.
O hardware foi projetado no Instituto de Tecnologia da
Califórnia. Um chip contém 16 processadores e um protótipo
da máquina de 16 chips foi validado, tornando possível a
computação de tamanho de seqüências ilimitadas. Essa
máquina não tem uma versão comercial.
Os protótipos do BISP e BioSCAN contém,
respectivamente, 256 processadores de 16 bits e 12.000
processadores de 1 bit. Porém, a arquitetura BISP e SAMBA
são similares. Elas diferem da seguinte maneira: o array BISP
é acionado com um processador programável (Motorola
68020) enquanto o SAMBA usa tecnologia FPGA.
Para efeitos de comparação também se usaram os dados
obtidos por Lavenier [17] [18], a partir da execução do
software SSEARCH (que encontra alinhamentos locais de
acordo com o algoritmo de Smith e Waterman, o qual é
fornecido com o pacote de softwares FASTA) e executam sob
uma workstation DEC-Alpha 21064 de 150Mhz.
Os dados da tabela III indicam o tempo de pesquisa usando
o software SSEARCH sob diferentes workstations, que
seguem a arquitetura SAMBA executando em diferentes
processadores. Na tabela III esses dados são denominados
conforme a máquina usada, assim por exemplo, SAMBA –
DEC - Alpha 150MHz, define a execução do SAMBA com
processadores DEC Alpha 150 MHz. As outras descrições
são: SAMBA - Sun SPARC 5 110MHz, SAMBA - DEC
5000/250 40MHz.
Os dados da tabela III comparam a implementação
seqüencial em C dos algoritmos AGM e ALM com aquelas
obtidas para o SAMBA em diferentes plataformas, as quais
usam vários processadores funcionando em paralelo. Para uma
melhor visualização, a Fig 1 ilustra os diferentes desempenhos
por meio do tempo de execução, em segundos, dos
alinhamentos global (AGM) e local (ALM) em C juntamente
com aqueles da arquitetura SAMBA.
2
Matrizes de Substituição: desenvolvida na década de 1980 e são as mais
usadas no alinhamento de seqüências protéicas [Raimbault, 1993].
MORONY AND MORENO : FPGA-BASED IMPLEMENTATION AND PERFORMANCE
583
IV. IMPLEMENTAÇÃO EM HARDWARE - FPGAS
TABELA III
COMPARAÇÃO DO TEMPO DE EXECUÇÃO DO AGM E ALM COM A
PLATAFORMA SAMBA [17][18]
Tama
nho
da
Seqüê
ncia
10
30
100
300
1000
Tempo em Segundos
AGM
ALM
SA
MB
A
0.22
ms
2
57
2664
300184
0.16
ms
2
60
2979
328280
SAMBA
- Sun
SPARC
5
95
SAMBA
- DEC
5000
25
SAMB
A
DECAlpha
57
25
26
30
40
120
350
1041
3468
239
746
2215
7300
548
1407
4054
12920
182
Performances
Na implementação dos algoritmos de alinhamento de
seqüências, global (AGM) e local (ALM), em VHDL usou-se
uma máquina de estado finito (Finite State Machine – FSM)
[23]. Esta máquina de estado permite descrever os estados da
máquina e as suas respectivas transições de maneira síncrona.
Com a máquina de estado é possível: i) ficar em um estado
sempre após ocorrer um evento; ii) mudar de estado conforme
mudança de um valor; iii) mudança de estado em seqüência
lógica; e iv) mudança de estado sem seqüência.
A tabela IV apresenta o número de estados e suas
respectivas descrições no algoritmo global em VHDL. O
algoritmo global precisou de 5 estados, enquanto o algoritmo
local de 6 estados (um adicional ao algoritmo global, que
permite calcular o maior valor dentro da matriz). Os estados
do algoritmo local são mais bem definidos na tabela V.
Tem po em Segundos
5000
TABELA IV
DESCRIÇÃO DOS ESTADOS DO ALGORITMO GLOBAL EM VHDL
4000
3000
2000
1000
0
Estado
Descrição dos Estados
0
Inicializa a máquina de estados e zera todas as posições da
matriz.
Preenche a primeira linha e primeira coluna do inicio ao
fim.
Inicialização dos caracteres das seqüências 1 e 2 que serão
comparadas e apresentação dos mesmos nos respectivos
vetores da linha e da coluna.
Cálculo para realizar o preenchimento do restante da
matriz e atribuição de valores a sinais e variáveis.
Cálculo para realizar o procedimento traceback, o qual
retorna o melhor alinhamento entre as seqüências
analisadas e comparadas.
1
101
302
3
100
3004
2
Tamanho das Seqüências
AGM
SAMBA
SAMBA Sun-SPARC 5 110 MHz
ALM
SAMBA DEC-Alpha 150Mhz
SAMBA DEC 5000/250 40MHz
Fig. 1. Comparação do Tempo de Execução: Algoritmos AGM, ALM e
SAMBA para Seqüências de até 300 caracteres
Importante ressaltar que a arquitetura SAMBA contém uma
workstation, um array sistólico linear composto de 32 chips
full custom distribuídos sobre 2 (duas) placas. Um chip integra
4 (quatro) processadores, conduzindo a um array sistólico de
128 processadores e uma interface baseada em FPGA.
Esses dados do SAMBA foram obtidos em 1996 e com
múltiplos processadores. Não obstante, a implementação do
AGM e ALM possui bom desempenho (menor tempo de
execução) para seqüências menores a 300 caracteres. Para
seqüências maiores a 300 caracteres, essa versão seqüencial é
muito lenta e, então, merece atenção o uso de máquinas
paralelas.
Considerando que nos últimos anos não se vê um
desenvolvimento de máquinas paralelas específicas para
problemas de bioinformática, e nem a utilização de FPGAs
modernas, e levando em consideração os avanços tecnológicos
nesta área e a necessidade crescente de ter-se soluções
eficientes para esses problemas, decidiu-se então fazer uma
implementação específica desses algoritmos em FPGAs.
3
4
TABELA V
DESCRIÇÃO DOS ESTADOS DO ALGORITMO LOCAL EM VHDL
Estado
0
1
2
3
4
5
Descrição dos Estados
Inicializa a máquina de estados e zera todas as posições da
matriz.
Preenche a primeira linha e primeira coluna do inicio ao
fim.
Inicialização dos caracteres das seqüências 1 e 2 que serão
comparadas e apresentação dos mesmos nos respectivos
vetores da linha e da coluna.
Cálculo para realizar o preenchimento do restante da
matriz
Busca e retorna o maior valor dentro da matriz.
Cálculo para realizar o procedimento traceback, o qual
retorna o melhor alinhamento entre as seqüências
analisadas e comparadas.
Desta forma, os algoritmos global e local foram descritos
em VHDL e simulados usando o recurso de síntese do FPGA
e obtiveram-se dados de desempenho em hardware. Após esta
descrição fez-se o uso do recurso da implementação dos
mesmos, usando apenas duas famílias da ferramenta Xilinx
Foundation Series [30].
É
importante
ressaltar
que
arrays
(arranjos)
multidimensionais geralmente não são suportados pela
ferramenta de síntese (synthesis) e por este motivo as famílias
da ferramenta Xilinx [30] que conseguiram suportar a
584
implementação dos arrays usados nos algoritmos foram
apenas:
Família : VIRTEX,Dispositivo
V800FG680,
Velocidade: -6; e
Família: VIRTEXE, Dispositivo: V812EFG900,
Velocidade: -8.
IEEE LATIN AMERICA TRANSACTIONS, VOL. 6, NO. 7, DECEMBER 2008
somente 7 caracteres, obtendo um atraso também similar, de
43 ns.
TABELA VI
TEMPORIZAÇÃO DOS ALGORITMOS GLOBAL E LOCAL EM VHDL
COM AS FAMÍLIAS VIRTEXE E VIRTEXE
PLACA
Os tempos gerados pela ferramenta Xilinx [30] representam
o tempo necessário que o circuito precisa para implementar
todas as operações que executam os algoritmos global e local.
Esses dados estão relacionados aos atrasos para gerar a saída
desejada de um determinado circuito. Este tempo é o resultado
da soma do tempo de lógica propriamente dito, mais o de
roteamento em FPGA do circuito digital. Importante ressaltar
que a tabela VI exibe as estatísticas temporais em
nanosegundos, para uma seqüência de tamanho 10 caracteres.
Nessa tabela se observa um tempo de lógica menor para a
família VIRTEXE em relação à família VIRTEX. Conforme
visto na seção 3, percebe-se novamente que o algoritmo local
requer mais tempo de execução em relação ao algoritmo
global. Neste caso, as diferenças são respectivamente de 10%
e 6.2% para as placas Virtex e Virtex E. Lembrar que essa
diferença, para um tamanho de 10 caracteres, foi de 27% para
a implementação em C. Isto quer dizer que em hardware as
diferenças são menores.
Pode-se observar então que as estatísticas temporais (dadas
em nano segundos – ns, e MHz) não sofrem grandes
diferenças quando se mapeiam esses algoritmos em diferentes
FPGAs, uma vez que os algoritmos implementados têm
pequenas diferenças, ou seja, nota-se isso nos estados da
tabela IV e V.
Também foi possível mudar o tamanho das seqüências,
considerando 8, 10 e 15 caracteres. Na tabela VII se observa o
tempo (em nano segundos - ns) da implementação dos
algoritmos de alinhamento global e local em software, (usando
a linguagem de programação C e executados em um Pentium
IV 1.66 GHz).
Já a tabela VIII apresenta os tempos (também em nano
segundos) da implementação em hardware (FPGAs), obtidos
usando a ferramenta Xilinx [30]. Para uma melhor
visualização, a figura 2 mostra o tempo de execução das
implementações dos algoritmos AGM e ALM tanto em C
quanto em VHDL, utilizando a família VIRTEX V800FG680.
Assim, é possível observar que a execução em hardware
(usando FPGAs) é mais rápida do que a implementação em
software em C executando em um computador Pentium IV
1.66 GHz. A implementação em hardware somente foi
possível para seqüências de até 15 caracteres, resultado similar
ao obtido por Lozano [19], que fez um processador sistólico
em FPGAS da Altera para seqüências de tamanho de até
Atras
o
Total
Freq.
MHz
36.59
77.1%
47.46
21.07
10.90
20.8%
41.52
72.9%
52.41
19.07
Global
7.16
16.0%
37.67
84.0%
44.83
22.30
Local
7.09
14.9%
40.54
85.1%
47.63
20.99
Algori
tmo
Tempo
Lógica
Tempo de
Global
10.88
22.9%
Local
VIRTEX
V800FG
680
VIRTEX
E
Roteament
o
V812EF
G900
TABELA VII
TEMPO EM (ns) DA IMPLEMENTAÇÃO EM C
Tamanho da
Seqüência
Global
Local
8 caracteres
10 caracteres
15 caracteres
216.000
220.000
750.000
156.000
160.000
744.000
TABELA VIII
TEMPO EM (ns) DA IMPLEMENTAÇÃO EM FPGAS
Tamanho da
Seqüência
8 caracteres
10 caracteres
15 caracteres
VIRTEX
V800FG680
Global
Local
47,47
45,90
57,44
52,42
55,06
67,48
VIRTEX E
V812EFG900
Global
Local
44,83
44,75
50,89
47,63
51,12
62,63
Após ter realizado as implementações dos algoritmos de
alinhamento global e local, das seqüências genéticas de DNA,
utilizando a técnica de programação dinâmica, tanto em nível
de software (em C) quanto em nível de hardware (VHDL e
prototipados em FPGA) foi possível comparar os nossos
dados com aqueles obtidos para outras plataformas.
A tabela IX oferece informações referentes aos caracteres
processados por segundo (CPS – Characters Processed per
Second) para a implementação do algoritmo BioSCAN
(também implementado em C) em plataformas paralelas [12].
Neste caso, foi feita a seguinte consideração: Se para uma
seqüência de 10 caracteres, o circuito precisou um tempo X,
medido em nanosegundos, então, calcula-se quantos
caracteres ele consegue processar em um segundo.
MORONY AND MORENO : FPGA-BASED IMPLEMENTATION AND PERFORMANCE
TABELA IX
CPS - CARACTERES PROCESSADOS POR SEGUNDO
Siste
mas
BioSC
AN
Sun
690
Conve
x 240
MasPar
Tamanho das seqüências
50
100
500
10
1000
1.979.583
1.979.583
1.979.583
1.979.583
1.979.583
5.776.729
1.235.597
625.385
125.359
62.629
6.423.184
2.953.318
1.733.355
371.772
189.344
1.162.529
1.160.915
1.160.850
1.161.847
1.161.107
No algoritmo global, usando a família
V800FG680, obteve-se um tempo de 45.902 ns.
VIRTEX
Então:
1 seg * 10 caracteres / 45.902 ns = 10/45.902*10-9 =
217.864.923 CPS
Comparados com os sistemas da tabela X, onde aparece o
valor de CPS para as respectivas implementações desses
algoritmos em linguagem de alto nível e plataformas especiais
de hardware, e observando o mesmo tamanho de seqüência de
10 caracteres, pode-se dizer que a implementação seqüencial e
específica em hardware com FPGAs mostrou-se mais rápida
do que alguns sistemas paralelos de alta performance.
TABELA X
COMPARAÇÃO COM SISTEMAS CONHECIDOS
Sistemas
FPGAs:
AGM e ALM de Morony
Sistólico de Lozano [19]
Paralelo:
Convex 240
Sun 690
BioSCAN
MasPar-1
CPS
Quantidade de
vezes mais
lento
217.864.923
217.864.923
1
1
6.423.184
5.776.729
1.979.583
1.162.529
33.9
37.7
110
187.4
Finalmente, ao comparar os dados em software e hardware
neste artigo, nota-se a diferença significativa nos tempos de
execução, visto que as performances em hardware são
melhores do que as versões em software. Não obstante os bons
resultados obtidos, seria interessante analisar seqüências com
tamanhos variados e maiores em hardware, já que não se
conseguiu que a ferramenta Xilinx suportasse a implementação
para tamanhos de seqüências maiores a 15 caracteres.
V. CONCLUSÕES
Neste trabalho foram implementados, tanto em software
usando a linguagem de programação C quanto em hardware
(usando VHDL e FPGA), os algoritmos de alinhamento global
585
e local, ou melhor conhecidos como Needleman-Wunsch e
Smith-Waterman, respectivamente. Com os dados de
desempenho obtidos (usando o tempo de execução) desses
algoritmos, a versão em nível de hardware usando VHDL e
FPGAs e sintetizando o circuito com a ferramenta Xilinx
Series Foundation [30] é mais rápida do que uma
implementação em nível de software utilizando a linguagem
de programação C e computadores pessoais, tais como
Pentium IV 1.66 GHz.
Em software, foram comparadas seqüências com tamanhos
de até 1000 caracteres e em FPGA o hardware suportou
apenas tamanho com 15 caracteres. Para seqüências de até
300 caracteres, a implementação em software obteve
desempenho razoável (tempo de execução comparável aos
obtidos em máquinas paralelas). Já para tamanhos maiores, as
outras implementações paralelas são bem melhores do que a
nossa seqüencial, motivando o uso de plataformas e soluções
paralelas para tamanhos de grandes seqüências.
Foi possível implementar os algoritmos acima descritos
utilizando tecnologia FPGA da Xilinx, porém somente as
placas VIRTEX e VIRTEXE conseguiram suportar esses
algoritmos, onde as seqüências de DNA analisadas e
comparadas conseguiram suportar seqüências com tamanho
máximo de 15 caracteres. A utilização de recursos espaciais
do FPGA é pequena, o que sugere a possibilidade de usar a
implementação para seqüências de tamanho maior.
Observando os resultados obtidos, percebe-se que a
implementação em hardware apresentou tempo de execução
mais rápido que alguns sistemas amplamente usados, tais
como: BioSCAN, Sun 690, Convex 240 e o MasPar-1 que
implementam os algoritmos em linguagem de alto nível e os
executam em hardware com maior capacidade de
processamento.
Portanto, FPGAs parecem ser uma alternativa para resolver
o problema dos algoritmos destinados ao alinhamento e a
comparação de seqüências genéticas, uma vez que esta
tecnologia permite baixos custos e ganhos em tempo de
execução.
Como trabalhos futuros, sugere-se realizar otimizações nos
algoritmos, paralelizar os cálculos com o objetivo de diminuir
os recursos espaciais do FPGA, comparar resultados com
outras propostas recentes tais como [3, 4, 5, 6]. Seria também
interessante propor novos algoritmos e/ou implementações, a
fim de contribuir para solucionar o problema do
seqüenciamento de gens, implementações como por exemplo:
mais placas FPGAs funcionando em paralelo. Também propor
outras técnicas para otimizar a velocidade de processamento
como pipeline, técnicas de paralelismo e o uso de outras
tecnologias como por exemplo SoC - System on Chip ou
MPSoC.
REFERÊNCIAS
[1]
ALTSCHUL, S. F. et al. (1990) “Basic local alignment search tool”,
Journal of Molecular Biology, 215:403–410.
586
IEEE LATIN AMERICA TRANSACTIONS, VOL. 6, NO. 7, DECEMBER 2008
[2]
ARNOLD, J. M. BUELL, D.A. and DAVIS, E.G. (1992) “Splash-2”, In
Proc. 4th Annual ACM Symposium on Parallel Algorithms and
Architectures, p. 316-322.
[3]
BOUKERCHE, Azzedine and CORREA, Jan M., and MELO, Alba
Cristina Alves de, and JACOBI, P., and ROCHA, A.F. (2007) A
FPGA-Based Accelerator for Multiple Biological Sequence
Alignement with DIALIGN. In Proc. of IEEE HiPC-2007.
[4]
BOUKERCHE, Azzedine and CORREA, Jan M., and MELO, Alba
Cristina Alves de, and JACOBI, P., and ROCHA, A.F. (2007)
Reconfigurable Architecture for Biological Sequence Comparison in
Reduced Memory Space. In Proc. of IPDPS-2007 Intl. Parallel and
Distributed Processing Symposium. IEEE Computer Society.
[22]
OLIVEIRA, D. C. (2002) “Alinhamento de Seqüências”. Monografia
de Graduação apresentada ao Departamento de Ciência da Computação
da Universidade Federal de Lavras como parte das exigências da
disciplina Projeto Orientado para obtenção do título de Bacharel em
Ciência da Computação. Lavras - Minas Gerais – Brasil.
[23]
ORDONEZ, E. D. M. et al. (2005) “Microcontroladores e FPGAs –
Aplicações em Automação”, Editora Novatec, Brasil, 2005. 360p.
[24]
RAIMBAULT, F. et al. (1993) “Fine grain parallelism on a MIMD
machine using FPGA’s”, Research Repport INRIA N.
[25]
SMITH, T. and WATERMAN, M. (1981) “Identification of common
molecular subsequences”, Journal of Moleular Biology, 147:195–197.
[26]
TANGEN, U., r MCCASKILL, J. S. (1998) “Hardware Evolution with
a Massively Parallel Dynamically Reconfigurable Computer: POLYP”,
In: International Conference On Evolvable Systems: From Biology To
Hardware, 2., 1998, Lausanne. Proceedings... Berlin: Springer-Verlag
(Lecture Notes in Computer Science v. 1478), p.364-371.
[5]
BOUKERCHE, Azzedine and MELO, Alba Cristina Alves de, and
RINCON, M.A., and WALTER, M.E.M.T. Parallel Strategies for Local
Biological Sequence Alignment in a Cluster of Workstations. (2007)
Journal of Parallel and Distributed Computing, v.67, p. 170-185.
[6]
BOUKERCHE, Azzedine and MELO, Alba Cristina Alves de, and
RINCON, M.A., and Santana, T.M. Parallel Strategies for Local
Biological Sequence Alignment in a Cluster of Workstations. (2005) In
Proc. of IPDPS-2005 Intl. Parallel and Distributed Processing
Symposium. IEEE Computer Society.
[27]
VIANNA, C. J. M. (2003) “Arquiteturas de Computadores para
alinhamento de seqüências biológicas”, Relatório Técnico da
Disciplina de Arquiteturas Avançadas. Departamento de Computação e
Estatística – Centro de Ciências Exatas e Tecnologia. Universidade
Federal de Mato Grosso do Sul, Julho.
[7]
BERTIN, P., RONCIN, D. and VUILLEMIN, J. (1992)
Programmable active memories: a performance assessment. In F.
Meyer, B. Monien, and A.L. Rosenberg, editors, Parallel Architectures
and their efficient use, p. 119-130. LNCS, October.
[28]
[8]
CARVALHO, L. G. A. (2003) “Uma abordagem em hardware para
algoritmos de comparação de seqüências baseados em programação
dinâmica”, Dissertação de Mestrado, Departamento de Ciência da
Computação, Universidade de Brasília – DF, Brasil, Dezembro.
WARD, R. J., GALBAN, V. D. and RUIZ, J. C. (2004) “Tópicos em
Bioinformática. Introdução à Análise de Seqüências”, Faculdade de
Medicina de Riberão Preto – FRMP – USP. Departamento de
Bioquímica
e
Imonologia.
Disponível
em:
<http://rbq.fmrp.usp.br/bioinfo/bioinfo1.htm>, Julho.
[29]
WHITE, C. T. et al. (1991) BioSCAN: A VLSI-basead system for
biosequence analysis. Proceedings of the International Conference on
Computer Design: VLSI in Computers & Processors, p. 504-509.
[30]
XILINX. (2006) The Programmable Gate Array Data Book. 2100
Logic Drive, San Jose, CA 95124 USA.
[9]
CHOW, E. et al. (1991) Biological information signal processor. In:
ASAP, (Valero, M. et al., eds) p.144-160, Los Alamitos, CA: IEEE
Computer Society.
[10]
GOKHALE, M. B. et al. (1990) “SPLASH: A reconfigurable linear
logic arrays”, In Proc. of ICPP – 2005, p.526-532, Aug. 2005.
[11]
GUERDOUX-JAMET, P. and LAVENIER, D. (1995) “Systolic filter
for fast dna similarity search”, In ASAP’95, Strasbourg.
[12]
HOFFMAN, D. L. (1993) “A Comparison of the BioSCAN Algorithm
on Multiple Architectures”, Department of Computer Science.
University of North Carolina at Chapel Hill. 27599-3175.
[13]
HUGHEY, R. and LOPRESTI, D. P. (1991) “B-SYS: A 470-processor
programmable systolic array”, Proceedings of the International
Conference Parallel Processing, p.580-583.
[14]
HUGHEY, R. (1991) “Programmable Systolic Arrays”, PhD thesis,
Departament of Computer Science, Brown University, Providence, RI.
[15]
JEANMOUGIN, F. et al. (1998) “Multiple sequence alignment with
CLUSTAL X”, Trends Biochem Sci, 23:403–405, Outubro de 1998.
Disponível em: < http://www.ncbi.nlm.nih.gov/entrez/, Dez. 2004.
[16]
LANG, H. (1986) “The instruction systolic array a parallel architecture
for vlsi”, Journal of VLSI , 1:65–74.
[17]
LAVENIER, D. (1996) “Dedicated Hardware for Biological Sequence
Comparison”, Journal of Universal Computer Science, 2(2):77-86.
[18]
LAVENIER, D. (1996) “SAMBA: Systolic Accelerators for Molecular
Biological Applications”, Technical Report 988 IRISA 35042 Rennes
Cedex, França.
[19]
LOZANO, Martin A.; MEDINA, Jaime Velasco (2006). Diseño de un
procesador para el alineamiento global de secuencias de DNA. Iberchip
Workshop, Costa Rica, p. 1-5, Marzo.
[20]
MATTOS, N. P. e RASKIN, S. F. (1994) “Aspectos da Arquitetura de
Processadores Risc. Um comparativo RISC X PC”, Disponível em:
<http://www.pr.gov.br/batebyte/edicoes/1994/bb35/aspectos.htm>,
Novembro de 2004.
[21]
NEEDLEMAN S. B. and WUNSCH, C. D. (1970) “A general method
applicable to the search for similarities in the amino acid sequence of
two proteins”, Journal Molecular Biology, 48, p. 443-453.
Cristiane da Silva Morony. She is BS
in Computer Science and received the
MSc degrees in Computing Sciences
from UNIVEM – Euripides Foundation
of Marilia – Brazil, in 2006. She now is
working in Faculdades COC at
Araçatuba, S.P., Brazil. She is
interested in bioinformatics, distributed
systems and reconfigurable computing.
Edward David Moreno. Received the
MSc. and PhD degrees in Electrical
Engineering from University of Sao
Paulo - Brazil, in 1994 and 1998.
During 1996 and 1997 he stayed as
invited researcher at University of
Toronto, Canada, and Chalmers
University of Technology, Sweden. He
is professor. at the UEA – Amazonas
State University. and professor and
researcher at UFAM – Federal Univ. of
Amazonas, Manaus, AM, Brazil. Prof. Moreno has participa ted as an
IPC member of 70 intl. scientific events, and he is editorial board
member of three Journals: JUCS – Journal Universal on Computer
Science, Springer Transactions on Computational Science and IJCSNS
Intl. Journal of Computer Science and Network Security. He has
published five books about digital systems, FPGAs, Microcontrollers,
Reconfigurable Computing and Hardware Security. The research areas
are: computer architecture, reconfigurable computing, embedded
systems, hardware security, power aware computing and performance
evaluation.