Comment gérer la prédiction de branchement lors de l'utilisation d'un boîtier de commutation dans l'émulation CPU

Question

J'ai récemment lu la question ici Pourquoi est-il plus rapide de traiter un tableau trié qu’un tableau non trié ? et j'ai trouvé la réponse absolument fascinante et cela a complètement changé ma vision de la programmation lorsque je traite des branches basées sur des données.

J'ai actuellement un émulateur Intel 8080 interprété assez basique, mais entièrement fonctionnel, écrit en C, le cœur de l'opération est une table de 256 commutateurs de long pour gérer chaque opcode.Ma première pensée était que ce serait évidemment la méthode de travail la plus rapide, car le codage des opcodes n'est pas cohérent dans tout le jeu d'instructions 8080 et le décodage ajouterait beaucoup de complexité, d'incohérence et de cas ponctuels.Une table de commutation remplie de macros de pré-processeur est très soignée et facile à entretenir.

Malheureusement, après avoir lu le message susmentionné, je me suis rendu compte qu'il n'y avait absolument aucun moyen pour le prédicteur de branchement de mon ordinateur de prédire le saut pour le boîtier de commutation.Ainsi, chaque fois que vous parcourez le boîtier de commutation, le pipeline devrait être complètement effacé, ce qui entraînerait un retard de plusieurs cycles dans ce qui devrait autrement être un programme incroyablement rapide (il n'y a même pas de multiplication dans mon code).

Je suis sûr que la plupart d'entre vous pensent "Oh, la solution ici est simple, passez à la recompilation dynamique".Oui, cela semble supprimer la majorité du boîtier de commutation et augmenter considérablement la vitesse.Malheureusement, mon principal intérêt est d'émuler les anciennes consoles de l'ère 8 bits et 16 bits (l'Intel 8080 ici n'est qu'un exemple car c'est mon morceau de code émulé le plus simple) où le cycle et le timing respectant les instructions exactes sont importants comme la vidéo et le son. doivent être traités en fonction de ces horaires précis.

Face à ce niveau de précision, les performances deviennent un problème, même pour les consoles plus anciennes (regardez bSnes par exemple).Existe-t-il un recours ou s'agit-il simplement d'un simple fait lorsqu'il s'agit de transformateurs dotés de longs pipelines ?

Answer 1

Au contraire, switch les déclarations sont susceptibles d'être converties en tables de saut, ce qui signifie qu'ils effectuent éventuellement quelques ifs (pour vérifier la portée) et un seul saut.Le ifs ne devrait pas poser de problème avec la prédiction de branche car il est peu probable que vous ayez un mauvais code opérationnel.Le saut n'est pas si convivial avec le pipeline, mais au final, ce n'est qu'un pour l'ensemble switch déclaration..

Je ne crois pas qu'on puisse convertir longtemps switch déclaration des codes opérationnels sous toute autre forme qui entraînerait de meilleures performances.C'est bien sûr si votre compilateur est suffisamment intelligent pour le convertir en table de sauts.Sinon, vous pouvez le faire manuellement.

En cas de doute, mettez en œuvre d’autres méthodes et mesurez les performances.

Modifier

Tout d'abord, assurez-vous de ne pas confondre prédiction de branche et bifurquer cible prédiction.

La prédiction de branche fonctionne uniquement sur les instructions de branche.Il décide si une condition de branchement échouera ou réussira.Ils n'ont rien à voir avec l'instruction jump.

La prédiction de cible de branche, quant à elle, essaie de deviner où le saut aboutira.

Ainsi, votre déclaration "il n'y a aucun moyen pour le prédicteur de branche de prédire le saut" devrait être "il n'y a aucun moyen pour que le prédicteur de branche puisse prédire le saut". cible un prédicteur peut prédire le saut".

Dans votre cas particulier, je ne pense pas que vous puissiez réellement éviter cela.Si vous aviez un très petit ensemble d’opérations, vous pourriez peut-être trouver une formule qui couvre toutes vos opérations, comme celles effectuées dans les circuits logiques.Cependant, avec un jeu d'instructions aussi grand que celui d'un processeur, même s'il s'agissait de RISK, le coût de ce calcul est bien supérieur à la pénalité d'un seul saut.

Answer 2

Comme les branches de votre relevé de commutation de 256 voies sont densément emballées, le compilateur implémentera ceci comme une table de saut, vous avez donc raison que vous avez raison de déclencher une seule trajectoire de branche chaque fois que vous passez à travers ce code (comme Le saut indirect n'affiche aucune sorte de comportement prévisible). La sanction associée à cela sera d'environ 15 cycles d'horloge sur un processeur moderne (pont sablonneux) ou peut-être jusqu'à 25 sur des microchitectures plus anciennes qui n'ont pas de cache micro-op. Une bonne référence pour ce type de chose est "Ressources d'optimisation logicielle" sur agner.org. Page 43 Dans "Optimiser les logiciels en C ++" est un bon endroit pour commencer.

http://www.agner.org/optimize/?e=0, 34

Le seul moyen de pouvoir éviter que cette pénalité est en veillant à ce que les mêmes instructions soient exécutées, quelle que soit la valeur de l'opcode. Cela peut souvent être fait en utilisant des mouvements conditionnels (qui ajoutent une dépendance de données, de sorte que la branche prévisible est plus lente) ou à la recherche de symétrie dans vos chemins de code. Compte tenu de ce que vous essayez de faire cela ne sera probablement pas possible, et s'il s'agissait alors, cela ajouterait presque certainement une surcharge supérieure aux cycles d'horloge de 15-25 pour le tagistrédict.

En résumé, sur une architecture moderne, vous ne pouvez pas faire que cela sera plus efficace qu'un commutateur / un cas, et le coût de la fausse déclaration sur la traduction n'est pas autant que vous pourriez vous attendre.

Answer 3

Le saut indirect est probablement la meilleure chose à faire pour le décodage d'instructions.

sur des machines plus anciennes, comme dire l'Intel P6 à partir de 1997, le saut indirect obtiendrait probablement une branche inexprimé.

sur des machines modernes, comme Say Intel Core I7, il y a un prédicteur de saut indirect qui fait un assez bon travail d'évité à la mauvaise répugnation de la branche.

Mais même sur les anciennes machines qui n'ont pas de prédicteur de la branche indirecte, vous pouvez jouer un tour. Cette astuce est (était), à la manière, documentée dans le Guide d'optimisation du code Intel à partir du retour dans les Jours Intel P6:

au lieu de générer quelque chose qui ressemble à

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       jmp loop
    label_instruction_01h_SUB: ...
       jmp loop
    ...

générer le code comme

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_01h_SUB: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    ...

I.e. Remplacez le saut en haut de l'instruction Fetch / Decod / Execute Boop par le code en haut de la boucle à chaque endroit.

Il s'avère que cela a beaucoup de meilleure prédiction des succursales, même en l'absence de prédicteur indirect. Plus précisément, une cible conditionnelle, une cible unique, PC indexé BTB sera très bien meilleure dans ce dernier, fileté, code, que sur l'original avec une seule copie du saut indirect.

La plupart des ensembles d'instructions ont des modèles spéciaux - par exemple Sur Intel X86, une instruction de comparaison est presque toujours suivie d'une branche.

bonne chance et amusez-vous!

(au cas où vous vous inquiétez, les décodeurs d'instructions utilisés par les simulateurs d'instructions dans l'industrie font presque toujours toujours une arborescence de sauts N-Way, ou le Dual piloté par les données, naviguez sur une arborescence de tables N-Way, à chaque entrée de l'arbre pointant vers d'autres nœuds, ou à une fonction pour évaluer.

OH, et peut-être que je devrais mentionner: ces tables, ces instructions de commutation ou des structures de données sont générées par des outils spéciaux.

Un arbre de N-Way saute, car il y a des problèmes lorsque le nombre de cas dans la table de saut devient très grand - dans l'outil, MKIRECOG (faire reconnaître l'instruction) que j'ai écrit dans les années 1980, je faisais habituellement des tables de saut Jusqu'à 64k entrées de taille, c'est-à-dire sautant sur 16 bits. Les compilateurs du temps ont éclaté lorsque les tables de saut ont dépassé 16 m de taille (24 bits).

Données entraînées, c'est-à-dire un arbre de nœuds pointant vers d'autres nœuds car (a) sur des sauts indirects de machines plus anciens peut ne pas être prédit, et (b) il s'avère que la plupart du temps il y a du code commun entre les instructions - à la place. d'avoir une branche malfrédiction lorsque vous passez à l'affaire par instruction, puis exécutant du code commun, puis en passant à nouveau et obtenez un deuxième malfistricat, vous faites le code commun, avec des paramètres légèrement différents (comme, combien de bits du flux d'instructions avez-vous consommer et où le prochain ensemble de bits à la branche est (sont).

J'étais très agressif dans MKIRECOG, car je dis que vous disez jusqu'à 32 bits d'être utilisé dans un commutateur, bien que des limitations pratiques m'ont presque toujours arrêté à 16-24 bits. Je me souviens que j'ai souvent vu le premier décodage sous forme d'interrupteur de 16 ou 18 bits (entrées de 64k-256k), et tous les autres décodes étaient beaucoup plus petits, pas de plus grand que 10 bits.

Hmm: J'ai posté Mkirecog à Usenet Back Circa 1990. FTP: // FTP. lf.net/pub/unix/programming/misc/mkirecog.tar.gz Vous pourrez peut-être voir les tables utilisées si vous vous souciez. (Soyez gentil: J'étais jeune alors. Je ne me souviens pas si c'était Pascal ou C. J'ai depuis réécrit de nombreuses fois - bien que je n'ai pas encore réécrit d'utiliser des vecteurs bits C ++.)

La plupart des autres gars, je sais qui fait ce genre de chose fait des choses un octet à la fois - c'est-à-dire un huit bits, 256 voies, une branche ou une recherche de table.)

Answer 4

Je pensais ajouter quelque chose puisque personne ne l'a mentionné.

accordé, le saut indirect est probablement la meilleure option.

Cependant, devriez-vous aller avec la N-Compare Way, il y a deux choses qui me viennent à l'esprit:

Tout d'abord, au lieu de faire de n égalité se compare, vous pouvez faire des inégalités de journal (n) compare vos instructions en fonction de leur opcode numérique par dichotomie (ou testez le bit de numéro si l'espace de valeur est proche de la totalité). Ceci est un peu comme une haquetable, vous implémentez un arbre statique pour trouver l'élément final.

Deuxièmement, vous pouvez exécuter une analyse sur le code binaire que vous souhaitez exécuter. Vous pourriez même faire cela par binaire, avant exécution et exécution de votre émulateur. Cette analyse construirait un histogramme représentant la fréquence des instructions, puis organiseriez vos tests afin que les instructions les plus fréquentes soient prédites correctement.

Mais je ne peux pas voir cela étant plus rapide qu'une pénalité de cycles de milieu, à moins que vous n'ayez 99% de MOV et que vous mettez une égalité pour le fonctionnement de MOP avant les autres tests.