Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.

Forum Casio - Projets de programmation


Index du Forum » Projets de programmation » [C/ASM] Optimiser au cycle près : la référence
Lephenixnoir En ligne Administrateur Points: 20317 Défis: 143 Message

[C/ASM] Optimiser au cycle près : la référence

Posté le 20/06/2021 22:24

J'adore programmer des add-ins, je pense que ça ne vous aura pas échappé. Le sujet est très large, mais s'il y a une problématique spécifique que je considère ma «spécialité», c'est d'exploiter toutes les astuces logicielles et matérielles pour améliorer les performances.

Ce topic est une référence de techniques d'optimisation d'add-ins, de tous les styles et niveaux. Ce post contient un index de tous les sujets qui me paraissent utiles (sauf ceux que j'ai oubliés), et j'écrirai des bouts au gré des opportunités et des découvertes.

Le sujet étant large, je ne m'attarderai pas sur les notions générales de C/assembleur dans un premier temps ; si vous comprenez les notions d'«accès mémoire» , «instruction», «cycle d'horloge», «timer», et «bus» vous savez tout ce qu'il faut pour aborder les catégories «Bas niveau». Sinon, demandez dans les commentaires

Tutoriels qui vous aideront à comprendre les concepts :

La référence de l'optimisation au cycle près

Identifier les besoins d'optimisation
Il est très tentant, mais inutile, d'optimiser du code qui ne limite pas les performances du programme. Identifier les parties critiques et les liens faibles qui monopolisent les ressources est toujours la première étape.

  • Concepts généraux et bons benchmarks (Programmation générale — ★☆☆)
  • Mesurer et visualiser les performances  (Programmation générale — ★☆☆)
  • Mesurer au cycle près (Bas niveau — ★★★)

Optimisations algorithmiques
On ne peut pas sous-estimer l'importance des optimisations algorithmiques. En un sens, l'algorithmique est la science de calculer ce qu'on veut avec la bonne méthode, indépendamment de l'implémentation. Avec l'exception du dessin sur Graph 90+E et des programmes très intensifs en calcul, l'immense majorité des améliorations du code sont des fourmis au pied de la montagne de l'algorithmique.


Optimisations de calcul et d'implémentation
Vous allez voir que nos chères calculatrices ne sont pas si bien équipées pour calculer que ça.

  • Calcul en point fixe et en point flottant (Programmation générale — ★☆☆)
  • Précalcul des divisions (Maths — ★★☆)
  • Approximations polynomiales : développements limités, séries entières (Maths — ★★★)
  • Approximations itératives : méthode de Newton, simulation d'équa diffs (Maths — ★★☆)
  • Produits : Karatsuba (entiers/polynômes), Strassen (matrices), Hörner (Maths — ★☆☆)

Optimisations sur la mémoire
En général, plus vous progressez en C, plus vous regardez la mémoire de près. Je vais jusqu'à dire que la mémoire est le concept fondamental et omniprésent qui guide l'implémentation de tout programme en C (avec bien sûr l'algorithmique qui guide la conception). Sur la calculatrice, c'est encore plus vrai, et de toutes les optimisations de code très peu concurrenceront une gestion supérieure de la mémoire.

  • Accès aux mémoires, bus, et compromis taille/vitesse (Bas niveau — ★☆☆)
  • Exploiter efficacement les caches (Programmation générale — ★☆☆)
  • La cartographie du SH4AL-DSP et du SH7305 (Bas niveau — ★★☆)
  • Optimisations des copies et écritures avec le DMA (Programmation générale — ★☆☆)
  • Benchmark de toutes les méthodes d'accès par région (Programmation générale — ★☆☆)
  • L'écran R61524 de la Graph 90+E (Bas niveau — ★★☆)

Optimisations sur le code assembleur
C'est dans le boucles critiques, exécutées plusieurs millions de fois par seconde, où chaque cycle compte, que ce topic trouve son nom. Vous avez optimisé les algos, les méthodes de calcul, conçu le programme avec la meilleure distribution possible de la mémoire, et maintenant vous voulez écrire en assembleur la version la plus rapide possible. Voilà comment.

  • Les forces et les limites de l'optimisation dans le compilateur (Programmation générale — ★★☆)
  • Idiomes d'assembleur SuperH, techniques classiques (Programmation générale — ★☆☆)
  • Exécution simultanée d'instructions : le pipeline (Bas niveau — ★★★)
  • Exécution simultanée d'instructions : l'architecture superscalaire (Bas niveau — ★★☆)
  • Accès mémoire : délais, alignement, conflits (Bas niveau — ★★☆)
  • Dépendances de données et ordonnancement des instructions (Bas niveau — ★★☆)
  • Entrelacement des boucles, «ouverture» des itérations (Bas niveau — ★★★)
  • Détournements du jeu d'instructions parallèle du DSP (Bas niveau — ★★☆)



Dark storm En ligne Labélisateur Points: 11501 Défis: 176 Message

Citer : Posté le 30/06/2021 17:10 | #


Ceci étant dit, typiquement sur la division par 10 l'opti de passer par des templates est grosso-modo équivalente à l'opti de la call-table ? Ou du moins c'est pas si horrible de faire un / 10 dans un bout de code que ce que tu laissais imaginer au début.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Lephenixnoir En ligne Administrateur Points: 20317 Défis: 143 Message

Citer : Posté le 30/06/2021 18:32 | #


Je suis pas sûr que call-table soit ce que tu penses ; c'est pas parce qu'un diviseur est petit que tu peux avoir le résultat de la division de toutes les entrées possibles dans une table.

Maintenant je suis surpris de voir que GCC le génère effectivement comme ça (ie. une multiplication au lieu d'une division) sur un programme que je viens de tester... contrairement à mes essais précédents. Je sais pas comment expliquer la différence. o_o

Well, tu as ta réponse à ta question précédente du coup. ¯\_(ツ)_/¯
Dark storm En ligne Labélisateur Points: 11501 Défis: 176 Message

Citer : Posté le 30/06/2021 21:50 | #


Je suis pas sûr que call-table soit ce que tu penses ; c'est pas parce qu'un diviseur est petit que tu peux avoir le résultat de la division de toutes les entrées possibles dans une table

Non, mais tu peux avoir les constantes x dans une table, et soit appliquer l'algo optimisé si le diviseur est référencé dans la table, soit faire du call-div1 si il n'est pas dedans. En tout cas c'est comme ça que j'ai compris l'extrait de doc.

Ajouté le 30/06/2021 à 22:26 :
Du coup je suis allé fouiner dans le dépôt de GCC, j'ai trouvé des trucs intéressants, de type :

un snippet pour générer ce qui a l'air d'être une table des x
le résultat

J'ai pas l'impression que ce soit exactement l'opti que tu présente, mais en tout cas c'est définitivement mieux que faire une division classique. Même si faire un bout de code custom reste plus fiable pour les raisons que tu expliquais
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Lephenixnoir En ligne Administrateur Points: 20317 Défis: 143 Message

Citer : Posté le 30/06/2021 22:35 | #


Hmm si ça ressemble, ok ok. Dans l'ensemble j'ai clairement sous-estimé/pas réussi à observer le job que GCC fait de ce côté-là, tu as bien fait de creuser. Effectivement c'est cool d'avoir la garantie, mais du coup c'est moins rentable de maintenir le code manuel en C si c'est pas critique.
Lephenixnoir En ligne Administrateur Points: 20317 Défis: 143 Message

Citer : Posté le 07/07/2021 12:56 | #


Introduction à la complexité (Algorithmique — ★☆☆)

De toutes les optimisations que vous pouvez faire, la plupart du temps les optimisations algorithmiques sont les plus poussées. En général, quand on a un algorithme il n'y a pas énormément de façons différentes de le coder ; la structure du code (conditions, boucles, etc.) et déjà fixée ; et ce qu'on va voir avec la «complexité» c'est que le nombre d'opérations à faire l'est aussi dans une certaine mesure.

Le but de la complexité algorithmique c'est donc de quantifier le nombre d'opérations à faire pour exécuter un algorithme.

(Si vous savez qu'une multiplication de matrices prend O(n³) et un tri rapide O(n·log n), ce message ne vous apprendra rien.)

Qu'est-ce qu'une opération exactement ?

Quand on fait de la complexité algorithmique, on regarde un algorithme écrit en pseudo-code, comme par exemple cet algorithme qui calcule l'accumulation de 3 matrices de n lignes et n colonnes :

Accumulation de matrices : C = C + A×B
• A,B,C: double[n][n]

Pour i=1 à n:
  Pour j=1 à n:
    cumul <- 0
    Pour k=1 à n:
      cumul <- cumul + A[i][k] × B[k][j]
    C[i][j] <- C[i][j] + cumul

On aimerait pouvoir déterminer combien de temps cet algorithme va prendre, et comme le processeur va à une vitesse à peu près fixe on s'intéresse à combien d'opérations il prend.

Mais du coup, qu'est-ce qui compte comme une opération ? Les additions et multiplications d'accord, mais est-ce que incrémenter i et j ça compte ? Est-ce que les affectations comme cumul <- 0 ça compte ?

La réponse est : on compte les opérations les plus lentes. Par exemple sur la calculatrice, les opérations en point flottant sur les double sont très lentes, dans le genre 300 à 400 fois plus lentes que les opérations sur les entiers. Ce qu'on fait donc c'est qu'on néglige les accès aux matrices, les opérations sur i et j, et on ne compte que les additions et les multiplications de double.

Selon les cas, ce choix peut varier. Par exemple, il y a des simulations physiques qui multiplient des matrices tellement gigantesques qu'elles ne passent pas dans la RAM d'un ordinateur moderne. On est alors obligés de les lire sur le disque dur, ce qui est extrêmement lent (bien plus que les opérations sur les double). Dans ce cas-là, les accès aux matrices comme A[i][k] sont les points les plus sensibles parce que chaque accès au disque dur prend beaucoup de temps, et donc c'est ça qu'on compte.

Ici, je vais compter les opérations arithmétiques parce que c'est le plus classique. Cependant, sur la calculatrice les accès mémoire sont parfois plus limitants ; quelques exemples seront donnés dans la section sur la mémoire. Une bonne connaissance de ce qui se passe sur le matériel permet de faire des analyses algorithmiques plus pertinentes.

Le paramètre pour la complexité

Vous aurez remarqué quand dans mon exemple, j'ai dit que les matrices sont de taille n×n sans dire quelle est la valeur de n. C'est parce qu'en complexité ça ne nous intéresse pas vraiment de savoir combien d'opérations il faut pour multiplier des matrices 10×10. Non, on veut savoir combien d'opérations il faut pour multiplier des matrices de n'importe quelle taille (qu'on note n×n) et ensuite voir ce qui se passe quand n devient grand.

C'est parce que le but de la complexité c'est de trouver des algorithmes robustes qui vont être rapides même quand il faut multiplier des matrices géantes, quand il faut trier des listes gigantesques ou quand il faut chercher un chemin entre un PNJ et le joueur dans une map immense.

En ne spécifiant pas la valeur de n, on se prépare à calculer une complexité qui donnera le nombre d'opérations en fonction de n, ce qui nous permettra de comparer n=10, n=100, n=1000, et de voir si l'algorithme reste rapide quand le sujet devient grand ou s'il devient catastrophiquement lent.

Si votre programme ne multiplie que des matrices de 3×3 alors la complexité ne vous aidera pas à l'optimiser. Mais si vous multipliez des matrices de 20×20, ou 50×50, ou 100×100, alors là la complexité peut vous dire comment il faut faire le calcul pour que ça aille vite.

En général, on étudie un seul paramètre qui est la taille du problème (la taille des matrices, la taille des tableaux, le nombre de cases sur la map, etc). Comme pour tout il y a des exceptions, mais on choisit souvent la taille parce que c'est ça qui influence le plus le nombre d'opérations à faire.

Avec tous ces détails bien mis en place, on peut calculer la complexité de l'algorithme d'accumulation de matrices que j'ai présenté ci-dessus.

Accumulation de matrices carrées : 2n³ + n²

Pour rappel, on compte les opérations sur les double. Il y a une multiplication et une addition dans cumul + A[i][k] × B[k][j], et une addition dans C[i][j] + cumul. La question qui est importante ici, c'est donc «combien de fois est-ce qu'on exécute ces deux lignes ?».

La première est dans une boucle k=1...n et est donc exécutée n fois. Mais la boucle elle-même est exécutée n fois (pour j=1...n) et cette boucle encore est exécutée n fois (pour i=1...n). La ligne est donc exécutée n×n×n = n³ fois, et comme il y a deux opérations sur les double (une addition et une multiplication), ça donne un total de 2n³.

La deuxième ligne est dans la boucle j=1...n, qui est elle-même dans la boucle i=1...n, et donc elle est exécutée n² fois, pour un total de n² opérations (puisqu'il n'y a qu'une addition sur la ligne).

Le nombre d'opérations en point flottant dans cet algorithme est donc T(n) = 2n³ + n². (On dit T pour le temps de calcul, par habitude.)

L'influence énorme de la complexité dans le temps de calcul

Dans le tableau ci-dessous j'ai résumé les valeurs de n², n³, et 2n³ et T(n) pour différentes valeurs de n.

n2n³T(n) = 2n³+n²
5 25 125 250 275
10 100 1000 2000 2100
250 62500 15.625 millions 31.25 millions 31.31 millions
4'000 16 millions 64 milliards 128 milliards 128.02 milliards
10'000 100 millions 1 billion 2 billions 2.0001 billions

La première chose à voir, c'est que ça grandit très vite ! Il est évident qu'avec cette méthode accumuler des matrices de 250×250 ça passe encore, 4000x4000 c'est faisable avec un bon ordinateur, mais 10000x10000 c'est même pas envisageable sans un super-ordinateur.

On peut comparer ça avec un algorithme de tri, pour se donner une idée. Une matrice de 10000x10000 possède 100 millions d'éléments ; peut-on trier 100 millions d'éléments ? Oui, et c'est même assez facile, ça prend environ n·log₂ n = 2.5 milliards de comparaisons de double. C'est beaucoup bien sûr, mais c'est réaliste rien qu'avec mon ordinateur portable.

La morale c'est que dans quasiment tous les cas, la complexité de l'algorithme domine complètement le temps de calcul quand on prend des objets très grands. Ici j'ai pris des objets vraiment grands avec des millions de nombres, mais si votre jeu a une map de 100x100 = 10000 tiles vous verrez déjà des grandes différences de performance entre les algorithmes lents qui une complexité élevée, et les algorithmes intelligents qui ont une complexité plus faible.

Complexité asymptotique et notation grand O : O(n³)

À propos de dominer, vous remarquerez que dans le 2n³+n² c'est clairement le n³ qui fait tout le boulot ; dès que n est assez grand la contribution de n² au nombre total d'opérations est assez négligeable. De la même façon, le facteur 2 a de moins en moins d'importance.

Pour cette raison, les algorithmiciens utilisent une notation spéciale pour simplifier les formules. On parle d'une notation asymptotique, ce qui veut dire qu'elle s'intéresse uniquement à ce qui se passe quand n devient grand (asymptotique = «au voisinage de l'infini» si vous êtes prêt·es à simplifier un peu).

Cette notation s'écrit avec un O majuscule (prononcé «grand O»). La définition est la suivante :

On dit que T(n) = O(f(n)) si à partir d'une certaine valeur de n, T(n) ≤ C × f(n) pour une constante fixée C.

Décortiquons doucement cette définition. «À partir d'une certaine valeur de n» concrétise le fait qu'on ne s'intéresse qu'au comportement quand n devient grand. Si la complexité qu'on a déterminée ne marche pas pour n=0 ou n=1, on s'en moque. On veut juste quelle marche pour n≥2, ou n≥10, ou n≥100. (Évidemment si elle ne marche que pour n ≥ 1 million le résultat sera inutile, mais techniquement c'est acceptable aussi.)

T(n) ≤ C × f(n) ça veut dire qu'à une constante C près, T(n) est plus petit que f(n). Autrement dit, que f(n) indique une borne sur le nombre d'opérations, à ×2 près, ou à ×3 fois, ou à ×1000 près.

Par exemple, on peut dire que T(n) = O(n³) : en effet, T(n) = 2n³ + n² ≤ 3 × n³ dès que n ≥ 0. En revanche, on ne peut pas dire que T(n) = O(n) puisque peu importe la constante C qu'on choisit, il y a des grandes valeurs de n pour lesquelles T(n) > C × n.

Attention, O() n'est pas une fonction, c'est une notation. (Les gens vraiment rigoureux seront contents de savoir qu'il y a une définition propre : O(f) c'est l'ensemble de toutes les fonctions qui valident la propriété par rapport à f, et on écrit T ∈ O(f), ou dans notre cas, T ∈ O(n ↦ n³). Mais il faut vraiment aller chercher des mathématiciens pour raisonner comme ça.)

Pour résumer, on dit que la complexité de cet algorithme est O(n³) (prononcé «un grand O de n³») pour mettre en avant le fait que le nombre d'opérations est très proche de n³ quand n est grand, en ignorant les petits facteurs qui sont négligeables à côté. Moralement, le temps de calcul est «de l'ordre de grandeur de n³».

Comment ça marche en pratique ?

Souvent, les problèmes qu'on veut résoudre dans un programme sont déjà étudiés (produits de matrices, tris de tableaux, recherches de chemin sur une map pour ne citer que les exemples que j'ai déjà mentionnés). Le processus de réflexion pour le développeur du programme est donc à peu près comme ça :

  1. Déterminer si le calcul qu'on veut faire correspond à un problème classique (souvent oui), et lequel.
  2. Consulter les différents algorithmes disponibles pour ce problème.
  3. Comparer la difficulté d'implémentation, la complexité, le quantité de mémoire nécessaires, et d'autres facteurs pertinents dans le code en général.
  4. Implémenter un ou plusieurs algorithmes prometteurs, et valider que le temps d'exécution correspond aux attentes.

Typiquement si vous voulez trier un tableau vous utilisez par exemple un tri rapide en O(n·log n), ça se code en 20-30 lignes en C ; vous n'avez pas besoin de l'inventer (le copier/coller de Wikipédia marche très bien), et ça ira souvent 10-15 fois plus vite qu'un tri naïf comme un tri bulle en O(n²).

Ou bien pour une recherche de chemin entre un PNJ et le joueur sur la map, vous modélisez la map comme un graphe et vous implémentez soit un parcours en largeur, soit un Dijkstra, soit un A*... parfois d'autres algorithmes sont plus appropriés, comme Floyd-Warshall si vous avez énormément de chemins à calculer, ou Bellman-Ford si le map change par petites touches ; etc etc.

Il n'est pas nécessaire de connaître tous ces algorithmes pour écrire des programmes optimisés. Mais il est important de savoir que la complexité d'un algorithme peut influencer énormément le temps d'exécution d'un programme, et de pouvoir reconnaître quand un amélioration de d'algorithme est plus rentable qu'optimiser le code.

N'oubliez pas que si vous optimisez le code aux petits oignons mais que vous devez ensuite changer d'algorithme parce que celui que vous utilisez est super lent, toute l'optimisation sera perdue. Idéalement on veut choisir les bons algos en premier, ensuite les coder, et ensuite optimiser ce code.
Lephenixnoir En ligne Administrateur Points: 20317 Défis: 143 Message

Citer : Posté le 18/07/2021 19:27 | #


Accès aux mémoires, bus, et compromis taille/vitesse (Bas niveau — ★☆☆)

Le microprocesseur SH7305 qui est au cœur de la calculatrice est un ordinateur relativement moderne, dans le sens où ses préoccupations en termes de performances sont similaires à celles des processeurs plus avancés qu'on trouve communément dans nos ordinateurs (par exemple x64/amd64) ou appareils mobiles (par exemple arm/aarch64).

À l'époque (aujourd'hui révolue) où les processeurs et les mémoires étaient alignés sur la même horloge, un programme passait un cycle pour faire une addition et un cycle aussi pour lire un octet dans la mémoire. Aujourd'hui, cet équilibre n'est plus du tout vérifié, mais ces deux types d'opérations continuent de dominer l'occupation des programmes.

Un programme donna sera donc limité selon les moments soit par la vitesse de calcul du processeur soit par sa capacité à accéder rapidement la mémoire.

La différence est significative : par exemple, un programme qui fait de très nombreux accès à la VRAM pour dessiner des objets à des positions éloignées de l'écran imposera une charge maximale sur les accès mémoire. À l'inverse, un programme qui calcule les points d'une fractale de Mandelbrot ne fait que du calcul et sera exclusivement limité par l'ordre et la quantité des opérations arithmétiques. Il est crucial de savoir ce qui limite chaque programme pour optimiser où il faut.

(Précision : sur un ordinateur la VRAM est de la mémoire sur le GPU, mais pour nous c'est juste un tableau de pixels dans la RAM. Si je parle de VRAM c'est donc juste une variable qui est dans la RAM principale et qui est trop grosse pour aller dans les mémoires plus petites.)

La différence est aussi subtile, car une simulation du jeu de la vie pourra se trouver à la fois limitée par le calcul (puisque le calcul de l'état de chaque cellule à la génération suivante demande une addition de 8 termes et des comparaisons, entre autres) et par les accès mémoire (puisque ce calcul nécessite l'information des 8 cellules qui l'entourent, qu'il faut aller lire en mémoire). Une analyse fine est parfois requise.

Dans cette technique du guide d'optimisation, je m'intéresse à la mémoire ; les calculs seront plutôt abordés dans les optimisations sur le code assembleur.

Mécanisme des accès mémoires et bus

Pour bien comprendre l'impact des accès mémoire sur les performances, il est important de voir comment ils se déroulent en termes matériels.

La connexion entre le processeur et les différents modules qui l'entourent (dont les mémoires, mais aussi tous les modules périphériques entre autres) se fait par l'intermédiaire d'un bus. Un bus est un peu une route sur laquelle les informations circulent entre différents composants électroniques.

Dans l'idée, c'est juste un fil qui relie tous les composants ; dès que quelqu'un écrit un 0 ou un 1 dedans, tout le monde reçoit la valeur. On y ajoute un mécanisme pour éviter que deux personnes écrivent en même temps, on attribue des «adresses» pour que chaque composant puisse identifier les messages qui lui sont destinés et ignorer les autres, on met plusieurs fils pour pouvoir écrire plusieurs bits simultanément, et c'est à peu près tout (mais je ne suis pas spécialiste ici, ne me citez pas sur le sujet).

Lorsque le processeur exécute une instruction d'accès mémoire, il écrit sur le bus l'adresse à laquelle il veut accéder, la taille de l'accès (1, 2 ou 4 octets), si l'accès est une lecture ou une écriture, et, si c'est une écriture, la valeur à écrire. La mémoire, qui «écoute» sur le bus, reçoit l'information et traite la demande ; si c'est une lecture elle va chercher la valeur et l'écrit sur le bus en réponse, si c'est une écriture elle sauvegarde la valeur fournie par le processeur. Dans les deux cas la mémoire indique via le bus à quel moment elle a terminé.

Il y a plusieurs éléments importants ici en termes de performance ; le principal c'est qu'il n'y a pas de contrainte sur le temps de traitement de l'accès. Le processeur «attend» jusqu'à ce que la mémoire indique qu'elle a fini, et donc différentes mémoires qui ont différents mécanismes électroniques peuvent mettre des temps différents (et elles le font).

Le bus a aussi un rôle à jouer. Comme le bus est utilisé pour passer des messages entre plusieurs composants, et qu'une seule personne peut écrire dessus à la fois, il peut y avoir des délais pour cause d'embouteillages. Parfois, l'optimisation est une affaire de faire passer les bons messages sur les bons bus pour éviter les collisions.

L'éternel équilibre entre taille et vitesse

La mémoire parfaite est une mémoire à la fois très grande et très rapide. La nature faisant bien les choses, il est clair d'emblée qu'une mémoire à la fois très grande et très rapide ne peut donc pas exister.

Il y a beaucoup de raisons pour ça, mais la plus simple est que plus il y a d'octets dans la mémoire plus il y a de travail à faire pour identifier le petit composant électronique qui contient la donnée. Tout comme plus une bibliothèque est grande, plus il y a de travail à faire pour identifier un livre spécifique, même si les livres sont numérotés de façon parfaite. Les octets de mémoire, comme les livres, occupent physiquement de la place ; plus il y en a plus le circuit est grand, et plus le signal électrique met longtemps à le traverser.

Par conséquent, une mémoire qui est plus grande est nécessairement plus lente (à autre facteurs égaux), et de la même façon une mémoire plus rapide est nécessairement plus petite.

Cette dichotomie est omniprésente, et pour compenser ses effets chaque ordinateur a souvent beaucoup de mémoires de différentes tailles (et de vitesses inversement proportionnelles).

Par exemple, sur un ordinateur portable moyen comme le mien, un accès à la RAM prend beaucoup plus qu'un cycle d'horloge du processeur. Pour compenser ce problème, on a inventé le cache ; une mémoire intermédiaire située entre le processeur et la RAM, plus petite que la RAM mais aussi plus rapide, qui contient une copie des données auxquelles on a accédé récemment. Si on utilise les mêmes données plusieurs fois de suite le cache répond à la place de la RAM, ce qui va beaucoup plus vite, sinon il accède à la RAM comme avant.

Le cache améliore tellement les performances que les ordinateurs en ont aujourd'hui trois niveaux, chacun plus gros mais plus lent que le précédent. La calculatrice a aussi un cache, quoiqu'un seul niveau, ce qui suffit car la mémoire n'est pas aussi lente que sur un PC (principalement parce qu'elle n'est pas aussi grosse !).

L'échelle des mémoires est assez longue ; les plus petites sont les registres du processeur, les plus grandes sont les disques durs et autres périphériques externes, avec toute une palette d'intermédiaires. Il est donc important de savoir à qui on s'adresse dans un programme pour contrôler les performances.

Structure du SH4AL-DSP et du SH7305

Le processeur qu'on a est un SH4AL-DSP. Malheureusement, sa documentation ne contient pas de diagramme montrant la structure du bus et des composants. À la place, en voici une que j'ai prise dans celle du SH-4A (page 30), qui est relativement proche.


Ce diagramme n'est pas aussi compliqué qu'il en a l'air de loin, on peut le déchiffrer ensemble. Chaque ligne représente une connexion physique, et des formes épaisses sont utilisées pour indiquer que les connexions sont larges (plusieurs bits en parallèle).

La partie "SH-4A core" en pointillés représente le processeur. Physiquement, cette région est sur une unique puce au milieu du circuit. Le reste c'est les parties du MPU (pour nous, le SH7305) qui sont autour. Il y a trois bus dans le processeur :
  • Le bus d'instructions ;
  • Le bus d'opérandes ;
  • Et le bus interne cache/RAM.

Et il y a deux bus à l'extérieur :
  • Le SuperHyway (littéralement l'autoroute) ;
  • Et le bus périphérique.

Bus d'instructions et bus d'opérandes

Ces deux bus sont les plus proches du processeur et aussi les plus rapides. Ils sont tous les deux reliés soit aux mémoires très proches (ILRAM ou cache par exemple) soit aux modules qui permettent d'accéder aux mémoires plus éloignées (typiquement le MMU).

Le bus d'instructions est utilisé pour lire le code dans les mémoires très proches, et le bus d'opérandes est utilisé pour lire et écrire les données : variables, tableaux, et autres opérandes d'instructions. Séparer les deux est utile parce qu'on fait souvent les deux à la fois et parce que les programmes se comportement très différemment vis-à-vis des deux.

Deux cas simples sont l'ILRAM (Instruction Local RAM) et l'OLRAM (Operand Local RAM). La première est dédiée au stockage d'instructions et est connectée au bus d'instructions, la seconde est dédiées au stockage d'opérandes et est connectée au bus d'opérandes. (Sur le SH4-AL DSP l'OLRAM est remplacée par autre chose de similaire.) La vitesse de ces bus et mémoires est illustrée par la documentation concernant les accès en instructions à la mémoire IL :

Instruction fetch access from the CPU is performed directly via the instruction bus for a given virtual address. In the case of successive accesses to the same page of IL memory and as long as no page conflict occurs, the access takes one cycle.

Du code placé en mémoire IL peut donc être lu en un seul cycle, ce qui est le meilleur résultat possible. On notera quand même que la mémoire IL est divisée en «pages» de 4 ko et que la garantie d'un cycle n'est valide que tant qu'on reste sur la même page. Nous on n'a qu'une page de toute façon (l'ILRAM fait 4 ko en tout) mais on retrouvera ce genre de contraintes sur d'autres exemples.

Vous remarquerez que la vitesse d'accès n'est pas la même si on accède à la mémoire IL par une opérande :

Operand access from the CPU and access from the FPU are performed via the cache/RAM internal bus. Access via the cache/RAM internal bus takes more than one cycle.

Eh bien tout de suite ça passe par le bus interne cache/RAM, qui est plus lent, donc ça prend plus d'un cycle. Vous voyez déjà que différents types d'accès à la même mémoire peuvent passer par différents bus et donc prendre différentes durées.

Sur le SH4-AL DSP, on n'a pas de FPU à côté du CPU, mais on a un DSP. Ce DSP a deux zones de mémoire dédiées, la XRAM et la YRAM, qui sont toutes les deux reliées au DSP par des bus dédiés de 16 bits, le bus X et le bus Y. Ça il y en a un schéma dans la doc du SH4AL-DSP (page 177).


Vous pouvez voir que le bloc "DSP unit" est relié aux mémoires X et Y par ces deux bus dédiés. Ils font chacun 16 bits, si bien que le DSP peut lire 16 bits de mémoire X et 16 bits de mémoire Y en même temps. (Il peut aussi lire 32 bits d'une seule parce que chacun des deux bus peut accéder aux deux mémoires, même si le schéma ne le montre pas.) Les accès par les bus X et Y se font en un seul cycle.

Cela dit, le DSP n'est pas pratique à utiliser pour des raisons que j'explorerai dans une autre technique, donc on préfère accéder à la mémoire X et Y par le CPU. Pour ça, il faut utiliser le bus d'opérandes que vous pouvez voir représenter à droite du diagramme (ou le bus d'instructions qui lui n'est pas représenté). Par chance, les accès à la mémoire X et Y par ces deux bus prennent aussi 1 seul cycle, donc le CPU bénéficie des mêmes performances remarquables que le DSP.

Voilà qui conclut à peu près le tour des mémoires très proches. Il y aussi les caches, mais on ne peut pas contrôler directement ce qu'il y a dedans, ils sont associatifs donc non triviaux à utiliser efficacement, et ça méritera une technique complète qui suivra certainement un autre jour.

Le bus interne cache/RAM

Le bus interne cache/RAM est, comme son nom l'indique, le bus avec lequel le processeur interface avec le cache et la RAM (toute la mémoire "principale" donc). Le cache, qui est séparé en un cache d'instructions et un cache d'opérandes (parce que le code et les données ne sont pas du tout traitées pareil par le programme donc on gagne à gérer les deux caches différemment), est accessible directement pas les bus d'instructions et d'opérandes quand le CPU demande un accès, et reçoit les données en provenance de la RAM par le bus interne cache/RAM quand les données demandées ne sont pas immédiatement disponibles.

La RAM à proprement parler, et la ROM (OS + mémoire de stockage) aussi d'ailleurs, sont derrière le BSC (Bus State Controller), donc l'accès ne s'arrête pas au bus interne cache/RAM, il continue encore (et vous commencez peut-être à voir pourquoi les accès à la VRAM sont lents).

Il n'y a pas grand-chose de très intéressant à accéder par ce bus ; vous noterez que les accès en opérandes/instructions aux mémoires IL/OL (les accès pour lesquels ces mémoires ne sont pas conçues, donc) passent par le bus interne cache/RAM comme je l'ai illustré précédemment, donc sont plus lents.

Le point le plus important concernant ce bus est le MMU. Le MMU est le composant qui traduit les adresses virtuelles en adresses physiques quand on accède à la mémoire par une adresse virtuelle dans P0 (à savoir, en gros, la ROM ou le segment de données) ou P3 (qui ne contient rien sur la calculatrice). Ça veut dire que si vous mappiez l'ILRAM dans P0 par exemple vous perdriez la vitesse d'accès. Pour les mémoires qui sont hors du processeur et qui doivent passer par le bus interne cache/RAM dans tous les cas, utiliser les adresses physiques est quand même utile puisque ça économise le temps de décodage par le MMU, mais je ne sais pas quel est l'ordre de grandeur.

Le SuperHyway et le bus périphérique

Les modules hors du processeur sont reliés par le SuperHyway où on trouve notamment le BSC, qui donne accès à la RAM principale et à la ROM (qui ne sont même pas dans le SH7305 mais encore à l'extérieur), et le contrôleur DMA.

Vous pouvez voir ici en pleine action la dichotomie taille/vitesse dont je parlais tout à l'heure. Un accès à la RAM principale (comme le dessin dans la VRAM) passe d'abord par le bus d'opérandes, puis optionnellement le MMU, puis le bus interne cache/RAM, puis le SuperHyway, puis le BSC, un bus externe, et ensuite seulement il atteint la RAM, avant de refaire le même chemin en sens inverse. Ce sera toujours beaucoup plus long qu'un accès parfait d'un cycle à la mémoire X par le bus d'opérandes, pour des raisons évidentes.

Le DMA est un cas intéressant. On s'en sert souvent pour copier des données de la RAM à la RAM, ou de la RAM à l'écran, ou de l'ILRAM à la RAM dans quelques cas (comme la fonction dma_memset() de gint). Le DMA est derrière le SuperHyway, donc il est raisonnablement bien placé pour accéder à la RAM et à l'écran, mais il est moins bien placé que le processeur pour accéder aux mémoires rapides comme les mémoires IL, X ou Y. C'est pour cette raison par exemple que copier de la mémoire X vers la mémoire Y va beaucoup plus vite par le CPU mais copier de la RAM vers la RAM va beaucoup plus vite par le DMA. (On explorera en détail les débits dans une autre technique, sinon celle-ci ne se terminera jamais. x3)

Le bus périphérique n'est pas très intéressant, il mène aux modules périphériques, mais comme on n'y accède jamais très souvent ce n'est pas un problème pour les performances.

Paramètres d'horloges, overclock

Comme à peu près tous les composants, les bus sont cadencés par des horloges. Et qui dit horloge dit paramétrage de la fréquence (voire overclock) avec le CPG (Clock Pulse Generator, le module qui gère les horloges). Je ne détaille pas, mais on retrouve principalement ces horloges pour contrôler les bus :

  • : Horloge du CPU (et des trois bus qui sont dedans)
  • : Horloge du bus SuperHyway (et du DBSC)
  • : Horloge du BSC (donc accès RAM, ROM) et des modules périphériques sur le SuperHyway
  • : Horloge du bus périphérique et des modules qui sont dessus

Il y en a d'autres, y compris certaines qui servent à cadencer des périphériques externes. (Je n'ai pas encore trouvé d'horloge qui permette d'overclock spécifiquement l'écran, mais peut-être que ça arrivera.)

En général elles sont toutes overclockées en même temps, vous pouvez regarder par exemple les paramètrages par défaut de Ptune3 pour vous donner une idée. Il y a aussi pas mal de contraintes, par exemple la fréquence de Iϕ doit être un multiple de celle de Sϕ, Sϕ ne peut être égale qu'à Bϕ ou à 2Bϕ, et d'autres du même style (voyez la documentation du SH7724, 17.5.2 pour les détails).

Voilà qui devrait vous donner une bonne idée des enjeux. L'usage de mémoires proches et rapides est très bénéfique voire inégalable, surtout lorsque la mémoire est de loin le facteur limitant (ce qui est le cas dans le dessin en général). Dans une autre technique je ferai une cartographique complète des zones de mémoire et de leurs tailles, ce qui permettra ensuite de discuter des différentes méthodes d'accès (CPU, DSP, DMA, instructions vs opérandes, caches) et de leurs vitesses au cas-par-cas.
Lephenixnoir En ligne Administrateur Points: 20317 Défis: 143 Message

Citer : Posté le 18/07/2021 21:42 | #


Interlude : éléments d'analyse asymptotique (Maths — ★★★)

Quand j'ai écrit la technique Introduction à la complexité on m'a demandé des détails sur la notation O() et ce que ça veut dire exactement donc je prends ce moment pour en parler. Ça c'est des maths uniquement et ça n'a aucun lien direct avec l'optimisation des programmes, n'hésitez pas à survoler ou sauter le post

Le domaine dont ces outils sont tirés s'appelle l'analyse asymptotique. C'est le domaine où on étudie des fonctions à la limite, soit vers l'infini soit vers des points finis (typiquement 0). Le but est de caractériser le comportement des fonctions au voisinage du point limite, en ignorant ce qui se passe ailleurs, et notamment de calculer des formes simplifiées qui sont «équivalentes» (pour une certaine définition très précise d'équivalence) à la fonction originale.

Pour toute cette technique, on se donne un point limite a qui est soit un réel soit un infini. Comme le sujet général c'est la complexité par défaut je prendrai comme limite +∞, mais je mentionnerai aussi parfois le cas 0 (pour lequel les relations sont assez différentes). Je suppose aussi que toutes les fonctions sont strictement positives (ie. à valeurs dans ℝ⁺*) pour simplifier les définitions.

Pour info, c'est du cours du Maths sup. en gros (mais je le ressors de tête parce que je l'ai pas avec moi pour vérifier xD).

Domination et petit o

Une première idée qu'on veut formaliser c'est le fait que certaines fonctions grandissent plus vite que d'autres (... au voisinage de +∞, en 0 ce serait diminuent en général). Cette relation de «domination» va par exemple permettre de se concentrer sur un seul terme dans une complexités et d'ignorer les autres. Typiquement dans 2n³+n² le terme 2n³ domine le terme n² en +∞, et le terme n² domine le terme 2n³ en 0.

On dit que f domine g au voisinage de a si: lim(x→a) g(x)/f(x) = 0.

Très concrètement la domination on la représente par un quotient. Si le quotient g/f tend vers 0, f domine g. Quand f peut s'annuler c'est plus casse-pieds à définir, mais l'idée reste la même.

Comme on utilise souvent cette relation, on définit l'ensemble o_a(f) (prononcé « petit o en a de f ») qui inclut toutes les fonctions dominées par f.

o_a(f) = { g | lim(x→a) g(x)/f(x) = 0 }.

Et c'est là qu'on trouve une ribambelle de raccourcis de notation plus ou moins douteux :
  • On écrit o(f) sans spécifier a quand c'est clair dans le contexte. Ça ok.
  • On écrit souvent o(2n³) au lieu de o(n ↦ 2n³) ou o(f(x)) au lieu de o(f). Pas hyper propre mais passable.
  • On écrit g = o(f) au lieu de g ∈ o(f). Ça c'est extrêmement répandu et aussi extrêmement trompeur.

La raison évidemment pour laquelle utiliser le signe d'égalité est manipulateur, c'est que c'est pas une relation d'équivalence. Déjà o(f) = g ça n'a aucun sens, et puis on peut avoir g = o(f) et h = o(f) sans avoir g = h (y'a qu'à prendre g(x) = x² et h(x) = x dans l'exemple précédent).

Néanmoins, on voit couramment des trucs comme T(n) = 2n³+n² = O(2n³) = O(n³), ce qui sert juste à donner différentes approximations successives, ce qu'on écrirait d'une façon plus rigoureuse T(n) = 2n³+n² ; T ∈ O(n ↦ 2n³) ⊆ O(n ↦ n³). (On verra dans un instant ce que veut dire O(), mais la définition est similaire et le raccourci est le même.)

Attention donc aux raccourcis, en cas de doutes il faut bien se rappeler que o(f) est un ensemble, et à partir de là on arrive généralement à s'y retrouver.

Équivalents

Une des grandes idées de l'analyse asymptotique est de trouver des équivalents. Et par équivalent, on entend quelque chose qui se rapproche de la fonction dans un ratio de 1 (et rien d'autre).

On dit que f est équivalent à g au voisinage de a, et on écrit f ~_a g, si: lim(x→a) f(x)/g(x) = 1.

Par exemple, au voisinage de l'infini on a 2n³+n² ~ 2n³ parce que le terme en n² ne contribue qu'à une proportion négligeable du total. (Vous noterez que j'emploie les mêmes raccourcis que précédemment : termes libres. vs fonctions, et omettre la valeur de a.)

Attention par contre, 2n³ ≁ n³ (puisque le rapport est 2). On a (x+1)⁵ ~ x⁵, mais en revanche e^(x+1) ≁ e^x (le rapport est e). Là on commence à voir la différence entre les polynômes (qui sont assez réguliers et se moquent de petits décalages) et les exponentielles (qui sont très sensibles). Plus tard ça explique pourquoi on choisit d'avoir P et EXPTIME comme classes de complexité.

Notez que la définition rigoureuse c'est f ~_a g si f-g ∈ o_a(f), autrement dit la différence est négligeable devant le total. Ça évite les problèmes de division mais ça revient au même dans le cas des fonctions strictement positives.

L'analyse asymptotique aime beaucoup les équivalents et souvent on essaie d'en établir. Parfois c'est assez tordu, par exemple on peut définir une suite de façon implicite du style «soit u_n la valeur x telle que de f(n,x)=0» et ensuite déterminer un équivalent de u_n en l'infini. Ça revient à estimer où se trouvent les racines de f(n,·) en fonction de n, ce qui est déjà assez musclé. D'ailleurs j'ai du mal avec ce genre de choses, heureusement en informatique (typiquement en complexité) on se trimballe presque exclusivement des fonctions explicitement définies. x)

Bornes supérieures et O()

Un autre outil très important pour les bornes supérieures est O() (« grand O »). Le principe est similaire à o(), sauf que cette fois on ne veut pas dominer, on veut juste une borne supérieure à une constante près. Cette définition est très utile même pour les fonctions qui s'annulent, donc en général on déroule la limite pour avoir une forme plus générale. Comme la limite s'écrit différemment en +∞ et pour un réel je vous donne la version +∞.

On dit que f ∈ O_+∞(g) s'il existe M∈ℝ et C>0 tels que ∀ x≥M, f(x) ≤ C·g(x).

Je pense que la définition est relativement explicite, mais à défaut ça dit que g est une borne supérieure de f à une constante C près et au voisinage de +∞ (on ne chercher pas à savoir ce qui se passe pour x<M).

Conceptuellement, c'est un peu comme si le quotient f(x)/g(x) était borné par une constante à l'infini. Mais attention ce n'est pas la définition et il n'y a pas besoin que le quotient ait une limite pour avoir un O(). Le but de cette remarque est simplement de montrer la relation entre ces trois outils (pour des fonctions à valeurs strictement positives) :

  • Si f(x)/g(x) tend vers 0, on a un petit o.
  • Si f(x)/g(x) tend vers 1, on a un équivalent.
  • Si f(x) est borné par un multiple constant de g(x), on a un grand O.

Notez que O() c'est vraiment que la borne supérieure, je peux prendre n'importe quel algorithme et dire que sa complexité est O(2^(n!^n)), ça ne sert juste à rien. En informatique on écrit O() et on prouve bien la propriété de O() mais on cherche toujours à trouver la plus petite borne possible. Par exemple c'est techniquement correct de dire que le produit matriciel est O(n⁴), mais si vous mettez ça au partiel je vous garantis que vous n'aurez pas les points sur la question. x3

Notez que pour pas mal de problèmes on ne sait juste pas quelle est la meilleure complexité qu'on peut obtenir avec un algorithme. Rien que pour le produit matriciel par exemple, il y a des algos plus malins que l'algo naïf (comme celui de Strassen) qui font O(n^2.807), il y a des algos super tordus qui O(n^2.373) mais que personne n'utilise, et on ne sait pas jusqu'où on peut descendre à part le fait qu'on ne peut pas descendre plus bas que O(n²).

Autres notations parfois utiles

On écrit f = Ω(g) si g = o(f).

On écrit f = Θ(g) si f = O(g) et g = O(f) ; notez que du coup, g = Θ(f) aussi. Ça revient à dire que f est coincé entre 2 multiples constants de g, ce qui est une sorte d'équivalent à facteur constant près (et inversement). Ce que je disais plus haut c'est qu'en général en complexité algorithmique on essaie d'obtenir des Θ(), ce qui indique que la borne est optimale. Cela dit même quand on les atteint en général on écrit O() et on ajoute à côté « la borne est optimale », parce que la notation est assez rare (et que parfois la condition d'optimalité est légèrement différente).

Propriétés intéressantes et quelques développements limités

J'y vais un peu rapidement ici parce qu'il y a beaucoup de choses à explorer (toute une théorie, en fait) et je peux pas faire un cours complet d'analyse asymptotique. :x

Les o() et les O() peuvent être additionnés et soustraits. Par exemple, 2n³ = O(n³) et n² = O(n³) donc 2n³ + n² = O(n³). C'est aussi des trucs transitifs, typiquement si f = o(g) et g = o(h), alors f = o(h)... pareil avec O(). La multiplication marche aussi sans problème. Dans l'idée votre intuition de ce que «domination» et «borne supérieure» veulent dire se traduit assez bien par des propriétés sur les o() et O(), il n'y a pas fondamentalement de piège (à part celui de croire qu'il y a des propriétés suffisamment évidentes pour qu'on n'ait pas besoin de les prouver :P).

L'équivalence est une relation d'équivalence (oui c'est bien nommé !).

Les équivalents ça se multiplie et divise très bien et sans piège (à part si la fonction quotient s'annule). Par contre, additionner ou soustraire des équivalents est un crime capital passable de -4 sur n'importe quelle copie de prépa et aussi la source #2 de frustration du prof de sup' sur ce chapitre (la source #1 étant les gens qui balancent des équivalents sur tout et n'importe quoi en se disant «bwarf, c'est presque la même fonction donc c'est probablement ~équivalent~»).

Tout ça se raccroche beaucoup au développements limités. Pour vous donner une petite idée de la puissance de l'analyse asymptotique, prenons un exemple. Vous savez peut-être que sin(x)/x se rapproche beaucoup de 1-x²/6 au voisinage de 0. On peut quantifier à quel point en calculant un développement limité de sin(x)/x en 0 (c'est une série de MacLaurin/Taylor que vous connaissez probablement) :

sin(x)/x = 1 - x²/6 + x⁴/24 - x⁶/720 + ...

Le premier terme (à savoir 1) est un équivalent, et ensuite à chaque fois que vous coupez la séquence vous avec un o(). Par exemple sin(x)/x = 1 + o(1) ou bien sin(x)/x = 1 - x²/6 + o(x²). Vous pouvez prendre le nombre de termes qui vous arrange, vous aurez à chaque fois une approximation de sin(x)/x avec plus ou moins de précision.

Pour comparer avec notre seconde fonction 1 - x²/6 je peux prendre aussi un développement limité en 0, mais comme c'est un polynôme c'est juste lui-même. Donc là aussi l'équivalent c'est 1, et on peut écrire 1 - x²/6 = 1 + o(1) ; je peux continuer aussi avec le second terme mais à ce moment-là ce ne sera plus une approximation donc le o() disparaîtra.

Maintenant on peut déterminer à quel point les deux fonctions sont proches en 0 en soustrayant les développement limités (que je coupe à l'ordre 4 parce que je veux qu'un seul terme) :

sin(x)/x - (1-x²/6) = x⁴/24 + o(x⁴)

Et voilà un équivalent de la différence : au voisinage de 0, sin(x)/x et 1 - x²/6 se rapprochent à la vitesse de x⁴/24. Bon courage pour trouver ce résultat autrement !

Vous voyez bien d'ailleurs que ce n'est pas la différence des équivalents (qui est 1 - 1 = 0). Faire cette soustraction c'est comme faire la différence des développements limités mais avec un seul terme, ce qui ne donne rien d'utile :

sin(x)/x = 1 + o(1)
1 - x²/6 = 1 + o(1)
sin(x)/x - (1-x²/6) = (1 + o(1)) - (1 + o(1)) = o(1)

Je cache un peu des règles de «calcul sur les o()» qui sont juste des raccourcis supplémentaires sur la notation ensembliste. Mais vous pouvez voir que le résultat qu'on a c'est que la différence est o(1), ce qui est techniquement correct mais pas assez précis pour sortir un équivalent (pour ça il faut aller à l'ordre 4).

Voilà donc quelques éléments d'analyse asymptotique et un exemple jouet de ce qu'on peut faire avec.

Ne vous inquiétez pas si cette dernière partie vous a complètement échappé, c'est plus destiné aux étudiants qui ont eu un cours dessus. Un seul post de ce style n'est pas suffisant pour introduire autant de notions de façon digeste.
Lephenixnoir En ligne Administrateur Points: 20317 Défis: 143 Message

Citer : Posté le 19/07/2021 22:10 | #


Concepts généraux et bons benchmarks (Programmation générale — ★☆☆)

Optimiser un programme est une activité un peu ambiguë ; ça peut être crucialement utile mais aussi une perte complète de temps, selon ce qu'on optimise et comment on le fait. Dans l'ensemble c'est aussi une activité chronophage, d'où l'intérêt d'optimiser intelligemment et surtout là où ça frappe le plus fort. Avoir un programme optimisé c'est cool, ne pas avoir de programme parce qu'on a plus le temps de le finir c'est moins cool.

Avoir un objectif bien défini

Il est utile d'avoir un cahier des charges pour savoir où on va. Parfois on veut juste que le jeu atteigne 30 FPS, parfois on veut que le jeu soit assez rapide pour pouvoir enregistrer une vidéo du gameplay par USB sans le ralentir, parfois on veut que la simulation calcule 400 générations par seconde, et parfois on veut carrément avoir le code le plus rapide possible pour un challenge personnel.

Avoir une idée préliminaire de ce qui appartient au domaine du possible est utile pour se fixer des objectifs réalistes. Ça demande un peu d'expérience, mais par exemple je pense que si vous voulez un jeu en 3D classique à 10 FPS en pleine résolution sur Graph 90+E vous allez apprendre des choses sympa et vous amuser, si vous le voulez à 30 FPS vous allez suer, et si vous le voulez à 60 FPS vous allez échouer. En cas de doute, visez l'objectif modeste, ce sera plus fun.

Une autre idée utile, même si ça ça déborde un peu sur la gestion des projets de façon générale, c'est d'avoir une idée du temps qu'on veut y passer. C'est dur à estimer au début d'un projet (ça dépend à la fois des possibilités techniques et de votre expérience), mais après quelques heures de travail on sent en général si on s'attaque à un truc simple ou monstrueux, et on peut ajuster les ambitions en conséquence.

Identifier les parties du code qui ont besoin d'attention

On ne peut pas optimiser tout le code d'un programme à la fois, et de toute façon la plupart du code n'a pas besoin d'attention spécifique. Pour ménager le temps (et les nerfs), il est utile d'avoir une portée claire et raisonnable, ce qui nécessite de savoir ce qu'on veut optimiser et pourquoi on le fait.

Pour ça, il n'y a pas de meilleur outil que celui qui identifie quelle partie du programme consomme le plus de ressources.

Honnêtement, même avec toute l'expérience du monde, il n'y a pas de bonne raison d'optimiser des morceaux de programme avant d'avoir vérifié que c'est bien les morceaux qui prennent le plus du temps.

Dans un jeu par exemple, on prendra un soin considérable à mesurer le temps d'exécution du rendu de chaque frame, du traitement des entrées, et de la simulation physique ; à collecter des statistiques sur plusieurs frames pour observer les variations ; et à sous-diviser les parties qui prennent le plus de temps en mesures plus fines pour voir où se trouvent précisément les lenteurs.

De façon générale, si vous avez une partie qui prend un temps considérable par rapport aux autres, concentrez-vous dessus. Découpez la mesure en morceaux correspondant aux sous-fonctions de cette partie, et comparez les sous-mesures. S'il y en a une qui prend la majorité du temps, concentrez-vous dessus et oubliez les autres. Plus vous pouvez descendre bas comme ça et mieux vous serez, parce que ça veut dire qu'une petite partie du code prend une majorité du temps. Et on aime ça parce que plus la partie qu'on regarde est petite plus c'est facile à optimiser.

À l'inverse, si vous avez différentes parties indépendantes qui prennent toutes des temps similaires, vous aurez plus de mal à optimiser le programme parce que chaque transformation localisée n'affectera qu'une petite proportion du temps total.

Attention donc à optimiser avant d'avoir mesuré. Ça rejoint la célèbre maxime de Donald Knuth: "Premature optimization is the root of all evils" (l'optimisation prématurée est l'origine de tous les maux), qui avertit des problèmes qui attendent ceux qui programment un code «optimisé» avant d'avoir codé une version naïve. Notamment le risque de passer beaucoup d'efforts à pré-optimiser du code qui n'est pas du tout limitant, et le travail supplémentaire nécessaire pour gérer le code optimisé qui est souvent plus complexe que la version naïve (et donc plus facile à écrire de travers, buggé, etc).

Avoir une idée des ordres de grandeur

Dans les add-ins, beaucoup de choses peuvent être mesurées avec une grande précision. (On peut même mesurer le nombre exact de cycles processeur qu'une séquence d'instructions prend en la répétant un peu !) Par conséquent, on connaît des ordres de grandeur à toutes les échelles, et c'est très utile de voir comment les cycles presque-instantanés se transforment en microsecondes puis en millisecondes puis en secondes parfaitement tangibles pour les utilisateurs.

Voilà quelques ordres de grandeur classiques mais utiles à avoir en tête :

  • Un jeu qui tourne à 60 FPS dispose de 17 ms pour simuler et produire chaque frame.
  • Un jeu qui tourne à 30 FPS dispose de 33 ms pour simuler et produire chaque frame.
  • De façon générale le cerveau humain perçoit un effet d'instantanéité/fluidité quand la boucle de feedback entre l'action (par exemple la pression d'une touche) et le résultat (par exemple la mise à jour de l'écran) prend moins de 100 ms, et de préférence moins de 50 ms.
  • En général une seconde c'est la mesure de performance sur laquelle on définit un objectif (en FPS ou générations de simulation ou autre) ; une milliseconde c'est une partie du budget pour chaque frame/génération ; et une microseconde c'est 50-100 cycles d'horloge.

Voilà quelques ordres de grandeur pour les Graph mono :

  • Le processeur tourne à 58 MHz (Graph 35+E II) ou 29 MHz (autres modèles), donc il y a 58 ou 29 cycles par microseconde.
  • L'écran est aussi rapide que le proco, dupdate() prend environ 1 µs ou 2.5 µs (même distinction entre les modèles). On peut atteindre 400-500 FPS avec un peu d'effort, mais de toute façon l'écran ne s'actualise qu'à 64 Hz, donc ça ne sert à rien d'aller au-delà, il vaut mieux essayer d'être précisément synchronisé.
  • La VRAM fait 1024 octets et peut être couverte en 256 accès mémoire de 4 octets chacun, ce qui est très rapide.
  • Par conséquent, la puissance de calcul est souvent le principal limiteur, et l'overlock a beaucoup d'effet.
  • Il y a environ 96 ko de RAM très facilement accessible (un peu plus sur Graph 35+E II), et dans les 500 ko si on va chercher toutes les options y compris les plus casse-pieds.

La conclusion c'est que la Graph mono est une plateforme très chill en termes d'optimisation, sauf si on fait vraiment des choix défavorables (genre coller des nombres en point flottant partout). Je pense qu'on peut aisément écrire des jeux et atteindre le maximum absolu de 64 FPS sans jamais rien optimiser pourvu que ce soit fait dans les règles de l'art. La 3D est une exception évidemment (la 3D est toujours une exception).

Et voilà d'autres ordres de grandeur pour le modèle où l'optimisation est le plus souvent nécessaire, la Graph 90+E :

  • Le processeur tourne à 117 MHz (par défaut), donc il y a 117 cycles par microseconde.
  • dupdate() ou Bdisp_PutDisp_DD() prend 11.0 ms (!!), même si dans le cas de dupdate() ce temps est consommé en tâche de fond (ce qui peut fausser les mesures).
  • La VRAM fait 177 ko et peut être couverte en 44'000 accès mémoire de 4 octets chacun, ce qui en plus d'être lent nécessite d'être mis dans la RAM principale, ce qui n'aide pas à accélérer les choses.
  • Modifier à la main tous les pixels (396×224) prend environ 6.1 ms.
  • Afficher une image depuis la ROM en plein écran dépend du format de l'image, plus l'image prend de la place en ROM plus c'est lent. Pour du 16-bit complet compter environ 25 ms, pour du 8-bit indexé 20 ms, pour du 4-bit indexé 15 ms.
  • Clairement le dessin est extrêmement limitant pour à peu près tout le monde, sauf les programmes vraiment orientés calcul genre les fractales de Mandelbrot ou automates cellulaires.
  • L'overclock a de l'effet mais moins que sur Graph mono parce que la RAM et l'écran ne sont pas overclockées autant que le processeur.
  • Il y a environ 1 Mo de RAM très facilement accessible, et dans les 1.5 Mo si on va chercher toutes les options y compris les plus casse-pieds. Là-dedans, il y a environ 20 ko de mémoire réellement rapide, plus 32 ko de cache de données (associatif !).
  • Pour la plupart des applications, 30 FPS c'est un objectif sérieux (et c'est fluide pourvu qu'il n'y ait pas de tearing), 60 FPS c'est inutilement dur/limitant, et plus de 90 FPS c'est purement impossible avec les méthodes d'affichage classique.

Imaginons par exemple que je veux coder un RPG en plein écran sur Graph 90+E. À chaque frame, je dois afficher la map, qui couvre tout l'écran, à partir d'un tileset. Je suis quelque part entre 6.1 ms et 15 ms, sachant que le tileset est plus petit en mémoire qu'une image plein écran ; disons 10 ms. À ça on ajoute 11 ms pour rafraîchir l'écran, ce qui donne un total de 21 ms. Je sais donc déjà, avant d'avoir touché le moindre code, que mon jeu ne dépassera pas un plafond absolu de 50 FPS sauf à faire des choses non-orthodoxes. Mettons que je vise 30 FPS avec 30 simulations par seconde, ça me laisse 12 ms pour faire tout le dessin hors map, la simulation physique, et les IA (entre autres). Et là on rentre immédiatement dans le vif du sujet (spoiler: si les ennemis font du pathfinding sur une map de 200x200 avec un algo tout nul ça ne passera pas x3).

Mesurer souvent et rigoureusement

J'ai une théorie que dans les problèmes techniques et compliqués on se perd beaucoup plus vite parce qu'on n'arrive pas à organiser et analyser ce qu'on fait que par la complexité réelle des problèmes.

Pour ce qui est de l'optimisation, la réponse à beaucoup de choses est de mesurer plus, plus souvent, et plus rigoureusement. Dans mon expérience si la réponse n'est pas là, alors c'est soit un bug dans le programme soit un comportement du matériel qui était inconnu jusque-là.

Les yeux ne sont pas un bon instrument de mesure pour déterminer si le programme va plus vite ou pas. La RTC c'est potable mais c'est pas précis. Je ne vois aucune excuse pour ne pas utiliser le TMU pour mesurer les performances, surtout qu'on peut le faire sur tous les SDK : fx-9860G SDK, PrizmSDK, fxSDK sans problèmes particuliers. Pour le dernier, il y a même une bibliothèque qui automatise tout ça, libprof.

Comme la paire fxSDK/gint est la plateforme la plus courante sur Planète Casio, voilà un résumé express du cas d'usage le plus trivial le plus trivial de libprof. Le header est <libprof.h>, on initialise avec prof_init() et on nettoie avec prof_quit() :

#include <libprof.h>

int main(void)
{
    prof_init();
    /* .... */
    prof_quit();
    return 0;
}

Et pour savoir combien de temps un bout de code prend, prof_exec() :

uint32_t temps_rendu = prof_exec({
    dclear(C_WHITE);
    dimage(player_x, player_y, &image_player);
    dupdate();
});

temps_rendu; // = 2145 µs (exemple fictif)

Croyez-moi, vous ne regretterez jamais d'avoir codé ça en 3 minutes et d'avoir soudain des vrais chiffres à améliorer sur votre projet. De façon générale, vous ne regretterez pas de programmer les mesures du temps d'exécution dans votre programme parce que c'est à la fois très rapide à coder et extrêmement utile.

Je détaillerai les possibilités de mesure et de visualisation dans une autre technique, mais ça vous donne un avant-goût.

Quand vous envisagez d'optimiser quelque chose, prenez vraiment 30 minutes pour mesurer dans le détail ce qui prend du temps. Non seulement ça vous guidera pour optimiser les parties utiles, mais en plus ça vous aidera à former une intuition de ce qui peut poser des problèmes de performance et pourquoi.

Une fois que vous avez identifié le problème et la solution à atteindre, continuez de mesurer votre nouveau code à différentes étapes pour vérifier que la solution se conforme à vos attentes. On peut assez facilement avoir des surprises, et à la fin c'est toujours les chiffres qui ont raison.

Conclusion

Avoir les bonnes compétences et la bonne expérience technique permet certainement de rendre des programmes beaucoup plus rapides, mais avoir la bonne méthodologie permet de le faire avec beaucoup moins d'efforts de développement. Ne négligez pas d'y revenir de temps en temps, je promets que vous ne le regretterez pas.
Dark storm En ligne Labélisateur Points: 11501 Défis: 176 Message

Citer : Posté le 20/07/2021 20:56 | #


Excellent tout ça !

Je me permets de faire un petit aparté sur la complexité des algorithmes (#183646). Je ne garantis pas tout de suite l'exactitude de ce que je raconte, je mettrais à jour si il y a des trucs à corriger.

Problèmes NP-complets et solutions approximatives

Comme expliqué par Lephe, la grande majorité des problèmes auxquels vous allez être confrontés ont déjà été théorisés. Le tout étant de trouver quel(s) algorithme(s) connu(s) correspond(ent) au-dit problème . Si je prends l'exemple des tris, un tri bulle en O(n²) sera bien évidemment moins efficace dans le cas général qu'un tri rapide en O(n⋅log n). Donc si je compte trier la distance à la caméra d'un nuage de points de quelques centaines voire milliers d'éléments, j'ai tout intérêt à utiliser le meilleur algorithme à disposition.

Là où est l'os, c'est que tous les problèmes n'ont pas forcément un algorithme exact efficace. Si l'on prend par exemple le problème du voyageur de commerce, il faut nécessairement (n-1)!/2 opérations pour trouver la solution exacte. On est sur une complexité de O(n!). Pour rappel, la factorielle est une fonction qui croit très rapidement. Si 10! = 3 628 800, 100! ≈ 10¹⁵⁷. Autant dire qu'il n'est pas envisageable de résoudre exactement le problème pour une liste de villes qui dépasse la douzaine.

Dans ce cas il ne faut pas chercher à résoudre exactement le problème, mais trouver une solution suffisante. Un algorithme qui donne une solution approximative en un temps très court sera très probablement plus intéressant à utiliser que l'algorithme exact, qui en pratique sera inutilisable parce que vous n'allez pas attendre (littéralement) quelques milliers d'années qu'il vous retourne la solution.

Ces problèmes sont dit NP-complets. C'est à dire qu'on ne sait pas trouver la solution exacte en temps polynomial, que ce soit O(n²), O(n⁴) ou même O(n⁴⁹²⁷). Pour être très précis, NP signifie que l'on sait vérifier une solution en temps polynomial et complet veut dire que c'est le problème le plus difficile de sa classe (ie, de même complexité).

Bref, revenons à nos moutons, concrets. Je vais digresser un peu et prendre un exemple moins subtil mais beaucoup plus parlant, celui de la recherche d'un chemin dans un graphe. En anglais on parle de pathfinding. Il existe beaucoup d'algorithmes différents, mais je m'attarderais sur deux en particulier. Si l'algorithme de Dijkstra est exact, il est beaucoup moins rapide que l'A* (prononcez A-star), qui lui est bien, mais sans garantie que le résultat soit le meilleur possible.

Il est évident que choisir celui qui est le plus adapté sera primordial. Pour une IA qui ne laisse aucune chance au joueur, Dijkstra sera sûrement un bon choix, alors que A* sera sûrement préférable pour guider une horde de 143 zombies qui se dirigent vers le joueur à tout allure. On se fiche probablement que les zombies prennent exactement le meilleur chemin. Si ils prennent un chemin qui va vers le joueur, si possible sans faire le tour de la carte, ce sera déjà très bien.

La conclusion à cet addendum est que vous pouvez très bien, pour un problème donné, choisir d'utiliser une solution approximative : elle sera très probablement beaucoup plus rapide à calculer que la solution exacte. Dans certains cas, cela peut vous permettre de gagner quelques précieux FPS au détriment de la non-garantie d'être parfait. Comme d'habitude, l'optimisation est un jeu d'équilibre et de compromis.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Lephenixnoir En ligne Administrateur Points: 20317 Défis: 143 Message

Citer : Posté le 20/07/2021 21:05 | #


Merci ! C'est tout à fait exact, les algorithmes d'approximation sont très utiles. Quand ils sont formalisés en général on a une garantie, qui ressemble à «cet algorithme calcule un chemin qui est au plus 2 fois plus long que le chemin le plus court». Mais même quand ils ne sont pas formalisés et qu'il n'y a pas de garantie ça peut être très utile.

Deux petites corrections :
  • NP ⊆ EXPTIME donc le voyageur de commerce a des solutions en temps exponentiel, qui même si pas rapide, reste bien plus rapide que Θ(n!).
  • Tous les problèmes difficiles ne sont pas NP-complets ; il y en a des (beaucoup) plus difficiles, par exemple TQBF qui est PSPACE-complet (même si techniquement pas prouvé hors de NP), ou décider si une machine de Turing s'arrête en moins de k étapes, qui est EXPTIME-complet. Certains comme le problème de l'arrêt sont carrément indécidables, et il y en a d'autres qui sont «encore plus indécidables».
  • Mais c'est vrai que la plupart des problèmes de tous les jours sont dans NP donc les pires sont NP-complets.
Dark storm En ligne Labélisateur Points: 11501 Défis: 176 Message

Citer : Posté le 20/07/2021 21:42 | #


J'en profite pour caler ici un exemple concret, le Sprite Optimizer. Les lignes à dessiner que calcule l'outil ne sont pas forcément les plus optimales, mais dans la majorité des cas la solution est suffisante pour le but recherché.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Lephenixnoir En ligne Administrateur Points: 20317 Défis: 143 Message

Citer : Posté le 20/07/2021 21:47 | #


Très bon exemple ! Soit dit en passant je n'avais pas réussi à trouver de preuve directe que le problème dans le cas du Super DrawStat (où le lever de crayon a un coût) est NP-complet, mais je serais pas surpris qu'il le soit.

Le problème dans le cas de Multi DrawStat est un cas particulier de Set Cover, qui est NP-complet... mais qui a une approximation polynomiale qui donne un nombre de lignes au plus ln(n)+1 fois l'optimal (où n est le nombre d'ensembles). Les notions se retrouvent comme tu peux le voir
Lephenixnoir En ligne Administrateur Points: 20317 Défis: 143 Message

Citer : Posté le 20/07/2021 22:24 | #


Exploiter efficacement les caches (Programmation générale — ★☆☆)

Parmi les mémoires rapides du SH4AL-DSP (celui de la calculatrice en tous cas) auxquelles on peut accéder en un cycle, on a 8 ko de mémoire X, 8 ko de mémoire Y, 4 ko de mémoire IL, et un peu de mémoire RS qui est utilisée par l'OS pour des choses très importantes et à laquelle on ne touche donc pas en général. (X, Y, IL et RS sont juste les noms de ces mémoires, pas des «types» différents.)

Ce total est assez faible et même plus faible que la taille du cache : 32 ko pour le cache d'opérandes (et 32 ko aussi pour le cache d'instructions, mais ça c'est moins important en général). Ça veut dire qu'utiliser correctement le cache peut maximiser le nombre d'accès à un cycle (ou presque) pour des données de jusqu'à 32 ko dans la RAM principale, quand tout va pour le mieux.

Fonctionnement d'un cache simple

Le cache est un composant invisible pour le programme. Il sert d'intermédiaire durant tous les accès entre le CPU et la RAM, et accélère les accès quand c'est possible, mais n'affecte pas le comportement du programme.

Il faut bien voir qu'on ne peut pas contrôler ce qu'il y a dans le cache. Les contenus sont gérés automatiquement par un algorithme de remplacement, et même si on peut tout à fait faire des accès mémoire de façon à charger certaines données qu'on vise dans le cache, on ne peut pas écrire dans le cache comme on écrit dans les mémoires internes (X, Y, IL par exemple).

L'algorithme en question est assez simple :
  • Au début, le cache est vide.
  • Lors d'un accès en lecture, si les données sont dans le cache, il les renvoie. Sinon il charge les données de la RAM vers le cache et ensuite les renvoie. (Le cache note les données mais aussi leur adresse en RAM pour les retrouver plus tard.)
  • Lors d'un accès en écriture c'est à peu près pareil, mais il y a un paramètre pour choisir si on écrit immédiatement dans la RAM (write-through) ou uniquement dans le cache (copy-back). J'y reviendrai.
  • Quand on charge des données de la RAM vers le cache, s'il y a un emplacement libre «compatible» pour ces données elle est utilisée, sinon l'emplacement «compatible» qui est resté inutilisé le plus longtemps est expulsé et ses contenus sont recopiés dans la RAM.

Vous noterez que les données que vous demandez ne sont chargées qu'à un emplacement «compatible». La raison pour ça est simple : si le cache fait 8 ko et que vous demandez une adresse spécifique, le cache ne peut pas comparer toutes les 8000 adresses à la votre pour savoir s'il a les données. Il doit répondre en un cycle ! (Le choix de 8 ko comme exemple est important ; le cache réel de 32 ko est un peu différent, j'en parle dans la section suivante.)

Ce problème est éliminé de deux façons. D'abord les données ne sont pas chargées par octets mais par blocs qu'on appelle des lignes de cache. Sur le SH4AL-DSP, les lignes de cache font 32 octets, et alignées à des adresses multiples de 32. Par exemple (en supposant que les adresses dans la RAM commencent à 0 pour simplifier), 0x40-0x5f c'est une ligne de cache. Si vous accéder à l'adresse 0x54, le cache va charger toute la ligne 0x40-0x5f. Si vous accédez ensuite à 0x64, le cache va charger la ligne suivante 0x60-0x7f même si les deux adresses concernées sont distantes de moins de 32 octets.

Cela dit, quand vous demandez à accéder à une adresse, le cache de 8 ko ne peut pas faire 256 comparaisons pour savoir si la ligne est chargée, c'est toujours trop long. Donc en fait le cache est agencé pour que chaque ligne ne puisse être chargé qu'à un seul emplacement, à partir des bits de l'adresse.

Voilà comment ça se passe : dans une adresse de ligne de 32 bits, les 5 bits du bas sont forcément à 0 parce que l'adresse est multiple de 32. Les 8 bits suivants indiquent lequel des 256 emplacements peut contenir la ligne.

0x08103a40 = 0000 1000 0001 0000 001[1 1100 010][0 0000] → emplacement 1110 0010 = 226

Ça c'est très pratique pour le cache parce que quand vous demandez d'accéder à une adresse dans la RAM, il efface les 5 bits du bas pour trouver l'adresse de la ligne, il extrait les 8 bits suivants pour obtenir le numéro de l'emplacement, et ensuite il regarde si cet emplacement contient ou non la donnée que vous demandez. Si oui, il la renvoie. S'il est vide, il charge la donnée par un accès à la RAM. Sinon, il expulse la donnée présente et la remplace par la donnée que vous demandez par un accès à la RAM.

Vous noterez par conséquent que si vous accédez à 0x08103a40 puis à 0x08105a40, il y a une collision et donc l'accès à la deuxième ligne expulse la première ligne du cache, même si le cache est absolument vide partout ailleurs !!

Un cache simple de ce type est donc approprié pour charger un gros bloc continu, mais très mauvais si on accède à plusieurs zones à la fois parce que les collisions sont très difficiles à éviter. Le seul moyen de s'assurer que les adresses qu'on utilise n'ont pas de collisions, c'est d'avoir un seul bloc continu. (Cela dit, très souvent on utilise toujours la pile et la région des variables globales en même temps que les gros buffers de données, ce qui rend ce travail difficile.)

Les caches associatifs

Le cache associatif mitige les problèmes du cache simple en ajoutant plusieurs «voies». Essentiellement chaque voie est une copie du cache simple que j'ai présenté plus haut. Dans le SH4AL-DSP, il y a 4 voies de faisant chacune 8 ko (256 lignes de 32 octets), pour un total de 32 ko.

Avoir 4 voies signifie que chaque ligne de RAM peut maintenant être chargée à 4 emplacements différents. Ça donne aussi au cache 4 comparaisons à faire à chaque accès mémoire, mais ça reste assez raisonnable pour tenir en un cycle.

Avoir plusieurs voies donne aussi le choix de quel emplacement expulser quand aucun n'est libre pour charger une nouvelle ligne dans le cache. L'algorithme optimal, bien sûr, c'est d'expulser la ligne qui sera nécessaire la plus tard dans le futur. Mais ça, le proco ne le connaît pas. À la place, il expulse celle qui est restée inutilisée le plus longtemps possible. Cet algorithme s'appelle LRU (least recently used) et on peut prouver qu'il est pas mal par rapport à l'optimal.

Avec ça, vous pouvez comprendre quasiment tous les éléments dans la description des caches dans la documentation du SH4AL-DSP :


Accès favorables au cache et prefetching

Le cache associatif à 4 voies résout en partie le problème des collisions entre les accès au sujet du programme (par exemple un buffer de données de calcul ou de données graphiques) et les accès à des objets plus ou moins aléatoires comme la pile ou le segment de données.

Par exemple, dans la mesure où la pile est assez locale et occupe généralement une seule voie, vous pouvez accéder sans problème à un buffer de 8, 16 ou 24 ko puisque qu'il y aura assez de voies pour couvrir le buffer entier en plus des quelques accès à la pile.

Cependant, l'histoire ne s'arrête pas là. Si vous faites simplement une lecture ou une écriture linéaire du buffer, vous n'allez pas gagner énormément de temps. La raison c'est qu'à chaque fois que vous allez changer de ligne, le premier accès paiera le tarif complet d'un aller-retour vers la RAM pour charger la ligne, et ensuite seuls 7 accès (en supposant que tous les accès font 4 octets) seront réellement accélérés.

Pour cette raison, le cache dispose d'une opération dite de pré-chargement (prefetch). Le principe est d'indiquer à l'avance qu'on prépare un accès à une ligne, comme ça le cache charge la ligne pendant qu'on fait autre chose et au moment ou l'accès annoncé se présente tout est déjà dans le cache.

Le prefetching ne fait pas de la magie, surtout dans le cas d'une lecture linéaire, parce qu'il me semble que charger une ligne de cache prend plus de 8 cycles de toute façon donc même en saturant la RAM on ne peut pas lire un buffer de 8 ko en entier en un cycle par accès. Mais si on reste plus longtemps sur chaque ligne ça peut être assez utile.

Pour ce qui est des écritures, il y a deux modes : write-through (WT) où les écritures sont systématiquement faites dans la RAM ; et copy-back (CB) où les écritures sont faites uniquement dans le cache et le résultat est sauvegardé dans la RAM quand la ligne est expulsée (ce qu'on peut demander à la main avec une instruction dédiée).

Pour les performances, copy-back est bien évidemment mieux. Mais ça pose le problème que les données ne sont pas réellement écrites dans la RAM, donc si quelqu'un va lire la RAM sans passer par le cache il aura un résultat pas à jour. Et si vous regardez la cartographie des bus du processeur, vous pouvez identifier des accès de ce type ; par exemple le DMA ignore le cache, donc une écriture dans la RAM sur une page en copy-back qui est toujours dans le cache est invisible pour le DMA. Ce problème dit de cohérence des mémoires est une des raisons pour laquelle les caches sont un sujet compliqué ; nous on n'a qu'un cache donc c'est raisonnablement simple, mais dans les processeurs multi-coeurs ça peut vite devenir un enfer.

Avec ça, je pense avoir fait le tour des éléments importants. Je ne vous donne pas ici de recette pour utiliser le cache efficacement, à part utiliser des buffers pas trop gros de façon très linéaire, parce que je n'en connais pas. Mais au moins vous devriez avoir toutes les informations pour étudier l'usage du cache au cas-par-cas dans vos programmes.

Dans l'ensemble, bien utiliser le cache dans un programme est relativement compliqué et demande pas mal d'attention aux détails. Personnellement, je préfère utiliser en priorité les mémoires rapides (X, Y, IL) et utiliser le cache en dernier ressort.

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2021 | Il y a 69 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd