Soluções em GPU para o Problema do Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Soluções em GPU para o Problema do Alinhamento Spliced Defesa de Dissertação de Mestrado

Anisio Vitorino Nolasco Orientadora

Profa. Dra. Nahri Balesdent Moreano Faculdade de Computação, UFMS 10 de outubro de 2014

Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Motivação e Objetivos

GPU como plataforma de computação paralela Não usada somente para processamento gráfico Crescimento praticamente exponencial das bases de dados biológicas (ex.:GenBank) Desenvolver soluções em GPU para problema do alinhamento spliced Utilizar os recursos da GPU de forma eficiente Avaliar desempenho das soluções

Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Identificação de Genes e Alinhamento Spliced











b1 b2 b3 b4 b5 β s AATGCATCCCAGTCCAATTAGTAGTTTAGTAGCCTGTGTCTAA

t ATGCATCCCCTGTCTAA s: sequência base sendo investigada, onde m = |s| t: sequência alvo, com |t| = n, onde m > n β: conjunto com todos os éxons candidatos, β = {b1 , b2 , ..., bk , bk+1 , ..., b|β| }. Problema: encontrar subconjunto de β de maior similaridade com t

Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Algoritmo de Gelfand para o Alinhamento Spliced Usa programação dinâmica Calcula matriz de similaridade S:   S(i − 1, j − 1, k) + ω(s[i], t[j]) S(i − 1, j, k) + ω(s[i], ‘–’) S(i, j, k) = max  S(i, j − 1, k) + ω(‘–’, t[j])

, se i 6= first(k)

  maxl ∈β(first(k)) S(last(l), j − 1, l) + ω(s[i], t[j]) maxl ∈β(first(k)) S(last(l), j, l) + ω(s[last(l)], ‘–’) S(i, j, k) = max  S(i, j − 1, k) + ω(‘–’, t[j])

, se i = first(k)

Similaridade do alinhamento ótimo: Sim(s, t, β) =

max

1≤ k ≤|β|

Anisio Vitorino Nolasco

S(last(k), n, k)

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Dependências de Dados sequˆencia alvo 1

Caso i = first(k)

1

Caso i 6= first(k)

.. .

···

j −1 j

···

n

Sl

∀ ´exon bl tal que last(l) < f irst(k)

sequˆencia i > last(l) base .. .

1

···

j −1 j

···

n

Sk

1 m

.. . f irst(k) = i .. . last(k) .. . m

Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

i−1 i

´exon bk

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Paralelismo Intra-éxon

sequˆencia alvo t

Sk

Células de uma anti-diagonal calculadas em paralelo Cada célula calculada por uma thread Tamanho da anti-diagonal limitado pelo comprimento do éxon

Anisio Vitorino Nolasco

´exon bk

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Paralelismo Intra-éxon

sequˆencia alvo t

Sk

Células de uma anti-diagonal calculadas em paralelo Cada célula calculada por uma thread Tamanho da anti-diagonal limitado pelo comprimento do éxon

Anisio Vitorino Nolasco

´exon bk

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Paralelismo Inter-éxon sequˆencia alvo t

Sk

Anti-diagonais de éxons com trecho em comum calculadas em paralelo Cada célula calculada por uma thread

´exon bk

Cada éxon calculado por um bloco

sequˆencia alvo t

Sl

´exon bl

Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Paralelismo Inter-éxon sequˆencia alvo t

Sk

Anti-diagonais de éxons com trecho em comum calculadas em paralelo Cada célula calculada por uma thread

´exon bk

Cada éxon calculado por um bloco

sequˆencia alvo t

Sl

´exon bl

Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Dados Biológicos e Plataforma Dados biológicos: [Kishi, 2010] Projeto ENCODE, Base Homologene / NCBI Total de casos de teste: 1010 Informação

Mínimo

Médio

Máximo

Tamanho da sequência base Número de éxons de uma sequência base Tamanho dos éxons de uma sequência base Soma do tamanho dos éxons de uma sequência base Número total de sequências base

2848 2 1 442

42181,10 55,08 149,35 7711,73 240

575746 622 4778 71873

Número de sequências alvo por sequência base Tamanho da sequência alvo

1 189

4,20 1460,48

5 8652

Plataforma: GPU NVIDIA GeForce GTX 460 Host com Intel Core 2 Quad Processor de 2.83 GHz e 4GB RAM CUDA Toolkit e SDK versão 5.0 Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Potencial de Paralelismo 16, 55% 15

Intra-éxon % de ´exons

11, 04% 10

5

1, 31%

32 64 96 128 160 192 224 256 288 320 352 384 416 448 480 512 544 576 608 640 672 704 736 768 800 832 864 896 928 960 992 1024

0

C´elulas calculadas em paralelo (comprimento do ´exon)

% grupos de ´exons

60, 13%

40 21, 35%

20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Inter-éxon

60

Matrizes (correspondentes a ´exons) calculadas em paralelo Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Estimativa de Desempenho Tempo de execução estimado de uma solução sequencial tempo estimado seq = n ×

|β| X

|bk |

k=1

Tempo de execução estimado de uma solução paralela intra-éxon tempo estimado par intra-éxon =

|β| X

(|bk | + n − 1)

k=1

Tempo de execução estimado de uma solução paralela intra- inter-éxon X tempo estimado par intra-éxon max |bk | + n − 1 inter-éxon = ∀G

Anisio Vitorino Nolasco

∀bk ∈G

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Estimativa de Desempenho

Tempo de execu¸c˜ao estimado (escala log)

3×108 108

Solu¸ca˜o sequencial Solu¸c˜ao paralela intra-´exon Solu¸ca˜o paralela intra- e inter-´exon

107

106

105

104

103 100

200

300

400

500

600

700

800

900

1000

Caso de teste biol´ogico Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Aceleradores em GPU Primeiro acelerador: Explora paralelismo intra-éxon Kernel invocado uma vez para cada éxon Grid com um bloco de até 1024 threads, dependendo do comprimento da sequência alvo

Segundo acelerador: Explora paralelismo intra- e inter-éxon Kernel invocado uma vez para cada grupo de éxons independentes Grid com vários blocos de até 1024 threads, dependendo ...

Aceleradores invocam mesmo kernel que realiza 3 fases: Fase 1: Busca em paralelo pelas melhores concatenações entre éxons já calculados Fase 2: Cálculo em paralelo das células de uma anti-diagonal Fase 3: Cópia em paralelo para memória global da última linha de Sk

Técnica de tiling: Aceleradores capazes de tratar entradas com éxons e sequência alvo maiores que no máximo de threads Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Kernel: Fases 1, 2 e 3 ead thr− 1 n ...

...

2 ead thr 1 ead thr 0 ead thr

Sl

∀ ´exon bl tal que last(l) < f irst(k)

S

2

1

0

ead thr 1 n− ...

...

ead thr

ead thr

ead thr

´exon bk

maxAnt

Sk

sequˆencia alvo t

thread |bk | − 1 ...

´exon bk thread 2 thread 1 thread 0

sequˆencia alvo t Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Organização das Estruturas de Dados Convencional:

Inclinada:

Cálculos de índices complexos Divergências

Padrão não uniforme de acessos Divergências 1

sequˆencia alvo t

Sk 1

´exon bk

3

6

10

14

18

2

5

9

13

17

21

4

8

12

16

20

23

7

11

15

19

22

2

3

4

5

6

7

8

9

12

13

14

15

16

17

18

24 20

22

23

24

Cálculos simples Padrão uniforme de acessos Sem divergências

1

10

11

19

Inclinada e alinhada à direita:

21

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24 Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Organização das Estruturas de Dados Convencional:

Inclinada:

Cálculos de índices complexos Divergências

Padrão não uniforme de acessos Divergências 1

sequˆencia alvo t

Sk ´exon bk

1

3

6

10

14

18

2

5

9

13

17

21

4

8

12

16

20

23

7

11

15

19

22

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

24 19

20

22

23

24

Anisio Vitorino Nolasco

21

Inclinada e alinhada à direita: Cálculos simples Padrão uniforme de acessos Sem divergências Passo 1

thread thread thread thread 0 1 2 3

1

2

2

3

3

4

5

6

4

7

8

9

10

5

11

12

13

14

6

15

16

17

18

7

19

20

21

8

22

23

9

24

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Resultados dos Aceleradores em GPU Tempo de execução (ms) (escala log) 104

Speedup 30

Implementa¸c˜ao sequencial Primeiro acelerador: paralelismo intra-´exon Segundo acelerador: paralelismo intra- e inter-´exon

Primeiro acelerador Segundo acelerador

25

103

20 102

15

10

10

5 1 100

200

300

400

500

600

700

800

900

1000

Caso de teste biol´ogico

100

200

300

400

Acelerador Primeiro Segundo

Anisio Vitorino Nolasco

500

600

700

800

Caso de teste biol´ogico

Speedup Médio Máximo 3,57 7,89 7,28 31,51

Soluções em GPU para o Alinhamento Spliced

900

1000

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

CUPS e Escalabilidade Solução Implementação sequencial Primeiro acelerador Segundo acelerador

MCUPS médio 62,01 219,83 452,73

MCUPS máximo 83,90 506,71 2083,81

Caso de teste maior: gene IL1RAPL1 do Homo sapiens Solução Implementação sequencial Primeiro acelerador Segundo acelerador

Anisio Vitorino Nolasco

Tempo 357.506,67 ms 6.794,17 ms 3.934,57 ms

Speedup 1 52,62 90,86

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Comparação com Trabalho Relacionado Tempo de execução do segundo acelerador em GPU

Tempo de execução de [Sarje & Aluru, 2009] no CellBE

103

••

•• •

• • •• •••• •• •• • ••• • • •••• • ••• • •• • •• • •• • • • ••• • • ••• •• • •• • •• ••• ••••• •••••• • •• • • ••• • • •• •• •• • • •• •• • • • ••• ••• •• •• • • •• • •••• ••••• • • • •• • •• •• • • •••• •••• • • • •• •• • • • •• • •• • • •• ••••• •••• •• • • ••• • • ••• ••• •• • •• • •• •• ••• •••••• • •• • •••• ••• •• • • • • •••••••• •• •• ••••• • •• ••• • • •• • ••••••• • • • •• •• •• • • • •• •• •• ••••• • •••• • •• •• ••••• •• ••• • •• • •• • • •• •• • • •• • •• • •• • •• • • •• • • • • • •• •• • •• • • ••• • • • ••••• • • • •••• •• • •••• ••••••• • •• • •• • •• ••• •• • ••• •••• • •••••••• • • •• •• •• • •••••••••••• • • • •••••••••••

102

••• • ••

10

• • •• • ••

• • •

••

••

• • •••• •• • ••• • • •

•

•

• ••

• • • •• • •••

•

••

• •• •

•

76

48

× 47 55 25

44

38

48

02

× 21

28

55

× 20 50 27

13

4× 16

08 53

43 20

3× 17

32

84

8 92

× 15

× 55 60

55

63

× 28

5

•

38

1

32

Tempo de execu¸c˜ao (ms) (escala log)

•• •

m × n (escala log)

Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

102

106

10

105

1 100

200

300

400

500

600

700

800

900

1000

Caso de teste biol´ogico

Estimativa da solu¸c˜ ao paralela intra-´exon Primeiro acelerador

106

103

102 105

10 104

1 100

106

200

300

400

500

600

700

800

900

1000

Estimativa da solu¸c˜ ao paralela intra- e inter-´exon Segundo acelerador

103

102 105

10 104

1 103 100

200

300

400

500

600

700

800

900

Caso de teste biol´ ogico

Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

1000

Tempo de execu¸c˜ao (ms) (escala log) Tempo de execu¸c˜ao (ms) (escala log)

103 107

Tempo estimado (log scale)

104

Tempo de execu¸c˜ao (ms) (escala log)

Estimativa da solu¸c˜ ao sequencial Implementa¸c˜ ao sequencial 108

Tempo estimado (log scale)

Tempo estimado (log scale)

Precisão da Estimativa de Desempenho

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Conclusão Identificamos duas formas para explorar paralelismo no algoritmo de alinhamento spliced Desenvolvemos dois aceleradores em GPU para problema do alinhamento spliced Aceleradores obtiveram excelentes resultados de desempenho Aceleradores apresentaram escalabilidade do desempenho Propusemos uma organização para estruturas de dados dos aceleradores que otimiza sua eficiência Aceleradores são capazes de tratar entradas de dados maiores que no máximo de threads da plataforma Realizamos análise do potencial de paralelismo dos dados biológicos Propusemos um modelo preciso de estimativa de desempenho das soluções paralelas Resultados divulgados em artigo aceito no ICPADS 2014 Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced

Introdução

Alinhamento Spliced

Paralelismo

Solucões

Resultados e Análise

Conclusão

Trabalhos Futuros Otimizar procura dos valores máximos nas matrizes de similaridade correspondentes aos éxons anteriores Otimizar cálculo da similaridade do alinhamento spliced ótimo Experimentar otimizações no uso da memória compartilhada Diferentes implementações da técnica de tiling Encontrar alinhamento ótimo propriamente dito (por exemplo, adaptando método de espaço linear) Analisar código PTX gerado para garantir que compilador não está gerando código com alguma ineficiência Investigar outras formas de exploração de paralelismo no algoritmo de alinhamento spliced Estudar outros problemas similares ao alinhamento spliced, como por exemplo, o alinhamento spliced múltiplo, e analisar se soluções desenvolvidas podem ser estendidas para eles Anisio Vitorino Nolasco

Soluções em GPU para o Alinhamento Spliced