comment calculer le temps d'exécution attendu


Réponse 1:

Vous ne pouvez pas, car vous devez en savoir beaucoup plus que la vitesse du processeur. La fréquence du processeur n'est qu'un facteur, et probablement même pas le facteur le plus important.

  • Vous devez également connaître le nombre de cycles d'horloge dont chaque instruction machine a besoin.
  • Vous devez également connaître le nombre de cycles d'horloge pour toutes les entrées et sorties, y compris tous les accès à la mémoire et aux périphériques.

De nombreux programmes (la plupart?) Sont «liés aux E / S» plutôt que «liés au processeur», ce qui signifie que la récupération des instructions et des données et l'envoi des données prennent la majorité du temps.

Et c'est plus compliqué que ça.

L'accès à la mémoire des ordinateurs modernes comprend la mémoire principale et différents niveaux de cache. L'accès au cache sur puce de niveau 1 (L1) ne peut prendre qu'un cycle, tandis que le cache de niveau 2 plus grand (également sur puce) prend plusieurs fois plus de temps à accéder et le cache de niveau 3, s'il existe, prendra encore plus de temps, mais tout cela sont beaucoup plus rapides que l'accès à la mémoire principale de l'ordinateur. Et tous ces types de mémoire sont beaucoup plus rapides que l'accès à la mémoire non volatile où votre programme et vos données sont stockés. Et ceux-ci sont beaucoup plus rapides que les données auxquelles il faut accéder via le réseau local. Et celles-ci sont beaucoup plus rapides que toutes les données auxquelles vous avez besoin d'accéder via Internet.

Souvent, vous obtiendrez une meilleure estimation du temps d'exécution du programme simplement en additionnant tous les temps d'E / S plus longs et en supposant que le processeur est infiniment rapide.

Enfin, si vous trouvez que vous avez un programme rare dominé par le temps CPU plutôt que par le temps d'E / S, vous devez comprendre que les instructions se chevauchent dans les processeurs modernes, de sorte que le temps total de toutes les instructions prend beaucoup moins de temps que la somme de les heures de chaque instruction. Pour calculer ce temps, vous avez besoin d'une connaissance très détaillée du pipeline d'instructions et de la manière dont ces instructions se chevauchent.

Leçon principale: Pour rendre votre programme aussi rapide que possible, minimisez vos temps d'E / S et localisez votre accès à la mémoire afin que les données et la mémoire du cache soient utilisées autant que possible avant d'être vidées par d'autres instructions et données.


Réponse 2:

L'équation de performance

L'équation de performance analyse le temps d'exécution comme un produit de trois facteurs relativement indépendants les uns des autres.

Cette équation reste valide si les unités de temps sont modifiées des deux côtés de l'équation. Le côté gauche et les facteurs du côté droit sont traités dans les sections suivantes.

Les trois facteurs sont, dans l'ordre, appelés nombre d'instructions (IC), horloges par instruction (CPI) et heure d'horloge (CT). L'IPC est calculé comme une valeur effective.

Équation de performance

Nombre d'instructions Valeurs efficaces Horloges par instruction Horloge Heure Exemples d'améliorations

L'équation de performance

L'équation de performance analyse le temps d'exécution comme un produit de trois facteurs relativement indépendants les uns des autres.

Nombre d'instructions

Les architectes informatiques peuvent réduire le nombre d'instructions en ajoutant des instructions plus puissantes au jeu d'instructions. Cependant, cela peut augmenter l'IPC ou le temps d'horloge, ou les deux.

Horloges par instruction

Les architectes informatiques peuvent réduire l'IPC en exploitant davantage de parallélisme au niveau des instructions. S'ils ajoutent des instructions plus complexes, cela augmente souvent l'IPC.

Temps d'horloge

Le temps d'horloge dépend de la vitesse du transistor et de la complexité du travail effectué dans une seule horloge. Le temps d'horloge peut être réduit lorsque la taille des transistors diminue. Cependant, la consommation d'énergie augmente lorsque l'heure de l'horloge est réduite. Cela augmente la quantité de chaleur générée.

Nombre d'instructions

Le nombre d'instructions (IC) est une mesure dynamique: le nombre total d'exécutions d'instructions impliquées dans un programme. Il est dominé par des opérations répétitives telles que des boucles et des récursions.

Le nombre d'instructions est affecté par la puissance du jeu d'instructions. Différents ensembles d'instructions peuvent effectuer différentes quantités de travail en une seule instruction. Les instructions du processeur CISC peuvent souvent accomplir jusqu'à deux ou trois instructions du processeur RISC. Certaines instructions de processeur CISC ont un bouclage intégré de sorte qu'elles peuvent accomplir jusqu'à plusieurs centaines d'exécutions d'instructions RISC.

Pour prédire les effets des changements incrémentiels, les architectes utilisent les traces d'exécution des programmes de référence pour obtenir le nombre d'instructions. Si le changement incrémentiel ne modifie pas le jeu d'instructions, le nombre d'instructions ne change normalement pas. S'il y a de petits changements dans le jeu d'instructions, les informations de trace peuvent être utilisées pour estimer le changement dans le nombre d'instructions.

À des fins de comparaison, deux machines avec des jeux d'instructions différents peuvent être comparées sur la base de compilations du même code de langage de haut niveau sur les deux machines.

Horloges par instruction

Les horloges par instruction (IPC) sont une moyenne effective. Il est moyenné sur toutes les exécutions d'instructions dans un programme.

L'IPC est affecté par le parallélisme au niveau de l'instruction et par la complexité de l'instruction. Sans parallélisme au niveau des instructions, les instructions simples nécessitent généralement 4 cycles ou plus pour s'exécuter. Les instructions qui exécutent des boucles prennent au moins une horloge par itération de boucle. Le pipelining (exécution superposée des instructions) peut ramener la moyenne des instructions simples à près de 1 horloge par instruction. Le pipelining superscalaire (émettant plusieurs instructions par cycle) peut ramener la moyenne à une fraction d'horloge par instruction.

Pour calculer les horloges par instruction en tant que moyenne effective, les cas sont des catégories d'instructions, telles que des branches, des charges et des magasins. Les fréquences des catégories peuvent être extraites des traces d'exécution. La connaissance de la façon dont l'architecture gère chaque catégorie donne les horloges par instruction pour cette catégorie.

Temps d'horloge

Le temps d'horloge (CT) est la période de l'horloge qui synchronise les circuits dans un processeur. C'est l'inverse de la fréquence d'horloge.

Par exemple, un processeur 1 GHz a un temps de cycle de 1,0 ns et un processeur 4 GHz a un temps de cycle de 0,25 ns.

L'heure de l'horloge est affectée par la technologie des circuits et la complexité du travail effectué en une seule horloge. Les portes logiques ne fonctionnent pas instantanément. Une porte a un délai de propagation qui dépend du nombre d'entrées de la porte (fan in) et du nombre d'autres entrées connectées à la sortie de la porte (fan out). L'augmentation du ventilateur ou de la sortie du ventilateur ralentit le temps de propagation. Le temps de cycle est défini comme étant le temps de propagation total le plus défavorable à travers les portes qui produisent un signal requis dans le cycle suivant. Le temps de propagation total le plus défavorable se produit le long d'un ou plusieurs chemins de signaux à travers les circuits. Ces chemins sont appelés chemins critiques.

Au cours des 35 dernières années, la technologie des circuits intégrés a été grandement affectée par une équation de mise à l'échelle qui indique comment les dimensions individuelles des transistors devraient être modifiées à mesure que les dimensions globales diminuent. Les équations d'échelle prédisent une augmentation de la vitesse et une diminution de la consommation d'énergie par transistor avec une taille décroissante. La technologie s'est améliorée de sorte qu'environ tous les 3 ans, les dimensions linéaires ont diminué d'un facteur 2. La consommation d'énergie des transistors a diminué d'un facteur similaire. La vitesse a augmenté d'un facteur similaire jusqu'en 2005. À cette époque, la consommation d'énergie a atteint un point où le refroidissement par air n'était pas suffisant pour maintenir les processeurs au frais s'ils fonctionnaient à la vitesse d'horloge la plus élevée possible.

Énoncé du problème

Supposons qu'un programme (ou une tâche de programme) nécessite 1 milliard d'instructions pour s'exécuter sur un processeur fonctionnant à 2 GHz. Supposons également que 50% des instructions s'exécutent en 3 cycles d'horloge, 30% s'exécutent en 4 cycles d'horloge et 20% s'exécutent en 5 cycles d'horloge. Quelle est la durée d'exécution du programme ou de la tâche?

Énoncé du problème Solution

Solution

Supposons qu'un programme (ou une tâche de programme) nécessite 1 milliard d'instructions pour s'exécuter sur un processeur fonctionnant à 2 GHz. Supposons également que 50% des instructions s'exécutent en 3 cycles d'horloge, 30% s'exécutent en 4 cycles d'horloge et 20% s'exécutent en 5 cycles d'horloge. Quelle est la durée d'exécution du programme ou de la tâche?

Nous avons le nombre d'instructions: 109 instructions. L'heure de l'horloge peut être calculée rapidement à partir de la fréquence d'horloge à 0,5 × 10-9 secondes. Il suffit donc de calculer les horloges par instruction en tant que valeur effective:

Valeur Fréquence Produit

3 0,5 1,5

4 0,3 1,2

5 0,2 1,0

IPC = 3,7

Ensuite nous avons

Temps d'exécution = 1,0 × 109 × 3,7 × 0,5 × 10-9 sec = 1,85 sec.

Énoncé du problème

Supposons que le processeur de l'exemple précédent soit redessiné de telle sorte que toutes les instructions initialement exécutées en 5 cycles s'exécutent maintenant en 4 cycles. En raison de changements dans les circuits, la fréquence d'horloge doit être diminuée de 2,0 GHz à 1,9 GHz. Quelle est l'amélioration globale en pourcentage?

Énoncé du problème Solution Formulaire Solution

Formulaire de solution

Supposons que le processeur de l'exemple précédent soit redessiné de telle sorte que toutes les instructions initialement exécutées en 5 cycles s'exécutent maintenant en 4 cycles. En raison de changements dans les circuits, la fréquence d'horloge doit être diminuée de 2,0 GHz à 1,9 GHz. Aucune modification n'est apportée au jeu d'instructions. Quelle est l'amélioration globale en pourcentage?

W peut déterminer rapidement le pourcentage d'amélioration en trouvant d'abord le rapport entre les performances avant et après. L'équation de performance implique que ce rapport sera un produit de trois facteurs: un rapport de performance pour le nombre d'instructions, un rapport de performance pour l'IPC ou son réciproque, le débit d'instructions et un rapport de performance pour le temps d'horloge ou sa fréquence d'horloge réciproque. Nous pouvons ignorer le premier facteur de ce problème puisqu'il est de 1.0: le nombre d'instructions n'a pas changé. Il ne nous reste plus qu'à déterminer le rapport de performance pour l'IPC et, puisque l'on nous donne des fréquences d'horloge, le rapport de performance pour les fréquences d'horloge.

Solution

Supposons que le processeur de l'exemple précédent soit redessiné de telle sorte que toutes les instructions initialement exécutées en 5 cycles s'exécutent maintenant en 4 cycles. En raison de changements dans les circuits, la fréquence d'horloge doit être diminuée de 2,0 GHz à 1,9 GHz. Aucune modification n'est apportée au jeu d'instructions. Quelle est l'amélioration globale en pourcentage?

Le rapport de performance pour les fréquences doit être inférieur à 1,0: si les autres facteurs sont les mêmes, une fréquence d'horloge plus lente implique de moins bonnes performances. Donc, ce facteur du rapport d'amélioration doit être de 1,9 / 2,0.

Pour les horloges par instruction, nous avions une valeur de 3,7 avant le changement. Nous calculons les horloges par instruction après le changement comme une valeur effective:

Valeur Fréquence Produit

3 0,5 1,5

4 0,3 1,2

4 0,2 0,8

IPC = 3,5

Maintenant, des horloges plus faibles par instruction signifie un débit d'instructions plus élevé et donc de meilleures performances, nous nous attendons donc à ce que cette partie du rapport de performance soit supérieure à 1,0; c'est-à-dire 3,7 / 3,5.


Réponse 3:

Je suggère d'écrire le programme et de tester en prenant le temps en millisecondes au début de l'exécution et à la fin de l'exécution. Il est difficile de décider sans écrire le programme à moins qu'il ne soit en assemblage. Je penserais à une commande de saut d'assemblage ou de déplacement comme une seule instruction. Dans une seule ligne de code de haut niveau, il y a plus d'une instruction. Par code de haut niveau, j'entends C ++, Java, C, Fortran. Peut-être pourrait-il être estimé avec approximation. Supposons que vous ayez une boucle for régulière qui dure 100 itérations. si vous avez approximé le temps de faire une assighnment / déclaration de variable, et comment y ajouter une. cela prendrait assighnmentTime + declarationTime + (100 * additonTime). Je dis que vous auriez besoin de connaître le nombre d'instructions simplement, car les instructions par seconde ou IPS peuvent être calculées par des informations matérielles.


Réponse 4:

Vous ne pouvez vraiment faire cela que pour de simples microcontrôleurs car leur fiche technique vous donne le nombre d'horloge pour chaque instruction et ceux-ci ont généralement des cycles d'exécution d'extraction très simples. Les machines plus puissantes ont des caches à plusieurs niveaux, une prédiction de branche, une réorganisation des instructions et une exécution spéculative, ce qui rend pratiquement impossible de déterminer l'heure. D'autres facteurs qui influenceraient la synchronisation seraient le cache de partage du cœur du processeur adjacent, l'effet de tout hyperviseur et même la révision du microcode du processeur.

Le seul moment où vous voudrez peut-être essayer, c'est lors de l'optimisation du «cœur» d'un algorithme DSP, mais vous le feriez probablement juste pour qu'il tienne dans le cache.


Réponse 5:

InstructionsExécuté x CyclesPerInstruction / CpuFrequency

Le hic, c'est que les cycles par instruction ne sont absolument pas constants sur les cœurs modernes et peuvent aller de 0,2 à 100+ (et cela ne prend même pas en compte la fréquence d'horloge multicœur et variable).

Sur les processeurs 8 bits, vous pouvez connaître le nombre exact de cycles que prend chaque instruction (généralement à partir du manuel du processeur) et les additionner.

Pour les processeurs modernes,

https://www.agner.org/optimize/instruction_tables.pdf

vous donne un guide de la vitesse maximale possible à laquelle différentes instructions peuvent s'exécuter.


Réponse 6:

Vous devez en savoir plus que la simple fréquence du processeur. Combien d'instructions par cycle sont exécutées? Combien de cache y a-t-il? Quelle est la bande passante de la mémoire système? Dans quelle mesure le programme est-il optimisé en ce qui concerne la mise en cache ou l'accès aux ressources. Si le programme doit accéder à un autre matériel, comme un disque dur ou une carte réseau, il peut être presque impossible de prévoir avec précision.

Sur des systèmes très basiques comme les microcontrôleurs embarqués, vous avez moins de variables dans votre environnement, et vous pouvez raisonnablement simuler l'exécution du programme, et donc prédire le temps d'exécution.


Réponse 7:

Pour cela, vous devez connaître précisément le temps d'exécution de chaque instruction. Et il est préférable de tirer sur le programme en langage d'assemblage et non quelque chose comme see, cplusplus ou l'un des langages de programmation interprétés. Une instruction de langage de programmation ne s'exécutera pas dans un laps de temps prévisible à moins qu'il ne s'agisse d'une opération de base très simple. Alors que chaque instruction en langage d'assemblage peut être minutée avec précision


Réponse 8:

Dans les temps très anciens, il y avait une chance de faire cela, mais pas plus. Les ordinateurs disposent désormais de divers caches et pipelines, ainsi que d'optimisations, de files d'attente et d'unités fonctionnelles qui rendent impossible le calcul du temps d'exécution à moins de 25%.


Réponse 9:

tandis que (rand ()! = 3,14159) {};

Bien que ce ne soit pas un programme réaliste, il illustre la difficulté de ce que vous essayez de faire.

Bonne chance.