Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
1
Frédéric Jarlier
2000-2007: The Mathworks SAS (Ingénieur)
2007-2013: CNRS (IR2)
2014: Institut Curie (IR2)
Le HPC appliqué aux données de séquençage
07/04/2016
2
● Plan– Contexte
– Optimisations
– Résultats
– Conclusion
– Annexes
Le HPC appliqué aux données de séquençage
07/04/2016
3
● Contexte
– Comprendre le cancer c'est comprendre la structure du génome
– Le cancer est une maladie des gènes
● Ré-arrangement chromosomiques et mutations
CK Rocha et al., Molecular Cytogenetics 2011
07/04/2016
4
● Contexte
– Le séquencage du génome, un exemple de pipeline
10 séquenceurs 1 WG (30X) / heure => 300 Go / heure
BGI 181 séquenceurs => 6 To par jour
Illumina HiSeq 20h avec 8 threads
Tri
6h sur 32 threads
Variant calling
>5 jour
Alignement
La question : comment analyser des volumes importants de données
07/04/2016
1 WGS 30X
507/04/2016
● Le pipeline QUASART
6
● Exemple d'architecture dédiée au calcul parallele
180 dual processor nodes (Intel Sandy Bridge E5-2680, 2.7 GHz, 8 cores) with
128 GB of memory per node, i.e. a total of 2,880 cores (Bull),
QDR Infiny Band (36 GB/s)
Lustre file System
07/04/2016
7
● L'alignement principe– Trouver les coordonnées des reads sur le genome de référence
T T G A T T A TC A T T C C C GC G C G G C C T G A A T T G A
G A T T C G C G
Reads (nucléotides)
G A T T C G C G G C C A T T C C T G A A T T G A T T A T G C C G T T
T G C C G T T G
référence …
● Référence (humaine) = 3,4 milliards de nucléotides
● Des milliards de reads suivant la profondeur du séquençage
● L'alignement est un processus très complexe
07/04/2016
8
● L'alignement “Embarrassingly parallel”
Split
Alignement (BWA, Bowtie)...
Merge
Fichiers de reads
07/04/2016
907/04/2016
● Le pipeline QUASART
10
NFS, Lustre,...
Shared File pointer operations (MPI)
NFS, Lustre,...
NFS, Lustre,...
Operation non collective => très peu de communications
07/04/2016
● Le pipeline QUASART
NFS, Lustre,...
11
MPI Shared File pointer (Operations non bloquantes)
Supporté par NFS, Lustre,...
Découpage en chunks (100 Mpb)
Fastq
SAM
Fastq
I/O streaming
Chunks list
07/04/2016
● Le pipeline QUASART
12
HCC1187C WG 90X breast ductal carcinoma cell line
Input = 700 GoOutput = 900 Go
07/04/2016
● Le pipeline QUASART
Speed alignment compare with BWA on 16 threads
1307/04/2016
● Le pipeline QUASART
14
● Le principe du tri
Conclusion : Trier c'est déplacer 1To (3 milliars de reads) ( 1 read = 300 carac. ASCII)
Le tri est réalisé sur les coordonées génomiques des reads
Fichier SAM Fichier BAM
Read 3Read 7Read 2
Read 6
Read 5
Read 4
Read 8Read 1
Read 1Read 2Read 3
Read 4
Read 5
Read 6
Read 7Read 8
07/04/2016
15
● Le tri par merge sort
Solutions actuelles utilisent des fichiers temporaires => problème de scalabilité
Fichier SAM Fichier BAM
Read 3Read 7Read 2
Read 6
Read 5
Read 4
Read 8Read 1
Read 1Read 2Read 3
Read 4
Read 5
Read 6
Read 7Read 8
read 3read 7
Fichiers Temporaires
Merge sort Merge sortdecoupage
read 2read 6
read 1read 4read 5read 8
read 8read 1
read 5read 4
read 2read 3read 6read 7
Samtools, sambamba
07/04/2016
16
● Le tri par QUASART
Pour éviter les accés constants au file system on utilise des caches
=> 5h pour trier 1 To avec 500 cpu, 3To de RAM
=> nouveau bottle neck = les communications, All2all de complexité n^2
Fichier SAM
Fichier BAM
Caches Caches Ecritures paralleles
All2all
Read 3Read 7Read 2
Read 6
Read 5
Read 4
Read 5Read 1
Tri bitonic
Read 1Read 2Read 3
Read 4
Read 5
Read 6
Read 7Read 8
07/04/2016
17
Pour l'echange entre les caches on utilise l'agorithme de Bruck
=> 5h reduit à 30mn pour trier 1 To avec 320 cpu, Total RAM <1To
Fichier SAM
Fichier BAM
Indexation Caches Compression et écriture
Read 3Read 7Read 2
Read 6
Read 5
Read 4
Read 5Read 1
Tri bitonic
Read 1Read 2Read 3
Read 4
Read 5
Read 6
Read 7Read 8
Algorithme de Bruck
Bruck et al. 97
Offset 3Offset 7Offset 2
Offset 6
Offset 5
Offset 4
Offset 5Offset 1
Caches
MPI_File_viewMpi_read_allDataType
Mpi_send_recieve MPI_File_set_viewMpi_write_all
07/04/2016
● Le tri par QUASART
1807/04/2016
● Le tri par QUASART
Speed up linéaire, efficacité, scalabilité
32 threads
19
● Conclusion – Code disponible sour licence GPLv3 : https://github.com/InstitutCurie/QUASART
– En HPC les accélérations matérielles sont essentielles : Réseau faible latence, File system distribué, Caches,...
– HPC = 50% accélérateurs matériels + 50% algorithmes
– MPI propose un paradigme interessant qui permet de faire un traitement global de la données
– Les marqueurs du HPC : le speed up, l'efficacité, la scalabilité.
Le HPC appliqué aux données de séquençage
07/04/2016
20
● Remerciements– De l'Institut Pasteur :
● Nicolas Joly
– De l'Institut Curie :
● Philippe Hupe, François Prud’Homme, Maxime Chevailliot
– Les étudiants de Paris Descartes :
● Nicolas Fedy, Leonor Sirotti, Thomas Magalhaes, Paul Paganiban
Le HPC appliqué aux données de séquençage
07/04/2016
21
● Annexe : Gestion de la donnée avec MPI– Utiliser les structures de données (DataType) pour éviter la recopie en mémoire
– Masquer les communications par le calcul (operation non bloquantes)
– Utilisation des vues (view) pour la lecture en paralléle
– Plusieurs mode lecture parallele:
● Data sieving
● 2 phases collective read
Le HPC appliqué aux données de séquençage
07/04/2016
22
● Annexe : QUASART load balancing
Algorithme efficace : 90% du temps est passé dans l'alignement
Taille des buffers pour load balancing
07/04/2016
23
Minu
tes
500 600 700 800 900 10000
10
20
30
40
50
60
70
80
Spee
dup
/ BW
A M
EM (1
6T)
Speed-up alignment of the mpiBWA compare with BWA 16 threads on 90X WG
CPU number
0
10
20
30
40
50
60
70
80
90
100
Minu
tes
10 / 34 20 / 74 30 / 128 40 / 145 50 / 182 60 / 218 70 / 256 80 / 292 90 / 3800
10
20
30
40
50
60
70
80
Spee
dup
/ Sa
mba
mba
16
T
Speed-up sorting of the mpiSORT compare with Sambamba 16 threads on 90X WG
Sample coverage / CPU number
1
3
5
7
9
11
13
15
17
19
● Annexe : le tri speed up
07/04/2016
24
● Annexe : Analyse du tri par QUASART
Pas d'influence des threads
Sorting 4%
Bruck 20%
Compression 21%
Writing 31%
Parsing 17%
Analyse of Sorting algorithm for 93X WG
Pipeline équilibré
07/04/2016
25
● Annexe : Discussions– MPI (Message Passing Interface)
● Avantages
– Basé sur les messages entre jobs
– Depuis MPI2 supporte les IO distribuées
– Meilleure gestion des ressources (mémoire, cpu)
– 2 implémentations OpenMPI, MVAPICH2
● Inconvénients
– Implémentation en langage bas niveau C, C++
– Matériels adaptés
07/04/2016
26
● Annexe : Discussion– Méthodes basées sur le l'utilisation d'un cloud
● Techniques “In memory” : SPARK
● Hadoop
– facile à implémenter (MapReduce)
– scalabilité
– Tout ne peut pas être “MapReducer”
– File system spécifique HDFS
– Protocole sécurisé
– HPC
● XeonPhi, GPU
– Bande passante limitée
07/04/2016