Préchargement de données dans le cache

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 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.

Delphi 6 ou Kylix (1 et 2).
Delphi 2 à Delphi 5 peuvent suffire, 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 est 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.

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

La mémoire cache est en fait divisée en plusieurs parties, encore appelées niveaux. 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 à côté 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 des formes différentes avec les nouvelles CPU.

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 :

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 pointeur 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 :

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 :

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 :

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 pointeur est un multiple de 32.

Si nous utilisons déjà du code Assembleur, 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 :

  @@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;

J'ai réuni tout ceci dans un projet Delphi (sources) qui inclut donc les traitements classiques, 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 cycles CPU par pixel.

Les gains en performances 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 octet 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.
À la vue de ces résultats, le recours à l'instruction Prefetch est intéressant, en particulier vu 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.

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 performances.

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émâché 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 :

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

registre :

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

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

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