Apprenez à adapter vos données pour accélérer le cache PPC !
Un article de GuruMed.
Sommaire |
De la vitesse bon sang !
ça c'est de la bonne optimisation ! ( par krabob )
Ah ah ! Sur les Amiga classiques avec des extensions PowerPC, vous avez un processeur puissant sur le papier, mais vous avez moins de puissance que vous ne le désiriez avec vos routines. POURQUOI ? parce que le processeur n'est pas tout. Il y a un bus entre lui et la mémoire, mais il y a également des 'mémoires cache' à l'intérieur du processeur : Quand vous accédez à la mémoire (en écriture ou en lecture), les données prennent le bus et celui-ci est lent. Heureusement, la cache garde ce qui a été récemment lu ou écrit et évite des accès inutile à la RAM. Je veux dire si vous écrivez ces lignes de C :
void DoTwoAssignment ( int *somewhereInMemory )
{
int a = *somewhereInMemory ;
int c = *somewhereInMemory ;
}
La deuxième assignation sera exécutée bien plus rapidement que le premier parce que la valeur a été chargée par le bus pendant le premier et les a mis à la fois dans 'a' et dans le cache. Pendant le deuxième assignmement, la valeur a déjà été trouvée dans la cache, donc aucun besoin de la charger encore par le bus lent. Si nous avions :
void Do_A_Write_And_A_Read ( int *somewhereInMemory )
{
*somewhereInMemory =4;
int c = *somewhereInMemory ;
}
La première assignation serait lente, parce que cette fois une valeur est écrite dans la mémoire. En fait le cache va lire cette mémoire et effectuer l'écriture dans le cache. Cette écriture assure donc que cette mémoire est présente pour la prochaine instruction qui devrait être exécutée rapidement. La vrai écriture en ram sera réalisé n'importe quand dans le futur. ( Dans la plupart des cas.) Notez que le comportement du cache n'est jamais visible ( d'ou son nom), : On ne peut pas savoir ce qu'il garde, et vous pouvez parfaitement l'oublier quand vous codez.
Certains s'exclameront que tout le monde est au courant... Oui, mais sur Amigas classiques avec des extensions PowerPC 603 et 604, le processeur est rapide, mais les bus sont incroyablement LENTS : (il n'y a pas de ccache de niveau 2, alors que les pegasos et les AmigaOne en ont.) Ainsi, la différence de vitesse entre un source optimisé pour un cache PPC et un qui ne l'est pas, est ÉNORME.
Mais d'abord jetons un oeil aux descriptions de ces processeurs:
La taille des caches sur les processeurs des amigas
| taille du cache de donnée | taille du cache instruction | Taille du CACHELINE | |
|---|---|---|---|
| G4 | |||
| G3 | 256 KiloOctet | ... | ... |
| PowerPC 604 | 32 KiloOctet | 32 KiloOctet | 32 oct. |
| PowerPC 603 | 16 KiloOctet | 16 KiloOctet | 32 oct. |
| 68060 | 8 KiloOctet | 8 KiloOctet | 16 oct. |
| 68030 | 256 Octets | 256 Octets | 16 oct. |
Que cela signifie-t-il ? Que le cache du PPC 603 se "souviendra" des 16 derniers kiloOctets lu par votre programme. Quand une cache est complétement remplie, elle efface les valeurs les moins utilisées par des neuves. Le Cache de Donnée (data cache) est la cache utilisée pour la mémoire commune. La cache instruction (instruction cache) garde seulement le code exécuté : Ainsi, elle accélère les boucles et les fonctions réutilisées.
Et maintenant la chose importante :
Qu'est ce qu'un Cache Line (ligne de cache) ? C'est le morceau de données vraiment lu ou écrit lors d'un accés. Le fait est, quand vous lisez un simple octet avec un PPC, vous lisez en fait les 32 octets autour de lui, en commençant par l'adresse alignée sur 32 la plus proche ( adresse multiple de 32.), et à partir de ce moment, ces 32 octets sont dans la cache.
Comment utiliser ce savoir pour un effet visuel ?
Prennez un effet de demo classique comme le Rotozoom (aussiconnu comme: rotator ) et faites-le tourner et zoomer sur l'écran : c'est un effet 2D qui fonctionne comme une simple application de texture : une image est déformée. Pour cet effet, 2 zones mémoires sont employés :
- la mémoire de l'écran qui est écrite.
- et la mémoire de l'image qui est lue.
L'image originale sans zoom ni rotation
Le rotozoom en action avec rotation et zoom
Voici une présentation rapide de ce code : une boucle parcours l'écran verticalement, et à l'intérieur cette boucle, une autre boucle parcours chaque ligne horizontalement. Dans cette boucle horizontale, une équation de rotation lit un Pixel sur une image source et l'écrit sur l'écran visible. De cette façon, tous les Pixel de l'écran sont traitées et affiche une déformation de l'image.
Les pixels de l'écran sont écrit sur des lignes horizontales.
L'image source est lue sur des vecteurs qui bougent
Avec un écran de 320*240 en 15bit et une image 256*256 pixels, dessiner une image prendra 1 centiéme de seconde avec le seul PPC et une rotation de 0 degrés ou de 180 degrés : c'est parce que l'effet se comporte alors comme une simple copie: quand un Pixel est lu, la cache garde les 15 prochains Pixel et n'a pas à les relire par le bus pour le pixels suivant. Le fait est que nos pixel font 2 octets et la taille de cacheline du PPC est de 32 octets.
Quand l'image est lue verticalement, avec un dégré de rotation de 90 ou -90, la mémoire est lue de façon non continue parce que le prochain prochain Pixel à écrire est sur d'autres lignes de l'image. Dessiner une image prends 20 fois plus de temps ! ÉNORME DIFFÉRENCE ! ! (en fait la cache ralentie le code dans ce cas de figure.)
Voilà un premier truc pour empécher ça
Précalculez une deuxième texture : la même de 256*256 Pixels, mais avec une rotation de 90 degrés ! Avant le dessin de votre effet, vérifiez le vecteur de lecture sur l'image qui correspond à l'écriture horizontale sur l'ércan: si abs(Y)>abs(X) échangez tous les X et Y et utilisez la DEUXIÈME image source. Alors quand votre rotozoom changera sa rotation, l'image source utilisée changera : de cette façon, les Pixels seront lus dans le même ordre que leurs dispositions en mémoire, et la cache sera efficace. Mais vous noterez que les angles 45°, -45° sont alors toujours plus lent que 0°, 180° et 90° et-90°.
Mais il existe un truc bien plus puissant!
Oooouh ! Honte sur moi ! ce truc semble être périmé ! J'ai été averti par mes amis codeurs peskanov/capsule et scorpion/silicon qu'un autre truc de cache texture est plus rapide et prend moins de mémoire : Il faut simplement changer l'ordre des Pixels de l'image, de sorte que la cache ait la même chance de lire les prochains Pixels quelque soit la valeur de la rotation !
Utilisez seulement une image de 256*256 pixels comme source :
Habituellement, on met les Pixels d'une image dans la mémoire ligne par ligne, de la gauche vers la droite, et les lignes de haut en bas. Dés lors on adresse ses pixels avec: image[ Y*256 + X ]. De cette manière, dans les 65536 Pixels, le Y est codé par par les 8 bits de poids fort et les X par les 8 bits de poid faible.
Et bien nous allons entrelacer l'ordre de ces 16 bits de cette façon:
- Ordre classique (avant entrelaçage):
- 6bits Fort de Y |2bits Faible de Y | 6bits Fort de X |2bits Faible de X
- Ordre entrelacé:
- 6bits Fort de Y | 6bits Fort de X |2bits Faible de Y |2bits Faible de X
Puis adapter votre code de lecture/écriture des pixels à cet entrelaçage, avec des instructions de décalage de bits.
Image source avec alignement classique.
Image source avec entrelaçage.
Sur ce schema, vous pouvez noter les Pixels chargés par un cacheline avec les frontières noires. En bleu il y a les vecteurs de lecture des pixels quand la rotation est autour de 0° ou 180°, en rouge quand la rotation est 90° ou -90°. Les points représentent les Pixels lus. Ainsi vous pouvez comprendre que les vecteurs bleus sont rapidement exécutés, mais sans l'entrelaçage le vecteur rouge charge 16 fois trop de mémoire, ce qui explique le ralentissement déjà décrit.
Ainsi cette manière de coder votre image est meilleure pour tous les effets de déformation. En fait, les cartes accélératrices graphique harware (GPU) entrelaçent leurs textures d'une maniére voisine dans leurs mémoires !
Une autre manière de changer l'ordre des pixels des images est le "MIP Mapping" (MIP vient du latin "multim im parvo" signifiant "Plusieurs choses dans peu de place" :-) Il s'agit de réduire et filtrer votre image vers d'autres images de tailles 128x128,64x64,32x32,16x16,8x8..., jusqu'à 1x1, et d'utiliser la plus adapté à votre facteur de zoom. Dans le domaine du rendu hardware, cette technique améliore le rendu, mais pour des déformations d'image logicielle (rotozoom, texture mapping...), il l'accélère également, parce que pour un petit facteur de zoom, la lecture d'une grande image donnerait de grands sauts en mémoire.
Extension du domaine...
Et voilà ! Vous avez appris comment employer votre connaissance de l'architecture des caches pour accélérer un code graphique donné. A l'avenir, essayez de voir si cela peut s'appliquer à d'autres algorithmes : Par exemple, si vous avez beaucoup de petites structures en mémoire lues non linéairement, vous pourriez gagner de la vitesse en les alignant sur des adresses multiples de 32 et prêter attention à ce que ces structure ne dépassent pas 32, 64 ou 96 oct: Une taille de 34 octet ferait lire le double de donnée our rien ! N'oubliez jamais que les meilleures implémentations prennent moins de mémoire, et c'est ça l'esprit amiga !
