goog_ilp
Contexte & Introduction
Il est très regrettable de voir le parallélisme d'instructions (ou ILP pour "Instruction Level Parallelism") marginalisé par les développeurs. Cette marginalisation, est souvent, due au trop de confiance qu'on accorde au compilateur (en se suffisant par des options lambda genre -Ox, ou -fast). Le fait est que les compilateurs actuels ne sont pas en mesure, dans la majorité des cas, de détecter automatiquement des parties du code susceptibles d'être accélérées, et de mettre en œuvre cette accélération.
Nous l'avons appris à l'école, nous ne cessons pas de nous le murmurer. Qui sait ?! Nous le répéterons, peut être, plus tard à nos disciples.
Les solutions matérielles les plus connues, et les plus élémentaires, intégrées dans les CPU modernes, et qui permettent de faire de l'ILP sont, sans doute, le pipeline matériel et le superscaling (j'invente ce terme pour décrire les processeurs superscalaires pour des soucis de confort de rédaction).
Le premier permettant une exécution chevauchée des instructions en exploitant les étages libres du pipeline (chargement d'instruction, décodage, recherche opérandes, évaluation, écriture mémoire), ce qui permet de débiter, dans un cas idéal, une instruction par cycle. Alors qu'elle en nécéssite, au moins (pour être simpliste), quatre (un par étage).
Le superscaling est purement et simplement la duplication des unités de calculs. Ce qui permet d’exécuter plusieurs instructions entières et/ou flottantes en parallèle.
L’exécution en désordre réordonnance le flux d'instructions pour maximiser le potentiel parallèle. Vous l'avez compris! les constructeurs du matériel ne font (faisaient?) pas confiance en la qualité des codes générés par les compilateurs.
Les branchements provoquent, au moins, les désastres suivants (hormis les problèmes de localité spatiale et temporelle):
Le premier problème acceler8 était parallélisable à volonté et à tous les niveaux. Je mets, ici, deux exemples qui représentent un pattern récurrent dans mon implémentation:
Ex1:
res=0;
for(i=0;i<N;i++)
res += coef[i]+power[k][i];
Ex2:
for(i=0;i<N;i++)
coef1[i] = coef2[i];
res=0;
for(i=0;i + U < N;i+=U){
res += coef[i]+power[k][i];
res += coef[i+1]+power[k][i+1];
…
res += coef[i+U-1]+power[k][i+U-1];
}
// épilogue du unroll
for( ; i < N;i++)
res += coef[i]+power[k][i];
Le nombre de branchements est divisé par U. Un unroll de degré N (si N est connu à la compilation) provoquera un aplatissement complet de la boucle, aucun branchement ne sera généré, mais la taille du code sera conséquente (pour N très grand).
Mon objectif est d'attirer l'attention sur l'importance de l'ILP, je ne présente que succinctement les éléments matériels. Je donne des solutions simples à des cas pratiques inspirés de l'implémentation de la solution smallbrain. Pour plus de détails, rien ne vaut dieu (comprendre google), et la documentation officielle.
Les branchements ont des effets néfastes sur l'ILP
Nous l'avons appris à l'école, nous ne cessons pas de nous le murmurer. Qui sait ?! Nous le répéterons, peut être, plus tard à nos disciples.
Les solutions matérielles les plus connues, et les plus élémentaires, intégrées dans les CPU modernes, et qui permettent de faire de l'ILP sont, sans doute, le pipeline matériel et le superscaling (j'invente ce terme pour décrire les processeurs superscalaires pour des soucis de confort de rédaction).
Le premier permettant une exécution chevauchée des instructions en exploitant les étages libres du pipeline (chargement d'instruction, décodage, recherche opérandes, évaluation, écriture mémoire), ce qui permet de débiter, dans un cas idéal, une instruction par cycle. Alors qu'elle en nécéssite, au moins (pour être simpliste), quatre (un par étage).
Le superscaling est purement et simplement la duplication des unités de calculs. Ce qui permet d’exécuter plusieurs instructions entières et/ou flottantes en parallèle.
L’exécution en désordre réordonnance le flux d'instructions pour maximiser le potentiel parallèle. Vous l'avez compris! les constructeurs du matériel ne font (faisaient?) pas confiance en la qualité des codes générés par les compilateurs.
Les branchements provoquent, au moins, les désastres suivants (hormis les problèmes de localité spatiale et temporelle):
- Le vidage complet du pipeline,
- Une sous-exploitation des multiples unités de calculs disponibles. Et cela pendant toute la durée d’exécution du branchement.
- Directif : en lui précisant ce qu'il faut faire.
- Pédagogique: en écrivant le code d'une manière à lui simplifier la tâche.
Exemples de motivation : smallbrain
Le premier problème acceler8 était parallélisable à volonté et à tous les niveaux. Je mets, ici, deux exemples qui représentent un pattern récurrent dans mon implémentation:
Ex1:
res=0;
for(i=0;i<N;i++)
res += coef[i]+power[k][i];
Ex2:
for(i=0;i<N;i++)
coef1[i] = coef2[i];
EX1 est une réduction sur res. Des dépendances inter-itérations peuvent être contournées en exploitant les propriétés arithmétiques de l'addition. Ce qui permettera une parallélisation du calcul. Les compilateurs de production actuels en sont incapable pour le moment.
EX2 est complètement parallèle, et peut être paralléliser automatiquement si N est jugé suffisamment important.
Pour mon smallbrain, N valait tout le temps 10 ou 8. Ici pour des soucis de généricités, N vaut une constante symbolique dont la valeur n'est connue qu'à l’exécution. J'appelle une constante symbolique, un scalaire qui ne change pas de valeur dans le scope analysé.
Il est évident que les deux boucles génèrent N instances de branchement conditionnel (i<N), N branchements inconditionnesl, pour N blocs d'instructions utiles. Ce qui revient à évaluer deux branchements pour 4 instructions utiles pour le premier exemple (2 chargements, 2 additions) Ce qui aura un effet néfaste pour le pipeline qui ne sera jamais rempli.
L'UNROLL
L'unroll (je pense qu'on dit aplatissement en français), est la transformation source-à-source la plus élémentaire et la plus pratique. Elle est toujours légale, définie par une constante U appelée: taux d’aplatissement. Cette transformation permet d’exécuter les itérations d'une boucle par paquets de U itérations de la manière suivante (appliquée à EX1):res=0;
for(i=0;i + U < N;i+=U){
res += coef[i]+power[k][i];
res += coef[i+1]+power[k][i+1];
…
res += coef[i+U-1]+power[k][i+U-1];
}
// épilogue du unroll
for( ; i < N;i++)
res += coef[i]+power[k][i];
Le nombre de branchements est divisé par U. Un unroll de degré N (si N est connu à la compilation) provoquera un aplatissement complet de la boucle, aucun branchement ne sera généré, mais la taille du code sera conséquente (pour N très grand).
Faut il le faire à la main?
NON, car cela reviendrait à faire le travail du compilateur. Il y a au moins deux choix pour faire faire la transformation: Les options du compilateur, et les directives de compilation (#pragma). Ici, je ne traite que les options et les pragmas supportés par le compilateur C d'intel.
Les options
-unroll[n] : unroller toutes les boucles quand c'est possible de 'n' itérations. 'n' étant le degré de l'unroll.
-unroll-aggressive : utilise une technique plus aggressive que celle de la première. Ce qui permet d'unroller les boucles qui ne le sont pas *unrollable* avec la première option. Attention, cela ne veut pas dire pour autant que toutes les boucles seront aplaties.
Le pragma:
#pragma unroll(N) : Ce pragma doit être attaché à une boucle 'for'. Unroller la boucle 'for' qui suit le pragma. 'N' est le degré de l'unroll, si absent, icc choisira un degré adéquat.
res=0;
#pragma unroll(8)
for(i=0;i<N;i++)
res += coef[i]+power[k][i];
Option et/ou pragma ? à vous de choisir !
Les options
-unroll[n] : unroller toutes les boucles quand c'est possible de 'n' itérations. 'n' étant le degré de l'unroll.
-unroll-aggressive : utilise une technique plus aggressive que celle de la première. Ce qui permet d'unroller les boucles qui ne le sont pas *unrollable* avec la première option. Attention, cela ne veut pas dire pour autant que toutes les boucles seront aplaties.
Le pragma:
#pragma unroll(N) : Ce pragma doit être attaché à une boucle 'for'. Unroller la boucle 'for' qui suit le pragma. 'N' est le degré de l'unroll, si absent, icc choisira un degré adéquat.
res=0;
#pragma unroll(8)
for(i=0;i<N;i++)
res += coef[i]+power[k][i];
Option et/ou pragma ? à vous de choisir !
Cela est il suffisant?
Malheureusement, NON!
Les boucles doivent être reconnues par le compilateur comme des boucles 'for' (et non pas des 'while' déguisés) pour que la transformation soit faite. Une boucle 'for', est une boucle dont la variable d'induction (de préférence un scalaire) a une borne inférieure, une borne supérieure constante (de préférence un scalaire), avec une incrémentation constante (de préférence +1). En plus de cela, toutes les références de tableaux doivent avoir des indices simples (formule linéaire en fonction de la variable d'induction de la boucle).
Une borne supérieure ou une variable d'induction du genre (ptr->b[c[i]].N) peuvent réduire les analyses du compilateur (ici: l'analyse d'alias et de dépendances) en échec, et tous les efforts d'optimisation avec. Aussi innocente qu'elle puisse parraitre, icc n'arrive pas à vectoriser et/ou unroller cette boucle :
#pragma unroll
for(i=0; i<30;i+=2)
v[i/2] = 0;
Ce problème est résolu dans les récentes versions de GCC (à partir de la 4.1) par ce qu'on appelle la normalisation de boucles. Toute boucle normalisée aura une variable d'induction virtuelle (soit: iv) principale qui a :
Quelques conseils de codage
Et la parallélisation dans tout cela !
--
goog_iceandmagic
PS: le français n'étant pas ma langue natale. Excusez les nombreuses erreurs d'orthographes qui se sont faufiler dans le présent.
Une borne supérieure ou une variable d'induction du genre (ptr->b[c[i]].N) peuvent réduire les analyses du compilateur (ici: l'analyse d'alias et de dépendances) en échec, et tous les efforts d'optimisation avec. Aussi innocente qu'elle puisse parraitre, icc n'arrive pas à vectoriser et/ou unroller cette boucle :
#pragma unroll
for(i=0; i<30;i+=2)
v[i/2] = 0;
Ce problème est résolu dans les récentes versions de GCC (à partir de la 4.1) par ce qu'on appelle la normalisation de boucles. Toute boucle normalisée aura une variable d'induction virtuelle (soit: iv) principale qui a :
- 0 comme borne inférieure.
- +1 comme pas d'incrémentation.
- une borne supérieure constante (for), ou pas (while).
La vectorisation automatique
L'intégration des puces multimédias (ou plus spécifiquement les extensions SSE d'intel) dans les processeurs modernes ouvre de nouveaux horizons pour l'ILP qui sont, cette fois-ci, accessibles aux dévoppeurs. Qu'est ce qui plus beau qu'un arsenal de 8 registres vectoriels (les fameux MMX) de 128bits qui viennent consolider les accumulateurs du CPU. Cela permet de faire des opérations sur un paquet de 4 entiers de 32bits (ou 8 de 16, ou 16 de 8) à la fois … plus fort encore que le superscaling car une seule instruction est chargée, n'est décodée qu'une fois et pour couronner le tout, le CPU est libre. Très pratique pour les petites boucles qui manipule de éléments contigus d'un ou plusieurs vecteurs, à l'image de l'exemple Ex2.
Malheureusement, en plus des contraintes liées à l’écriture de codes précédemment citées. Les indices d'accès aux vecteurs doivent référencer des éléments contigus, dans un sens croissant (condition suffisante mais pas nécessaire). Tout autre schéma d'accès entrainera un échec de vectorisation.
Options et pragmas utiles:
-vec : activer la vectorisation automatique. Cette option semble être incluse par défaut par -fast.
-vec-threshold[n] : 0 <= n <= 100. fixer de taux de confiance accordé aux prédictions statiques réalisées par le compilateur. 0 Toujours vectoriser, 100 ne vectoriser que si le modèle de performances du compilateur assure un gain. Un conseil, méfiez vous des analyses statiques et faite un profile.
-vec-report[n] : volume des messages du compilateur liés à la vectorisation. 0 ne rien reporter, 1 ne reporte que les boucles vectorisées, …, 5 tout reporter avec la raison de l'échec si échec il y a.
-ax<code1>[,<code2> …] : (voir aussi -x) générer, quand c'est possible, des instructions liées appartenant aux jeux <code1>, <code2> … l’intérêt est de spécifier les jeux de la famille SSE. Exemple:
$ icc -vec -vec-report3 -axSSE2,SSE3,SSE4.1 fichier.c
Il vaut mieux se reférer à la section qui parle des intrisics SSE pour avoir une idée sur le jeu d'instructions offert par chaque évolution. Vous allez apprendre, pour l'occasion, à programmer en instrinsics (ce qui ne vous sera pas de grande utilité).
#pragma vector : demande au compilo de vectoriser la boucle 'for' qui suit. Je ne vais pas rentrer dans les détails car cela prendra du temps, et je pense qu'il n'a pas d'intérêt majeur.
#pragma ivdep : Le pragma à tout faire ! Informe le compilateur que la boucle 'for' qui suit n'a pas de dépendances inter-itérations. Cela provoquera le déclenchement d'une optimisation appropriée qui débouche souvent sur une vectorisation ou une parallélisation. A s'en souvenir, et s'en servir sans modération!
Malheureusement, en plus des contraintes liées à l’écriture de codes précédemment citées. Les indices d'accès aux vecteurs doivent référencer des éléments contigus, dans un sens croissant (condition suffisante mais pas nécessaire). Tout autre schéma d'accès entrainera un échec de vectorisation.
Options et pragmas utiles:
-vec : activer la vectorisation automatique. Cette option semble être incluse par défaut par -fast.
-vec-threshold[n] : 0 <= n <= 100. fixer de taux de confiance accordé aux prédictions statiques réalisées par le compilateur. 0 Toujours vectoriser, 100 ne vectoriser que si le modèle de performances du compilateur assure un gain. Un conseil, méfiez vous des analyses statiques et faite un profile.
-vec-report[n] : volume des messages du compilateur liés à la vectorisation. 0 ne rien reporter, 1 ne reporte que les boucles vectorisées, …, 5 tout reporter avec la raison de l'échec si échec il y a.
-ax<code1>[,<code2> …] : (voir aussi -x) générer, quand c'est possible, des instructions liées appartenant aux jeux <code1>, <code2> … l’intérêt est de spécifier les jeux de la famille SSE. Exemple:
$ icc -vec -vec-report3 -axSSE2,SSE3,SSE4.1 fichier.c
Il vaut mieux se reférer à la section qui parle des intrisics SSE pour avoir une idée sur le jeu d'instructions offert par chaque évolution. Vous allez apprendre, pour l'occasion, à programmer en instrinsics (ce qui ne vous sera pas de grande utilité).
#pragma vector : demande au compilo de vectoriser la boucle 'for' qui suit. Je ne vais pas rentrer dans les détails car cela prendra du temps, et je pense qu'il n'a pas d'intérêt majeur.
#pragma ivdep : Le pragma à tout faire ! Informe le compilateur que la boucle 'for' qui suit n'a pas de dépendances inter-itérations. Cela provoquera le déclenchement d'une optimisation appropriée qui débouche souvent sur une vectorisation ou une parallélisation. A s'en souvenir, et s'en servir sans modération!
Quelques conseils de codage
La manière dont vous écrivez vos codes impacte directement les capacités du compilo à l'optimiser. Jusqu'à nouvel ordre, et pour le moment, il vaut mieux :
- Normaliser ses boucles, et choisir des scalaires pour ses bornes et sa variable d'induction. J'ai évoqué le cas GCC plus haut, mais même GCC, aussi sophistiqué qu'il soit, peut ne pas détecter les boucles 'for', notamment en cas de référence par pointeurs.
- Eviter de traverser un vecteur par un poiteur, et toujours privilégier la notation tableau. Les petits malin qui s'amusent à traverser un vecteur par un pointeur ne se rendent pas compte de la diffuculté qu'ils imposent aux compilateurs actuels.
- Eviter les indirections du genre A[B[i]], et les pointeurs d'une manière générale. Les déclarer comme 'const' pour faciliter l'analyse de dépendances.
- Essayer de donner le même indice pour les tableaux dans une même boucle. Eviter ... A[i] op B[i-2] !
- Essayer de ne faire apparaitre qu'une seule dimension d'une table dans une instruction itérée. Ces derniers deux points est une honte pour les compilateurs actuels, cela va être certainement corrigé rapidement.
- Mettre des pragmas adéquats, ils ne coûtent rien.
Et la parallélisation dans tout cela !
Les problèmes liés aux transformations sources-à-sources, la vectorisation, et la parallélisation automatiques sont exactement les mêmes. Et ça se résume en une seule phrase, la précision des analyses de dépendances réalisées. Celles implémentées dans les compilateurs de production actuels sont largement au dessous des attentes, mais cela est entrain de changer.
Option et pragmas:
-parallel
-par-report[n]
-par-num-threads
-par-schedule
#pragma ivdep
Merci pour votre intérêt,
--
goog_iceandmagic
PS: le français n'étant pas ma langue natale. Excusez les nombreuses erreurs d'orthographes qui se sont faufiler dans le présent.