Le co-inventeur du XML plaide pour la programmation concurrente et fonctionnelle

Version imprimable

26/07/2010, 18h24
Idelways

Le co-inventeur du XML plaide pour la programmation concurrente et fonctionnelle

L'inventeur du XML plaide pour la programmation concurrente et fonctionnelle
Elle serait mieux adaptée aux progrès liés aux CPU multi-coeurs

Lors d'une présentation à l'O'Reilly Open Source Convention 2010, Tim Bray, le co-inventeur du XML, a fortement plaidé pour la programmation concurrente et fonctionnelle.

Au lieu d'utiliser des threads, la programmation fonctionnelle présenterait, d'après lui, une meilleure approche pour les développeurs qui doivent réaliser des programmes pour les processeurs multi-coeurs

La programmation pour les CPU multi-coeurs amène en effet son lot de problèmes, au premier rang desquels la simultanéité. Ces nouveaux problèmes (dont les goulets d'étranglement), seraient des « problèmes très difficiles à appréhender ou à comprendre », a-t-il souligné.

La programmation fonctionnelle, paradigme des langages comme Erlang et Clojure, permettrait de mieux les solutionner, et donc de mieux gérer cette simultanéité.

La programmation fonctionnelle repose sur le principe que les données ne sont pas partagées. Conséquence, les développeurs n'ont pas à se soucier de savoir si elles changeront, ce qui « permet de désigner les données au lieu de les envoyer », souligne Bray.

Erlang (conçu pour la programmation massive des Switch téléphoniques avec des centaines voire des milliers de processeurs) est par exemple un langage qui n'a ni classes, ni objets, ni variables. Sa gestion des fichiers est « misérable ». Mais il resterait particulièrement approprié et puissant pour gérer le multi-coeur.

Idem pour Clojure, « un langage de très, très hautes performance » pour Bray. Clojure est un Lisp qui fonctionne sur la machine virtuelle Java et qui compile en code Java classique. Ses performances en terme de vitesse sont remarquables.

La thèse de la démonstration de Bray est de dire que gérer la simultanéité avec le threading n'est pas une mauvaise idée en soi. Mais cette programmation avec les threads (qui offre de multiples accès à partager, des données mutables, etc) est mal, voire pas du tout comprise.

Pire, elle « ne sera jamais comprise par les développeurs d'applications », provoque-t-il.

Faudrait-il donc tout revoir à zéro pour accompagner l'évolution du hardware ?

C'est un peu ce que pense Bill Dally, un des ingénieurs les plus importants de Nvidia, mais dans un registre différent lorsqu'il écrit dans Forbes « après 40 ans de programmation linéaire [il faudrait] une rupture avec les pratiques de longue date ».

Et de regretter le manque de formation des développeurs dans la programmation parallèle et les technologies propres aux multi-coeurs.

Deux visions pour un même constat : le multi-coeurs n'a pas fini d'être un défi pour les développeurs.

Source : Site de l'O'Reilly Open Source Convention 2010

Lire aussi :

:fleche: Quel langage pour la JVM est pour vous promis à un bel avenir ?

:fleche: Qu'est-ce qu'un langage fonctionnel

Les rubriques (actu, forums, tutos) de Développez :

:fleche: Hardware
:fleche: Langages

Et vous ?

:fleche: Pratiquez-vous de la programmation concurrente ou fonctionnelle ?

:fleche: Dans l'ère du multicoeurs, pensez-vous comme Bray que les paradigmes de programmation fonctionnelle et concurrente soit plus adaptés ?

En collaboration avec Gordon Fowler
26/07/2010, 19h06
Invité

Threads are evil : Avoid them (R.Hipp)

Programmation parrallèle selon Intel : http://software.intel.com/en-us/parallel/
Pour ceux qui ont du temps devant eux !
Threads are evil : Avoid them ! (D. Richard Hipp sqLite)
The problem with threads (Edward A. Lee Berkeley) :
http://www.eecs.berkeley.edu/Pubs/Te...ECS-2006-1.pdf

Sinon, les telecoms se prêtent très bien au multithread contrairement au reste.
La règle "Un thread = un device (telecom, GPU, sound, ...)" fonctionne pas trop mal.
En traitement de raw input : division du raw par le nombre de core : marche parfois aussi (sauf si agregation) (zip, flat, trt de signal)
SGBD : monothread obligatoire (voir titre).
Le reste est un casse tête à moins de faire "dormir" les threads pour.. imiter le monothread par synchronisation... J'espere que les core48 supporteront le turbo-boost.

Citation:

C'est un peu ce que pense Bill Dally, un des ingénieurs les plus importants de Nvidia, mais dans un registre différent lorsqu'il écrit dans Forbes « après 40 ans de programmation linéaire [il faudrait] une rupture avec les pratiques de longue date ».

D'accord avec ce qu'il dit, c'est même exactement ce que je dis aussi, sauf que ça ne dit pas qu'on pourra faire en parrallèle ce qu'on fait en séquentiel et personnellement j'en doute. Comme tout le monde l'exige, je ne demande qu'à apprendre mais parfois.. l'info n'est pas là !
Et la solution non plus..

Multicore et multi servers sont des disciplines très voisines pour le traitement. J'ai fait un peu des deux mais peut-être qu'un grand maître du multi-server pourrait donner quelques trucs et astuces....
27/07/2010, 00h29
pseudocode

Citation:

Envoyé par Idelways

:fleche: Dans l'ère du multicoeurs, pensez-vous comme Bray que les paradigmes de programmation fonctionnelle et concurrente soit plus adaptés ?

Oui. Mais ce n'est pas pour autant qu'il faut vouloir enterrer la programmation impérative. Remplacer les programmes 100% impératif par des programmes 100% fonctionnel c'est un peu extrème comme approche.

Je préfèrerai que les langages impératif traditionnels évoluent pour intégrer proprement les paradigmes fonctionnels/concurrents. On n'a pas tout le temps besoin de penser en multicoeurs. ;)
27/07/2010, 07h42
oxyde356

Ca commence à être un peu fatiguant tous ces spécialistes qui veulent prendre les développeurs par la main et les pousser vers des solutions plus simples mais jamais plus performantes contrairement à ce qui est dit, bien au contraire. Je trouve que cette politique est responsable de l'abaissement du niveau des développeurs comme l'a été le mouvement massif vers Java ... si on continue comme ça on ne va faire plus que des scripts :roll:
27/07/2010, 08h38
zul

Pour intégrer proprement le fonctionnel, il faut commencer par intégrer le concept de fonction pure (ou transparence référentielle ou autre terme à la mode) qui est en soit assez contradictoire avec impératif.

Je ne vois pas bien où est la simplification. Il dit juste que d'utiliser des paradigmes différents que le sacro-saint objet-impératif pourrait s'avérer judicieux pour gérer les problématiques "multi-//". À mon avis, ça ne se fera justement pas rapidement, parce que c'est compliqué : ce n'est pas juste voir de syntaxe comme entre Java / C# / autre clone objet, mais profondément repensé les paradigmes à utiliser / les architectures qui vont avec.

Erlang en soit n'est pas extrêmement performant sur un seul score, mais il passe bien à l'échelle sur n-core / n-machines (sans compter la gestion des nodes qui tombent etc ...).
27/07/2010, 08h39
Julien Bodin

Citation:

Envoyé par oxyde356

Je trouve que cette politique est responsable de l'abaissement du niveau des développeurs comme l'a été le mouvement massif vers Java ... si on continue comme ça on ne va faire plus que des scripts :roll:

C'est quoi ce vieux troll ? :aie:
27/07/2010, 08h42
oxyde356

Citation:

Envoyé par julien.1486

C'est quoi ce vieux troll ? :aie:

Je n'avais aucunement l'intention de pourrir Java, je l'ai pris au hasard :pastaper:
27/07/2010, 10h28
amaury pouly

Citation:

Envoyé par unBonGars

Programmation parralèle selon Intel : http://software.intel.com/en-us/parallel/
Pour ceux qui ont du temps devant eux !
Threads are evil : Avoid them ! (D. Richard Hipp sqLite)
The problem with threads (Edward A. Lee Berkeley) :
http://www.eecs.berkeley.edu/Pubs/Te...ECS-2006-1.pdf

Sinon, les telecoms se prètent très bien au multithread contrairement au reste.
La règle "Un thread = un device (telecom, GPU, sound, ...)" fonctionne pas trop mal.
En traitement de raw input : division du raw par le nombre de core : marche parfois aussi (sauf si agregation) (zip, flat, trt de signal)
SGBD : monothread obligatoire (voir titre).
Le reste est un casse tête à moins de faire "dormir" les threads pour.. imiter le monothread par synchronisation... J'espere que les core48 supporteront le turbo-boost.

D'accord avec ce qu'il dit, c'est même exactement ce que je dis aussi, sauf que ça ne dit pas qu'on pourra faire en parrallèle ce qu'on fait en séquentiel et personnellement j'en doute. Comme tout le monde l'exige, je ne demande qu'à apprendre mais parfois.. l'info n'est pas là !
Et la solution non plus..

Multicore et multi servers sont des disciplines très voisines pour le traitement. J'ai fait un peu des deux mais peut-être qu'un grand maître du multi-server pourrait donner quelques trucs et astuces....

Je dois voir le mal partout mais en quoi cet article est-il pertinent ? En gros il dit "les threads c'est mal" parce que c'est non-déterministe. Il dit aussi que le non-déterminisme c'est mal. Or certaines tâches sont non-déterministes. Si le code a une partie GUI et une partie calcul, une intervention de l'utilisateur est une action non-déterministe.

Je pense qu'on peut tourner le problème comme on veut, faire du message passing, faire des diagrammes et tout ce qu'on veut mais le problème fondamental c'est de faire plusieurs choses à la fois et cela nécessitera toujours de la synchronisation et donc il y aura un risque de bug.

On parle aussi beaucoup de la programmation fonctionnelle pour le calcul en parallèle et c'est vrai que c'est tentant étant donné que toutes les structures de données sont en lecture seulement. Toutefois, cela cache aussi ses propres problèmes. Par exemple, en fonctionnelle, tout est en lecture mais comme on écrit ? En créant des objets ! Or créer des objets demande de la mémoire qu'il faut allouer et libérer. Donc le problème n'a pas disparu.
Par ailleurs, on peut aussi perdre en performance puisque l'idée de la plupart des structures de données fonctionnelle c'est qu'on a l'intégralité de l'historique des modifications. En pratique cela veut dire que si on une structure A et qu'on veut la modifier pour obtenir B alors on représente B par représente A + modification. Autrement dit on se retrouve avec un empilement de modifications qui si elles ne sont pas bien faites seront moins performantes.
Bref, ce que je veux dire c'est que le fonctionnel d'accord mais en réalisant que ce n'est pas gratuit et que les problèmes sont encore là mais sous d'autres formes.
27/07/2010, 10h44
S(ô.Ô)B

Pour avoir déjà fait de l'Erlang, je suis tout à fait d'accord avec amaury pouly, lorsqu'on programme en fonctionnel pur comme Erlang d'autres problèmes apparaissent, et souvent pas des moindres. Mais ce langage est vraiment intéressant et j'invite tout le monde à y jeter un coup d'œil ne serait-ce que pour sa gestion de la modification du code à chaud, ou du parallélisme sur plusieurs machines déconcertant de facilité à mettre en place.

Après par rapport à l'intervention de Tim Bray, qui dit en gros que les threads c'est le mal car les données sont partagées, et ben avec un peu de discipline et de rigueur de programmation on peut très bien travailler qu'avec des données propres à chaque thread...
27/07/2010, 11h12
Invité

Citation:

Envoyé par amaury pouly

Je dois voir le mal partout mais en quoi cet article est-il pertinent ? En gros il dit "les threads c'est mal" parce que c'est non-déterministe. Il dit aussi que le non-déterminisme c'est mal. Or certaines tâches sont non-déterministes. Si le code a une partie GUI et une partie calcul, une intervention de l'utilisateur est une action non-déterministe.

Je pense qu'on peut tourner le problème comme on veut, faire du message passing, faire des diagrammes et tout ce qu'on veut mais le problème fondamental c'est de faire plusieurs choses à la fois et cela nécessitera toujours de la synchronisation et donc il y aura un risque de bug.

On parle aussi beaucoup de la programmation fonctionnelle pour le calcul en parallèle et c'est vrai que c'est tentant étant donné que toutes les structures de données sont en lecture seulement. Toutefois, cela cache aussi ses propres problèmes. Par exemple, en fonctionnelle, tout est en lecture mais comme on écrit ? En créant des objets ! Or créer des objets demande de la mémoire qu'il faut allouer et libérer. Donc le problème n'a pas disparu.
Par ailleurs, on peut aussi perdre en performance puisque l'idée de la plupart des structures de données fonctionnelle c'est qu'on a l'intégralité de l'historique des modifications. En pratique cela veut dire que si on une structure A et qu'on veut la modifier pour obtenir B alors on représente B par représente A + modification. Autrement dit on se retrouve avec un empilement de modifications qui si elles ne sont pas bien faites seront moins performantes.
Bref, ce que je veux dire c'est que le fonctionnel d'accord mais en réalisant que ce n'est pas gratuit et que les problèmes sont encore là mais sous d'autres formes.

Parlez vous de l'article développez ?
De la blague de R.Hipp ? j'aime bien ce gars car il a eu du succès , n'appartient à aucune grosse compagnie et a une vision très scandinave du monde, donc il parle comme ça lui vient et dit bien haut ce que tout le monde murmure ...

Les questions de thread ne datent pas du premier multicore , cela existe depuis Unix. Or s'il est vrai que des virtuoses ont posé les jalons d'un certain multithreading , il s'agit le plus souvent de software réseau-telecom. Cela concerne un petit nombre de développeurs. Un exemple parlant est l'usage que FTP fait des caractères jokers.

Pour le reste, dans le meilleur des cas , on a des synchros encombrantes en code comme en cpu. Dans les cas plus tordus, on modifie la structure du programme pour gérer des evènements soit existants dans le framework soit réécrit à la main (boucles infinies ...) C'est de cette manière qu'on peut quand même faire de la BDD asynchrone (multithread donc) même si M Hipp ne nous le conseille pas. En effet, il ne suffit pas d'orchestrer une messagerie interne : on a aussi des problèmes d'accès concurrent qu'on gère en interne avec des delegates mais ça ne suffit pas non plus et notamment dans le cas de R.Hipp et son sqlite qui n'est pas très multi-users mais c'est juste un cas parmi d'autres.

Donc le deal est : désormais le multithread n'est plus une amélioration des techniques existantes mais une nécessité rendue obligatoire par l'industrie des processeurs qui n'arrive plus à monter en fréquence (je résume beaucoup)

Avant que nos élites nous demandent de tout refaire en multithread , je crois urgent de dire que le multithread n'est pas une bonne solution sauf pour les telecom+++ et dans une moindre mesure quelques problèmes pas trop itératifs(GPU?..). Mais que pour un très grand nombre de cas, ils n'apportent absolument rien , si ce n'est un paquet d'ennuis avec du software qui marchait très bien en monothread..

Plus proche de l'utilisateur on peut designer du fonctionnel astucieux et très spécifique pour lui rendre la vie plus agréable, mais pour conclure je dirais surtout :

Le software ne peut pas gagner avec le multithread autant que le hardware actuellement. Un processeur à 48 coeurs ne sera jamais 48x plus rapide mais il pourra faire le travail de 48 machines auparavant .. Peut-être avez vous des idées de formulation plus diplomatique (je suis preneur)
27/07/2010, 11h22
pseudocode

Citation:

Envoyé par unBonGars

Plus proche de l'utilisateur on peut designer du fonctionnel astucieux et très spécifique pour lui rendre la vie plus agréable, mais pour conclure je dirais surtout :

Le software ne peut pas gagner avec le multithread autant que le hardware actuellement. Un processeur à 48 coeurs ne sera jamais 48x plus rapide mais il pourra faire le travail de 48 machines auparavant .. Peut être avez vous des idées de formulation plus diplomatique (je suis preneur)

Je pense que l'idée de l'article c'est de dire que les langages impératifs obligent le développeur à concevoir son application en Mono-thread ou en Multi-thread. Mais une fois que ce choix est fait, il est immuable (sauf a réécrire l'application).

Les paradigmes fonctionnels/concurrentiels sont là pour ne pas solutionner ces problèmes par la conception, et donc repousser "au plus tard" (compilation, run-time) les optimisations relatives aux multi-coeurs.
27/07/2010, 14h35
Invité

Citation:

Envoyé par pseudocode

Je pense que l'idée de l'article c'est de dire que les langages impératifs obligent le développeur à concevoir son application en Mono-thread ou en Multi-thread. Mais une fois que ce choix est fait, il est immuable (sauf a réécrire l'application).

Les paradigmes fonctionnels/concurrentiels sont là pour ne pas solutionner ces problèmes par la conception, et donc repousser "au plus tard" (compilation, run-time) les optimisations relatives aux multi-coeurs.

C'est plutôt rassurant quant aux demandes à venir.. En fait les notions que je développe consistent aussi à présenter aux décideurs non-spécialistes, afin de faire comprendre la situation avec des termes qu'ils peuvent comprendre.

Dans ce domaine plus qu'ailleurs, je crains des demandes irréalistes formulées par des élites qui se laisseraient séduire par un discours peu compréhensible. Cela m'est arrivé avec des spécialistes du hardware plutôt haut-de-gamme. Ils sont très compétents et donc très écoutés. Leur impression est que le soft ne suit pas parce que les développeurs n'utilisent pas les bonnes techniques. Si vous relisez l'article, vous verrez que cette confusion est parfaitement possible.

Par protocole ou par politesse , on en oublie de préciser que le soft est un peu à la masse par rapport au hard dans cette histoire. Ce n'est pas vraiment une histoire de techno ou de méthode. Ce que les fondeurs présentent comme une avancée majeure, n'en est pas vraiment une pour le software.

Ce qui aurait vraiment permis d'améliorer nos affaires, ce sont des micro-codes plus rapides ou des fréquences d'horloge supérieures. Le multicore quant à lui ne permet que d'améliorer une partie du logiciel et risque de ralentir le reste.

C'est pourquoi le turbo-boost d'intel est si interressant dans les core i5 et i7. Actuellement, cette question est traitée dans la presse d'une façon qui laisse planer un doute sur la compétence du software.

Ce doute n'est pas vraiment une bonne chose. Il faudra du temps pour qu'il se dissippe. Personnellement, je ne suis pas en position de faire avancer les choses de façon crédible, je ne peux que donner une position que certains peuvent très bien interpréter comme défensive.

Je n'ai pas très envie de faire beaucoup de recherche sur le multithread car je devine que le potentiel d'optimisation monothread est bien meilleur.
En appliquant bêtement ce qui saute aux yeux : une FFT multithread : même Einstein ne saurait pas le faire. Une FFT 3D (plusieurs FFT's), oui on peut le faire massivement parrallèle même avec un langage ancien. (cela annonce de grandes améliorations lecture mpeg et divx) Et quid d'un simple QuickSort sur un index d'un milliard d'entrées ? comment comparer une ligne si on n'est pas sûr qu'un autre thread ne l'a pas déjà swappée ?

Une boucle for(; ; ) parallèle : ça existe depuis longtemps déjà mais si cette boucle fait appel à des calculs issus de la boucle précédente, ça ne marchera jamais. Ce n'est pas une question de langage ou de méthode : c'est physiquement impossible. Tout le monde ne comprend pas forcément ça comme un ingénieur qui passe ses journées dans le code.. les notions de récursion, d'itérativité, ... ne sont pas maîtrisées par grand monde et pas spécialement par les électroniciens qui ne s'en servent pas dans leur travail d'après ce que j'ai compris.
27/07/2010, 16h15
S(ô.Ô)B

Citation:

Par protocole ou par politesse , on en oublie de préciser que le soft est un peu à la masse par rapport au hard dans cette histoire. Ce n'est pas vraiment une histoire de techno ou de méthode. Ce que les fondeurs présentent comme une avancée majeure, n'en est pas vraiment une pour le software.

Ce qui aurait vraiment permis d'améliorer nos affaires, ce sont des micro-codes plus rapides ou des fréquences d'horloge supérieures. Le multicore quant à lui ne permet que d'améliorer une partie du logiciel et risque de ralentir le reste.

Pour nombre d'algorithmes le parallélisme représente un gain de performances considérable ! Mais il est vrai que pour des programmes où le parallélisme ne représente pas une grande amélioration, il serait plus profitable à ces programmes d'avoir des processeurs plus performants sur chaque cœur...

Citation:

Je n'ai pas très envie de faire beaucoup de recherche sur le multithread car je devine que le potentiel d'optimisation monothread est bien meilleur.
En appliquant bètement ce qui saute aux yeux : une FFT multithread : même Einstein ne saurait pas le faire. Une FFT 3D (plusieurs FFT's), oui on peut le faire massivement parrallèle même avec un langage ancien. (cela annonce de grandes améliorations lecture mpeg et divx) Et quid d'un simple QuickSort sur un index d'un milliard d'entrées ? comment comparer une ligne si on n'est pas sûr qu'un autre thread ne l'a pas déjà swappée ? Si je dessine une courbe en fausse 3D en commençant par la plus "lointaine" et en finissant par la plus proche , chaque courbe plus proche écrase en partie les précédentes. En séquentiel , l'effet 3D est excellent, en parallèle l'écrasement ne se fait plus dans le bon ordre et je dois passer à un rendu en vraie 3D beaucoup plus gourmand.

On peut très bien paralléliser un tri rapide : multi-threaded quicksort
Et regardez les gains de performance à la fin !

Je pense que la problématique actuelle pour les "gros" calculs est de repenser les algorithmes derrières afin de tirer parti au mieux des processeurs multi-cores. Mais cela a un véritable coût pour les logiciels car penser parallèle, et non plus itératif, n'est pas une gymnastique intellectuelle auquelle on a été habitué...
27/07/2010, 16h27
pseudocode

Citation:

Envoyé par S(ô.Ô)B

On peut très bien paralléliser un tri rapide : multi-threaded quicksort
Et regardez les gains de performance à la fin !

Cela se parallélise bien car le quicksort est au départ un algorithme du type "Divide and conquer", chose que l'implémentation impérative a justement fait disparaitre.

Dans ce cas particulier, il est meme plus facile de comprendre l'algo sous sa forme fonctionnelle:

qsort (first:other) = qsort ( x in other where x < first ) ++ [first] ++ qsort ( x in other where x >= first )
27/07/2010, 17h14
Invité

merci pour cette précision très interressante que je vais regarder de près

J'espere que cet exemple que j'ai ajouté à la dernière minute , et qui s'avère contestable n'a pas annulé le sens de mon message.

Pour un maître du hard : processeur plus récent, plus gros, plus cher = logiciel plus rapide.
Pour le développeur, ça ne suit pas et dans les faits , mon quicksort est effectué par une dll tierce qui n'est pas dispo en multithread.
Quant au reste de mon programme , je serai sans doute dans l'autre monde quand quelqu'un le parallèlisera si cela arrive jamais.
C'est un modèle temps réel qui a déjà été optimisé de facteurs > 40 par rapport aux tests initiaux.

Autres optimisations :

Gains de performance constatés :
Rafraichissement d'affichage : facteur 50 environ ,
Optimisation disque vers ram : environ facteur 1000
Optimisation disque écriture : environ 40
Multithread sur QuickSort : environ 2
...
Le multithread sur affichage n'augmente pas vraiment les perfs mais apporte un confort visuel et une fluidité inquantifiables..

Maintenant je suis heureux de voir que les vieux algos récursifs sont parallèlisables et ça me donne des idées ...:ccool:
27/07/2010, 20h41
Invité

Citation:

Envoyé par S(ô.Ô)B

On peut très bien paralléliser un tri rapide : multi-threaded quicksort
Et regardez les gains de performance à la fin !

Je pense que la problématique actuelle pour les "gros" calculs est de repenser les algorithmes derrières afin de tirer parti au mieux des processeurs multi-cores. Mais cela a un véritable coût pour les logiciels car penser parallèle, et non plus itératif, n'est pas une gymnastique intellectuelle auquelle on a été habitué...

Merci encore pour ce lien ! après lecture , je constate que cette page concerne l'hyperthreading d'intel et non pas (encore) le multicore. Le résultat est quand même passionnant et confirme qu'il faudra lire attentivement les publications intel si on veut "accrocher les wagons" quand les processeurs atteindront plusieurs 10zaines ou 100aines de core. C'est un peu dans cette optique que ça devient intéressant. D'ici là , on peut se former et améliorer la portabilité de l'existant vers le massivement parallèle mais...

Il me semble un peu prématuré de se risquer dans cette direction si au moins une copie du logiciel qu'on développe risque de tourner sur Atom N270 !

Pour les traitements GPU c'est différent mais connaissez vous une seule personne qui travaille vraiment sur GPU ? moi aucun , pourtant s'il y avait vraiment un challenge de ce coté, plusieurs collègues ou concurrents auraient produit quelque chose. Or actuellement dans ma spécialité le processeur de l'extrème parallèle est le powerPC !! qui a remplacé les anciens réseaux de DSP dont les systèmes de développement sont restés anecdotiques

La vraie rupture technologique est plutôt dans les prochaines générations de CPU 50 ou 100 cores. Mais je suis quelqu'un de trop concret pour m'avancer à des prévisions sur quelque chose que je n'ai pas les moyens de tester à part un I7 core 4 hyper threading : soit 8 cores virtuels.

Cela dit, jamais la programmation parallèle n'a jamais été aussi imminente et c'est vrai qu'il y a de quoi s'enthousiasmer. Anticiper le marché est un jeu très dangereux sur un plan professionnel mais certainement pas dans les conversations ou l'imagination.

Au point de vue du style de conception , ce ne sera pas une rupture plus traumatique que les précédentes, et il est amusant d'anticiper des architectures à centaines de cores dans un smartphone ce qui devrait arriver assez vite... tandis que les machines traditionnelles pourraient bien en totaliser des millions ou en tout cas , on peut rêver. Encore une fois, l'amérique me cloue au sol et parvient à sauver son modèle de croissance.

Je ne suis pas vraiment enclin à me diriger vers des méthodes comme celles qu'on enseigne à l'école aujourd'hui ou à utiliser le terme paradigme plus d'une fois par an. Peut-être un collègue habile me fera changer d'avis et adopter ce vocabulaire. En l'état et dans mon échelle très personnelle un peu heroïc fantasy , je dirais que c'est une nouvelle forme de vie dont la multiplication cellulaire pourrait bien , un jour , s'inspirer de la nature et croitre par elle même pour former des entités de la taille d'un système stellaire et d'une intelligence bien supérieure à celle de ses concepteurs. Ca m'a ouvert l'appétit

Bonne soirée
28/07/2010, 12h40
amaury pouly

Citation:

Envoyé par unBonGars

Pour les traitements GPU c'est différent mais connaissez vous une seule personne qui travaille vraiment sur GPU ? moi aucun , pourtant s'il y avait vraiment un challenge de ce coté, plusieurs collègues ou concurrents auraient produit quelque chose. Or actuellement dans ma spécialité le processeur de l'extrème parallèle est le powerPC !! qui a remplacé les anciens réseaux de DSP dont les systèmes de développement sont restés anecdotiques

J'en connais et je peux vous dire que les GPU représente un challenge encore plus important, au moins lorsqu'on les utilisent comme des calculateurs généraux (CUDA par exemple). La raison pour cela c'est que d'une part le parallèlisme y est beaucoup plus massif et que d'autres part c'est un parallisme de données. La hiérarchie des mémoire est beaucoup plus complexe que sur un processeur classique. Cela complique énormément le travail pour le compilateur (c'est de ce point de vue là que je parle) et tout autant pour celui qui écrit le code.

J'ai déjà vu en conférence des gens qui faisaient du parallèlisme et qui avaient essayé d'implémenter des algorithmes à la fois sur des plate-formes avec des dizaines de coeurs et sur des GPU. Leur conclusion étaient que d'une part que c'était très différent et d'autre part le temps nécessaire pour le faire fonctionner sur GPU était très important, justement à cause des éléments que j'ai cités (la mémoire principalement).

Je pense qu'il ne faut pas se leurrer, fonctionnel ou impératif c'est du pareil au même quand on à 10 coeurs ou plus. Ce qui compte c'est l'algorithme. La littérature sur l'algorithmique parallèle est très dévelopée mais on a jamais été aussi proche d'en avoir autant besoin :) Il faudra très sûrement récrire de nombreux algorithmes pour en tirer parti car cela n'a rien à voir avec l'algorithmique classique et c'est beaucoup plus casse-gueule :aie: D'ailleurs algorithme parallèle ne veut pas dire threads, cela s'applique aussi bien des processeurs en réseaux ou même des machines.
L'avantage du multi-coeur c'est que les communications sont plus rapides que sur un réseau et que l'on peut partager de la mémoire (utile mais dangereux si mal fait). Avantage toutefois à relativiser car lorsque le nombre de coeurs augmente, les architectures sont sûrement de type NUMA (Non Uniform Memory Architecture) et du coup, j'imagine que l'accès à de la mémoire partagée est plus lent que l'accès à la mémoire locale.

Nous verrons bien assez tôt ce qui va se passer mais je pense qu'il va s'écouler encore un peu de temps avant qu'on ait des processeurs à cent coeurs chez soi.
28/07/2010, 16h40
Invité

Citation:

Envoyé par amaury pouly

(...)
Nous verrons bien assez tôt ce qui va se passer mais je pense qu'il va s'écouler encore un peu de temps avant qu'on ait des processeurs à cent coeurs chez soi.

Vrai

Comme on est d'accord sur le caractère expérimental, on peut aller plus loin en réunissant nos expériences et en mettant en commun nos veilles technologiques.
Je pense qu'une plateforme dédiée serait plus adaptée qu'une news car les mises à jour seraient assez espacées et irrégulières.

Si vous entendez parler d'un atelier de ce genre, je serais assez interressé d'y contribuer.

Pour les GPU, je pense qu'il y a un vrai challenge car cette famille de composants a fait l'objet d'une compétition industrielle monstre (à l'avantage d'AMD jusqu'ici) et le potentiel est à la hauteur de l'énorme marché qui les finance (cartes graphiques accélérées).
Pour celui qui se lancerait dans cette course, il faut s'attendre à des années de recherche pour un revenu aléatoire voire nul ! Qui peut vraiment faire ça ? Les fondeurs eux-mêmes sans doute.

C'est un peu pareil pour les architectures massivement parallèles utilisées dans l'industrie, le spatial ou les grands projets d'envergure (simulations meteo, physique nucléaire, imagerie médicale, astrophysique, ...) Ceux qui y travaillent "épousent" une carrière et restent relativement discrets sur une plateforme publique comme developpez.com.

Il existe de véritables kadors des réseaux géants qui comptent les baies de serveurs par buildings entiers et qui , selon moi , ont d'excellentes compétences en paralélisme.
Mon expérience principale se situe là aussi. Ainsi que le multiTACHE d'unix qu'on appelle, parfois à tord, multithread aujourd'hui.
C'est pourquoi j'en parlais dans mon premier message : le parallélisme ne suppose pas forcément le partage de ressources : pire :
Certaines ressources parallèles servent justement à arbitrer l'accès aux ressources protégées et ne servent qu'à cela.

Il peut s'agir d'un serveur situé dans un domaine volontairement isolé qui sert de passerelle unique vers ce domaine...

Pour le grand public et le développeur lambda, l'état de l'art se situe plutôt dans les serveurs que dans les architectures multi-processeurs.
Cela dit, les grands travaux sur le parallèlisme seront un jour partiellement déclassés comme l'internet ou le GPS aujourd'hui, et gare à celui qui aura fait sa petite cuisine dans son coin en bricolant des cartes multi-procs. Il se retrouvera en concurrence avec des projets financés par les états ou l'industrie médicale.. Attention jeunes gens, une aventure pareille , on ne s'en remet pas facilement !

Notre challenge est de s'adapter à la prochaine mutation des processeurs coûte que coûte puisque le multicore n'est pas vraiment une attente du marché mais une obligation pour les fondeurs.

A suivre en tous cas
29/07/2010, 23h57
hsyl20

Bonne lecture :-)

Bon alors déjà il y a plusieurs objectifs :
- l'application utilise plusieurs processus/threads/etc. à cause de certaines contraintes (thread dédié à l'interface utilisateur, thread en attente sur un socket, etc.) => programmation concurrente
- l'application a besoin d'aller le plus vite possible et pour cela doit utiliser au mieux les différentes unités de calcul présentes => programmation parallèle

Dans le premier cas, le nombre de threads est fixe et dépend de la sémantique. Dans le second cas, le nombre de "threads" peut potentiellement varier en fonction de l'architecture. Dans la suite je ne parle que de programmation parallèle (dont l'objectif est les performances).

1) Inconvénients des programmes impératifs
Quand vous écrivez un programme avec un langage impératif, vous donnez une suite d'ordres (d'où le nom "impératif") qui sont implicitement en séquence :
faireci();
faireça();
Implicitement vous savez que faireça() va être exécuté après faireci(). Parfois c'est ce qu'on veut :
a = 10;
b = a+1;
Parfois c'est une contrainte inutile :
a = 10;
b = 11;
Le gros du boulot du compilateur est de savoir quelles sont les vraies dépendances et quelles sont celles qui ont été introduites pour rien. Vous pouvez aider le compilateur en utilisant certains mots clés (const, restrict, etc.) qui lui donnent des informations supplémentaires. Sachant ça, le compilo peut vectoriser (instructions SSE) plus facilement ou réordonner les instructions sans que la sémantique ne change bien sûr.

Le problème est que le compilo n'a souvent pas assez d'informations pour savoir qu'il peut paralléliser le code. Dans l'exemple ci-dessus, le compilo ne peut pas déterminer si "faireça()" dépend d'effets de bord (modification d'une variables quelque part en mémoire) de "faireci()", il ne parallélisera donc jamais ce code. Pour paralléliser ça, vous pouvez utiliser OpenMP :
#pragma omp parallel num_threads(2)
{
if (omp_get_thread_num() == 0)
faireci();
else
faireça();
}
C'est tout de suite beaucoup plus contraignant... Et encore avec OpenMP, c'est simple. Si vous voulez gérer vos threads à la main avec mutexes, spinlocks, conditions, etc. ça devient encore plus sympa.

1.1) Nombre de threads et placement
Un autre problème est le nombre de threads. Si vous avez N sections potentiellement exécutables en parallèle et P cores, combien de threads créer simultanément ? Si vous créez N threads avec N très grand, vous allez plomber votre OS. La création de thread a un coût. D'ailleurs il est préférable d'utiliser des threads en espace utilisateur schedulés sur des threads usuels. Il faut alors également bien choisir les stratégies d'ordonnancement des sections parallèles sur les différents threads.

Encore un autre problème : le placement des threads. Si deux threads partagent des données, il est préférable qu'ils soient placés sur deux cores qui partagent un cache. Ensuite il faut éviter le "false sharing" (deux threads éloignés qui écrivent dans deux zones mémoires proches telles qu'elles partagent la même ligne de cache). Les coûts peuvent être beaucoup plus élevés dans le cas d'architectures NUMA.

1.2) Parallélisme imbriqué
Si vous avez des sections parallèles imbriquées dans d'autres sections parallèles, les stratégies d'ordonnancement peuvent être modifiées. Les affinités (partage de données) entre sections parallèles peuvent évoluer, etc.

1.3) Conclusion langages impératifs
Ça fait rêver non ? Et encore, on n'a pas parlé des clusters qui exécutent des programmes qui communiquent par le (ou les...) réseau(x) en utilisant MPI.Pour rester simple, je vais parler de la programmation sur GPU.

2) Programmation GPU
On utilise soit CUDA (de NVidia), soit OpenCL. OpenCL étant un standard fortement inspiré de CUDA, je vais parler de ça. À noter qu'AMD/ATI avait aussi sa technologie Stream mais ça n'était pas très répandu. Maintenant qu'AMD et NVIDIA supportent plus ou moins OpenCL, c'est un peu moins la foire.

2.1) OpenCL
Bon alors c'est simple :-) vous avez des fonctions pour transférer des données depuis/vers la mémoire principale du PC (RAM) vers/depuis la mémoire principale de la carte graphique. Les transferts peuvent être synchrones ou asynchrones (DMA...). Le mieux c'est d'anticiper et de les faire en asynchrone le plus tôt possible.

Vous écrivez un "kernel" OpenCL : ça rassemble à une fonction classique, sauf qu'elle va être exécutée en parallèle par N threads (N <= 512 jusqu'à récemment pour les cartes NVIDIA). Vous avez accès au numéro du thread donc vous pouvez faire des traitements spécifiques en fonction du numéro du thread (comme en MPI quoi). Ces threads ont accès à la mémoire principale de la carte graphique. Ils peuvent donc utiliser les données que vous avez préalablement transférées.

Cependant l'accès à cette mémoire et relativement lent. Heureusement il existe une petite mémoire (16KB) à accès rapide dans laquelle les threads peuvent stocker des données. Les threads peuvent se synchroniser (barrières, etc.) et partager des données à travers cette mémoire (ou la mémoire principale). Bon je ne vous raconte pas le "coalescing" en détail, mais en gros si vous voulez que les accès à la mémoire partagée soient encore plus rapides, il faut que les threads accèdent simultanément à des données contigües (le thread n accède à la donnée A[n], le thread n+1 accède à la donnée A[n+1], etc.).

Bon jusque là c'est facile. Sauf qu'en fait des groupes de threads comme ça, on peut en exécuter plusieurs en parallèle. Plus vous avez une carte puissante, plus elle peut exécuter simultanément de groupes de threads. Donc il FAUT en exécuter plusieurs en parallèle pour exploiter la carte. Ces groupes de threads ne peuvent pas communiquer entre eux (pas de barrières, etc.).

2.2) Conclusion GPU
Le modèle de programmation sur GPU est complètement différent. La communication entre la mémoire principale et le GPU doit se gérer comme on gère un réseau (transferts asynchrones, placement des threads de communication avec le GPU sur les coeurs à proximité des bus PCI-E, etc.). On peut aussi avoir plusieurs cartes graphiques, ce qui complexifie encore plus.

3) Les langages fonctionnels
Voyons pourquoi les langages fonctionnels sont de plus en plus courtisés ces derniers temps.

3.1) Fonctions pures et variables immutables
Une fonction pure est une fonction qui ne dépend pas de l'environnement et qui ne le modifie pas. En gros si j'appelle f(a,b,c) à n'importe quel moment dans mon programme, j'obtiendrai le même résultat. C'est une fonction au sens mathématique en fait, donc avec de vraies propriétés.

De la même façon, une variable immutable est en fait une variable au sens mathématique. En maths quand vous posez "a = racine(168)", la valeur de "a" ne va pas changer au cours de votre calcul ("je pose a = 36 et b = f(a). Combien vaut a ?". En C (avec un pointeur) on ne peut même pas répondre à ça dans le cas général).

Donc en fonctionnel quand vous écrivez :
a = f(10)
b = f(a)
Il y a une dépendance entre ces deux lignes. Alors que quand vous écrivez :
a = f(10)
b = f(18)
Vous pouvez être certain (et le compilo aussi) qu'il n'y a pas de dépendance entre ces deux lignes. De plus, si vous avez :
a = f(10)
b = f(10)
Le compilo peut optimiser en :
a = b = f(10)
(cf Common Subexpression Elimination, Memoization, etc.)

Bon alors déjà on voit qu'on n'a pas les contraintes nuisibles des langages impératifs. On a d'autres contraintes, j'en parle après.

3.2) Data Parallelism
Un des gros défaut des langages fonctionnels usuels est qu'ils reposent majoritairement sur des structures récursives (listes) et emploient donc des algorithmes récursifs. Par exemple pour appliquer une fonction à tous les éléments d'une liste, vous allez utiliser la fonction Map définie naïvement comme suit (exemple en Scala) :
def map(maliste: List[A], f: A => B): List[B] = maliste match {
case Nil => Nil
case x :: xs => f(a) :: map(xs, f)
}

On voit bien que la fonction Map s'auto-appelle en séquence pour tous les éléments de la liste. L'idée est donc d'utiliser des structures de données non récursives avec lesquelles on peut travailler en parallèle. En gros, des vecteurs/tableaux.

On trouve ce type de langage chez Intel (Intel Ct) mais ils n'ont rien inventé puisque NESL le faisait il y a 17 ans. Ce type de langage devrait revenir à la mode.

3.3) Défauts de l'approche fonctionelle
Un des gros défaut de l'approche fonctionnelle est que l'on ne modifie pas les données (données immutables). Du coup, si vous voulez changer la valeur d'une cellule d'un tableau, vous devez en faire une copie avec la cellule actualisée à sa nouvelle valeur. Ça devient vite très lent pour des tableaux de millions d'éléments.

Dans certains cas, le compilateur peut détecter que le tableau source ne sera plus utilisé et faire une modification in-place. Dans le cas général, il ne peut pas.

3.4) Conclusion langages fonctionnels
On a vu que l'approche fonctionnelle avec data-parallelism résout de nombreux problèmes et permet au compilo de trouver du parallélisme plus facilement. Cependant les modifications in-place restent nécessaires dans certains cas pour avoir de bonnes perfs. Une solution est l'approche hybride : le programme utilise principalement le paradigme fonctionnel ; certaines fonctions sont écrites en langage impératif mais respectent les contraintes fonctionnelles (pas d'effet de bord).

4) Conclusion
OpenCL (côté hôte, pas dans les kernels) est très proche du paradigme fonctionnel. On exécute des kernels en indiquant les dépendances entre eux et ces kernels sont quasiment purs (buffers ReadWrite exceptés). Ça reste très contraignant et l'exécution de kernels sur CPU ("supporté" par AMD) n'est pas encore terrible. C'est déjà un progrès car ça force les développeurs à isoler des portions parallélisables et quasi-pures de leur code.

La gestion efficace des cartes graphiques et des transferts mémoire est très compliquée. C'est pourquoi certains travaux de recherche visent à fournir une couche au-dessus d'OpenCL/CUDA (voir le runtime StarPU).

Pour conclure, le paradigme fonctionnel sera donc forcément remis au goût du jour, même si ça ne ressemble pas à du Lisp. Les compilos ont besoin de propriétés pour travailler sur les codes. Les codes ne peuvent plus être à la fois portables et tunés à la main car il y a trop de facteurs à prendre en compte : nombre de coeurs, topologies des coeurs, cartes graphiques (capabilities...), mémoire disponible sur chaque carte graphique, NUMA, etc. Autant on pouvait s'en sortir avec des #ifdef bien crades auparavant pour passer de PowerPC à x86 à x86_64, autant ça n'est plus possible maintenant.