GPGPU, le "supercalculateur" du pauvre

En bio­in­for­ma­tique, nous sommes sou­vent ame­nés à tra­vailler avec des don­nées à grande échelle. Il suf­fit de voir le nombre de publi­ca­tions incluant les termes “large-scale”, “exten­sive” ou encore “high-through­put” pour s’en rendre compte. Dans la majo­ri­té des cas, on est satis­fait du déve­lop­pe­ment d’un outil quand celui-ci fait son job cor­rec­te­ment en se sou­ciant assez peu de son opti­mi­sa­tion. Il est donc assez cou­rant de lan­cer des tâches de plu­sieurs heures sur des giga-octets de don­nées pour réa­li­ser des ana­lyses. Cela ne veut pas dire que bio­in­for­ma­ti­cien rime avec bour­rin (enfin si, la, en l’occurrence, ça rime…), mais les quan­ti­tés de don­nées à trai­ter sont telles qu’il est par­fois dif­fi­cile de faire autre­ment.

Dans cet article, je vais ten­ter de pré­sen­ter un exemple concret d’utilisation de la tech­no­lo­gie GPGPU (Gene­ral-Purpose com­pu­ta­tion on Graphic Proces­sing Units) qui n’est, d’après moi, pas encore assez exploi­tée dans notre domaine.

Il n'est pas tou­jours pos­sible d'avoir accès à un super­cal­cu­la­teur pour lan­cer ses ana­lyses, la tech­no­lo­gie GPGPU est une alter­na­tive peu coû­teuse et par­fai­te­ment adap­tée pour le trai­te­ment des tâches mas­si­ve­ment paral­lèles. Les pro­ces­seurs gra­phiques actuels ont une capa­ci­té de cal­cul sou­vent sous-esti­mée, il serait dom­mage de les exploi­ter uni­que­ment pour les cal­culs de pixels de vos jeux vidéos !

Architecture matérielle

Les pro­ces­seurs clas­siques (Cen­tral Pro­ces­sing Unit ou CPU) sont très effi­caces pour exé­cu­ter rapi­de­ment des tâches séquen­tielles. En rai­son de son archi­tec­ture dif­fé­rente, un GPU, lui, ne sera pas aus­si per­for­mant pour ce type de taches, par contre, il convient très bien au trai­te­ment d’algorithmes « paral­lé­li­sables ». Ce qui rend cette tech­no­lo­gie très inté­res­sante pour notre domaine .

Le sché­ma sui­vant aide à com­prendre un peu mieux cette capa­ci­té de paral­lé­li­sa­tion du GPU :

Archi­tec­ture CPU vs GPU. Cré­dit : J. Geinz. (licence CC-by-SA 2.0)

Les ALU ("Arith­me­tic Logic Unit" ou Uni­té arith­mé­tique et logique) sont les com­po­sants char­gés des cal­culs : on com­prend mieux, d'après cette image, pour­quoi les GPU sont puis­sants pour la paral­lé­li­sa­tion. En effet, c'est sur ces par­ties maté­rielles que la majo­ri­té des opé­ra­tions de cal­culs sont réa­li­sées et les pro­ces­seurs gra­phiques en ont un très grand nombre en com­pa­rai­son aux pro­ces­seurs clas­siques.

Architecture logicielle

Il existe dif­fé­rentes API de bas niveau per­met­tant d’exploiter l’architecture de nos GPU, les plus popu­laires étant CUDA et Open­CL (Open Com­pu­ting Lan­guage). CUDA a été spé­cia­le­ment déve­lop­pé pour les GPU NVi­dia, en consé­quence le code a été opti­mi­sé pour ce maté­riel et per­met­trait donc des implé­men­ta­tions plus per­for­mantes. Open­CL est un stan­dard ouvert, l'avantage majeur de cette API est sa por­ta­bi­li­té. En effet, une appli­ca­tion déve­lop­pée en Open­CL pour­ra être uti­li­sée sur tout type de plate-formes et sys­tèmes d'exploitation.

Je ne vais pas m’étendre sur les avan­tages et incon­vé­nients de ces deux implé­men­ta­tions. Actuel­le­ment, il semble que l’adoption du stan­dard Open­CL soit en pleine crois­sance et c’est l’API que j’ai choi­si d’utiliser dans mes déve­lop­pe­ments. Dans les deux cas, la struc­ture des appli­ca­tions reste rela­ti­ve­ment simi­laire et le code se décom­pose prin­ci­pa­le­ment en deux par­ties :

  • host code”: est exé­cu­té sur le pro­ces­seur. Cette par­tie de l’application est uti­li­sée pour toutes les tâches non-paral­lé­li­sées (lec­ture des don­nées, inter­ac­tion avec l’utilisateur, etc.). L’hôte est com­mu­né­ment écrit en C mais dif­fé­rents lan­gages de pro­gram­ma­tion peuvent être uti­li­sés grâce à une mul­ti­tude de bin­dings (Python, Java, C, C++, Ruby, etc.).
  • ker­nel” : ce code inter­agit direc­te­ment au niveau  du GPU. En consé­quence, l’API est rela­ti­ve­ment bas niveau (syn­taxe proche du C99) et donc pas spé­cia­le­ment accueillant au pre­mier abord. Le ker­nel contient donc toutes les opé­ra­tions arith­mé­tiques paral­lé­li­sables de votre pro­gramme. Pour sim­pli­fier, c’est un peu le type de code que l’on uti­li­se­rait dans le corps d’une boucle.

Il existe de nom­breux docu­ments au sujet de cette API qui four­nissent de très bons exemples d’implémentations et expli­que­ront tout cela bien mieux que moi. Je vous invite à consul­ter l'API offi­cielle pour plus de détails. Je ten­te­rai de pré­sen­ter dif­fé­rents exemples d'implémentations dans un futur billet.

Exemple de problème "parallélisable"

Pour en reve­nir à nos mou­tons, j’ai été récem­ment ame­né à déve­lop­per un outil per­met­tant l’analyse de liai­son géné­tique (gene­tic lin­kage en anglais) à grande échelle.

Pour sim­pli­fier, il s’agit d’analyser com­ment cer­tains gènes sont trans­mis à la des­cen­dance. Par exemple, deux gènes étant sys­té­ma­ti­que­ment trans­mis (ensemble) chez des per­sonnes ayant un phé­no­type par­ti­cu­lier (mala­die géné­tique par exemple) joue­ront poten­tiel­le­ment un rôle dans le déve­lop­pe­ment de ce phé­no­type. En gros, c’est une manière d’identifier de nou­veaux gènes pou­vant être impli­qués dans le déve­lop­pe­ment d’un trait phé­no­ty­pique par­ti­cu­lier.

Je reçois donc un pre­mier jeu de don­nées incluant :

  • l’expression rela­tive de 250 000 gènes ;
  • 150 000 SNP ;
  • le tout pour un groupe de 2500 patients atteints d’une mala­die géné­tique par­ti­cu­lière.

Sans ren­trer dans les détails de l’algorithme, il s’agit de tes­ter les 250 000 gènes contre les 150 000 SNP.

La pre­mière approche évi­dente est donc :

 

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.



Pour continuer la lecture :


Commentaires

22 réponses à “GPGPU, le "supercalculateur" du pauvre”

  1. Beau­coup de coquilles dans l'article, faut de la relec­ture.
    Sinon connais­sant, le cal­cul GPGPU le gain me semble trop beau pour qu'il n'y ait pas une coquille dans la pre­mière implé­men­ta­tion. Dans beau­coup de cas, on arrive au mieux à *10. Y a du avoir une cor­rec­tion de l'algo pour arri­ver à de telles perfs. Je suis un peu dubi­ta­tif pour le coup…

    1. Salut et mer­ci pour ton com­men­taire.

      Peux-tu indi­quer où sont les nom­breuses coquilles que tu déplores ? Ce billet, comme tous ceux publiés, sont relus par au moins 3 per­sonnes avant d'être publiés…

      1. "though­put” ->"through­put”
        "qu’il par­fois est " -> "qu’il est par­fois "
        et y en a encore deux, mais je les retrouve plus 🙂

      2. Avatar de équilibreuniqueenminéraux
        équilibreuniqueenminéraux

        "sera dans cer­tainS cas plus per­for­mante" (mais c'est la seule que j'ai trou­vée, quant à moi).

        1. Mer­ci, cor­ri­gées

          1. Mer­ci pour le com­men­taire et les cor­rec­tions.

    2. Salut,
      pour le gain du cal­cul GPGPU il est fait men­tion de 12h de cal­culs réduits à 2h, ce qui fait un gain de *6.

      1. ce n'était pas pour les 750 fichiers, les deux heures ? C'est mar­qué que "les résul­tats" sont cal­cu­lés en 2h. J'avais com­pris que les 750 était fai­sable en 2h. J'ai mal com­pris ?

        1. Les ana­lyses prennent bien 2h par fichier et non pour la tota­lite des 750 jeux de don­nées.
          C'est beau­coup mieux que la ver­sion ini­tiale, mais ca reste encore assez long pour ana­ly­ser la tota­li­té des don­nées (~60 jours).
          Au final, nous n'avons pas réa­li­sé ces ana­lyses sur l’intégralité de nos don­nées mais seule­ment sur sur les sets les plus inté­res­sants.

        2. Tu peux néan­moins trou­ver des implé­men­ta­tions qui vont per­mettre à ton appli­ca­tion de tour­ner 300x plus vite : (voir ici).

  2. Article très inté­res­sant, mais je me pose une ques­tion, si l'on veut uti­lise cette méthode il faut réécrire les appli­ca­tion, dans le lan­gage de l'API.
    Ce qui peut-être long et com­plexe, sur­tout quand on doit pas­sée d'un script Perl (par exemple) a du C99 (d’après ce que tu dits), pas de sup­port d'expression régu­lière (ou pas aus­si simple), pas de Bio::Perl. Et étant don­née que le Perl et très uti­li­sée (en tout cas chez moi) com­ment pour­rait ont uti­lise cette tech­nique sans réécrire tout le script dans un lan­gage plus bas niveaux.

    On pour­rais réécrire une machine vir­tuelle Perl qui uti­lise le GPU, ou crée une lib Perl qui fasse, l'interface avec l'API.

    Mais est ce que c'est inté­res­sant, utile, uti­li­sable, en bref est-ce qu'il faut essaye d'utilisée le GPU dans un script Perl qui fait du trai­te­ment de don­née paral­lé­li­sable ?.

    1. Avatar de Yoann M.
      Yoann M.

      Salut Natir,

      Je pense que la réponse à ta ques­tion se trouve dans ces quelques lignes (par­tie Conclu­sion)

      "Les lan­gages de bas niveau uti­li­sés par les ker­nels en sont sans doute la cause prin­ci­pale. Il est éga­le­ment impor­tant de noter que le GPGPU est uni­que­ment effi­cace pour des taches paral­lé­li­sables. Une implé­men­ta­tion plus clas­sique sera dans cer­tains cas plus per­for­mante. Un état des lieux pré­cis du pro­blème à résoudre est donc indis­pen­sable afin d’être sûr qu’une telle implé­men­ta­tion sera béné­fique avant de se lan­cer dans le déve­lop­pe­ment."

      Mais je lais­se­rai éga­le­ment l'auteur de l'article te répondre plus en détail. Il n'est pas sur le même fuseau horaire que nous (Aus­tra­lie) donc sois patient 🙂

      Mer­ci pour ton mes­sage !

    2. Avatar de Yoann M.
      Yoann M.

      Après relec­ture de ton com­men­taire, je ne sais pas si ça répond bien à ta ques­tion en fait…
      Peux tu la répo­ser avec d'autres mots, ou tour­née dif­fé­re­ment ?
      Mer­ci d'avance

    3. Comme on me la deman­der sur le chan irc je refor­mule :

      En gros est-ce qu'on peut appli­quer cette tech­nique rapi­de­ment a un script Perl ?
      et sinon qu'est ce qu'on pour­rais faire pour que sa le soit ? Je pro­pose des élé­ments de réponse(3 para­graphe) est-ce qu'il sont réa­liste ?

      1. Avatar de Guillaume Collet
        Guillaume Collet

        Je ne code abso­lu­ment pas en perl mais avec une petite recherche google, j'ai trou­vé ceci :

        Kap­pa­CU­DA — Easy access to NVIDIA CUDA from Perl using the Kap­pa Libra­ry.

        Si quelqu'un a tes­té cette librai­rie, un retour pour­rait être très inté­res­sant.

        1. Après une petit recherche, mer­ci pour l'idée, j'ai trouve un petit truc
          donc un lib pour faire de l'openGL en Perl , et j'ai trou­vé dans un lien vers une réfé­rence
          Ou j'ai lue sa (para­graphe : Perl Out­per­forms C with Open­GL)
          The author has recent­ly publi­shed a open source update to CPAN's Open­GL module, adding sup­port for GPGPU fea­tures. With this release, he has also pos­ted Open­GL Perl ver­sus C benchmarks–demonstrating cases where Perl out­per­forms C for Open­GL ope­ra­tions.

          Donc si mon anglais et pas trop rouiller on peut faire de GPGPU en perl via un module CPAN, et dans cer­tain cas c'est meilleur que le C(j'ai pas lue le bench­marks).

          Donc j'ai ma réponse mer­ci.

          1. Atten­tion à ne pas confondre Open­GL et Open­CL.
            L'un est pré­vu pour des cal­culs gra­phique, de tex­tures alors que l'autre pour­ra être uti­li­sé pour n'importe quel cal­cul paral­lé­li­sable. Pour en savoir plus sur la dif­fé­rence entre les deux : ici.

      2. Je ne suis pas expert, mais je ne pense pas que tu puisses trou­ver des bin­ding sur le CPAN, mais en cher­chant un peu, il existe quelques implé­men­ta­tion pour CUDA et Open­CL (ici par example).
        Il faut aus­si savoir ce que tu entends par "rapi­de­ment", 2 jours/​semaines/​mois, est ce que tu vas vrai­ment gagner du temps sur ton ana­lyse, si tu passes un peu de temps à apprendre le C où à cher­cher les bin­dings en perl…

        1. Exemple pour rapi­de­ment, 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 mau­vais (je ne le connais pas je ne me per­met­trais pas de le dire comme sa). Pour moi rapi­de­ment c'est tu mets 1 semaine pour coder l'apli en clas­sique, tu mets une semaine pour la reco­der l'apli pour uti­lise le GPGPU. Alors évi­de­ment tu dois avoir un temps d'adaptation et tu dois repen­ser un peu ton apli mais si tu a l'habitude sa devrais te prendre plus de temps que la coder de puis rien.

          1. A ma connais­sance il n'existe pas de moyen direct pour pas­ser d'un script perl a une imple­men­ta­tion en Open­CL.
            Dans cet exemple, la tran­si­tion a ete plus longue que le deve­lo­pe­ment ini­tial car l'appli a com­ple­te­ment ree­crite C/​OpenCL. J'etais loin d'etre un expert en C et encore moins en Open­CL que je decou­vrais tout juste => d'ou une pro­duc­ti­vite limi­tee 😉
            La pre­miere ver­sion, bien que plus lente, fonc­tion­nant cor­rec­te­ment, per­met­tait de lan­cer des ana­lyses dans l'attente d'une release plus effi­cace. Une per­sonne habi­tuée a coder en C/​C++ aura moins de dif­fi­cultes a pas­ser a une imple­men­ta­tion en Open­CL.

            Il existe des bin­dings pour d'autres lan­gages de plus haut niveau. J'ai teste celui-ci : http://​wiki​.tiker​.net/​P​y​O​p​e​nCL qui per­met d'executer un ker­nel direc­te­ment a par­tir d'un script python. Le ker­nel doit lui, tou­jours etre ecrit en Open­CL.
            J'ai ega­le­ment enten­du parle de CLy­ther (http://​gpg​pu​.org/​2​0​1​0​/​0​3​/​0​9​/​c​l​y​t​h​e​r​-​p​y​t​h​o​n​-​o​p​e​ncl) qui per­met­trait d’écrire des ker­nels avec une syn­taxe proche du python. Appa­rem­ment le pro­jet est encore en déve­lop­pe­ment, mais je pense que d'autres implé­men­ta­tions de ce genre vont rapi­de­ment voir le jour.

  3. Avatar de Arnaud

    Salut,

    inté­res­sant comme article, et plus encore les com­men­taires des non-infor­ma­ti­ciens (tous bio­lo­gistes je sup­pose). Le pro­blème du temps de conver­sion du C/​C++ vers l'openCL, c'est qu'il faut mettre en place une struc­ture assez intel­li­gente pour paral­lé­li­ser les trai­te­ments sans que des valeurs inter­mé­diaires soient cor­rom­pus. On ne gagne pas un fac­teur 10X de temps de trai­te­ment en fai­sant une bête tra­duc­tion de code, c'est un nou­vel algo­rithme à faire. Et c'est du cos­taud puisqu'après, on peut avoir un gain presque linéaire en fonc­tion de la puis­sance du pro­ces­seur gra­phique et du nombre pré­sent dans l'ordinateur (cf Fas­tra de Anvers).

    Cor­dia­le­ment

  4. j'avais lou­pé cet article ! 😀

    j'espère que depuis de nom­breux algo­rithme ont été codé en Open­CL… car pour moi, si le titre est bien accro­cheur… il loupe sur­tout un des plus gros avan­tage du GPGPU… l'optimisation !

    au lieu de payer (ou plu­tôt de mono­po­li­ser) un Bi-Xéon@64cores (à 10 000€ -.-' ) un bête A10-7850K à 500€ ferait le job !
    et sur­tout avec une bonne éco­no­mie de watt… qui au niveau mon­dial ferait du bien !!!
    (même si cela chauffe le labo… 😀 )

    d'ailleurs au vu des pre­miers résul­tats sur "por­table" (donc GPU blo­qué à 35W de "puis­sance") pour­quoi ne pas avoir inves­ti un peu dans une mini-tour ?

    sinon, à quand un nou­velle article sur une nou­velle grosse évo­lu­tion du GPGPU : le HSA.
    qui doit aider les pro­grammes de ce genre à uti­li­ser en paral­lèle les CPU (dont le gros avan­tage est d'être Out Of Order) et les GPU avec un par­tage de mémoire.

    mal­heu­reu­se­ment, comme dit en conclu­sion, c'est un lan­gage très spé­ci­fique et BCP de logi­ciels gagne­raient à être reco­der… mais se serait un bou­lot sans fin avec des per­sonnes plus spé­cia­li­ser ! :/​

Laisser un commentaire