Machine à empiler

Les machines à pile présentent une densité de code plus élevée . Contrairement aux instructions classiques des machines à pile, qui tiennent facilement sur 6 bits ou moins, les machines à registres nécessitent deux ou trois champs de numéro de registre par instruction ALU pour sélectionner les opérandes ; les machines à registres les plus denses utilisent en moyenne 16 bits par instruction, plus les opérandes. Elles utilisent également un champ de décalage plus large pour les opérations de chargement/stockage. Le code compact d'une machine à pile permet naturellement de stocker davantage d'instructions en cache, ce qui peut améliorer l'efficacité du cache , réduire les coûts de mémoire ou permettre des systèmes de mémoire plus rapides pour un coût donné. De plus, la plupart des instructions des machines à pile sont très simples, composées d'un seul champ d'opcode ou d'un seul champ d'opérande. Ainsi, les machines à pile nécessitent très peu de ressources électroniques pour décoder chaque instruction.

Un programme compilé pour une machine à pile doit exécuter davantage d'instructions que pour une machine à registres ou une machine mémoire-à-mémoire. Chaque chargement de variable ou de constante requiert sa propre instruction de chargement, au lieu d'être regroupé dans l'instruction qui utilise cette valeur. Bien que ces instructions séparées soient plus simples et plus rapides à exécuter, le nombre total d'instructions reste plus élevé.

La plupart des interpréteurs de registres spécifient leurs registres par numéro. Cependant, les registres d'une machine hôte ne sont pas accessibles par un tableau indexé ; un tableau mémoire est donc alloué aux registres virtuels. Par conséquent, les instructions d'un interpréteur de registres doivent utiliser la mémoire pour transmettre les données générées à l'instruction suivante. Ceci contraint les interpréteurs de registres à être beaucoup plus lents sur les microprocesseurs à gravure fine (c'est-à-dire des transistors plus rapides sans amélioration de la vitesse du circuit, comme le Haswell x86). Ces derniers nécessitent plusieurs cycles d'horloge pour l'accès à la mémoire, contre un seul pour l'accès aux registres. Dans le cas d'une machine à pile dotée d'un circuit de transfert de données au lieu d'un fichier de registres, les interpréteurs de pile peuvent allouer les registres de la machine hôte pour les premiers opérandes de la pile, au lieu de la mémoire de la machine hôte.

Dans une machine à pile, les opérandes utilisés dans les instructions se trouvent toujours à un décalage connu (défini par le pointeur de pile) par rapport à une adresse fixe (le bas de la pile, qui, dans une conception matérielle, correspond généralement à l'adresse mémoire zéro). Ceci permet d'économiser de précieuses ressources de mémoire cache ou de processeur , en évitant de stocker un trop grand nombre d'adresses mémoire ou d'indices. Ces registres et le cache peuvent ainsi être utilisés pour des calculs autres que ceux liés au flux.

Certains acteurs du secteur estiment que les machines à pile exécutent plus de cycles de cache de données pour les valeurs temporaires et les variables locales que les machines à registres.

Sur les machines à pile, les valeurs temporaires sont souvent déversées en mémoire, tandis que sur les machines à registres multiples, elles restent généralement dans les registres. (Toutefois, ces valeurs doivent souvent être déversées dans des « cadres d'activation » à la fin de la définition d'une procédure, d'un bloc de base, ou au minimum, dans un tampon mémoire lors du traitement des interruptions). Les valeurs déversées en mémoire augmentent le nombre de cycles de cache. Cet effet de déversement dépend du nombre de registres cachés utilisés pour stocker les valeurs en haut de la pile, de la fréquence des appels de procédures imbriqués et de la vitesse de traitement des interruptions de l'ordinateur hôte.

Sur les machines à registres utilisant des compilateurs optimisants, il est très fréquent que les variables locales les plus utilisées restent dans les registres plutôt que dans les cellules mémoire de la pile. Cela permet d'éliminer la plupart des cycles de cache de données pour la lecture et l'écriture de ces valeurs. Le développement de la « planification de la pile » pour effectuer une analyse des variables en temps réel , et donc conserver les variables clés sur la pile pendant des périodes prolongées, contribue à résoudre ce problème.

En revanche, les machines à registres doivent décharger une grande partie de leurs registres en mémoire lors d'appels de procédures imbriqués. La décision concernant les registres à décharger, et le moment de ce déchargement, est prise statiquement à la compilation, et non en fonction de la profondeur dynamique des appels. Cela peut engendrer un trafic de cache de données plus important que dans une implémentation de machine à pile avancée.

Dans les machines à registres, une sous-expression courante (une sous-expression utilisée plusieurs fois avec le même résultat) peut être évaluée une seule fois et son résultat stocké dans un registre rapide. Les réutilisations suivantes n'entraînent aucun coût en temps ni en code, seulement une référence au registre. Cette optimisation accélère les expressions simples (par exemple, le chargement de la variable X ou du pointeur P) ainsi que les expressions complexes moins fréquentes.

Avec les machines à pile, en revanche, les résultats peuvent être stockés de deux manières. Premièrement, ils peuvent être stockés dans une variable temporaire en mémoire. Le stockage et les accès ultérieurs nécessitent des instructions et des cycles de cache supplémentaires. Cette méthode n'est avantageuse que si le calcul de la sous-expression est plus coûteux en temps que la récupération en mémoire, ce qui est presque toujours le cas sur la plupart des processeurs à pile. Elle n'est jamais intéressante pour les variables simples et les accès aux pointeurs, car leur coût est déjà d'un cycle de cache par accès. Elle n'est que marginalement avantageuse pour des expressions telles que les langages concaténatifs . Un compilateur optimisant ne peut gagner que sur les redondances que le programmeur aurait pu éviter dans le code source.

La seconde méthode consiste à laisser une valeur calculée sur la pile de données, en la dupliquant au besoin. Elle utilise des opérations de copie des entrées de la pile. La profondeur de la pile doit être suffisamment faible pour permettre les instructions de copie disponibles sur le processeur. Le code de gestion de pile écrit manuellement utilise souvent cette approche et atteint des vitesses comparables à celles des ordinateurs à registres classiques. Malheureusement, les algorithmes d'optimisation de la gestion de la pile sont peu utilisés par les langages de programmation.

Sur les machines modernes, le temps d'accès à une variable depuis le cache de données est souvent plusieurs fois supérieur au temps nécessaire aux opérations de base de l'UAL. Un programme s'exécute plus rapidement et sans blocage si ses chargements mémoire peuvent être lancés plusieurs cycles avant l'instruction qui requiert cette variable. Les machines complexes y parviennent grâce à un pipeline profond et à l'exécution hors séquence, qui examine et exécute plusieurs instructions simultanément. Les machines à registres peuvent même réaliser cela avec un matériel beaucoup plus simple fonctionnant en séquence, un pipeline moins profond et des compilateurs légèrement plus performants. L'étape de chargement devient une instruction distincte, et cette instruction est planifiée statiquement beaucoup plus tôt dans la séquence d'exécution. Le compilateur intercale des étapes indépendantes entre ces instructions.

La planification des accès mémoire requiert des registres spécifiques et disponibles. Sur les machines à pile, cela est impossible sans exposer certains aspects de la microarchitecture au programmeur. Pour l'expression AB −, B doit être évalué et empilé juste avant l'étape de soustraction. Sans permutation de la pile ni multithreading matériel, il est difficile d'exécuter du code utile pendant l'attente du chargement de B. Les machines à pile peuvent contourner ce délai mémoire soit en disposant d'un pipeline d'exécution hors séquence profond couvrant plusieurs instructions simultanément, soit, plus probablement, en permutant la pile pour pouvoir traiter d'autres charges de travail pendant le chargement, soit encore en entrelaçant l'exécution de différents threads, comme dans le système Unisys A9. Cependant, la parallélisation croissante des charges de calcul actuelles suggère que ce désavantage pourrait être moins important qu'on ne le pensait.

Les machines à pile peuvent omettre l'étape de récupération des opérandes d'une machine à registres. Par exemple, dans le microprocesseur Java Optimized Processor (JOP), les 2 opérandes supérieurs de la pile entrent directement dans un circuit de transfert de données plus rapide que le fichier de registres.

L' algorithme de Tomasulo exploite le parallélisme au niveau des instructions en les exécutant dès que leurs données sont disponibles. Conceptuellement, les adresses des positions dans une pile sont identiques aux indices des registres d'un fichier de registres. Cette conception permet d'utiliser l' exécution hors séquence de l'algorithme de Tomasulo avec des machines à pile.

L'exécution hors séquence dans les machines à pile semble réduire, voire éviter, de nombreuses difficultés théoriques et pratiques. Les recherches citées montrent qu'une telle machine à pile peut exploiter le parallélisme au niveau des instructions, et que le matériel résultant doit mettre en cache les données des instructions. Ces machines contournent efficacement la plupart des accès mémoire à la pile. Il en résulte un débit (instructions par cycle d'horloge ) comparable à celui des machines à architecture de chargement-stockage , avec des densités de code bien supérieures (grâce à l'implicite des adresses des opérandes).

L'une des problématiques soulevées par cette recherche est le suivant : il faut environ 1,88 instructions d'une machine à pile pour effectuer le travail d'une seule instruction sur une machine à architecture de type chargement-stockage. Les machines à pile à exécution hors séquence compétitives nécessitent donc environ deux fois plus de ressources électroniques pour le suivi des instructions (les « stations d'émission »). Ce surcoût peut être compensé par des économies réalisées sur la mémoire cache et la mémoire d'instructions, ainsi que sur les circuits de décodage des instructions.

Certaines machines à pile simples possèdent une puce dont la conception est entièrement personnalisée, jusqu'au niveau des registres individuels. Le registre d'adresse en haut de la pile et les N tampons de données en haut de la pile sont constitués de circuits de registres distincts, avec des additionneurs séparés et des connexions ad hoc.

Cependant, la plupart des machines à pile sont construites à partir de composants de circuits plus importants où les N tampons de données sont stockés ensemble dans un fichier de registres et partagent des bus de lecture/écriture. Les instructions de pile décodées sont mappées sur une ou plusieurs actions séquentielles sur ce fichier de registres caché. Les chargements et les opérations ALU agissent sur quelques registres de premier niveau, tandis que les débordements et remplissages implicites agissent sur les registres de second niveau. Le décodeur permet de compacter le flux d'instructions. Mais si le flux de code comportait des champs de sélection de registre explicites manipulant directement le fichier de registres sous-jacent, le compilateur pourrait mieux exploiter tous les registres et le programme s'exécuterait plus rapidement.

Les machines à pile microprogrammées en sont un exemple. Leur moteur de microcode interne est une machine à registres de type RISC ou VLIW utilisant plusieurs fichiers de registres. Lorsqu'il est contrôlé directement par un microcode spécifique à une tâche, ce moteur accomplit beaucoup plus de travail par cycle que lorsqu'il est contrôlé indirectement par un code de pile équivalent pour cette même tâche.

Les traducteurs de code objet qui ont converti le code des machines à pile HP 3000 et Tandem NonStop en code pour leurs remplaçantes RISC à registres constituent un autre exemple. Ils ont traduit les séquences de code à pile en séquences équivalentes de code RISC. Des optimisations « locales » mineures ont permis de réduire considérablement la surcharge liée à l'architecture à pile. L'utilisation de registres libres a permis d'éliminer les calculs d'adresses redondants. Le code traduit conservait néanmoins une surcharge d'émulation importante due à la différence entre les machines d'origine et cibles. Malgré cette surcharge, l'efficacité du code traduit était identique à celle du code à pile d'origine. Et lorsque le code source a été recompilé directement pour la machine à registres à l'aide de compilateurs optimisants, l'efficacité a doublé. Ceci démontre que l'architecture à pile et ses compilateurs non optimisants gaspillaient plus de la moitié de la puissance du matériel sous-jacent.

Les fichiers de registres sont d'excellents outils de calcul grâce à leur bande passante élevée et leur très faible latence, comparés aux accès mémoire via les caches de données. Sur une machine simple, le fichier de registres permet de lire deux registres indépendants et d'écrire dans un troisième, le tout en un seul cycle ALU, avec une latence inférieure ou égale à un cycle. En revanche, le cache de données correspondant ne peut effectuer qu'une seule lecture ou écriture (mais pas les deux) par cycle, et la lecture induit généralement une latence de deux cycles ALU. Cela représente un tiers du débit pour un délai de pipeline deux fois supérieur. Sur une machine complexe comme l'Athlon , qui exécute deux instructions ou plus par cycle, le fichier de registres permet de lire quatre registres indépendants ou plus et d'en écrire dans deux autres, le tout en un seul cycle ALU, avec une latence d'un cycle. En revanche, le cache de données à double accès correspondant ne peut effectuer que deux lectures ou écritures par cycle, avec une latence de plusieurs cycles. Là encore, le débit est réduit d'un tiers par rapport aux registres. La construction d'un cache avec des ports supplémentaires est très coûteuse.

Puisqu'une pile est un composant de la plupart des programmes informatiques, même lorsque le logiciel utilisé n'est pas strictement une machine à pile, une machine à pile matérielle pourrait mieux reproduire le fonctionnement interne de ses programmes. Les registres du processeur ont un coût thermique élevé, et une machine à pile pourrait afficher une efficacité énergétique supérieure.

Répondre à une interruption implique de sauvegarder les registres sur une pile, puis d'exécuter le gestionnaire d'interruptions. Les machines à pile réagissent généralement plus rapidement aux interruptions, car la plupart des paramètres sont déjà empilés et il n'est pas nécessaire de les y empiler. Certaines machines à registres gèrent ce problème en utilisant plusieurs fichiers de registres pouvant être permutés instantanément , mais cela augmente les coûts et ralentit le traitement des registres.

Les interpréteurs pour machines à pile virtuelle sont plus faciles à construire que ceux pour machines à registres ; la logique de gestion des modes d'adressage mémoire est centralisée au lieu d'être répétée dans de nombreuses instructions. Les machines à pile ont également tendance à présenter moins de variantes d'un même opcode ; un opcode généralisé couvre à la fois les cas fréquents et les cas particuliers obscurs d'accès mémoire ou d'initialisation d'appels de fonction. (Cependant, la densité du code est souvent améliorée en ajoutant des formes courtes et longues pour une même opération.)

Les interpréteurs pour machines virtuelles à pile sont souvent plus lents que les interpréteurs pour d'autres types de machines virtuelles. Ce ralentissement est plus marqué lors de l'exécution sur des machines hôtes dotées de pipelines d'exécution profonds, comme les puces x86 actuelles.

Dans certains interpréteurs, l'interpréteur doit exécuter un saut de type N-way switch pour décoder le code d'opération suivant et suivre les étapes associées. Une autre méthode de sélection des codes d'opération consiste à utiliser du code multithread . Les mécanismes de prélecture de la machine hôte ne peuvent pas prédire ni récupérer la cible de ce saut indexé ou indirect. Par conséquent, le pipeline d'exécution de la machine hôte doit redémarrer à chaque fois que l'interpréteur hôte décode une instruction virtuelle. Ce cas de figure est plus fréquent pour les machines virtuelles à pile que pour les autres types de machines virtuelles.

Le langage de programmation Java en est un exemple . Sa machine virtuelle canonique est une machine à pile 8 bits. Cependant, la machine virtuelle Dalvik pour Java, utilisée sur les smartphones Android , est une machine à registres virtuels 16 bits — un choix motivé par des raisons d’efficacité. Les instructions arithmétiques accèdent directement aux variables locales, en les stockant ou en les lisant, via des champs d’instructions de 4 bits (ou plus). De même, la version 5.0 de Lua a remplacé sa machine à pile virtuelle par une machine à registres virtuels plus rapide.

Depuis que la machine virtuelle Java s'est popularisée, les microprocesseurs utilisent des prédicteurs de branchement avancés pour les sauts indirects. Cette avancée évite la plupart des redémarrages de pipeline dus aux sauts N-way et élimine une grande partie des coûts liés au nombre d'instructions qui affectent les interpréteurs de pile.