linusmag

Après d'intenses débats, le parlement français vient d'inscrire pour la première fois dans la loi la priorité au logiciel libre pour un service public, avec l'adoption du projet de loi enseignement supérieur et recherche.

Cette disposition avait été introduite par le Sénat, puis confirmée fin juin 2013 par la commission mixte paritaire (CMP) qui s'était réunie pour réexaminer les dispositions votées non conformes dans les deux chambres (Assemblée nationale et Sénat). De nombreuses personnes s'étaient mobilisées suite à l'appel de l'April pour contacter les députés et sénateurs membres de cette CMP pour que la disposition en faveur du logiciel libre soit conservée.

L'Afdel et le Syntec numérique ont tenté de s'opposer à cette disposition notamment en arguant de prétendues « difficultés juridiques ». L'Inria a rejoint récemment le lobby contre la disposition en faveur du logiciel libre, générant plusieurs réactions dont l'Aful, François Pellegrini et des personnels de l'Inria. En contact avec les parlementaires et le gouvernement, l'April leur a communiqué une analyse sur la validité juridique d'une disposition législative donnant la priorité au logiciel libre.

Après le Sénat le 3 juillet 2013, l'Assemblée nationale a finalement adopté le 9 juillet 2013 le projet de loi relatif à l'enseignement supérieur et à la recherche. Le texte n'attend plus désormais que sa promulgation par le Président de la République.

L'article 9 du projet de loi précise que :

    II. – Au même code de l’éducation, il est rétabli un article L. 123-4-1 ainsi rédigé :

    « Art. L. 123-4-1. – Le service public de l'enseignement supérieur met à disposition de ses usagers des services et des ressources pédagogiques numériques.

    « Les logiciels libres sont utilisés en priorité. »

• site:korben.info - Retourne tous les flux RSS d'un site
• tech site:nytimes.com - Pour trouver tous les flux RSS en rapport avec un sujet précis sur un site donné.
• allintitle:revision3 - Pour trouver les podcasts de Revision3
• etc.

Il y a un bail, j'avais dit que je voulais un jour parler des architectures haute-performance, et de leur potentiel futur. Je me lance donc ici, en espérant que certains se permettront de me corriger là où j'aurai fait des erreurs (sans doute nombreuses).

Je vais diviser ces explications en trois parties. La première (qui suit juste après) va juste faire un rappel sur les architectures « séquentielles » de base. La deuxième partie (à venir très bientôt) s'occupera de décrire les systèmes multi-processeurs et multi-cœurs, ainsi que la raison de leur existence. J'en profiterai pour aussi expliquer les problèmes récurrents liés à l'exploitation de systèmes haute-performance. La dernière partie parlera des efforts effectués en ce moment pour fabriquer les supercalculateurs du futur (disons à l'horizon 2020-2025).

Sommaire

• Micro-architecture de base d'un micro-processeur
  • Le RISC, c'est bien
  • Tout ça fonctionne impec, à une condition…
  • Faites-moi le plein de super !
  • Ce dont je ne parlerai pas
  • Exploiter la localité des données
    • Localité temporelle
    • Localité spatiale
  • Spéculer sur le chargement des données
• Conclusions

Micro-architecture de base d'un micro-processeur

Le RISC, c'est bien

La plupart des architectures qui nous intéressent sont soit de type RISC (Reduced_instruction_set_computer), soit de type Very Long Instruction Word (VLIW). Bien qu'Intel garde (pour des raisons de compatibilité ascendante) un jeu d'instruction CISC (Complex Instruction Set Computer), en pratique, chaque instruction est ensuite décomposée en micro-instructions qui suivent les principes de RISC.

La plupart des processeurs traitent les données dans l'ordre qui suit :

Instruction Fetch → Instruction Decode → Execute → Memory → Write Back

En d'autres termes : on cherche la prochaine instruction à exécuter (Instruction Fetch, IF) ; puis on la décode (Instruction Decode, ID) ; on l'exécute (EX); si besoin on accède à la mémoire (Mem) ; et enfin on écrit le résultat (soit en mémoire, soit dans les registres).

L'intérêt de ce découpage par étages (en pipeline) est qu'on peut récupérer la prochaine instruction à exécuter pendant qu'on décode celle qui a été récupérée au cycle précédent, et qu'on exécute celle qui est venue encore avant. Ainsi l'exécution de 1000 instructions dans un pipeline de longueur n va prendre 1000+n instructions. Les cinq étages précédemment décrits sont les étages de base d'un processeur RISC. Certains processeurs ont eu jusqu'à 33 étages (comme le Pentium 4 par exemple). De nouveaux étages peuvent être introduits pour la multiplication et l'addition entières par exemple. Les unités de calcul flottant peuvent aussi nécessiter l'addition d'étages additionnels.

Tout un tas d'optimisations existent à ce niveau (si je n'ai pas besoin d'accéder à la mémoire par exemple, je peux simplement « sauter » l'étage mémoire du pipeline pour aller directement écrire les résultats dans les registres).

Cette utilisation d'un pipeline est cruciale. Avant, l'utilisation de jeux d'instructions CISC était nécessaire pour deux raisons :

1. La mémoire des machines étant extrêmement limitée, proposer un ensemble d'instructions qui permette d'effectuer plusieurs opérations en une permettait de gagner en concision lors de l'écriture du code, et de gagner de précieux octets dans le programme.
2. Il n'y avait pas réellement de pipeline comme expliqué précédemment. Par contre, chaque instruction CISC était optimisée pour prendre le moins de temps possible.

Tout ça fonctionne impec, à une condition…

L'approche RISC décrite au-dessus permet de plus ou moins garantir l'exécution d'une opération par cycle. Enfin, dans le meilleur des cas. En pratique, un programme a besoin de pouvoir emprunter des chemins différents en fonction des paramètres. Et donc, il doit être possible pour un programme de « sauter » dans une autre partie du programme (oui, on parle bien d'un if … else …).

Ici, l'exécution au niveau du pipeline est problématique : puisque le if nécessite de savoir si la condition évaluée est vraie, alors il faut:

1. Évaluer la condition
2. Vérifier sa valeur de vérité (vrai/faux)
3. Potentiellement effectuer le branchement vers la partie du programme concernée.

Visiblement, le programme ne peut pas continuer à tourner tant que ces trois étapes ne sont pas accomplies. Et du coup, le pipeline est « bloqué » (« stalled » en anglais). Pas de panique, des gens plutôt malins ont trouvé une réponse à ceci : on va prédire quelle branche de la conditionnelle sera prise. On va appeler ça de la prédiction de branchement, et le mécanisme qui la met en œuvre un prédicteur de branchement. Le fonctionnement est plutôt simple, et c'est bien pour ça qu'il est possible de mettre un mécanisme pareil directement dans le matériel. En gros, le prédicteur va faire un choix arbitraire au début, par exemple tous les ifs sont prédits pris (c'est-à-dire que si on rencontre un if, on considère que la condition qu'il évalue sera considérée vraie par défaut).

Grâce à cela, on n'a pas besoin d'attendre que l'évaluation se termine : on continue l'exécution comme si de rien n'était. Évidemment, l'évaluation de la condition doit être terminée avant que les instructions qui suivent le block if/else et qui ont été exécutées finissent par être réellement effectives.

Deux cas de figure se posent :

1. La prédiction était juste, et on n'a rien à faire. Les instructions sont réellement effectuées (« retired » en Anglais).
2. La prédiction était fausse, et il faut purger l'intégralité des étages du pipeline qui suivent le branchement, puisque les résultats qui en découlent sont faux, eux aussi.

Sans trop entrer dans les détails, les prédicteurs de branchements sont mis en œuvre grâce à une machine à états et une petite mémoire. Pour chaque instruction de branchement conditionnel, la mémoire se souvient de l'adresse du if, puis détermine si la condition sera « vraie », « plutôt vraie », « plutôt fausse », ou « fausse » (je simplifie un maximum bien entendu). On part d'un extrême (vrai ou faux). Cette méthode (et ses améliorations) fonctionne plutôt bien pour deux raisons principalement. La première est le fait que prédire que le branchement conditionnel d'une boucle est toujours pris est payant en règle générale (la prédiction est fausse uniquement si la boucle est terminée). La deuxième est que très souvent, les "motifs" d'exécution ("patterns" en anglais) sont similaires d'une exécution d'un programme à une autre. Par exemple, si un if est pris 7 fois sur 10 dans un programme à cause de la nature du programme, le prédicteur de branchement, bien qu'agnostique en ce qui concerne le programme lui-même, aura malgré tout fait gagner un temps précieux en termes d'exécution au final.

Il existe une autre façon de faire : faire de la spéculation de contrôle, via l'utilisation de prédicats. C'est par exemple une approche qu'on retrouve dans les processeurs Itanium, un processeur superscalaire et VLIW produit par Intel, ou certaines versions des processeurs ARM (Architecture_ARM).

Le principe est simple : lorsqu'un branchement conditionnel est rencontré, on peut « prédicater » (barbarisme couramment utilisé dans les labos info) les branches du [if]. Par exemple, quelque chose du genre :

if ( condition1:p0 )
    [p0] instruction1
    [p0] instruction2
else
    [!p0] instruction3
    [!p0] instruction4

Les instructions 1 à 4 vont toutes être exécutées. Cependant, leurs résultats ne seront réellement écrits qu'une fois la condition du if évaluée. Cette façon de faire permet de garantir une absence de stalls, et est souvent utilisée dans les processeurs VLIW (dont je ne parlerai pas trop ici, mais qui en gros prennent des « super-instructions » en entrée, composés de plusieurs instructions, par exemple : { load r1 = @X; load r2 = @X+4; r3 = r5 * r6 })

L'approche de la prédication est très intéressante car en gros le compilateur ou le programmeur expert peuvent décider de ce qu'il faut prédicater ou pas.

Cependant, le bilan énergétique peut être désastreux (après tout, toutes les instructions sont exécutées, qu'elles soient utiles ou pas !).

Je crois qu'on a fait le tour des processeurs scalaires (en fait, la prédication est un mécanisme plutôt utilisé dans le type de processeurs qui va suivre).

Faites-moi le plein de super !

Tout ceci concerne un micro-processeur scalaire, avec un seul pipeline d'instruction. Rien n'empêche de dupliquer les pipelines. C'est d'ailleurs ce qui est fait dans beaucoup de micro-processeurs modernes. On parle de processeur superscalaire.

Ce genre de processeurs a besoin de correctement réserver les resources dont il a besoin : additionneur pour calculer une adresse, UAL (unité arithmétique et logique) pour des calculs sur entiers, unité de calcul flottant (FPU), etc. Il peut bien y avoir deux pipelines, mais cela ne signifie pas qu'il y a deux UAL par exemple… De même, l'accès à la mémoire depuis un micro-processeur n'est peut-être possible que via un seul port, et du coup, si un chargement mémoire (load) doit être effectué dans un pipeline, il est parfaitement possible qu'un autre chargement soit bloquant dans l'autre pipeline. Dans un contexte d'exécution dans l'ordre (in order) la qualité du compilateur/programmeur expert est déterminante pour obtenir un programme qui s'exécute au moins (en fait, il s'agit de correctement ordonnancer le flot d'instructions statiquement).

Il existe plusieurs façon de régler le problème au niveau matériel. L'une d'entre elles est de passer par une méthode nommée scoreboarding. Pour faire simple, lorqu'une instruction écrit dans un registre donné (disons r1), alors l'état de r1 est marqué « occupé ». Les instructions suivantes sont lues ainsi que leurs dépendances sur les différentes ressources : lorsqu'une instruction qui veut lire r1 est émise, elle est placée dans une file d'attente, tant que r1 est « occupé ». Lorsque r1 est de nouveau libre (i.e. l'instruction qui écrit dans r1 est complétée et a signalé le scoreboard), alors l'instruction est « remise en place » dans le flot et peut s'exécuter.

Une autre méthode (bien plus connue) est l'exécution dans le désordre, appelée out-of-order execution en Anglais (OoO). Dans cette méthode, il existe un ensemble de « registres fantômes » ( shadow registers en Anglais). L'idée est de renommer les registres dont les instructions ont besoin, afin de réduire un maximum les dépendances entre instructions. Par exemple :

a = 10;
// ...
b = a * 3;
// ...
a = 0;
// ...
c = a + 12;

Si on suit un schéma de dépendance strict, il existe une anti-dépendance (une dépendance de nommage) entre la première utilisation de a et la deuxième, alors qu'en pratique leur utilisation est complètement indépendante.

En renommant a pour sa seconde utilisation, on permet l'exécution en parallèle de l'affectation à b et c :

a  = 10 || a1 = 0;
// ...
b = a * 3 || c = a1 + 12

L'objectif n'est pas d'expliquer l'intégralité de l'algorithme de Tomasulo ou du renommage de variables pour faire disparaître les fausses dépendances, mais ceci devrait permettre de donner une idée de ce que fait un moteur OoO. Une fois tous ces renommages effectués, il faut ensuite réordonner le flot d'instruction. C'est à cela que sert le « reordering buffer », qui comme son nom l'indique, sérialise le résultat des instructions, écrit dans les « vrais » registres (pour ensuite pouvoir écrire en mémoire par exemple), etc.

Ce dont je ne parlerai pas

Il existe tout un tas d'autres mécanismes qui existent pour augmenter la performance d'un programme. Certains sont destinés à être utilisés par le compilateur; d'autres par le programmeur.

Un exemple de mécanisme à la fonctionnalité identique sur plusieurs architectures différentes, et avec un usage différent est celui des registres rotatifs. Pour faire simple : il s'agit d'un ensemble de registres « glissants » qui sont automatiquement renommés lorsque certaines instructions sont utilisées. Les processeurs de type SPARC utilisent ces registres pour accélérer les changements de contexte entre threads/processus. Lorsqu'un thread est interrompu par le système, nul besoin de sauvegarder ses registres en mémoire (qui est une opération coûteuse) : si une fenêtre de registres est disponible, il suffit de faire « glisser » la fenêtre courante vers la nouvelle fenêtre, et y placer les informations du nouveau thread/de la nouvelle fonction. Encore mieux : si le thread à exécuter était déjà interrompu, il suffit de reglisser vers sa fenêtre (en une instruction ou presque).

L'Itanium utilise le même concept de registres rotatifs pour une autre raison : l'optimisation de boucles via l'utilisation de la technique de pipeline logiciel. Je ne vais pas m'étendre sur la technique. Disons simplement qu'elle permet de maximiser les ressources disponibles et de recouvrir tout un tas de latences (notamment mémoire).

J'ai jusqu'ici soigneusement éviter de parler de la mémoire en détails. Du point de vue du programmeur séquentiel, la mémoire est un ensemble de « cases » ayant un identifiant (une adresse) dans lesquelles on peu lire ou écrire des valeurs. La mémoire est bien entendu nécessaire car les registres sont en quantité limitée (32 ou 64 en moyenne pour les processeurs récents).

En pratique, malgré les progrès effectués pour produire de la mémoire rapide (on en est quand même à la DDR5…), il y a un fossé entre la fréquence d'horloge des micro-processeurs modernes (qui souvent tourne autour de 2 ou 3 GHz) et celle de la mémoire (entre 0,8 et 1,3 GHz). Pour réduire l'impact de la latence due aux accès à la mémoire principale (DRAM), on a logiquement décidé d'insérer des niveaux de mémoire plus rapides. On retrouve la fameuse « antémémoire » que tout le monde appelle « mémoire cache ».

Exploiter la localité des données

La mémoire cache permet d'obtenir deux types d'optimisations :

Localité temporelle

En supposant qu'un ensemble de mots mémoire vont être accédés séquentiellement (ou avec un pas régulier et relativement petit), alors charger une ligne de cache (souvent de 32 ou 64 octets dans les processeurs récents) permet de payer le coût du transfert mémoire (depuis la DRAM vers le cache) une seule fois, mais d'avoir plusieurs mots mémoires disponibles une fois le chargement effectué. Ainsi, si une boucle C suit le schéma d'accès mémoire suivant :

for (int i = 0; i < N-2; i += 2) {
    a[i+2] = f(i);
}

Alors, un entier (généralement 4 octets sur des architectures modernes) sera chargé ainsi (je fais une super simplification avec un pseudo-langage assembleur ultra pas optimisé) :

    ; on considère que r0 vaut toujours 0
    mov r10, $N ; R10 = N
    mov r11, r0 ; i = 0 
    mov r12, @a
    cmp r11, r10
    jge EXIT
LOOP:
    ; Convention à la con : r2, ..., r6 sont les six premiers arguments 
    ; passés aux fonctions ... le reste est passé sur la pile
    ; r1 contient la valeur de retour des fonctions
    mov r2, r11      ; premier argument de f()
    call f           ; r1      = f(i)
    mul r2, r11, $4  ; r2      = i * 4
    add r5, r12, r2  ; calcul de l'adresse dans a: r5 = (a + i * 4)
    store [r5], r1   ; a[i+2]  = r1
    add r2, r2, $2   ; i      += 2
    cmp r11, r10
    jlt LOOP
EXIT:
    ; Suite du programme

Ainsi, si on a une ligne de cache de 64 octets, il y a 16 entiers de 4 octets directement accessibles par une boucle. Du coup, plutôt que charger (et payer) N/2 fois le coût de chargement depuis la DRAM, on va envoyer 16 mots (dont 8 seulement seront utiles ici). Je passe sur les détails architecturaux, mais grâce à la mise en cache, on va passer de latences de plusieurs dizaines voire centaines de cycles (généralement entre 50 et 300 en fonction des architectures), tout à coup on ne paie qu'entre 2 et 10 cycles par accès quand la donnée est située dans le cache.

Bref. Les caches permettent de recouvrir les latences lors des accès mémoire et d'accélérer significativement l'exécution d'un programme. C'est ce qu'on appelle la localité temporelle : payer le coût de chargement d'une ligne de cache permet d'accéder à a[i+2], a[i+4], …, a[i+14], et donc alors que le « temps » avance (c'est-à-dire l'indice de boucle est incrémenté), les données restent « proches » du processeur.

Localité spatiale

La localité spatiale est le fait de pouvoir réutiliser plusieurs mots de la même ligne de cache d'affilée. Je ne m'étends pas dessus, mais en gros, dans un code, si on arrive à réutiliser a[i] plusieurs fois, alors on économise en « espace » (en nombre de registres ou de lignes de cache à utiliser).

À noter qu'il existe aussi des caches pour stocker les instructions les plus fréquemment utilisées, ou même des caches unifiés (qui contiennent code et données).

Reste un problème : lorsqu'une donnée ne se trouve pas en cache (un défaut de cache, communément appelé « cache miss »), alors on paie de nouveau le chargement de 64 octets pour chercher la prochaine ligne de cache, au prix fort.

Spéculer sur le chargement des données

Pour résoudre le problème évoqué précédemment, les concepteurs de micro-processeurs ont ajouté un mécanisme supplémentaire : les préchargeurs de mémoire. En gros, si on connaît les caractéristiques du matériel (latence pour accéder à la DRAM, taille des lignes de caches, etc.), et si le motif d'accès à la mémoire est suffisamment régulier, alors un bon programmeur/compilateur peut insérer des instructions de prefetch aux endroits stratégiques (généralement on en insère plusieurs avant le début d'une boucle, puis juste au début d'une itération). C'est ce qu'on appelle le préchargement logiciel (software prefetching). On peut la retrouver sur la plupart des processeurs modernes (ARM, x86, SPARC, POWER/PowerPC…).

Il existe une variante mise en œuvre de façon purement matérielle, logiquement appelée préchargement matériel (hardware prefetching). Il existe plusieurs variantes, aussi je vais en détailler deux, actuellement utilisées au moins dans certains processeurs x86. La première est appelée par Intel « adjacent line prefetching » (préchargement de ligne adjacente). Lors d'un cache miss, une ligne de cache est (logiquement) chargée depuis la mémoire principale. Cette méthode s'assure que la ligne suivante est chargée elle aussi, car statistiquement il y a de fortes chances que le programme en aura besoin lui aussi. À ma connaissance, tous les processeurs x86 (AMD, Intel) mettent en œuvre cette technique. La seconde technique est au moins utilisée dans les processeurs Intel (je ne me suis pas renseigné pour AMD). Il s'agit du stride prefetcher (préchargement par pas). L'idée est simple : le stride prefetcher retient en mémoire une liste des N dernières adresses accédées par le processeur. Si, pour une adresse donnée, on y accède par pas de K (comme mon a[i+2] de tout à l'heure), alors le prefetcher détectera le motif d'accès, et s'occupera de précharger correctement les lignes de cache correspondantes au pas. Le stride prefetcher est limité aux accès au sein d'une même page mémoire (4 kio ou 4Mio sur x86).

Conclusions

Voilà, j'ai plus ou moins fini mon rappel rapide des micro-processeurs séquentiels. Il faudrait aussi parler des instructions vectorielles (MMX, Streaming SIMD Extensions, AltiVec, etc.), mais ça prendrait encore quelques paragraphes et j'ai la flemme. La prochaine fois, on passe au multi-processeur et multi-cœur !