En bioinformatique, nous sommes souvent amenés à travailler avec des données à grande échelle. Il suffit de voir le nombre de publications incluant les termes “large-scale”, “extensive” ou encore “high-throughput” pour s’en rendre compte. Dans la majorité des cas, on est satisfait du développement d’un outil quand celui-ci fait son job correctement en se souciant assez peu de son optimisation. Il est donc assez courant de lancer des tâches de plusieurs heures sur des giga-octets de données pour réaliser des analyses. Cela ne veut pas dire que bioinformaticien rime avec bourrin (enfin si, la, en l’occurrence, ça rime…), mais les quantités de données à traiter sont telles qu’il est parfois difficile de faire autrement.
Dans cet article, je vais tenter de présenter un exemple concret d’utilisation de la technologie GPGPU (General-Purpose computation on Graphic Processing Units) qui n’est, d’après moi, pas encore assez exploitée dans notre domaine.
Il n'est pas toujours possible d'avoir accès à un supercalculateur pour lancer ses analyses, la technologie GPGPU est une alternative peu coûteuse et parfaitement adaptée pour le traitement des tâches massivement parallèles. Les processeurs graphiques actuels ont une capacité de calcul souvent sous-estimée, il serait dommage de les exploiter uniquement pour les calculs de pixels de vos jeux vidéos !
Architecture matérielle
Les processeurs classiques (Central Processing Unit ou CPU) sont très efficaces pour exécuter rapidement des tâches séquentielles. En raison de son architecture différente, un GPU, lui, ne sera pas aussi performant pour ce type de taches, par contre, il convient très bien au traitement d’algorithmes « parallélisables ». Ce qui rend cette technologie très intéressante pour notre domaine .
Le schéma suivant aide à comprendre un peu mieux cette capacité de parallélisation du GPU :
Architecture CPU vs GPU. Crédit : J. Geinz. (licence CC-by-SA 2.0)
Les ALU ("Arithmetic Logic Unit" ou Unité arithmétique et logique) sont les composants chargés des calculs : on comprend mieux, d'après cette image, pourquoi les GPU sont puissants pour la parallélisation. En effet, c'est sur ces parties matérielles que la majorité des opérations de calculs sont réalisées et les processeurs graphiques en ont un très grand nombre en comparaison aux processeurs classiques.
Architecture logicielle
Il existe différentes API de bas niveau permettant d’exploiter l’architecture de nos GPU, les plus populaires étant CUDA et OpenCL (Open Computing Language). CUDA a été spécialement développé pour les GPU NVidia, en conséquence le code a été optimisé pour ce matériel et permettrait donc des implémentations plus performantes. OpenCL est un standard ouvert, l'avantage majeur de cette API est sa portabilité. En effet, une application développée en OpenCL pourra être utilisée sur tout type de plate-formes et systèmes d'exploitation.
Je ne vais pas m’étendre sur les avantages et inconvénients de ces deux implémentations. Actuellement, il semble que l’adoption du standard OpenCL soit en pleine croissance et c’est l’API que j’ai choisi d’utiliser dans mes développements. Dans les deux cas, la structure des applications reste relativement similaire et le code se décompose principalement en deux parties :
- “host code”: est exécuté sur le processeur. Cette partie de l’application est utilisée pour toutes les tâches non-parallélisées (lecture des données, interaction avec l’utilisateur, etc.). L’hôte est communément écrit en C mais différents langages de programmation peuvent être utilisés grâce à une multitude de bindings (Python, Java, C, C++, Ruby, etc.).
- “kernel” : ce code interagit directement au niveau du GPU. En conséquence, l’API est relativement bas niveau (syntaxe proche du C99) et donc pas spécialement accueillant au premier abord. Le kernel contient donc toutes les opérations arithmétiques parallélisables de votre programme. Pour simplifier, c’est un peu le type de code que l’on utiliserait dans le corps d’une boucle.
Il existe de nombreux documents au sujet de cette API qui fournissent de très bons exemples d’implémentations et expliqueront tout cela bien mieux que moi. Je vous invite à consulter l'API officielle pour plus de détails. Je tenterai de présenter différents exemples d'implémentations dans un futur billet.
Exemple de problème "parallélisable"
Pour en revenir à nos moutons, j’ai été récemment amené à développer un outil permettant l’analyse de liaison génétique (genetic linkage en anglais) à grande échelle.
Pour simplifier, il s’agit d’analyser comment certains gènes sont transmis à la descendance. Par exemple, deux gènes étant systématiquement transmis (ensemble) chez des personnes ayant un phénotype particulier (maladie génétique par exemple) joueront potentiellement un rôle dans le développement de ce phénotype. En gros, c’est une manière d’identifier de nouveaux gènes pouvant être impliqués dans le développement d’un trait phénotypique particulier.
Je reçois donc un premier jeu de données incluant :
- l’expression relative de 250 000 gènes ;
- 150 000 SNP ;
- le tout pour un groupe de 2500 patients atteints d’une maladie génétique particulière.
Sans rentrer dans les détails de l’algorithme, il s’agit de tester les 250 000 gènes contre les 150 000 SNP.
La première approche évidente est donc :
|
1 2 3 4 5 6 7 8 9 |
foreach (genes){ foreach (snps){ // do some kickass statistical analysis } } |
Soit 250000 * 150000 = 37.5 milliards de tests… même pas peur.
Une semaine de développement plus tard (oui, le traitement est un peu plus compliqué qu’une simple (double) boucle !), l'application a l’air de fonctionner et l’analyse prend plus ou moins 12 heures. Demi-journées pendant lesquelles la machine n'est pas très réactive car les ressources sont saturées mais ce n’est pas très grave, ça tourne de nuit !
Première reunion, l’analyse semble fonctionner correctement, il m’a été demandé de l’étendre à quelques jeux de données supplémentaires. Deux jours plus tard, pas moins de 750 fichiers m'attendaient sur le serveur. (On se sera sans doute mal compris sur le terme “quelques jeux de données” 😉 ). Petit calcul rapide, si tout va bien j’aurais peut-être fini l’année prochaine. Bref, il va falloir revoir l’implémentation rapidement, sinon je vais passer pour un jambon incompétent…
Les analyses sont réalisées sur des couples gène//SNP mais chaque analyse reste indépendante. Ceci est donc un problème parfaitement adapté à la parallélisation. Trois semaines de développement supplémentaires ont été nécessaires pour traduire l’implémentation initiale en C et récrire les tests statistiques sous forme de kernel OpenCL.
Les résultats sont maintenant générés en moins de 2h (sur un simple portable doté d'une NVIDIA GeForce GT 330M). La quantité de jeux de données n'est donc plus un problème, le patron est content et je conserve mon emploi 😉
Conclusion
De nombreux problèmes liés à la bioinformatique sont parallélisables mais la technologie GPGPU n’est pas encore très répandue dans le domaine. Les langages de bas niveau utilisés par les kernels en sont sans doute la cause principale. Il est également important de noter que le GPGPU est uniquement efficace pour des taches parallélisables. Une implémentation plus classique sera dans certains cas plus performante. Un état des lieux précis du problème à résoudre est donc indispensable afin d'être sûr qu'une telle implémentation sera bénéfique avant de se lancer dans le développement. De plus, il est évident qu’une étape d’apprentissage est nécessaire et que ce type d’implémentation est moins rapide qu’avec un langage de plus haut niveau.
Plusieurs outils courants tels que GPU Blast, CUDASW+, GPU HMMER, etc. ont été traduits afin d’exploiter cette technologie, avec des résultats plutôt concluants. Le GPGPU semble être une approche relativement puissante et peu coûteuse. Son utilisation reste limitée à certains problèmes mais cela reste une possibilité à ne pas négliger pour de futurs développements d'outils d'analyse à grande échelle.
Que la (Ge)Force soit avec vous !
Remerciements à J. Geinz pour son illustration.
Amine
avril 16, 2012 à 11:46
Beaucoup de coquilles dans l'article, faut de la relecture.
Sinon connaissant, le calcul GPGPU le gain me semble trop beau pour qu'il n'y ait pas une coquille dans la première implémentation. Dans beaucoup de cas, on arrive au mieux à *10. Y a du avoir une correction de l'algo pour arriver à de telles perfs. Je suis un peu dubitatif pour le coup...
Malicia
avril 16, 2012 à 11:50
Salut et merci pour ton commentaire.
Peux-tu indiquer où sont les nombreuses coquilles que tu déplores ? Ce billet, comme tous ceux publiés, sont relus par au moins 3 personnes avant d'être publiés...
Amine
avril 16, 2012 à 12:13
"thoughput” ->"throughput”
"qu’il parfois est " -> "qu’il est parfois "
et y en a encore deux, mais je les retrouve plus 🙂
équilibreuniqueenminéraux
avril 16, 2012 à 12:15
"sera dans certainS cas plus performante" (mais c'est la seule que j'ai trouvée, quant à moi).
Malicia
avril 16, 2012 à 12:43
Merci, corrigées
Mica
avril 17, 2012 à 4:52
Merci pour le commentaire et les corrections.
nahoy
avril 16, 2012 à 12:51
Salut,
pour le gain du calcul GPGPU il est fait mention de 12h de calculs réduits à 2h, ce qui fait un gain de *6.
Amine
avril 17, 2012 à 11:32
ce n'était pas pour les 750 fichiers, les deux heures ? C'est marqué que "les résultats" sont calculés en 2h. J'avais compris que les 750 était faisable en 2h. J'ai mal compris ?
Mica
avril 17, 2012 à 2:22
Les analyses prennent bien 2h par fichier et non pour la totalite des 750 jeux de données.
C'est beaucoup mieux que la version initiale, mais ca reste encore assez long pour analyser la totalité des données (~60 jours).
Au final, nous n'avons pas réalisé ces analyses sur l’intégralité de nos données mais seulement sur sur les sets les plus intéressants.
nahoy
avril 17, 2012 à 3:00
Tu peux néanmoins trouver des implémentations qui vont permettre à ton application de tourner 300x plus vite : (voir ici).
Natir
avril 16, 2012 à 11:55
Article très intéressant, mais je me pose une question, si l'on veut utilise cette méthode il faut réécrire les application, dans le langage de l'API.
Ce qui peut-être long et complexe, surtout quand on doit passée d'un script Perl (par exemple) a du C99 (d’après ce que tu dits), pas de support d'expression régulière (ou pas aussi simple), pas de Bio::Perl. Et étant donnée que le Perl et très utilisée (en tout cas chez moi) comment pourrait ont utilise cette technique sans réécrire tout le script dans un langage plus bas niveaux.
On pourrais réécrire une machine virtuelle Perl qui utilise le GPU, ou crée une lib Perl qui fasse, l'interface avec l'API.
Mais est ce que c'est intéressant, utile, utilisable, en bref est-ce qu'il faut essaye d'utilisée le GPU dans un script Perl qui fait du traitement de donnée parallélisable ?.
Yoann M.
avril 16, 2012 à 1:24
Salut Natir,
Je pense que la réponse à ta question se trouve dans ces quelques lignes (partie Conclusion)
"Les langages de bas niveau utilisés par les kernels en sont sans doute la cause principale. Il est également important de noter que le GPGPU est uniquement efficace pour des taches parallélisables. Une implémentation plus classique sera dans certains cas plus performante. Un état des lieux précis du problème à résoudre est donc indispensable afin d’être sûr qu’une telle implémentation sera bénéfique avant de se lancer dans le développement."
Mais je laisserai également l'auteur de l'article te répondre plus en détail. Il n'est pas sur le même fuseau horaire que nous (Australie) donc sois patient 🙂
Merci pour ton message !
Yoann M.
avril 16, 2012 à 1:30
Après relecture de ton commentaire, je ne sais pas si ça répond bien à ta question en fait...
Peux tu la réposer avec d'autres mots, ou tournée différement ?
Merci d'avance
Natir
avril 16, 2012 à 1:34
Comme on me la demander sur le chan irc je reformule :
En gros est-ce qu'on peut appliquer cette technique rapidement a un script Perl ?
et sinon qu'est ce qu'on pourrais faire pour que sa le soit ? Je propose des éléments de réponse(3 paragraphe) est-ce qu'il sont réaliste ?
Guillaume Collet
avril 16, 2012 à 1:41
Je ne code absolument pas en perl mais avec une petite recherche google, j'ai trouvé ceci :
KappaCUDA - Easy access to NVIDIA CUDA from Perl using the Kappa Library.
Si quelqu'un a testé cette librairie, un retour pourrait être très intéressant.
Natir
avril 16, 2012 à 1:55
Après une petit recherche, merci pour l'idée, j'ai trouve un petit truc
donc un lib pour faire de l'openGL en Perl , et j'ai trouvé dans un lien vers une référence
Ou j'ai lue sa (paragraphe : Perl Outperforms C with OpenGL)
The author has recently published a open source update to CPAN's OpenGL module, adding support for GPGPU features. With this release, he has also posted OpenGL Perl versus C benchmarks--demonstrating cases where Perl outperforms C for OpenGL operations.
Donc si mon anglais et pas trop rouiller on peut faire de GPGPU en perl via un module CPAN, et dans certain cas c'est meilleur que le C(j'ai pas lue le benchmarks).
Donc j'ai ma réponse merci.
nahoy
avril 16, 2012 à 4:40
Attention à ne pas confondre OpenGL et OpenCL.
L'un est prévu pour des calculs graphique, de textures alors que l'autre pourra être utilisé pour n'importe quel calcul parallélisable. Pour en savoir plus sur la différence entre les deux : ici.
nahoy
avril 16, 2012 à 1:56
Je ne suis pas expert, mais je ne pense pas que tu puisses trouver des binding sur le CPAN, mais en cherchant un peu, il existe quelques implémentation pour CUDA et OpenCL (ici par example).
Il faut aussi savoir ce que tu entends par "rapidement", 2 jours/semaines/mois, est ce que tu vas vraiment gagner du temps sur ton analyse, si tu passes un peu de temps à apprendre le C où à chercher les bindings en perl...
Natir
avril 16, 2012 à 2:20
Exemple pour rapidement, y dit qu'il a mit une semaine pour faire sont apli puis 3 semaine pour l'adapté, pour moi c'est 3 fois trop. Je dits pas que l'auteur est mauvais (je ne le connais pas je ne me permettrais pas de le dire comme sa). Pour moi rapidement c'est tu mets 1 semaine pour coder l'apli en classique, tu mets une semaine pour la recoder l'apli pour utilise le GPGPU. Alors évidement tu dois avoir un temps d'adaptation et tu dois repenser un peu ton apli mais si tu a l'habitude sa devrais te prendre plus de temps que la coder de puis rien.
Mica
avril 17, 2012 à 6:14
A ma connaissance il n'existe pas de moyen direct pour passer d'un script perl a une implementation en OpenCL.
Dans cet exemple, la transition a ete plus longue que le developement initial car l'appli a completement reecrite C/OpenCL. J'etais loin d'etre un expert en C et encore moins en OpenCL que je decouvrais tout juste => d'ou une productivite limitee 😉
La premiere version, bien que plus lente, fonctionnant correctement, permettait de lancer des analyses dans l'attente d'une release plus efficace. Une personne habituée a coder en C/C++ aura moins de difficultes a passer a une implementation en OpenCL.
Il existe des bindings pour d'autres langages de plus haut niveau. J'ai teste celui-ci : http://wiki.tiker.net/PyOpenCL qui permet d'executer un kernel directement a partir d'un script python. Le kernel doit lui, toujours etre ecrit en OpenCL.
J'ai egalement entendu parle de CLyther (http://gpgpu.org/2010/03/09/clyther-python-opencl) qui permettrait d’écrire des kernels avec une syntaxe proche du python. Apparemment le projet est encore en développement, mais je pense que d'autres implémentations de ce genre vont rapidement voir le jour.
Arnaud
juin 20, 2012 à 6:07
Salut,
intéressant comme article, et plus encore les commentaires des non-informaticiens (tous biologistes je suppose). Le problème du temps de conversion du C/C++ vers l'openCL, c'est qu'il faut mettre en place une structure assez intelligente pour paralléliser les traitements sans que des valeurs intermédiaires soient corrompus. On ne gagne pas un facteur 10X de temps de traitement en faisant une bête traduction de code, c'est un nouvel algorithme à faire. Et c'est du costaud puisqu'après, on peut avoir un gain presque linéaire en fonction de la puissance du processeur graphique et du nombre présent dans l'ordinateur (cf Fastra de Anvers).
Cordialement
Augure
novembre 17, 2015 à 10:17
j'avais loupé cet article ! 😀
j'espère que depuis de nombreux algorithme ont été codé en OpenCL... car pour moi, si le titre est bien accrocheur... il loupe surtout un des plus gros avantage du GPGPU... l'optimisation !
au lieu de payer (ou plutôt de monopoliser) un Bi-Xéon@64cores (à 10 000€ -.-' ) un bête A10-7850K à 500€ ferait le job !
et surtout avec une bonne économie de watt... qui au niveau mondial ferait du bien !!!
(même si cela chauffe le labo... 😀 )
d'ailleurs au vu des premiers résultats sur "portable" (donc GPU bloqué à 35W de "puissance") pourquoi ne pas avoir investi un peu dans une mini-tour ?
sinon, à quand un nouvelle article sur une nouvelle grosse évolution du GPGPU : le HSA.
qui doit aider les programmes de ce genre à utiliser en parallèle les CPU (dont le gros avantage est d'être Out Of Order) et les GPU avec un partage de mémoire.
malheureusement, comme dit en conclusion, c'est un langage très spécifique et BCP de logiciels gagneraient à être recoder... mais se serait un boulot sans fin avec des personnes plus spécialiser ! :/