Aller plus loin

Conclusions sur le premier exemple

Au terme de l’exercice qui précède, vous devriez être arrivé à une performance de calcul d’un peu moins d’une multiplication 512 bits par cycle.

Un peu moins car à l’heure où ces lignes sont écrites, sur srv-calcul-ambulant, on calcule en réalité deux multiplications en trois cycles. Cela est dû à un problème d’exécution superscalaire appelé “4K aliasing”, dont vous pouvez surveiller l’émergence avec le compteur de performance Intel ld_blocks_partial.address_alias, à considérer en proportion du compteur de chargements mémoire mem_inst_retired.all_loads.

Pour mieux comprendre ce qui se passe, considérons la partie chaude de notre boucle de calcul tel que le CPU la voit, donc au niveau de l’assembleur généré :

vmulps (%rdi,%rax,1),%zmm0,%zmm10
vmovups %zmm10,(%r15,%rax,1)
vmulps 0x40(%rdi,%rax,1),%zmm0,%zmm11
vmovups %zmm11,0x40(%r15,%rax,1)
vmulps 0x80(%rdi,%rax,1),%zmm0,%zmm12
vmovups %zmm12,0x80(%r15,%rax,1)
vmulps 0xc0(%rdi,%rax,1),%zmm0,%zmm13
vmovups %zmm13,0xc0(%r15,%rax,1)
vmulps 0x100(%rdi,%rax,1),%zmm0,%zmm14
vmovups %zmm14,0x100(%r15,%rax,1)
vmulps 0x140(%rdi,%rax,1),%zmm0,%zmm15
vmovups %zmm15,0x140(%r15,%rax,1)
vmulps 0x180(%rdi,%rax,1),%zmm0,%zmm2
vmovups %zmm2,0x180(%r15,%rax,1)
vmulps 0x1c0(%rdi,%rax,1),%zmm0,%zmm4
vmovups %zmm4,0x1c0(%r15,%rax,1)
add    $0x200,%rax
cmp    %rax,%r8
jne    401918 <main._omp_fn.0+0x438>

A chaque étape du calcul, nous lisons des données depuis une adresse mémoire, calculons des résultats, et stockons les résultats à une autre adresse mémoire. Et pour travailler de façon efficace, le CPU voudrait exécuter l’ensemble de ces opérations en parallèle avec une organisation en pipeline : à chaque cycle d’horloge, il doit pouvoir simultanément lire des données pour une itération de boucle N, faire le calcul pour l’itération précédente N-1, et stocker le résultat de l’itération N-2.

Mais ce parallélisme d’instructions opère sous une contrainte importante : il doit produire le même résultat que si le programme avait été exécuté séquentiellement, une instruction à la fois. Et ce même dans le cas tordu où on spécifierait des tableaux d’entrée et de sortie qui se recouvrent.

Dans cette situation, si l’adresse d’écriture à l’itération N, que nous noterons $W(N)$, correspond à une adresse de lecture $R(M)$ pour une itération M > N future de la boucle de calcul, alors cette itération M de la boucle devra attendre que le résultat de l’itération N soit prêt pour s’exécuter. Ce n’est pas un problème si M est beaucoup plus grand que N, car le résultat de l’itération N sera prêt au moment où l’itération M en aura besoin. Mais c’est un problème si M est juste un peu plus grand que N, car cela crée une chaîne de dépendances qui empêche l’exécution parallèle.

Plus formellement, dans notre cas où nous faisons des écritures et lectures mémoire de même taille et bien alignées, ce qui permet d’écarter la question des recouvrements partiel, et où nous avons un pipeline de calcul de longueur 3 (lecture, multiplication, écriture), il y a un problème quand on se retrouve dans la situation $W(N-2)>=R(N)$ avec $\Delta =W(N-2)-R(N)$ petit.

Très bien, me direz-vous, mais pourquoi est-ce que je vous parle de ce cas tordu alors qu’il ne nous concerne clairement pas ici, vu que nous écrivons du code civilisé où les tableaux d’entrée et de sortie ne se recouvrent pas ? Eh bien parce que le CPU ne peut pas malheureusement pas vérifier cette propriété de façon exacte.

En effet, les CPU x86 disposent d’un mécanisme de mémoire virtuelle qui permet à deux pointeurs de valeurs différentes de correspondre à la même adresse physique en RAM. Pour éliminer cette possibilité, il faudrait consulter la table des traductions d’adresse, et cela prendrait bien trop de temps pour notre pauvre ordonnanceur superscalaire qui doit donner son verdict en quelques cycles. Une approximation est donc nécessaire ici.

L’approximation qui est faite, c’est de n’utiliser pour étudier la possibilité d’un recouvrement que les 12 bits de poids faible des adresses mémoire concernées, ceux-ci n’étant pas affectés par le processus de traduction d’adresse sous architecture x86 (qui travaille par blocs alignés de 4 Ko).

Nous ne voulons donc pas seulement avoir $R(N)>W(N-2)$. Nous voulons en fait avoir $R(N)-W(N-2)\equiv \Delta (\mathrm{mod}4096)$ avec $\Delta$ aussi petit que possible sans être nul. Comme nous travaillons en AVX-512, où nos accès mémoire se font par blocs consécutifs de 64 octets, cela revient à dire qu’on veut avoir…

$$\begin{array}{rlr}R(N)-W(N-2)& \equiv 64& (\mathrm{mod}4096)\\ R(N)-W(N)-2\times 64& \equiv 64& (\mathrm{mod}4096)\\ R(N)-W(N)& \equiv 192& (\mathrm{mod}4096)\end{array}$$

Il n’est pas facile de garantir ce genre de propriété sur les adresses mémoires de nos tableaux d’entrée et de sortie quand ils s’agit de deux allocations mémoire séparées dont le placement en mémoire est laissé à la discrétion de l’implémentation de la bibliothèque standard C. Mais on peut se placer dans cette situation en n’allouant qu’un seul gros tableau dont le début servira pour les sorties et la fin pour les entrées, avec un petit peu de padding au milieu pour atteindre l’espacement souhaité entre données d’entrée et de sortie :

const size_t aliasing_stride = 4096 / sizeof(float);
const size_t natural_alignment = amount % aliasing_stride;
const size_t desired_alignment = 192 / sizeof(float);
const size_t padding = (natural_alignment < desired_alignment)
                     ? desired_alignment - natural_alignment
                     : aliasing_stride - natural_alignment + desired_alignment;
//
simd_friendly_vector<float> buffer(2*amount+padding, 0.0);
float* const output = buffer.data();
const float* const input = output + amount + padding;
for (size_t iter = 0; iter < iterations; ++iter) {
    assumeAccessed(input);
    for (size_t i = 0; i < amount; ++i) {
        output[i] = input[i] * 4.2f;
    }
    assumeAccessed(output);
}

Et ceci étant fait, on arrive bien à une multiplication 512-bit par cycle, ce qui est déjà nettement mieux que notre point de départ. Mais au début du TP, j’avais mentionné que notre processeur peut effectuer deux multiplications par cycle. Il nous reste donc encore un facteur 2 de puissance de calcul flottante au niveau du CPU qui n’est pas exploitée par ce programme.

La raison est que notre processeur Cascade Lake ne peut faire qu’une écriture mémoire par cycle processeur. Or nous effectuons une écriture mémoire pour chaque calcul que nous faisons. Nous ne pouvons donc pas effectuer plus d’un calcul par cycle pour ce benchmark.

Donc si on veut des performances de calcul optimales de façon portable, une des contraintes qu’on doit respecter est de faire davantage de calculs par écriture en mémoire.

Pour une petit liste d’autres limites possible à la vitesse d’exécution d’un programme calculatoire, vous pourrez consulter https://travisdowns.github.io/blog/2019/06/11/speed-limits.html après le TP.

Exercice avancé

Si vous êtes en avance et êtes plutôt à l’aise en lecture d’assembleur x86, voici un second exercice qui vous permettra de mieux apprécier les possibilités offertes par perf annotate.

Le programme sum.cpp, qui calcule la somme des éléments d’un tableau de nombres flottants, n’est pas limité par la performance des écritures mémoire. On s’attendrait donc à ce qu’il atteigne une performance 2x plus importante que scale.cpp une fois pleinement optimisé.

Toutefois, dans son état actuel, ce programme s’exécute un peu moins de 13x plus lentement que la version initiale de scale.cpp !

Si l’on passe l’option -ffast-math à GCC, qui autorise des optimisations numériquement instables, le programme s’exécute plus rapidement. Mais pas encore aux performances crêtes du matériel.

Avec l’aide des outils que nous avons vus jusqu’à présent, essayez de comprendre par vous-même…

• Pourquoi les performances du programme de base sont aussi mauvaises.
• Quels changements surviennent dans le code généré lorsque l’option -ffast-math est passée à GCC, et pour quelle raison ces optimisations ne sont pas permises sans cette option.

Ayant éclairci ces points, vous pouvez ensuite essayer de terminer le travail d’optimisation incomplètement effectué par GCC en atteignant les performances crêtes du matériel. Pour cela, vous aurez besoin des deux informations microarchitecturales suivantes :

• Notre microarchitecture CPU ne peut effectuer qu’un seul saut par cycle.
• Deux opérations arithmétiques qui dépendent les unes des autres (ex : le résultat de la première opération est passé en paramètre de la seconde opération) ne peuvent pas être s’exécuter en parallèle.

Si vous souhaitez “pimenter” un peu l’exercice, essayez d’atteindre les performances crêtes du matériel sans avoir recours ni à -ffast-math, ni à des intrinsèques spécifiques à l’architecture x86.