Paralelización del algoritmo de Smith-Waterman
-
Upload
luis-belloch-gomez -
Category
Health & Medicine
-
view
1.703 -
download
3
description
Transcript of Paralelización del algoritmo de Smith-Waterman
![Page 1: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/1.jpg)
Paralelización del algoritmo de Smith-Waterman
Luis Belloch GómezBioinformática, Mayo 2010Master Computación Paralela y Distribuida
![Page 2: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/2.jpg)
BLAST y similares son más rápidos, pero pueden no detectar algunas alineaciones.
Smith-Waterman es más preciso, pero su ejecución es mucho más lenta.
![Page 3: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/3.jpg)
1. Construcción de la matriz de puntuación.
2. Recorrido inverso a partir del máximo.
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 28 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
2 AW-HE 5 || ||5 AWGHE 9
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
P1
P2
P3
P4
A B C D E F
B C D E F G
C D E F G H
D E F G H I
E F G H I J
F G H I J K
A(i-1,j-1) A(i-1,j)
A(i,j-1) A(i,j)
![Page 4: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/4.jpg)
Para poder ejecutar en paralelo es necesario saber
qué dependencias de datos existen
![Page 5: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/5.jpg)
Análisis de dependencias
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 28 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
2 AW-HE 5 || ||5 AWGHE 9
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
P1
P2
P3
P4
A B C D E F
B C D E F G
C D E F G H
D E F G H I
E F G H I J
F G H I J K
A(i-1,j-1) A(i-1,j)
A(i,j-1) A(i,j)
Cada elemento depende de su fila superior y su columna izquierda.
![Page 6: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/6.jpg)
A B
B C
Análisis de dependencias
Si ordenáramos la ejecución, los elemento B pueden ejecutarse en paralelo
P1 P2
![Page 7: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/7.jpg)
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 28 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
2 AW-HE 5 || ||5 AWGHE 9
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
P1
P2
P3
P4
A B C D E F
B C D E F G
C D E F G H
D E F G H I
E F G H I J
F G H I J K
A(i-1,j-1) A(i-1,j)
A(i,j-1) A(i,j)
A B
B C
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 4 10 4 0 4 16 26
P1
P2
P3
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 4 10 4 0 4 16 26
P1
P2
P3
envío de datos de P1 a P2
envío de datos de P3 a P4
Ejecución por bloques
Para evitar un envío excesivo de datos, se divide la matriz en bloques
![Page 8: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/8.jpg)
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 28 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
2 AW-HE 5 || ||5 AWGHE 9
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
P1
P2
P3
P4
A B C D E F
B C D E F G
C D E F G H
D E F G H I
E F G H I J
F G H I J K
A(i-1,j-1) A(i-1,j)
A(i,j-1) A(i,j)
A B
B C
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 4 10 4 0 4 16 26
P1
P2
P3
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 4 10 4 0 4 16 26
P1
P2
P3
envío de datos de P1 a P2
envío de datos de P3 a P4
Ejecución por bloques
Cada proceso comparte su última fila con el resto
![Page 9: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/9.jpg)
Ejecución por bloques
La ejecución se realiza en cascada, como máximo existirán max(c,f) procesos en paralelo
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 28 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
2 AW-HE 5 || ||5 AWGHE 9
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
P1
P2
P3
P4
A B C D E F
B C D E F G
C D E F G H
D E F G H I
E F G H I J
F G H I J K
A(i-1,j-1) A(i-1,j)
A(i,j-1) A(i,j)
A B
B C
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 4 10 4 0 4 16 26
P1
P2
P3
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 4 10 4 0 4 16 26
P1
P2
P3
envío de datos de P1 a P2
envío de datos de P3 a P4
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 28 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
2 AW-HE 5 || ||5 AWGHE 9
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
P1
P2
P3
P4
A B C D E F
B C D E F G
C D E F G H
D E F G H I
E F G H I J
F G H I J K
A(i-1,j-1) A(i-1,j)
A(i,j-1) A(i,j)
A B
B C
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 4 10 4 0 4 16 26
P1
P2
P3
- H E A G A W G H E E
- 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 21 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 4 10 4 0 4 16 26
P1
P2
P3
envío de datos de P1 a P2
envío de datos de P3 a P4
![Page 10: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/10.jpg)
Detalles Implementación
Paradigma: Memoria Distribuida.
Desarrollado en C & MPI.
La matriz de puntuación es un vector de c x f enteros, contiguos en memoria.
En lugar de almacenar la matriz de dirección por separado, se empaqueta en los dos bits superiores.
bits 29 a 000
![Page 11: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/11.jpg)
Entorno de pruebas
Quadcluster del DSIC
SGI Altix XE, 4 nodos
Cada nodo 2 Intel Xeon Quadcore 5365 (64 bits)
8 cores por nodo16 GB RAM
Total 32 procesadores (nucleos)
![Page 12: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/12.jpg)
Estructura de pruebas
El coste del algoritmo está en la construcción de la matriz de puntuación.
Secuencias de 100, 3K y 30K elementos, sacadas de Uniprot.
HBA_HUMAN.fasta HBB_HUMAN.fasta 142 x 147
FBN2_HUMAN.fasta FBN2_MOUSE.fasta 2.912 x 2.907
TITIN_HUMAN.fasta TITIN_MOUSE.fasta 34.350 x 35.213
![Page 13: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/13.jpg)
Coste Espacial
Una secuencia de 30K elementos produce una matriz de 30K x 30K = 900 millones de elementos.
900 x 4bytes ≅ 3.35GB
Repartidos entre 32 procesadores, cada uno construye una matriz de 30K x (30K/32) ≅ 100MB
![Page 14: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/14.jpg)
Resultados secuencial
icc test2.c util.c sw.c -o test2 -std=c99 -O3./test2Prueba de rendimiento secuencial (matriz puntuación solo).t25a.s t25b.s la: 25 lb: 25 it:1000 tst: 1 T: 0.01 mst100a.s t100b.s la: 140 lb: 140 it:1000 tst: 1 T: 0.16 mst3Ka.s t3Kb.s la: 2912 lb: 2907 it:1 tst: 1 T: 75.00 mst30Ka.s t30Kb.s la: 34350 lb: 35213 it:1 tst: 1 T: 11000.00 ms
![Page 15: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/15.jpg)
Resultados paralelo
np ts tp Sp SpRef Ep EpRef48162432
11 2,64114 4,16 4,00 1,04 1,0011 1,36494 8,06 8,00 1,01 1,0011 0,70934 15,51 16,00 0,97 1,0011 0,49275 22,32 24,00 0,93 1,0011 0,38880 28,29 32,00 0,88 1,00
0
5,00
10,00
15,00
20,00
25,00
30,00
35,00
40,00
4 8 16 24 32
4,16
8,06
15,51
22,32
28,29
Speed Up Sp ref.
0,70
0,80
0,90
1,00
1,10
4 8 16 24 32
1,041,01
0,97
0,93
0,88
Eficiencia Ep ref.
np ts tp Sp Ep48162432
11 2,641 4,165 1,04111 1,365 8,059 1,00711 0,709 15,507 0,96911 0,493 22,324 0,93011 0,389 28,292 0,884
* tiempos en seg.
TITIN Human\Mouse, 34Kx35K elementos4.5GB total, 140MB por proceso
![Page 16: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/16.jpg)
Speed Up Tiempo del mejor algoritmo secuencial frente al
tiempo del paralelo (sp = t1 / tp)
np ts tp Sp SpRef Ep EpRef48162432
11 2,64114 4,16 4,00 1,04 1,0011 1,36494 8,06 8,00 1,01 1,0011 0,70934 15,51 16,00 0,97 1,0011 0,49275 22,32 24,00 0,93 1,0011 0,38880 28,29 32,00 0,88 1,00
0
5,00
10,00
15,00
20,00
25,00
30,00
35,00
40,00
4 8 16 24 32
4,16
8,06
15,51
22,32
28,29
Speed Up Sp ref.
0,70
0,80
0,90
1,00
1,10
4 8 16 24 32
1,041,01
0,97
0,93
0,88
Eficiencia Ep ref.
np ts tp Sp Ep48162432
11 2,641 4,165 1,04111 1,365 8,059 1,00711 0,709 15,507 0,96911 0,493 22,324 0,93011 0,389 28,292 0,884
![Page 17: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/17.jpg)
Eficiencia
Grado de utilización del sistema (ep = sp/p)
np ts tp Sp SpRef Ep EpRef48162432
11 2,64114 4,16 4,00 1,04 1,0011 1,36494 8,06 8,00 1,01 1,0011 0,70934 15,51 16,00 0,97 1,0011 0,49275 22,32 24,00 0,93 1,0011 0,38880 28,29 32,00 0,88 1,00
0
5,00
10,00
15,00
20,00
25,00
30,00
35,00
40,00
4 8 16 24 32
4,16
8,06
15,51
22,32
28,29
Speed Up Sp ref.
0,70
0,80
0,90
1,00
1,10
4 8 16 24 32
1,041,01
0,97
0,93
0,88
Eficiencia Ep ref.
np ts tp Sp Ep48162432
11 2,641 4,165 1,04111 1,365 8,059 1,00711 0,709 15,507 0,96911 0,493 22,324 0,93011 0,389 28,292 0,884
![Page 18: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/18.jpg)
La paralelización funciona mejor con tamaños de problema grandes, el algoritmo secuencial se las
arregla para secuencias cortas.
Posibles trabajos futuros: Memoria compartida o sistemas híbridos.
Conclusiones
![Page 19: Paralelización del algoritmo de Smith-Waterman](https://reader034.fdocumento.com/reader034/viewer/2022042614/558cc67bd8b42a147c8b45ab/html5/thumbnails/19.jpg)