Question:
cache de pile au lieu de registres
beroal
2012-10-17 05:24:52 UTC
view on stackexchange narkive permalink

Existe-t-il un processeur qui effectue des opérations arithmétiques sur une pile et non sur des registres? Pour conserver les performances, bien sûr, ce processeur doit mettre en cache le bloc supérieur d'une pile dans le même type de mémoire que celui utilisé pour les registres.

J'ai lu dans un article (David R. Ditzel, HR McLellan. Allocation des registres gratuitement: le cache de la pile de la machine C.) qu'un cache est plus lent 2 fois que les registres en raison de:

  • adressage indirect lors de chaque accès au cache;
  • cache manque quand la pile grandit.

Le papier est vieux. Peut-être que des améliorations de la conception du processeur sont apparues qui rendent le cache de pile viable? Je pense que cela réduira la complexité des compilateurs et optimisera la copie entre les registres et le reste de la mémoire.

Mise à jour du 18/10/2012. Parce que ce concept était bien connu (pas de moi), je change la question en "… Processeurs modernes?"

Mise à jour du 18/10/2012. Je sens que je dois dire explicitement que je ne parle pas de «machine à adresse zéro». La mise en cache et «adresse zéro» sont orthogonales. Mon processeur hypothétique peut même avoir une addition 5-aire comme «r3: = r0 + r2 + r11 + r5 + r8». «R n» signifie la cellule mémoire à sp + n, où sp est un pointeur de pile. sp change avant et après un bloc de code. Un programme très inhabituel change sp à chaque opération arithmétique.

Comme je l'ai dit dans ma réponse, une difficulté fondamentale avec de telles machines est qu'il est en général difficile pour la logique d'ordonnancement d'instructions de maintenir une quelconque cohérence si le pointeur de pile change. Cela étant dit, je peux imaginer qu'il pourrait dans certains cas être utile d'avoir une pile spéciale de «sauvegarde de registre» pour les registres qui devront être préservés, mais auxquels il ne sera pas nécessaire d'accéder sauf pour les restaurer. Sur un système avec 16 registres «utilisateur» 32 bits, une telle pile peut être par ex. 16 de profondeur et 512 bits de largeur (plus quelques bits de contrôle).
Lorsqu'il est nécessaire de sauvegarder un sous-ensemble de registres, les 128 bits du fichier de registre sont copiés dans la pile en parallèle; si la pile est pleine, le "spill" serait écrit dans le cache principal sous forme d'une ou deux lignes de cache (selon la taille de la ligne de cache). Lors de la restauration des registres, seuls les registres devant être restaurés seraient rechargés. Une telle architecture pourrait dans de nombreux cas minimiser la quantité de trafic de sauvegarde / restauration de registre allant et venant du cache principal, mais je ne suis pas sûr que l'effet global sur les performances suffirait à le justifier.
OK, puisque vous ne parlez pas de machines à empiler, j'ai retracé le papier auquel vous faites référence et je l'ai lu. Les raisons qu'ils donnent au début pour expliquer pourquoi le cache est toujours plus lent que les registres sont des problèmes d'architecture, indépendamment de la technologie de mise en œuvre. Le cache explicitement géré qu'ils proposent se situe quelque part entre les deux. Au cours des 30 années qui se sont écoulées depuis la rédaction de cet article, la technologie du compilateur est devenue beaucoup plus sophistiquée et peut tirer pleinement parti du matériel conçu pour une vitesse maximale (en utilisant des registres).
@supercat: «Je peux imaginer qu'il pourrait être utile dans certains cas d'avoir une pile spéciale de« sauvegarde de registre »pour les registres qui devront être préservés» Dans certains cas? He-he. C'est le seul moyen pour les fonctions récursives de fonctionner. ;)
@Dave Tweed: J'ai supprimé votre lien payant; le premier lien dans les résultats de recherche Google est un téléchargement gratuit.
@Dave Tweed: Eh bien, les compilateurs génèrent des instructions pour déplacer des données entre la pile et les registres. IMHO, faire cela automatiquement serait plus rapide. Quoi qu'il en soit, l'objectif initial était de raccourcir la spécification d'un processeur.
Cinq réponses:
#1
+7
Dave Tweed
2012-10-17 07:27:17 UTC
view on stackexchange narkive permalink

Oui, toute la gamme d'ordinateurs centraux Burroughs à partir de 1961 avec le B5000 utilisait une architecture de pile.

Dans cette architecture, gérer le flux de données vers et depuis la pile n'est en fait pas trop un goulot d'étranglement pour les performances. Un problème plus important est le fait qu'une machine à "adresse zéro" a besoin de beaucoup plus d'instructions pour accomplir une tâche donnée qu'une machine à une, deux ou trois adresses. Le décodage des instructions et le pipeline d'exécution deviennent le principal goulot d'étranglement.

Quand j'y travaillais au début des années 1980, il y avait un effort pour construire un processeur capable de pré-extraire des séquences relativement importantes d'instructions à adresse nulle et de les traduire sur les opérations de vol à trois adresses qui seraient transmises au pipeline d'exécution. (Pensez à un compilateur Java JIT implémenté dans le matériel.) Il est devenu plutôt complexe, en particulier pour les technologies d'implémentation disponibles à l'époque, et je ne sais pas si cette stratégie a finalement réussi.

Au cas où vous ' Je me demande, la terminologie "N-adresse" fait référence au nombre d'opérandes qui peuvent être spécifiés dans une seule instruction. Toutes les opérations sur une machine de pile sont implicitement au premier ou aux deux emplacements supérieurs de la pile, il n'y a donc aucun opérande dans les instructions. Une machine qui a un accumulateur qui est utilisé pour toutes les opérations en conjonction avec un autre registre ou emplacement de mémoire est une machine à une adresse. Une machine à deux adresses peut spécifier un opérande source et une destination arbitraire dans une instruction, et une machine à trois adresses peut spécifier deux opérandes source et placer le résultat dans une destination indépendante.

+1. Pour mettre la N-adressabilité dans le contexte actuel, les PIC 8 bits comme le PIC 16 et le PIC 18 ont pour la plupart des instructions à une seule adresse puisque la plupart des opérations impliquent le registre W pour l'un des opérandes et le résultat est soit le registre W, soit le retour à l'emplacement source. Le dsPIC et ses dérivés (PIC 24, 30 et 33) sont en grande partie des machines à 3 adresses, bien que les opérations soient limitées à l'ensemble des registres 16 W. Néanmoins, de nombreuses opérations peuvent être effectuées avec deux registres W comme opérandes et le résultat écrit dans un troisième. Il s'agit essentiellement de la version RISC de 3 adresses.
Si l'on a un nombre spécifique de bits dans un opcode pour encoder toutes les adresses dont les instructions auront besoin, je pense que le plus grand ensemble de travail activé par une architecture à une ou deux adresses l'emporterait souvent sur les avantages d'une architecture à trois adresses, à condition que le jeu d'instructions réduise au minimum la «pénalité» pour les cas où le passage d'un seul registre était insuffisant. L'adresse zéro ne fonctionne pas très bien, mais je pense qu'une machine à pile à une adresse pourrait être très bonne si l'on n'essayait pas de chevaucher des instructions de manière trop agressive.
@OlinLathrop: Je considérerais quelque chose qui ressemble aux instructions à adresse unique du PIC avec une destination sélectionnable comme à peu près idéal, si l'entrée "W" de l'ALU provenait à la place d'un registre qui refléterait normalement W sauf en suivant un "uselw" ou "usefw" instruction (qui la chargerait avec une constante ou le contenu d'un autre registre). Au lieu d'un opcode "movff" dédié à deux mots, j'utiliserais la séquence "usefw src / movwf dest" [après quoi, le registre temporaire serait rechargé avec W]. Cela permettrait à "usefw src / addwf dest, f" comme moyen de "dest + = src" sans déranger W.
@OlinLathrop: Pour les applications où toutes les parties couramment utilisées du jeu de travail peuvent tenir dans la plage d'adressage d'une instruction sans mise en banque, `movf src / addwf dest, f` est plus rapide que` ldr r0, [src + r13] / ldr r1, [dest + r13] / add r0, r0, r1 / str [src + r13] `(et effectue sa mise à jour de destination de manière atomique). Dommage d'ajouter un nombre à un autre alors que la valeur de `W` est nécessaire pour autre chose coûte quatre cycles (un pour sauver W, un pour charger un opérande, un pour faire l'opération et un pour restaurer W). Quelque chose comme «usefw» pourrait réduire cela à deux.
Non, je ne parle pas d'une machine à «adresse zéro». Par exemple, l'opérande «R5» signifie la cellule de mémoire à SP + 5, et cette cellule de mémoire est mise en cache car elle est proche du haut de la pile.
#2
+3
supercat
2012-10-17 05:52:48 UTC
view on stackexchange narkive permalink

Je me souviens avoir lu un article similaire (peut-être le même) il y a environ 17 ans. Une telle approche pourrait être bonne si l'on développait un processeur pour exécuter rapidement une instruction à la fois. Malheureusement, cela ne fonctionne pas bien avec la planification d'instructions dans le désordre. Si on a du code comme:

 ldr r1, [r0] ... faire des trucs, n'impliquant pas r1, r2 ou [r2] str r1, [r2] 

Un Le planificateur d'instructions est libre de déplacer ces deux instructions comme bon lui semble. Bien qu'il puisse être difficile pour le planificateur d'instructions de savoir si une écriture dans un emplacement mémoire peut être une écriture dans [r2], de nombreux langages compilés exigent que les programmeurs indiquent quels éléments peuvent ou non être aliasés.

En revanche, les instructions ressemblaient plus à:

 mov.l [r0], [- sp]; Poussez [r0] sur la pile ... faites des trucs, ce qui affecte sp mov.l [sp ++], [r2]; Pop [r2] de la pile 

il serait beaucoup plus difficile pour un moteur d'exécution dans le désordre de déterminer si l'opérande source de la dernière instruction serait toujours le même que l'opérande de destination de la première, et si des instructions intermédiaires pourraient l'affecter.

#3
+2
Wouter van Ooijen
2012-10-17 12:35:19 UTC
view on stackexchange narkive permalink

Dans le passé, j'ai travaillé avec le Saab Ericsson Space Thor, un microprocesseur pour les applications spatiales. Cela fonctionnait, mais présentait de sérieux inconvénients. Un seul: le pipeline d'instructions a été exposé: l'instruction qui a chargé un mot de la mémoire utilisé comme adresse le haut de la pile il y a 2 instructions . J'ai écrit une routine de copie de mémoire rapide pour cela, mais Saab a dit qu'elle ne pouvait pas être utilisée car les interruptions causeraient des problèmes ...

#4
  0
placeholder
2012-10-17 06:47:33 UTC
view on stackexchange narkive permalink

Il y avait des processeurs Forth dédiés qui étaient utilisés au niveau du processeur de démarrage pour les machines Sun / Sparc dont l'architecture dédiée était mappée au langage. Mais pas généralement disponible.

#5
  0
Jon Watte
2012-10-20 13:38:40 UTC
view on stackexchange narkive permalink

Le x86 est presque l'un de ceux-ci :-) (et la partie x87 fp encore plus proche)

Dans les systèmes modernes, la pile est terrible, car elle peut alias entre les cœurs ou même les nœuds NUMA, donc beaucoup de signalisation lente et longue distance peuvent être impliquées. Ou, au minimum, plus de verrouillages que ce que vous obtenez avec un fichier de registre et un renommage de registre.

Considérez que même pas les processeurs, mais d'autres périphériques peuvent DMA dans votre pile - pensez aux tampons de lecture!

Ouais, presque. x86 a AX, BX, CX, DX, BP, SI, DI. Cette liste n'est pas particulièrement courte. :) En fait, j'ai testé pile vs registres sur AMD Athlon et j'ai trouvé que les registres sont 2 fois plus rapides que la pile. DMA ou tout autre processeur accédant à la pile du processeur est généralement une erreur du programmeur, le processeur n'a donc pas besoin de résoudre ce conflit, disons que «le comportement n'est pas défini» dans de tels cas.
Non, l'accès DMA à la pile est courant - considérez les tampons sur la pile pour les appels à read () ou write (). Ce n'est pas une erreur de programmeur, et les CPU ne peuvent pas dire "comportement non défini" pour cela. Je me souviens d'une ancienne carte mère PowerPC où ce comportement * était * indéfini en raison d'un bogue dans le matériel Apple; c'était "amusant" à gérer ... Le x87 est un jeu d'instructions entièrement basé sur la pile, bien que la "pile de travail" soit extrêmement limitée et doive se répandre dans la "vraie" pile.
«Considérez les tampons sur la pile pour les appels à read () ou write ()» Nous pouvons nous en débarrasser.
@JonWatte: Mettre un tampon DMA sur la pile semble être une mauvaise idée lors de l'utilisation d'E / S synchrones, et une très très mauvaise idée pour l'utilisation d'E / S asynchrones. Au minimum, même dans le cas des E / S synchrones, il faut que tout responsable multitâche sache comment annuler les opérations DMA en attente s'il a besoin de tuer un thread. Et dans le cas des E / S asynchrones, c'est une recette pour un désastre si la routine qui configure le DMA s'arrête de manière inattendue avant la fin du DMA.
De toute évidence, les E / S asynchrones ne peuvent pas utiliser de tampons de pile. UNIX n'est cependant pas très performant pour les E / S asynchrones; la plupart des programmes utilisent en fait des E / S synchrones.Le noyau n'a pas nécessairement à attendre que les E / S se terminent avant de supprimer un mappage de pile, tant que les pages physiques ont encore un nombre de références et ne seront pas supprimées avant l'E / S est terminée. N'oubliez pas: le DMA est généralement effectué avec des adresses physiques, en dehors de la couche de traduction de VM. Je connais des noyaux qui font référence au nombre de pages physiques; Je ne sais pas s'ils font tous ça.


Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 3.0 sous laquelle il est distribué.
Loading...