En raison de la multiplication chez le grand public des ordinateurs multi-cœurs, et de la tendance actuelle des fabricants de processeurs, le parallélisme et la concurrence sont redevenus des sujets très en vogue. Pour exploiter au maximum son matériel, il faut pouvoir structurer ses programmes pour que plusieurs calculs soient effectués en même temps.

Voici très rapidement quelques notions importantes à retenir et bien distinguer. En particulier, attention ne pas confondre "parallèle" et "concurrent".

• Programmation parallèle : si notre programme effectue plusieurs tâches indépendantes, et qu'on a plusieurs nœuds de calcul à disposition (par exemple un processeur à plusieurs cœurs), on peut les exécuter en même temps. Le parallélisme s'intéresse donc à comment découper un programme en tâches indépendantes, et comment les exécuter simultanément de façon à minimiser le temps de calcul total.

Parallélisme de tâches / de données : il y a deux façons principales de découper le travail à effectuer pour le parallélisme. On peut distinguer des tâches distinctes à exécuter séparément, ou remarquer qu'une tâche donnée doit être exécutée plusieurs fois sur des données différentes.

• Programmation concurrente : en pratique, peu de tâches sont complètement indépendantes les unes des autres. Elles peuvent avoir besoin de communiquer entre elles, de se synchroniser, et exploiter des ressources communes. Il faut alors mettre en place des méthodes de coopération entre les différentes tâches, sans quoi on risque l'inefficacité, voire le blocage complet du programme. C'est nettement plus compliqué que la simple programmation parallèle.

La programmation concurrente n'implique d'ailleurs pas nécessairement le parallélisme, on peut avoir des problématiques de synchronisation sur un ordinateur n'exécutant qu'un seul calcul à la fois. Par exemple, sur un système d'exploitation multitâches, le processeur alterne le temps de calcul entre différents processus, et on peut utiliser de la synchronisation pour maximiser l'utilisation d'un processeur : par exemple, si un programme attend que le disque dur lui donne un fichier, il bloque et on peut exécuter d'autres programmes pendant ce temps. De même, deux programmes n'ont pas le droit d'écrire dans un même fichier en même temps, donc doivent se synchroniser.

• Programmation distribuée : pour de grosses applications, utiliser les différents cœurs d'un processeur ou les différents processeurs d'une machine ne suffit pas. On veut répartir le calcul sur des grappes d'ordinateurs. Cela pose de nouveaux problèmes. Il faut prendre en compte la localité et les coûts de communication entre les nœuds de calcul. Il faut aussi prévoir le risque d'erreurs (machine distante qui plante, erreurs de transmission sur le réseau), gérer le déploiement du-des programme-s. Enfin, il peut y avoir des problématiques de sécurité/confiance : doit-on considérer que les autres participants au calcul sont honnêtes ?

• Programmation hétérogène : certains matériels spécialisés sont très bons pour certains types de parallélisme, mais imposent des contraintes fortes sur les programmes que l'on peut y exécuter. Par exemple, les cartes graphiques sont des processeurs spécialisés pour effectuer une opération sur un énorme nombre de données à la fois (parallélisme de données), mais la plupart des constructions "complexes" des langages de programmation y sont très coûteuses. Certains types de calculs très spécialisés pourront donc y être réalisés avec d'énorme gains, mais cela demande souvent de les ré-écrire en profondeur.

Il est aussi important de comprendre que ce sont des domaines très vastes pour lesquels il n'existe pas de solution unifiée, de méthode qui résolve tous les problèmes. Chaque choix a des forces et des faiblesses, et sera très adapté pour certains types d'applications mais inefficace pour d'autres.

Parallel Collections, pour des manipulations parallèles des données

Le chou gras de la programmation parallèle est sans doute la manipulation de gros volumes de données. En effet, les manipulations de séquences d'éléments sont omniprésentes dans les programmes informations : réordonner des informations, les analyser (par exemple, calculer le nombre d'éléments d'un tableau qui vérifie une certaine propriété), les transformer...

Mais la façon classique, impérative, de faire ces modifications, en utilisant une boucle for qui produit le résultat à l'étape i+1 en modifiant celui de l'étape i, est néfaste à toute tentative de parallélisme. Il faut changer de façon de voir les choses, et traiter chaque élément de la séquence indépendamment des autres, avant de réunir les résultats.

Google a largement diffusé sa technologie MapReduce destinée à découper d'énormes volumes de données sur des grappes de serveurs. Mais la même idée peut s'appliquer même sur des calculs de taille plus raisonnables; le langage Fortress, développé pour la programmation scientifique, a popularisé (dans les milieux de recherche) l'idée qu'il fallait changer notre façon de concevoir les programmes pour y exposer plus de parallélisme, et la variante Data Parallel Haskell (DPH) du langage généraliste Haskell a expérimenté en pratique avec des constructions de parallélisme de données.

Avec 'Parallel Collections', Scala se dote d'une bibliothèque logicielle favorisant des organisations de calcul plus propices au traitement parallèle des données indépendantes. Comme l'extension PLINQ du sous-langage de requêtes LINQ de Microsoft, elle est générique par rapport au type de séquence considérée (listes, tableaux, tables de hachage, arbres...).

La séparation entre parallélisme de données et parallélisme de tâches est ici assez floue, et des méthodes classiques de partage de tâches sont aussi utilisées pour répartir le travail entre différents processeurs, de façon à ce que ceux qui ont fini plus rapidement que les autres puissent récupérer du travail supplémentaire. En cela, il se rapproche des bibliothèques et extensions Cilk, Intel TBB, OpenMP et Apple Grand Central Dispatch.

Akka : un modèle à la Erlang pour simplifier la concurrence

Scala attaque aussi, comme tous les langages actuels, la question de la programmation concurrente. Jusqu'à récemment, le style de programmation le plus utilisé pour la concurrence était le modèle de mémoire partagée avec verrous : tous les nœuds de calculs ont accès à la même mémoire, et doivent se synchroniser pour décider comment la lire et la modifier sans se marcher sur les pieds.

Les méthodes de synchronisation par verrou peuvent poser des problèmes de 'deadlock', où deux programmes se bloquent mutuellement en gardant des ressources dont l'autre a besoin. Écrire des programmes pour éviter les blocages peut être très difficile. Quand on passe en plus à de la programmation parallèle (comme les systèmes multi-cœurs), d'autres problèmes apparaissent, liés au fait que la mémoire n'est pas vraiment partagée de façon transparente, mais qu'il y a des délais de modification et communication. L'implémentation d'algorithmes utilisant la mémoire partagée est extrêmement complexe et devrait être réservée aux experts; en particulier quand on arrive aux détails bas niveau (implémentation des bibliothèques de mutex etc.), la complexité est telle que seules une poignée de spécialistes savent écrire des programmes concurrents sûrs.

Un autre modèle de concurrence, le modèle d'acteur (Actor Model), est connu depuis longtemps dans certains milieux de recherche (il a été développé à partir de 1973), mais n'a été popularisée auprès du "grand public" que grâce au langage Erlang, qui s'est fait connaître pour sa grande élégance pour la programmation concurrente et distribuée. L'idée centrale pour la concurrence est d'empêcher l'accès à une mémoire commune par les différents processus, et de les forcer à communiquer explicitement par passage de messages.

Le passage de message évite une grande partie des problèmes de la programmation par mémoire partagée, et a tendance à favoriser une meilleure conception des programmes concurrents, où les problèmes de blocages sont moins susceptibles de se produire. Bien qu'elle ne soit pas adaptées pour certaines tâches où le coût de l'envoi de messages domine les gains du parallélisme, c'est un modèle généraliste solide pour la programmation concurrente, et la plupart des langages récents s'en insiprent, sans forcément utiliser le modèle d'acteur (par exemple D ou Go).

Akka est une bibliothèque logicielle récente qui apportel un modèle similaire à Erlang pour le langage Scala (et Java, qui en profite donc aussi). Comme Erlang, il facilite aussi la programmation distribuée et la résistance aux erreurs, et propose aussi un autre modèle de concurrence pour certains cas où les acteurs ne conviennent pas : STM (Software Transactional Memory), un modèle reposant sur des transactions atomiques de la mémoire, proposé par des chercheurs israëliens puis popularisé par le langage Haskell. La mise en œuvre d'Akka s'inspire de celle du langage fonctionnel Clojure (variante de Lisp), un autre langage JVM qui a beaucoup travaillé sur la concurrence.

Et pour le futur, l'argent de la commission européenne

En raison de la multiplication du matériel parallèle auprès du grand public (on oublie parfois que les scientifiques ont travaillé sur ce genre de machines dès les années 1950), le développement de technologies rendant le parallélisme et la concurrence plus accessibles est devenue une priorité pour tout le monde. Les pouvoirs publics en ont tenu compte et l'Union européenne a récemment lancé un appel à candidature aux chercheurs, qui pouvaient demander des fonds pour de la recherche sur ce domaine. L'équipe qui coordonne le développement du langage Scala, à l'École Polytechnique Fédérale de Lausanne, a monté un projet qui a remporté un financement de 2.3 millions d'euros sur 5 ans (cf. l'annonce du projet sur le site de Scala).

L'idée de ce projet de recherche, développé en collaboration avec l'université de Stanford, est de développer dans Scala des mini-langages spécialisés qui soient adaptés à certains domaines spécifiques où les méthodes de parallélisme sont très différentes des programmes généralistes.

Ces idées reposent sur des techniques de métaprogrammation qui ont été développées par les langages fonctionnels (d'abord dans la famille Lisp, puis dans des langages statiquement typés avec MetaML/MetaOCaml, les types fantômes, GADT, etc.). En utilisant ces méthodes, le code écrit par l'utilisateur d'une bibliothèque est optimisé par des fonctions spécialisées placées dans la bibliothèque logicielle, et plutôt que le compilateur.

Dans la version proposée par Scala, le code optimisé est écrit directement en Scala, mais dans un sous-ensemble décidé par chaque bibliothèque. Le code obtenu peut ensuite être compilé de façon spécialisée, par la bibliothèque, pour être envoyé par exemple sur une carte graphique en utilisant les technologies de programmation hétérogène comme OpenCL.

L'idée de développer des langages intégrés spécialisés n'est pas nouvelle, mais son application large à la programmation parallèle hétérogène représenterait une progression intéressante. Espérons donc que ce projet de recherche portera ses fruits.