Préchargement de données dans le cache

Nous allons voir comme mettre en oeuvre les instructions de préchargement (prefetching en anglais) des caches des microprocesseurs améliorer les performances d'une application.

Article lu   fois.

L'auteur

Site personnel

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Introduction

De nos jours, les microprocesseurs vont bien plus rapidement que la mémoire vive qui leur est associée sur la carte mère. Par exemple, sur le nouveau PC de mon bureau, le microprocesseur a une fréquence de 1,333 GHz contre 133 MHz pour la mémoire. Le microprocesseur ne peut donc demander des informations à la mémoire qu'un cycle sur 10. De plus, la réponse de la mémoire à une requête n'est pas instantanée. Il faut plusieurs cycles pour transférer les données demandées et ceci peut générer des temps d'attente importants pour le microprocesseur, en particulier lorsqu'il y a beaucoup de données à transférer. Pour limiter ces désagréments, les fabricants de microprocesseurs ont introduit de la mémoire cache dans ces derniers. Cette mémoire est plus rapide et répond plus vite aux demandes. Par contre, elle est en quantité plus limitée que la mémoire principale. Pour que cette mémoire soit efficace, faut-il encore qu'elle dispose des bonnes informations. Or comme elle est relativement restreinte en taille, ceci n'a rien d'évident. Il faut donc qu'elle soit alimentée à l'avance avec les bonnes données. Heureusement, en tant que programmeur, vous n'avez, dans un premier temps, pas à vous soucier de cette gestion. Le microprocesseur le fait pour vous, en général en conservant les données qui viennent d'être traitées et qui ont alors une forte probabilité d'être réutilisées à court terme. Néanmoins, dans certains cas, vous savez parfaitement les données dont vous allez avoir besoin et vous aimeriez bien l'indiquer au microprocesseur. C'est par exemple le cas lorsque que vous appliquez un traitement à une image où vous travaillez chaque pixel l'un après l'autre. Nous allons dans la suite de cet article voir comment utiliser les nouvelles instructions de préchargement de cache sur mon petit logiciel de traitement d'image.

II. Prérequis

Delphi 6 ou Kylix (1 et 2)
Delphi 2 à Delphi 5 peuvent suffirent mais c'est laborieux.
Microprocesseur supportant les instructions de préchargement : chez AMD, il faut le 3DNow! (K6-2, K6-3, tout Athlon et Duron) et chez Intel, le SSE (PIII, PIV et Celeron >=533A). Apparemment, les P II et les Celeron<=533 (dont le mien) supportent aussi les instructions de préchargement mais sans en tenir compte. Et je n'ai pas testé pour les Pentiums Pro mais j'imagine qu'il en ai de même.

Le code fourni en exemple doit se compiler avec toutes les versions de Kylix et, pour Delphi, celles supérieures à 3.
Les exemples présentés utilisent les instructions d'Intel et ne fonctionnent pas avec les K6-2 et K6-3. Des modifications mineures permettent de s'adapter à ces microprocesseurs.

III. Liste des instructions

Je vous conseille très fortement de regarder les documentations d'Intel et AMD pour une description complète des instructions.

Mnémonique Action Jeu d'instruction CPU
prefetch préchargement dans les caches, niveau de cache non précisé 3DNow! K6-2, K6-3, tous les Athlons et Duron
prefetchW idem avec écriture par dessus en prévision 3DNow! idem
prefetchT0 préchargement dans le cache de niveau 0 SSE
repris par les Athlons, même ceux qui n'ont pas le support SSE
P III, P IV, Celeron >=533A, Athlon, Duron
prefetchT1 préchargement dans le cache de niveau 1 idem idem
prefetchT2 préchargement dans le cache de niveau 2 idem idem
prefetchNTA préchargement en vue d'une utilisation immédiate idem idem

La mémoire cache est en faite divisée en plusieurs parties, encore appelées niveau. Les niveaux les plus faibles sont les plus proches de la CPU, les plus rapides et généralement les plus petits.
Le niveau 0 est inclus dans le microprocesseur et ne varie pas au sein d'une architecture (même cache de niveau 0 entre le Pentium Pro 200 MHz et le Pentium III Xéon 1 GHz).
Le niveau 1 est proche du microprocesseur, soit sur une puce à coté dans le même boîtier (Pentium II, premiers Athlons), soit sur la même pastille de silicium (on the die).
Le niveau 2, c'était la barrette de mémoire spéciale sur la carte mère pour les K6 qui n'avaient pas de cache de niveau 1 mais ça pourrait revenir sous forme différentes avec les nouvelles CPU.

IV. Mise en oeuvre

Il faut fournir à l'instruction Prefetch une adresse en mémoire. Le microprocesseur se charge alors de ramener la ligne de mémoire correspondant à l'adresse indiquée dans ses caches. La taille d'une ligne dépend de l'architecture du microprocesseur mais ne saurait être inférieure à 32 octets. Il n'est donc pas utile de réaliser un préchargement octet par octet. Une fois tous les 32 octets devrait suffire.
En pratique, pour appeler l'instruction Prefetch, une petite procédure convient très bien :

 
Sélectionnez

procedure Prefetch(p : pointer); register; 
asm 
  prefetchT1 byte ptr [eax] 
end;

Vous n'avez plus qu'à placer dans votre code un appel à cette procédure en fournissant un pointer sur l'adresse voulue.
Il faut noter au passage que cette instruction ne modifie en rien les résultats des calculs futurs, d'où une mise en œuvre peu risquée. Et cette instruction est indicative, c'est-à-dire que le microprocesseur n'est pas obligé d'en tenir compte.

Une première variante peut être de demander un chargement 256 octets en avance (en fait plus loin) plutôt que juste au moment où on en a besoin. Le résultat pour 256 octets d'avance :

 
Sélectionnez

procedure Prefetch(p : pointer); register; 
asm 
  prefetchT1 byte ptr [eax]+256 
end;

Au passage si on dispose d'une ancienne version de Delphi (<=5), il faut fournir directement le code hexadécimal de l'instruction :

 
Sélectionnez

procedure Prefetch(p : pointer); register; 
asm 
  DB $0F,$18,$90,$00,$01,$00,$00 
end; 

Plus de détails sur le codage en binaire à la fin.

Maintenant, observons l'utilisation lors du calcul de l'image négative d'un TBitmap :

 
Sélectionnez

Procedure negatifPre(b:Tbitmap); 
var 
  q : pointer; 
  i, j : integer; 
  procedure Prefetch(p : pointer); register; 
  asm 
  {$IFDEF VER140} 
    prefetchT1 byte ptr [eax]+256 
  {$ELSE} 
    DB $0F,$18,$90,$00,$01,$00,$00 
  {$ENDIF} 
  end; 

begin 
  b.PixelFormat:=pf32bit; 
  for i:=b.height-1 downto 0 do 
  begin 
    q:=b.ScanLine[i]; 
    for j:=0 to b.width-1 do 
    begin 
      if integer(q) mod 32=0 then // tout les 32 octets, on fait un préchargement 
        prefetch(q); 
      integer(q^):=not integer(q^); 
      inc(integer(q),4); 
    end; 
  end; 
end;

Comme nous travaillons avec scanline, nous avons directement un pointeur sur les données que nous traitons et nous réalisons l'appel à Prefetch chaque fois que ce pointer est un multiple de 32.

Si nous utilisons déjà du code Assembler, l'utilisation de Prefetch est un peu plus compliquée et nécessite en particulier de disposer d'un registre de libre pour pouvoir tester si le pointeur voulu est multiple de 32. Dans le code suivant, le registre EAX contient l'adresse (issue de scanline) des données à lire. Nous commençons par transférer EAX dans ECX puis nous testons si ECX est multiple de 32. Si c'est le cas, nous utilisons Prefetch à l'adresse de EAX augmenté de 256 octets :

 
Sélectionnez

  @@boucle: 
    mov ECX,EAX    // EAX est l'adresse de lecture 
    and CL,$1F     // si c'est un multiple de 32 (test après transfert dans ECX) 
    jnz @@suite 
  {$IFDEF VER140} 
    prefetchT1 byte ptr [eax]+256 // alors on fait un préchargement 
  {$ELSE} 
    DB $0F,$18,$90,$00,$01,$00,$00 
  {$ENDIF} 
  @@suite: 
    movq mm0,[EAX] // on prend les pixels par 2 
    pxor mm0,mm2 // revient à faire un NOT 
    movq [EAX],mm0 // on renvoie les pixels 

    add eax,8  // avance de deux pixels 
    dec edx 
    jnz @@boucle 
  end;

V. Résultats

J'ai réuni tout ceci dans un projet Delphi ( sources ) qui inclut donc les traitements classique, avec préchargement, MMX et les deux couplés. J'ai aussi rajouté une unité pour la détection des capacités du microprocesseur. J'ai réalisé quelques mesures de performances sur un Athlon 1,333 GHz couplé à de la mémoire SDRAM PC 133 sous Suse 7.1, kernel 2.2.19. L'image utilisée pour les tests mesurait 1280x960 pixels. Et j'ai rapporté les temps de calcul en nombre de cycle CPU par pixel.

Temps (Cycle/Pixel) Négatif Niveau de gris Flou
Classique 19,8 33,0 192
Préchargement 14,0 22,5 192
Gain 30 % 32 % 0 %
MMX 15,0 24,6 25,8
MMX avec préchargement 13,7 14,1 16,8
Gain 9 % 43 % 35 %

Les gains en performance sont intéressants, pouvant atteindre 40 %. Ou encore, votre code optimisé pour le préchargement serait aussi efficace sur un microprocesseur à 1 GHz que le code de base sur la même CPU à 1,666 GHz.
Les mesures ci-dessus sont pour PrefetchT1. Les résultats sont similaires avec toutes les autres variantes de Prefetch. De là à penser qu'AMD a utilisé la même implémentation pour toutes variantes ...
J'ai aussi fait varier la valeur de l'avance au préchargement. Une avance de zéro octets conduit à un gain nul. Les performances s'améliorent ensuite jusqu'à une avance de 256 octets avant de diminuer progressivement. Enfin, comme l'Athlon a des lignes de cache de 64 octets, j'ai essayé de ne faire le préchargement que tous les 64 octets, sans différence sur le temps d'exécution.
A la vue de ces résultats, le recours à l'instruction Prefetch est intéressant, en particulier vue sa facilité de mise en œuvre, par comparaison avec le MMX, par exemple. Parmi les limitations, l'écriture de multiples versions de son code, avec et sans prefetching, est un obstacle, en particulier pour la maintenance. Soit on supporte les instructions Intel et on oublie les K6-2 et K6-3, soit on supporte les instructions AMD et on oublie les P III et P IV.
Dans tous les cas, il faut deux versions avec détection automatique de la CPU pour choisir la bonne. Ou alors, on supporte tout et il faut trois versions. Mes tests n'ont porté que sur l'Athlon. Peut-être qu'avec le P III ou le P IV, l'avance de 256 octets n'est pas optimale. Pour terminer, on pourrait faire un code différent en fonction de la taille des lignes de cache (64 octets pour l'Athlon, 128 pour le PIV). On peut facilement se retrouver avec cinq versions et devoir en ajouter une à chaque nouvelle architecture.

VI. Conclusion

La mise en œuvre des instructions de préchargement est assez facile avec D6/Kylix, aux réserves précédemment énoncées près, et procure des gains significatifs de performance.

Annexe : Codage en binaire

Si vous disposez d'une ancienne version de Delphi (inférieure ou égale à 5), les instructions de préchargement ne sont pas reconnues par le compilateur. Néanmoins, vous pouvez toujours fournir le code binaire correspondant, le compilateur l'intégrera sans problème dans votre exécutable. Vous devez par contre lire attentivement les documentations d'Intel et AMD pour construire la correspondance binaire. Je vous ai prémaché le travail en regardant le code généré par Kylix dans la fenêtre CPU.

prefetch byte ptr [eax]+256
devient
DB $0F, $0D, $80, $00, $01, $00, $00

DB indique qu'on va fournir du code binaire

  1. $OF est commun à toutes les instructions prefetch
  2. $0D pour AMD (prefetch et prefetchW), $18 pour Intel (prefetchT0, prefetchT1, prefetchT2, prefetchNTA)
  3. le troisième octet se décompose comme suit :
1 0 0 ii rrr
décalage ? ? instruction registre

décalage : si on rajoute un décalage de l'adresse, ce bit doit être à 1 instruction :

prefetch 0
prefetchW 1
prefetchNTA 0
prefetchT0 1
prefetchT1 2
prefetchT2 3

registre :

EAX 0
EBX 3
ECX 1
EDX 2

(4) à (7) : décalage sur 32 bits si il existe.

Pour finir une liste d'exemple plutôt que de grands discours :

prefetch byte ptr [eax]
DB $0F,$0D,$00
prefetcht2 byte ptr [eax]+256
DB $0F,$18,$98,$00,$01,$00,$00
prefetch byte ptr [eax]+256
DB $0F,$0D,$80,$00,$01,$00,$00
prefetchnta byte ptr [eax]+256
DB $0F,$18,$80,$00,$01,$00,$00
prefetchW byte ptr [eax]+256
DB $0F,$0D,$88,$00,$01,$00,$00
prefetch byte ptr [ecx]+256
DB $0F,$0D,$81,$00,$01,$00,$00
prefetcht0 byte ptr [eax]+256
DB $0F,$18,$88,$00,$01,$00,$00
prefetch byte ptr [edx]+256
DB $0F,$0D,$82,$00,$01,$00,$00
prefetcht1 byte ptr [eax]+256
DB $0F,$18,$90,$00,$01,$00,$00
prefetch byte ptr [ebx]+256
DB $0F,$0D,$83,$00,$01,$00,$00

Code source

Le code source (10 ko)
Le fichier exécutable (410 ko) généré avec D6.

Liste de mes articles :
Types énumérés, intervalle et ensemble
MMX avec Delphi 6 / Kylix
Préchargement de données dans le cache
MMX ( 2 ) avec Delphi 6 / Kylix
Instructions SIMD sur les réels
Internationaliser un projet Delphi
Installer D6 sous Windows 95
Tramage d'une image
Coder le PNG soi-même
Utiliser LibTiff avec Delphi
Ecrire une UDF FireBird avec Kylix

Ce document est issu de http://www.developpez.com et reste la propriété exclusive de son auteur. La copie, modification et/ou distribution par quelque moyen que ce soit est soumise à l'obtention préalable de l'autorisation de l'auteur.