Au fur et à mesure qu'ils évoluent, les processeurs comportent toujours plus de coeurs. Et à chaque fois, les développeurs doivent trouver la meilleure façon d'utiliser cette puissance parallèle supplémentaire. Cette fois, les chercheurs de l'Institut de technologie du Massachusetts ont créé un algorithme baptisé SprayList qui, selon eux, peut augmenter l'efficacité de la prise en charge des tâches par les gros processeurs multicoeurs (jusqu'à 18 coeurs avec le Xeon E5v3 d'Intel). Leur solution consiste à déroger au principe de file d'attente traditionnel où le premier arrivé est le premier servi et à assigner les tâches de façon plus aléatoire. L'algorithme SprayList du MIT doit permettre aux processeurs comportant un grand nombre de noyaux d'étaler le traitement des tâches pour éviter les embouteillages, responsables de goulots d'étranglement qui entravent la performance. Si leurs résultats se confirment, un algorithme comme SprayList pourrait profiter aux processeurs multicoeurs, comme la puce serveur Xeon E5 2600v3 d'Intel et ses 18 coeurs.

Les processeurs multicoeurs, où un seul processeur contient deux ou plusieurs noyaux de calcul fonctionnant simultanément, posent de nombreux défis en matière de programmation. En effet, pour obtenir des performances maximales, le travail que doit accomplir l'ordinateur doit être également réparti entre chaque noyau. Il y a plus d'une décennie, quand sortaient les premiers processeurs bicoeurs et quadricoeurs, les développeurs ont cherché une solution pour adapter la technique simple et bien connue de répartition des tâches, appelée file d'attente prioritaire, où la tâche suivante dans la file d'attente est traitée par le prochain noyau disponible. La file d'attente peut être organisée en fonction d'une certaine priorité d'usage et selon le bon vieux principe du « premier arrivé, premier servi ». Mais, si, selon les chercheurs, le principe traditionnel de file d'attente prioritaire est optimum jusqu'à huit coeurs, au-delà, les performances sont ralenties. En effet, quand il y a beaucoup de noyaux, la probabilité que plusieurs coeurs soient disponibles précisément au même moment peut provoquer des goulots d'étranglement, chaque coeur se trouvant en concurrence pour exécuter la tâche suivante. Parce que chaque noyau conserve sa propre copie de la file d'attente prioritaire dans un cache, la synchronisation de cette file d'attente en perpétuel changement au niveau de chaque cache devient un vrai casse-tête.

Un algorithme efficace au dessus de 8 coeurs

Les chercheurs ont imaginé une nouvelle façon de traiter les files d'attente prioritaires pour que la méthode reste efficace jusqu'à 80 coeurs. Au lieu de demander à chaque coeur de prendre en charge la tâche suivante dans la file d'attente, la tâche est assignée de manière aléatoire, ce qui réduit la probabilité d'avoir des noyaux en concurrence pour une même tâche et donc les chances de créer un goulot d'étranglement. « Traditionnellement, l'assignation aléatoire était mal vue par ceux qui pensent exclusivement en terme de processeurs », font remarquer les chercheurs dans un document expliquant leur travail. Un algorithme d'ordonnancement aléatoire prend plus de temps à examiner la file d'attente que la hiérarchisation conventionnelle. Les caches ne peuvent pas être utilisés pour préparer les tâches à venir. Et quand l'exécution d'une tâche repose sur une série d'étapes hiérarchisées, l'ordinateur a besoin de temps supplémentaire pour réorganiser les résultats définitifs. Mais selon les chercheurs, quand le nombre de coeurs augmente, l'assignation aléatoire permet de compenser ces inconvénients par des gains en performance.

Les tests réalisés avec 80 coeurs ont été concluants.

Pour tester l'efficacité de SprayList, ceux-ci ont fait tourner leur algorithme sur un serveur Fujitsu RX600 S6 équipé de quatre processeurs 10-core Intel Xeon E7-4870 (Westmere EX), supportant 80 threads matériels, reproduisant ainsi le comportement d'un processeur 80-coeurs. Dans une simulation en deçà de huit threads processeurs, l'algorithme SprayList s'est montré été effectivement moins efficace que des algorithmes traditionnels fonctionnant selon le principe de la file d'attente. Mais à mesure que des threads étaient ajoutés, la performance de ces algorithmes, mesurée en opérations par seconde, a chuté, et celle de SprayList a augmenté de façon linéaire. En réalité, SprayList ne saisit pas les tâches complètement au hasard : il travaille sur une sorte de file d'attente prioritaire appelée liste d'exception, qui regroupe les tâches selon différents niveaux de priorité et fait en sorte que les tâches hautement prioritaires restent toujours traitées avant les tâches de faible priorité.

Présentation des travaux au PPoPP de San Francisco

« Les utilisateurs qui choisissent expressément la file d'attente prioritaire veulent que les éléments les plus prioritaires restent devant les éléments à priorité faible ». « Notre travail soutient l'idée qu'il est possible d'assouplir ce principe, par exemple, traiter la dixième plus haute priorité avant la première plus haute priorité sans trop de problèmes », a déclaré Justin Kopinsky, l'étudiant en doctorat du MIT qui a dirigé ces travaux avec son collègue diplômé Jerry Li. « Une randomisation pure pourrait faire que l'ordinateur traite en premier des tâches ayant une très faible priorité, ce qui poserait un vrai problème », a expliqué Justin Kopinsky par courriel. Pour leur travail, Justin Kopinsky et Jerry Li ont reçu l'aide de Nir Shavit, professeur en informatique et en ingénierie du MIT, et de Dan Alistarh, un ancien élève de Nir Shavit qui travaille pour Microsoft Research. Les chercheurs présenteront leurs travaux à San Francisco lors du 20eSymposium on Principles and Practice of Parallel Programming (PPoPP 2015) organisé par l'Association for Computing Machinery (7-11 février).