Developpez.com

Club des développeurs et IT pro
Plus de 4 millions de visiteurs uniques par mois

[HPC] Pour des chercheurs, « une décennie de cœurs perdue » par Linux,
Quelques modifications améliorent la performance d'un facteur jusque 137

Le , par dourouc05, Responsable Qt
L’ordonnanceur d’un système d’exploitation est une partie cruciale pour la performance. Il décide de l’affectation des fils d’exécution aux différents cœurs et processeurs d’une machine afin d’utiliser au mieux la machine à disposition, tout en garantissant une certaine réactivité pour les applications qui en ont besoin (notamment les interfaces graphiques : elles ne peuvent pas rester plusieurs minutes sans pouvoir exécuter la moindre instruction, car elles ne peuvent alors pas répondre aux stimuli de l’utilisateur, qui a alors toutes les raisons de râler).

Il y a de cela une quinzaine d’années, Linus Torvalds déclarait, en somme, que l’ordonnancement était un problème très facile et qu’il était déjà très bien résolu dans le noyau Linux depuis dix ans (c’est-à-dire depuis les toutes premières versions du noyau) : inutile d’en discuter, tout fonctionne pour le mieux, . Linus Torvalds estime même que l’extrapolation de ces techniques aux cas de machines à plusieurs processeurs est « trivial » : une logique de répartition de la charge entre les différents processeurs ne devrait représenter que quelques centaines de lignes de code, que les développeurs « ne devraient pas trop merder », selon ses termes.

Cependant, avec l’avènement de machines avec de plus en plus de cœurs pour le plus grand nombre, l’ordonnancement s’est alors révélé bien plus compliqué que dans le cas à un seul processeur et cœur par machine. En effet, les taux d’utilisation du processeur restent très élevés, tout semble se passer pour le mieux… sauf que certains cœurs restent inutilisés par moments. Au niveau technique, cet ordonnancement reste très similaire à celui pratiqué au début des années 1990, à la différence de la répartition de la charge : régulièrement, le noyau répartit à nouveau les tâches à effectuer sur les différents cœurs, chacun suivant alors une politique équitable entre les tâches (selon l’algorithme CFS, completely fair scheduler).

Une équipe de chercheurs a remarqué des déficiences majeures du côté de l’ordonnanceur en tentant d’expliquer certaines dégradations importantes de performance en laissant le noyau Linux gérer lui-même l’affinité des processus par rapport aux cœurs, plutôt qu’en les assignant manuellement aux cœurs disponibles. De fil en aiguille, ils ont éliminé les causes les plus probables, comme une mauvaise localité en mémoire, des contentieux à l’accès à une ressource partagée ou les changements de contexte. Ils en sont venus à suspecter l’ordonnanceur du noyau. Pour récupérer des informations suffisantes, ils ont développé des outils de suivi à très haute résolution pour caractériser la répartition des tâches aux différents cœurs et processeurs d’une machine de test. Le résultat était sans appel : certains processeurs étaient surchargés, d’autres presque complètement désœuvrés, selon des motifs étranges et difficiles à expliquer rationnellement.



Par la suite, l’équipe a cherché dans le code source du noyau les parties à incriminer, elle a trouvé un premier défaut dans le code de l’ordonnanceur CFS : les chercheurs sont alors partis dans l’exploration plus approfondie du code. Ils ont fini par trouver quatre défauts majeurs dans le code : une fois analysés et corrigés les patchs sont disponibles sur leur site pour le noyau en version 4.1, ils ne sont pas encore intégrés dans Linux), le test de performance de bases de données TPC-H a vu une amélioration de douze à vingt-trois pour cent, le plus flagrant étant probablement une amélioration d’un facteur de cent trente-sept dans certaines charges de type HPC !

Ce travail de détection et de correction doit être très fin, car les techniques conventionnelles de test et de débogage sont totalement inefficaces pour comprendre ce genre de défauts : les symptômes sont très évasifs (les épisodes problématiques sont assez fréquents, mais chacun dure au plus quelques centaines de millisecondes), il est impossible de distinguer un véritable problème du bruit de fond dans un outil comme htop.

En réalité, les problèmes se situent principalement au niveau des heuristiques de CFS : pour éviter des calculs très lourds et de la communication (forcément lente) entre les différents processeurs, certaines données sont approchées à l’aide d’heuristiques (principalement, la charge de chaque cœur et processeur). Cependant, leur impact n’a pas toujours été analysé en profondeur, ce qui laisse une grande marge d’améliorations à ce niveau.

Cet article tire plusieurs conclusions, la première étant que Linus Torvalds est très loin de détenir la vérité quant aux résultats des ordonnanceurs : non, ce n’est pas un problème résolu, il faudra encore pas mal de recherche à ce niveau pour exploiter au mieux le matériel disponible (et éviter de laisser des cœurs totalement inoccupés). Les correctifs proposés par les chercheurs ne résolvent que les problèmes qu’ils ont remarqués : ils ne prétendent pas donner des solutions génériques à tous les problèmes, ils n’ont pas poussé les tests jusqu’à déterminer l’impact sur d’autres types de charges.

L’objectif est atteint : les ordonnanceurs doivent encore évoluer.

Source : The Linux Scheduler: a Decade of Wasted Cores
Ce contenu a été publié dans HPC et calcul scientifique par dourouc05.


Vous avez aimé cette actualité ? Alors partagez-la avec vos amis en cliquant sur les boutons ci-dessous :


 Poster une réponse

Avatar de BufferBob BufferBob - Expert confirmé https://www.developpez.com
le 15/05/2016 à 3:37
l'article est intéressant, et si les prochains noyaux voient leurs perfs améliorées c'est une excellente nouvelle, mais aller reprocher à Torvalds une connerie qu'il a dite il y a 15 ans c'est complètement stupide (d'autant qu'il en dit régulièrement, ça devrait plus tellement choquer )

l'essentiel c'est que le projet y gagne, pas de s'adonner au lynchage d'1 seul bonhomme
Avatar de earhater earhater - Membre confirmé https://www.developpez.com
le 15/05/2016 à 6:35
Yes reprocher une connerie de linus torvald dite il y a 15 ans alors qu'il n'avait même pas les outils pour débugger ces performances n'est pas intelligent, même si ça pourrait le faire descendre sur terre parfois. En tout cas si le projet s'améliore grâce à ça tant mieux !
Avatar de rawsrc rawsrc - Modérateur https://www.developpez.com
le 15/05/2016 à 10:35
J'ai lu leur document technique sur la problématique et je me dois de vous poster une citation du sieur Linus :
“Nobody actually creates perfect code the first time around, except me. But there’s only one of me.”

Linus Torvalds, 2007 [44]

Bon, soit dit en passant, je confirme qu'il ramasse le Linus avec un peu de retard quand même...
Le seul point étonnant c'est que le code de l'ordonnanceur n'a jamais été modifié en profondeur depuis le début du siècle (2/3 broutilles par ci par là et pis c'est tout)
Là, c'est une correction importante de l'algo.
Avatar de BufferBob BufferBob - Expert confirmé https://www.developpez.com
le 15/05/2016 à 12:56
Citation Envoyé par rawsrc  Voir le message
Le seul point étonnant c'est que le code de l'ordonnanceur n'a jamais été modifié en profondeur depuis le début du siècle (2/3 broutilles par ci par là et pis c'est tout)

hum, t'es sûr de ça ? il me semble que justement il avait été complètement revu avec la sortie du noyau 2.6 à l'époque, notamment le passage d'un ordonnancement en O(1) au lieu de O(n)
Avatar de iciyas iciyas - Candidat au Club https://www.developpez.com
le 15/05/2016 à 15:13
D'abords bravo aux chercheurs pour cette découverte, ensuite rien n'est perdu tout est à gagner car Linux sera (je le penses) en mutation perpétuelle.

Par contre je n'ai pas aimé le ton de la conclusion:
M. Linus Torvalds n'avait de boule de cristal pour savoir que les cpu auront plusieurs cœurs.

Malgré que la communauté Linux n'est pas une firme type (La pomme ou les Fenêtres), mais les développeurs font de leurs mieux pour garder ce système en bonne santé.
Avatar de Aeson Aeson - Nouveau Candidat au Club https://www.developpez.com
le 15/05/2016 à 15:21
Là, c'est une correction importante de l'algo.

Là, c'est une correction importante de l''EGO' de Linus

M. Linus Torvalds n'avait de boule de cristal pour savoir que les cpu auront plusieurs cœurs.

On affirme pas qu'on est le meilleur et qu'on est le seul a ne pas faire d'erreur.....
Avatar de dourouc05 dourouc05 - Responsable Qt https://www.developpez.com
le 15/05/2016 à 20:15
Citation Envoyé par iciyas  Voir le message
M. Linus Torvalds n'avait de boule de cristal pour savoir que les cpu auront plusieurs cœurs.

Il a dit cette célèbre phrase en 2001, quand les premiers processeurs à deux cœurs sont sortis : les IBM POWER4. Les systèmes à plusieurs processeurs sont plus anciens encore. Ce qu'il ne pouvait peut-être pas imaginer, c'est que les systèmes multicœurs deviendraient la norme pour tout le monde, pas nécessairement les machines de calcul (là où Linux est maintenant prédominant, mais pas vraiment vers 2001).

Systèmes d'exploitation dans les 500 machines les plus rapides en juin 2001 :



Citation Envoyé par earhater  Voir le message
Yes reprocher une connerie de linus torvald dite il y a 15 ans alors qu'il n'avait même pas les outils pour débugger ces performances n'est pas intelligent

Les outils de débogage ont été créés spécifiquement pour cette publication scientifique, ils n'existaient pas avant que l'équipe ne décide de se plonger dans cette problématique précise. Il n'y a en fait jamais eu de raison de les développer, puisque le problème était censé résolu .
Avatar de FxMacCobra FxMacCobra - Membre du Club https://www.developpez.com
le 17/05/2016 à 7:45
Citation Envoyé par BufferBob  Voir le message
hum, t'es sûr de ça ? il me semble que justement il avait été complètement revu avec la sortie du noyau 2.6 à l'époque, notamment le passage d'un ordonnancement en O(1) au lieu de O(n)

Effectivement, il me semble que c'est entré en vigueur dans entre les versions de noyau 2.6.18 à 2.6.20 mais une évolution eu lieu aussi lors de la 2.6.22 (abandon des listes triées par niveau de priorité pour remplacer par un arbre de recherche rouge et noir).
Il y eu un article dans la revue Linux Magazine France à ce sujet justement à l'époque (mais je ne me rappelle plus du numéro ^^' )

Il est vrai que l'étude de l'ordonnancement des tâches n'est pas aussi trivial qu'il n'y paraît et est encore plus dur à "déboguer" sans des outils très spécifiques.
Toutefois, je trouve que c'est une bonne chose de voir que des gens s'attèlent à la tâche et que le noyau linux va encore gagner en performance.
Avatar de moueza moueza - Membre du Club https://www.developpez.com
le 17/05/2016 à 11:36
Linux+++++ Linus------
L’œuvre dépasse son créateur!
Avatar de Battant Battant - Membre actif https://www.developpez.com
le 18/05/2016 à 18:20
Bonjour,

À mon avis, c'est grâce aux faites que les logiciels y peut être expertisé qu'il a été corrigé par des grands chercheurs.

Est-ce que vous savez si les expertises par des chercheurs universitaires se font sur d'autres logiciels libres ?

Merci pour le renseignement

Salutations
Offres d'emploi IT
Ingénieur système de commande de vol H/F
Safran - Ile de France - Massy (91300)
Architecte / concepteur électronique analogique H/F
Safran - Ile de France - Éragny (95610)
Ingénieur statisticien H/F
Safran - Ile de France - Moissy-Cramayel (77550)

Voir plus d'offres Voir la carte des offres IT
Contacter le responsable de la rubrique Débuter - Algorithmique