Stapelmaschine - Stack machine

Für Stapelmaschinen in der Automatentheorie siehe Pushdown-Automat .

In der Informatik , Computertechnik und Programmiersprachenimplementierungen ist eine Stack-Maschine ein Computerprozessor oder eine virtuelle Maschine, bei der die primäre Interaktion darin besteht, kurzlebige temporäre Werte zu und von einem Push-Down- Stack zu verschieben . Bei einem Hardware-Prozessor wird ein Hardware-Stack verwendet. Die Verwendung eines Stacks reduziert die erforderliche Anzahl von Prozessorregistern erheblich . Stapelmaschinen erweitern den Push-down-Automaten um zusätzliche Lade-/Speichervorgänge oder mehrere Stapel und sind somit Turing-komplett .

Entwurf

Die meisten oder alle Stack-Maschinenbefehle gehen davon aus, dass die Operanden vom Stack stammen und die Ergebnisse im Stack abgelegt werden. Der Stack enthält problemlos mehr als zwei Eingaben oder mehr als ein Ergebnis, sodass eine Vielzahl von Operationen berechnet werden kann. Im Stack-Maschinencode (manchmal als p-Code bezeichnet ) haben Befehle häufig nur einen Opcode, der eine Operation befiehlt, ohne zusätzliche Felder, die eine Konstante, ein Register oder eine Speicherzelle identifizieren, bekannt als Nulladressenformat . Dies vereinfacht die Befehlsdecodierung stark. Verzweigungen, Lade-Direktbefehle und Lade-/Speicher-Befehle erfordern ein Argumentfeld, aber Stapelmaschinen sorgen oft dafür, dass die häufigen Fälle dieser immer noch zusammen mit dem Opcode in eine kompakte Gruppe von Bits passen. Die Auswahl von Operanden aus früheren Ergebnissen erfolgt implizit durch die Reihenfolge der Anweisungen. Einige Stack-Maschinen-Befehlssätze sind für die interpretative Ausführung einer virtuellen Maschine gedacht, anstatt die Hardware direkt anzusteuern.

Ganzzahlige Konstantenoperanden werden von Pushoder -Anweisungen geschoben Load Immediate. Auf den Speicher wird oft durch separate Loadoder StoreAnweisungen zugegriffen, die eine Speicheradresse enthalten oder die Adresse aus Werten im Stapel berechnen. Alle praktischen Stapelmaschinen haben Varianten der Lade-Speicher-Opcodes für den Zugriff auf lokale Variablen und formale Parameter ohne explizite Adressberechnungen. Dies kann durch Offsets von der aktuellen Top-of-Stack-Adresse oder durch Offsets von einem stabilen Rahmenbasisregister sein.

Der Befehlssatz führt die meisten ALU-Aktionen mit Postfix- Operationen ( Reverse Polish Notation ) aus, die nur auf dem Ausdrucksstapel arbeiten, nicht auf Datenregistern oder Hauptspeicherzellen. Dies kann für die Ausführung von Hochsprachen sehr praktisch sein, da die meisten arithmetischen Ausdrücke leicht in die Postfix-Notation übersetzt werden können.

Binärer Syntaxbaum für den Ausdruck A *( B - C ) + ( D + E )

Betrachten Sie zum Beispiel den Ausdruck A *( B - C )+( D + E ), der in umgekehrter polnischer Schreibweise als A B C - * D E + + geschrieben ist. Das Kompilieren und Ausführen auf einer einfachen imaginären Stapelmaschine würde die Form annehmen: 

                 # stack contents (leftmost = top = most recent):
 push A          #           A
 push B          #     B     A
 push C          # C   B     A
 subtract        #     B-C   A
 multiply        #           A*(B-C)
 push D          #     D     A*(B-C)
 push E          # E   D     A*(B-C)
 add             #     D+E   A*(B-C)
 add             #           A*(B-C)+(D+E)

Die Rechenoperationen 'subtrahieren', 'multiplizieren' und 'addieren' wirken auf die beiden obersten Operanden des Stapels. Der Computer nimmt beide Operanden von den obersten (neuesten) Werten des Stapels. Der Computer ersetzt diese beiden Werte durch die berechnete Differenz, Summe oder das Produkt. Mit anderen Worten, die Operanden des Befehls werden vom Stapel "geknallt", und sein Ergebnis bzw. seine Ergebnisse werden dann zurück auf den Stapel "geschoben", bereit für den nächsten Befehl.

Stack-Maschinen können ihren Ausdrucks-Stack und ihren Aufruf-Rückgabe-Stack getrennt oder als eine integrierte Struktur aufweisen. Wenn sie getrennt sind, können die Anweisungen der Stapelmaschine werden pipeline mit weniger Wechselwirkungen und weniger Design - Komplexität, so wird es in der Regel schneller laufen.

Die Optimierung von kompiliertem Stack-Code ist durchaus möglich. Es hat sich gezeigt, dass die Back-End-Optimierung der Compilerausgabe den Code und die potenzielle Leistung erheblich verbessert, während die globale Optimierung innerhalb des Compilers selbst weitere Vorteile erzielt.

Stapelspeicher

Einige Stapelmaschinen haben einen Stapel begrenzter Größe, der als Registerdatei implementiert ist. Darauf greift die ALU mit einem Index zu. Eine große Registerdatei verwendet viele Transistoren und daher ist diese Methode nur für kleine Systeme geeignet. Einige Maschinen haben sowohl einen Ausdrucksstapel im Speicher als auch einen separaten Registerstapel. In diesem Fall können Software oder ein Interrupt Daten zwischen ihnen verschieben. Einige Maschinen haben einen Stapel von unbegrenzter Größe, der als Array im RAM implementiert ist und von einigen "Top-of-Stack"-Adressregistern zwischengespeichert wird, um den Speicherzugriff zu reduzieren. Abgesehen von expliziten "Laden aus dem Speicher"-Befehlen ist die Reihenfolge der Operandenverwendung identisch mit der Reihenfolge der Operanden im Datenstapel, so dass ein hervorragendes Vorabrufen leicht erreicht werden kann.

Betrachten Sie X+1. Es kompiliert zu Load X; Load 1; Add. Bei einem vollständig im RAM gespeicherten Stack führt dies zu impliziten Schreib- und Lesevorgängen des In-Memory-Stack:

  • X laden, in den Speicher schieben
  • Load 1, push to memory
  • 2 Werte aus dem Speicher laden, hinzufügen und Ergebnisse in den Speicher verschieben

für insgesamt 5 Datencachereferenzen.

Der nächste Schritt davon ist eine Stack-Maschine oder ein Interpreter mit einem einzigen Top-of-Stack-Register. Der obige Code macht dann:

  • Laden Sie X in ein leeres TOS-Register (bei Hardware-Maschine) oder Push TOS-Register in den Speicher, Laden Sie X in das TOS-Register (bei Interpreter)
  • TOS-Register in den Speicher schieben, 1 in TOS-Register laden
  • Linken Operanden aus dem Speicher holen, zum TOS-Register hinzufügen und dort belassen

für insgesamt 5 Datencachereferenzen, Worst-Case. Im Allgemeinen verfolgen Interpreter keine Leere, weil sie es nicht müssen – alles unter dem Stack-Zeiger ist ein nicht leerer Wert, und das TOS-Cache-Register wird immer aktiv gehalten. Typische Java-Interpreter puffern den Top-of-Stack jedoch nicht auf diese Weise, da das Programm und der Stack eine Mischung aus kurzen und breiten Datenwerten haben.

Wenn die festverdrahtete Stack-Maschine 2 oder mehr Top-Stack-Register oder eine Registerdatei hat, wird in diesem Beispiel jeglicher Speicherzugriff vermieden und es gibt nur 1 Daten-Cache-Zyklus.

Geschichte und Implementierungen

Die Beschreibung eines solchen Verfahrens, bei dem nur zwei Werte gleichzeitig in Registern gehalten werden müssen, mit einem begrenzten Satz vordefinierter Operanden, die durch Definition weiterer Operanden, Funktionen und Unterprogramme erweitert werden konnten, wurde erstmals auf der Konferenz von Robert . bereitgestellt S. Barton im Jahr 1961.

Kommerzielle Stapelmaschinen

Siehe auch: Hochsprachen-Computerarchitektur

Beispiele für Stack-Befehlssätze, die direkt in Hardware ausgeführt werden, sind:

  • Die F18A-Architektur des 144-Prozessor-GA144-Chips von GreenArrays, Inc.
  • der Z4- Rechner von Konrad Zuse .
  • die Burroughs Großsystemarchitektur (seit 1961)
  • der am 27. April 1981 eingeführte Xerox Dandelion nutzte eine Stack-Maschinenarchitektur, um Speicher zu sparen.
  • die English Electric KDF9- Maschine. Das KDF9 wurde erstmals 1964 ausgeliefert und verfügte über einen 19-tiefen Pushdown-Stack von arithmetischen Registern und einen 17-tiefen Stack für Subroutinen-Rückkehradressen
  • der Minicomputer des Collins Radio Collins Adaptive Processing System (CAPS, seit 1969) und der Rockwell Collins Advanced Architecture Microprocessor (AAMP, seit 1981).
  • die UCSD Pascal p-machine (wie die Pascal MicroEngine und viele andere) unterstützte eine komplette Studenten-Programmierumgebung auf frühen 8-Bit-Mikroprozessoren mit schlechten Befehlssätzen und wenig RAM, indem sie zu einer virtuellen Stack-Maschine kompilierte.
  • MU5- und ICL 2900-Serie . Hybride Stapel- und Akkumulatormaschinen. Das Akkumulatorregister pufferte den obersten Datenwert des Speicherstapels. Varianten von Lade- und Speicher-Opcodes, die gesteuert werden, wenn dieses Register auf den Speicherstapel übertragen oder von dort neu geladen wurde.
  • HP 3000 (Klassisch, nicht PA-RISC)
  • Tandemcomputer T/16. Wie HP 3000, außer dass Compiler, nicht Mikrocode, kontrollierten, wann der Registerstapel in den Speicherstapel überschwappt oder vom Speicherstapel aufgefüllt wurde.
  • der Atmel MARC4 Mikrocontroller
  • Mehrere "Forth-Chips" wie der RTX2000, der RTX2010 , der F21 und der PSC1000
  • Der Setun Ternary Computer führte einen ausgeglichenen Ternary mit einem Stack durch.
  • Der 4stack-Prozessor von Bernd Paysan hat vier Stacks.
  • Die von Charles H. Moore entwickelte Ignite- Stack-Maschine von Patriot Scientific hält einen führenden Benchmark für die Funktionsdichte .
  • Saab Ericsson Space Thor strahlungsgehärteter Mikroprozessor
  • Inmos- Transputer .
  • ZPU Eine physisch kleine CPU zur Überwachung von FPGA- Systemen.
  • Einige technische Taschenrechner verwenden in ihrer Tastaturschnittstelle die umgekehrte polnische Notation, anstatt Klammern zu verwenden. Dies ist eine Form der Stapelmaschine. Die Plus-Taste beruht darauf, dass sich ihre beiden Operanden bereits an den korrekten obersten Positionen des für den Benutzer sichtbaren Stapels befinden.

Virtuelle Stack-Maschinen

Beispiele für virtuelle Stack-Maschinen, die in Software interpretiert werden:

Hybridmaschinen

(Diese sollten nicht mit Hybridcomputern verwechselt werden , die sowohl digitale als auch analoge Funktionen kombinieren, z. B. ein ansonsten digitaler Computer, der auf die analoge Multiplikation oder das Lösen von Differentialgleichungen durch Speicherzuordnung und Konvertierung zu und von den Ein- und Ausgängen eines analogen Geräts zugreift.)

Reine Stapelmaschinen sind für Prozeduren, die auf mehrere Felder desselben Objekts zugreifen, ziemlich ineffizient. Der Stack-Maschinencode muss den Objektzeiger für jede Zeiger+Offset-Berechnung neu laden. Eine übliche Lösung für dieses Problem besteht darin, der Stapelmaschine einige Registermaschinenfunktionen hinzuzufügen: eine sichtbare Registerdatei, die dem Halten von Adressen gewidmet ist, und Registerbefehle zum Ausführen von Ladevorgängen und einfachen Adressberechnungen. Es ist ungewöhnlich, dass die Register vollständig universell sind, da es dann keinen triftigen Grund für einen Ausdrucksstapel und Postfix-Befehle gibt.

Ein weiterer üblicher Hybrid besteht darin, mit einer Registermaschinenarchitektur zu beginnen und einen weiteren Speicheradressmodus hinzuzufügen, der die Push- oder Pop-Operationen von Stapelmaschinen emuliert: 'memaddress = reg; reg += instr.displ'. Dies wurde zuerst in verwendet Dezember ‚s PDP-11 Mini - Computer. Diese Funktion wurde in VAX- Computern und in Motorola 6800- und M68000- Mikroprozessoren übernommen. Dies ermöglichte die Verwendung einfacherer Stapelmethoden in frühen Compilern. Es unterstützte auch effizient virtuelle Maschinen mit Stack-Interpretern oder Thread-Code . Dieses Merkmal trug jedoch nicht dazu bei, dass der eigene Code der Registermaschine so kompakt wurde wie reiner Stapelmaschinencode. Außerdem war die Ausführungsgeschwindigkeit geringer als beim Kompilieren in die Registerarchitektur. Es ist schneller, den Top-of-Stack-Zeiger nur gelegentlich (einmal pro Aufruf oder Rückgabe) zu ändern, anstatt ihn während jeder Programmanweisung ständig auf und ab zu stufen, und es ist noch schneller, Speicherreferenzen vollständig zu vermeiden.

In jüngerer Zeit haben sogenannte Stapelmaschinen der zweiten Generation eine dedizierte Sammlung von Registern angenommen, die als Adressregister dienen, wodurch die Aufgabe der Speicheradressierung vom Datenstapel abgeladen wird. MuP21 basiert beispielsweise auf einem Register namens "A", während die neueren GreenArrays-Prozessoren auf zwei Registern basieren: A und B.

Die Intel x86-Mikroprozessorfamilie verfügt für die meisten Operationen über einen Befehlssatz im Registerstil (Akkumulator), verwendet jedoch Stack-Befehle für die x87- , Intel 8087- Gleitkommaarithmetik, die auf den iAPX87 (8087)-Coprozessor für den 8086 und 8088 zurückgeht das heißt, es gibt keine vom Programmierer zugänglichen Gleitkommaregister, sondern nur einen 80 Bit breiten, 8 tiefen Stapel. Der x87 verlässt sich stark auf die x86-CPU zur Unterstützung bei der Ausführung seiner Operationen.

Computer, die Aufruflisten und Stapelrahmen verwenden

Die meisten aktuellen Computer (jeglicher Befehlssatz-Stil) und die meisten Compiler verwenden einen großen Aufruf-Rückgabe-Stack im Speicher, um die kurzlebigen lokalen Variablen und Rückgabe-Links für alle derzeit aktiven Prozeduren oder Funktionen zu organisieren. Jeder verschachtelte Aufruf erstellt einen neuen Stapelrahmen im Speicher, der bis zum Abschluss des Aufrufs bestehen bleibt. Dieser Call-Return-Stack kann vollständig von der Hardware über spezielle Adressregister und spezielle Adressmodi in den Befehlen verwaltet werden. Oder es kann nur eine Reihe von Konventionen sein, die von den Compilern befolgt werden, die generische Register und Register+Offset-Adressmodi verwenden. Oder es kann etwas dazwischen sein.

Da diese Technik mittlerweile fast universell einsetzbar ist, sogar auf Registermaschinen, ist es nicht hilfreich, alle diese Maschinen als Stapelmaschinen zu bezeichnen. Dieser Begriff ist im Allgemeinen für Maschinen reserviert, die auch einen Ausdrucksstapel und nur Stapel-arithmetische Anweisungen verwenden, um die Teile einer einzelnen Anweisung auszuwerten.

Computer bieten im Allgemeinen direkten, effizienten Zugriff auf die globalen Variablen des Programms und auf die lokalen Variablen nur der aktuellen innersten Prozedur oder Funktion, des obersten Stapelrahmens. Eine 'Up-Level'-Adressierung des Inhalts der Stack-Frames der Aufrufer wird normalerweise nicht benötigt und nicht wie direkt von der Hardware unterstützt. Compiler unterstützen dies bei Bedarf, indem sie Frame-Pointer als zusätzliche, versteckte Parameter übergeben.

Einige Burroughs-Stack-Maschinen unterstützen Up-Level-Refs direkt in der Hardware, mit speziellen Adressmodi und einer speziellen 'Anzeige'-Registerdatei, die die Frame-Adressen aller äußeren Bereiche enthält. Keine nachfolgenden Computerzeilen haben dies in Hardware getan. Als Niklaus Wirth den ersten Pascal- Compiler für den CDC 6000 entwickelte , stellte er fest, dass es insgesamt schneller war, die Rahmenzeiger als Kette einzugeben, anstatt ständig komplette Arrays von Rahmenzeigern zu aktualisieren. Diese Softwaremethode fügt auch keinen Overhead für gängige Sprachen wie C hinzu, denen Referenzen auf höherer Ebene fehlen.

Dieselben Burroughs-Maschinen unterstützten auch das Verschachteln von Aufgaben oder Threads. Die Aufgabe und ihr Ersteller teilen sich die Stack-Frames, die zum Zeitpunkt der Aufgabenerstellung vorhanden waren, aber weder die nachfolgenden Frames des Erstellers noch die eigenen Frames der Aufgabe. Unterstützt wurde dies durch einen Kaktusstapel , dessen Layout-Diagramm dem Rumpf und den Armen eines Saguaro- Kaktus ähnelte . Jede Task hatte ihr eigenes Speichersegment, das ihren Stack und die ihr gehörenden Frames enthielt. Die Basis dieses Stapels ist mit der Mitte des Stapels seines Schöpfers verbunden. Bei Maschinen mit einem herkömmlichen flachen Adressraum wären der Erstellerstapel und die Aufgabenstapel separate Heap-Objekte in einem Heap.

In einigen Programmiersprachen sind die Outer-Scope-Datenumgebungen nicht immer zeitlich verschachtelt. Diese Sprachen organisieren ihre Prozedur-'Aktivierungsdatensätze' als separate Heap-Objekte und nicht als Stapelrahmen, die an einen linearen Stapel angehängt sind.

In einfachen Sprachen wie Forth , die keine lokalen Variablen und keine Benennung von Parametern enthalten, würden Stack-Frames nichts anderes als Rückkehrverzweigungsadressen und Overhead für die Frame-Verwaltung enthalten. Ihr Rückgabestack enthält also keine Frames, sondern bloße Rücksendeadressen. Der Rückgabe-Stack ist vom Datenwert-Stack getrennt, um den Ablauf des Anrufaufbaus und der Rückgaben zu verbessern.

Vergleich mit Registermaschinen

Stapelmaschinen werden oft mit Registermaschinen verglichen , die Werte in einem Array von Registern speichern . Registermaschinen können stapelähnliche Strukturen in diesem Array speichern, aber eine Registermaschine hat Befehle, die die Stapelschnittstelle umgehen. Registermaschinen übertreffen routinemäßig Stapelmaschinen, und Stapelmaschinen sind ein Nischenplayer bei Hardwaresystemen geblieben. Stack-Maschinen werden jedoch aufgrund ihrer Einfachheit und Einfachheit der Implementierung häufig bei der Implementierung virtueller Maschinen verwendet .

Anweisungen

Stapelmaschinen haben eine höhere Codedichte . Im Gegensatz zu üblichen Stapelmaschinenbefehlen, die problemlos in 6 Bits oder weniger passen, benötigen Registermaschinen zwei oder drei Registernummernfelder pro ALU-Befehl, um Operanden auszuwählen; die dichtesten Registermaschinen durchschnittlich etwa 16 Bits pro Befehl plus die Operanden. Registermaschinen verwenden auch ein breiteres Offset-Feld für Lade-Speicher-Opcodes. Der kompakte Code einer Stack-Maschine passt natürlich mehr Befehle in den Cache und könnte daher eine bessere Cache- Effizienz erreichen, die Speicherkosten senken oder schnellere Speichersysteme zu gegebenen Kosten ermöglichen. Außerdem sind die meisten Stapelmaschinenbefehle sehr einfach und bestehen aus nur einem Operationscodefeld oder einem Operandenfeld. Somit benötigen Stapelmaschinen sehr wenig elektronische Ressourcen, um jeden Befehl zu decodieren.

Ein Programm muss mehr Anweisungen ausführen, wenn es zu einer Stapelmaschine kompiliert wird, als wenn es zu einer Registermaschine oder einer Speicher-zu-Speicher-Maschine kompiliert wird. Jede Variable load oder Konstante erfordert ihre eigene separate Load-Anweisung, anstatt innerhalb der Anweisung gebündelt zu sein, die diesen Wert verwendet. Die getrennten Anweisungen können einfach und schneller ausgeführt werden, aber die Gesamtzahl der Anweisungen ist noch höher.

Die meisten Registerinterpreter spezifizieren ihre Register durch Nummern. In einem indizierten Array kann jedoch nicht auf die Register eines Host-Rechners zugegriffen werden, daher wird ein Speicherarray für virtuelle Register zugewiesen. Daher müssen die Befehle eines Registerinterpreters Speicher verwenden, um erzeugte Daten an den nächsten Befehl weiterzugeben. Dies zwingt Registerinterpreter, bei Mikroprozessoren, die mit einer feinen Prozessregel erstellt wurden, viel langsamer zu sein (dh schnellere Transistoren ohne Verbesserung der Schaltungsgeschwindigkeit, wie der Haswell x86). Diese benötigen mehrere Takte für den Speicherzugriff, aber nur einen Takt für den Registerzugriff. Im Fall einer Stack-Maschine mit einer Datenweiterleitungsschaltung anstelle einer Registerdatei können Stack-Interpreter die Register der Host-Maschine für die obersten mehreren Operanden des Stacks anstelle des Speichers der Host-Maschine zuweisen

In einer Stack-Maschine befinden sich die in den Anweisungen verwendeten Operanden immer an einem bekannten Offset (eingestellt im Stack-Pointer), von einer festen Stelle (der Unterseite des Stack, die in einem Hardware-Design immer an der Speicherstelle Null liegen könnte), Sparen von wertvollem In- Cache- oder In- CPU- Speicher davor, so viele Speicheradressen oder Indexnummern zu speichern . Dies kann solche Register und Cachespeicher zur Verwendung bei der Nicht-Fluss-Berechnung erhalten.

Temporäre / lokale Werte

Einige in der Industrie glauben, dass Stapelmaschinen mehr Datencachezyklen für temporäre Werte und lokale Variablen ausführen als Registermaschinen.

Auf Stack-Computern werden temporäre Werte oft in den Speicher übertragen, während auf Computern mit vielen Registern diese temporären Werte normalerweise in Registern verbleiben. (Allerdings müssen diese Werte oft in "Aktivierungsrahmen" am Ende der Definition einer Prozedur, eines Basisblocks oder zumindest während der Interrupt-Verarbeitung in einen Speicherpuffer geschüttet werden). Werte, die in den Speicher übertragen werden, fügen weitere Cache-Zyklen hinzu. Dieser Spilling-Effekt hängt von der Anzahl der versteckten Register ab, die zum Puffern von Top-of-Stack-Werten verwendet werden, von der Häufigkeit verschachtelter Prozeduraufrufe und von den Interrupt-Verarbeitungsraten des Host-Computers.

Auf Registermaschinen, die optimierende Compiler verwenden, ist es sehr üblich, dass die am häufigsten verwendeten lokalen Variablen eher in Registern als in Stack-Frame-Speicherzellen verbleiben. Dadurch entfallen die meisten Datencachezyklen zum Lesen und Schreiben dieser Werte. Die Entwicklung von "Stack Scheduling" zur Durchführung von Live-Variablenanalysen und damit zur Aufbewahrung von Schlüsselvariablen über längere Zeiträume auf dem Stack trägt diesem Anliegen Rechnung.

Auf der anderen Seite müssen Registermaschinen viele ihrer Register über verschachtelte Prozeduraufrufe in den Speicher ausschütten. Die Entscheidung, welche Register wann ausgeschüttet werden sollen, wird statisch zur Kompilierzeit getroffen und nicht nach der dynamischen Tiefe der Aufrufe. Dies kann zu mehr Datencacheverkehr führen als bei einer erweiterten Stack-Maschinenimplementierung.

Häufige Unterausdrücke

In Registermaschinen kann ein gemeinsamer Unterausdruck (ein mehrfach verwendeter Unterausdruck mit gleichem Ergebniswert) nur einmal ausgewertet und sein Ergebnis in einem schnellen Register gespeichert werden. Die nachfolgenden Wiederverwendungen haben keine Zeit- oder Codekosten, sondern lediglich eine Registerreferenz. Diese Optimierung beschleunigt sowohl einfache Ausdrücke (z. B. das Laden der Variablen X oder des Zeigers P) als auch weniger häufige komplexe Ausdrücke.

Bei Stapelmaschinen hingegen können die Ergebnisse auf zwei Arten gespeichert werden. Erstens können Ergebnisse unter Verwendung einer temporären Variablen im Speicher gespeichert werden. Das Speichern und anschließende Abrufen kosten zusätzliche Befehle und zusätzliche Daten-Cache-Zyklen. Dies ist nur dann ein Gewinn, wenn die Berechnung des Unterausdrucks mehr Zeit kostet als das Abrufen aus dem Speicher, was bei den meisten Stack-CPUs fast immer der Fall ist. Für einfache Variablen- und Pointer-Fetches lohnt es sich nie, da diese bereits die gleichen Kosten von einem Daten-Cache-Zyklus pro Zugriff haben. Für Ausdrücke wie X+1. Diese einfacheren Ausdrücke machen die Mehrheit der redundanten, optimierbaren Ausdrücke in Programmen aus, die in nicht-konkatenativen Sprachen geschrieben sind. Ein optimierender Compiler kann nur bei Redundanzen gewinnen, die der Programmierer im Quellcode hätte vermeiden können.

Der zweite Weg hinterlässt einen berechneten Wert auf dem Datenstapel und dupliziert ihn nach Bedarf. Dies verwendet Operationen, um Stack-Einträge zu kopieren. Die Tiefe des Stapels muss flach genug für die verfügbaren Kopierbefehle der CPU sein. Handgeschriebener Stack-Code verwendet häufig diesen Ansatz und erreicht Geschwindigkeiten wie bei universellen Registermaschinen. Leider sind Algorithmen für eine optimale "Stack-Planung" von Programmiersprachen nicht weit verbreitet.

Rohrleitungen

Bei modernen Maschinen dauert das Abrufen einer Variablen aus dem Datencache oft ein Vielfaches der Zeit, die für grundlegende ALU-Operationen benötigt wird. Ein Programm läuft schneller, ohne anzuhalten, wenn sein Speicher mehrere Zyklen vor dem Befehl gestartet werden kann, der diese Variable benötigt. Komplexe Maschinen können dies mit einer tiefen Pipeline und "Out-of-Order-Execution" tun, die viele Anweisungen gleichzeitig untersucht und ausführt. Registermaschinen können dies sogar mit viel einfacherer Hardware in der richtigen Reihenfolge, einer flachen Pipeline und etwas intelligenteren Compilern. Der Ladeschritt wird zu einem separaten Befehl, und dieser Befehl wird viel früher in der Codesequenz statisch geplant. Der Compiler legt unabhängige Schritte dazwischen.

Das Planen von Speicherzugriffen erfordert explizite Ersatzregister. Auf Stack-Maschinen ist dies nicht möglich, ohne dem Programmierer einen Aspekt der Mikroarchitektur offenzulegen. Für den Ausdruck AB - muss B ausgewertet und unmittelbar vor dem Minus-Schritt gepusht werden. Ohne Stack-Permutation oder Hardware-Multithreading kann relativ wenig nützlicher Code dazwischen eingefügt werden, während auf den Abschluss von Load B gewartet wird. Stack-Maschinen können die Speicherverzögerung umgehen, indem sie entweder eine tiefe Ausführungspipeline außerhalb der Reihenfolge haben, die viele Befehle gleichzeitig abdeckt, oder, was wahrscheinlicher ist, dass sie den Stack so permutieren, dass sie an anderen Workloads arbeiten können, während der Ladevorgang abgeschlossen ist, oder sie kann die Ausführung verschiedener Programm-Threads verschachteln, wie im Unisys A9-System. Die zunehmend parallelen Rechenlasten von heute deuten jedoch darauf hin, dass dies möglicherweise nicht der Nachteil ist, der in der Vergangenheit dargestellt wurde.

Stapelmaschinen können die Operandenabrufstufe einer Registermaschine weglassen. Beispielsweise treten in dem Mikroprozessor des Java Optimized Processor (JOP) die oberen 2 Operanden des Stapels direkt in eine Datenweiterleitungsschaltung ein, die schneller als die Registerdatei ist.

Außerordentliche Ausführung

Der Tomasulo-Algorithmus findet Parallelität auf Befehlsebene, indem er Befehle ausgibt, sobald ihre Daten verfügbar werden. Konzeptionell unterscheiden sich die Adressen von Positionen in einem Stapel nicht von den Registerindizes einer Registerdatei. Diese Ansicht ermöglicht die Ausführung des Tomasulo-Algorithmus außerhalb der Reihenfolge , um mit Stack-Maschinen verwendet zu werden.

Eine Ausführung außerhalb der Reihenfolge in Stapelmaschinen scheint viele theoretische und praktische Schwierigkeiten zu reduzieren oder zu vermeiden. Die zitierte Forschung zeigt, dass eine solche Stapelmaschine Parallelität auf Befehlsebene ausnutzen kann und die resultierende Hardware Daten für die Befehle zwischenspeichern muss. Solche Maschinen umgehen effektiv die meisten Speicherzugriffe auf den Stack. Das Ergebnis erreicht einen Durchsatz (Anweisungen pro Takt ) vergleichbar mit RISC- Registermaschinen, mit viel höheren Codedichten (da Operandenadressen implizit sind).

Ein Problem, das in der Forschung aufgeworfen wurde, war, dass ungefähr 1,88 Stapelmaschinenbefehle benötigt werden, um die Arbeit des RISC-Befehls einer Registermaschine zu erledigen. Wettbewerbsfähige Out-of-Order-Stack-Maschinen benötigen daher etwa doppelt so viele elektronische Ressourcen, um Anweisungen zu verfolgen ("Ausgabestationen"). Dies könnte durch Einsparungen beim Befehlscache- und Speicher- und Befehlsdecodierungsschaltkreis ausgeglichen werden.

Versteckt eine schnellere Kassenmaschine im Inneren

Einige einfache Stapelmaschinen haben ein Chipdesign, das bis auf die Ebene einzelner Register vollständig angepasst ist. Das Top-of-Stack-Adressregister und die N Top-of-Stack-Datenpuffer sind aus getrennten einzelnen Registerschaltungen mit getrennten Addierern und Ad-hoc-Verbindungen aufgebaut.

Die meisten Stapelmaschinen sind jedoch aus größeren Schaltungskomponenten aufgebaut, bei denen die N Datenpuffer zusammen in einer Registerdatei gespeichert sind und sich Lese-/Schreibbusse teilen. Die decodierten Stapelbefehle werden in eine oder mehrere sequentielle Aktionen dieser versteckten Registerdatei abgebildet. Ladevorgänge und ALU-Operationen wirken auf einige wenige oberste Register, und implizite Spills und Fills wirken auf die untersten Register. Der Decoder ermöglicht, dass der Befehlsstrom kompakt ist. Aber wenn der Codestrom stattdessen explizite Registerauswahlfelder hätte, die die zugrunde liegende Registerdatei direkt manipulierten, könnte der Compiler alle Register besser nutzen und das Programm würde schneller laufen.

Ein Beispiel hierfür sind mikroprogrammierte Stapelmaschinen. Die innere Mikrocode-Engine ist eine Art RISC-ähnlicher Registerautomat oder ein VLIW- ähnlicher Rechner, der mehrere Registerdateien verwendet. Wenn diese Engine direkt durch aufgabenspezifischen Mikrocode gesteuert wird, wird viel mehr Arbeit pro Zyklus abgeschlossen, als wenn sie indirekt durch einen gleichwertigen Stack-Code für dieselbe Aufgabe gesteuert wird.

Die Objektcode-Übersetzer für HP 3000 und Tandem T/16 sind ein weiteres Beispiel. Sie übersetzten Stack-Code-Sequenzen in äquivalente Sequenzen von RISC-Code. Kleinere "lokale" Optimierungen entfernten einen Großteil des Overheads einer Stack-Architektur. Ersatzregister wurden verwendet, um wiederholte Adressberechnungen auszuschließen. Der übersetzte Code enthielt immer noch viel Emulations-Overhead aufgrund der Nichtübereinstimmung zwischen Original- und Zielcomputern. Trotz dieser Belastung entsprach die Zykluseffizienz des übersetzten Codes der Zykluseffizienz des ursprünglichen Stapelcodes. Und wenn der Quellcode über Optimierungscompiler direkt auf die Registermaschine rekompiliert wurde, verdoppelte sich die Effizienz. Dies zeigt, dass die Stack-Architektur und ihre nicht optimierenden Compiler mehr als die Hälfte der Leistung der zugrunde liegenden Hardware verschwendet haben.

Registerdateien sind gute Rechenwerkzeuge, da sie im Vergleich zu Speicherreferenzen über Datencaches eine hohe Bandbreite und eine sehr geringe Latenz aufweisen. In einer einfachen Maschine ermöglicht die Registerdatei das Lesen von zwei unabhängigen Registern und das Schreiben eines dritten, alles in einem ALU-Zyklus mit einer Latenzzeit von einem Zyklus oder weniger. Wohingegen der entsprechende Datencache nur einen Lese- oder einen Schreibvorgang (nicht beides) pro Zyklus starten kann und der Lesevorgang typischerweise eine Latenzzeit von zwei ALU-Zyklen hat. Das ist ein Drittel des Durchsatzes bei der doppelten Pipeline-Verzögerung. In einer komplexen Maschine wie Athlon , die zwei oder mehr Befehle pro Zyklus ausführt, ermöglicht die Registerdatei das Lesen von vier oder mehr unabhängigen Registern und das Schreiben von zwei anderen, alles in einem ALU-Zyklus mit einer Latenzzeit von einem Zyklus. Während der entsprechende Dual-Ported-Datencache nur zwei Lese- oder Schreibvorgänge pro Zyklus mit mehreren Latenzzyklen starten kann. Das ist wiederum ein Drittel des Durchsatzes von Registern. Es ist sehr teuer, einen Cache mit zusätzlichen Ports aufzubauen.

Da ein Stack eine Komponente der meisten Softwareprogramme ist, kann eine Hardware-Stack-Maschine, selbst wenn die verwendete Software nicht unbedingt eine Stack-Maschine ist, das Innenleben ihrer Programme genauer nachahmen. Prozessorregister haben hohe thermische Kosten, und eine Stapelmaschine kann eine höhere Energieeffizienz beanspruchen.

Unterbrechungen

Das Reagieren auf einen Interrupt beinhaltet das Speichern der Register in einem Stack und das anschließende Verzweigen zum Interrupt-Handler-Code. Stack-Maschinen reagieren oft schneller auf Interrupts, da sich die meisten Parameter bereits auf einem Stack befinden und nicht dorthin verschoben werden müssen. Einige Registermaschinen umgehen dies, indem sie mehrere Registerdateien haben, die sofort ausgetauscht werden können, aber dies erhöht die Kosten und verlangsamt die Registerdatei.

Dolmetscher

Interpreter für virtuelle Stapelmaschinen sind einfacher zu erstellen als Interpreter für Registermaschinen; die Logik zum Behandeln von Speicheradreßmodi befindet sich an nur einer Stelle und wird nicht in vielen Befehlen wiederholt. Stack-Maschinen neigen auch dazu, weniger Variationen eines Opcodes zu haben; ein verallgemeinerter Opcode wird sowohl häufige Fälle als auch obskure Eckfälle von Speicherreferenzen oder Funktionsaufrufen behandeln. (Aber die Codedichte wird oft verbessert, indem kurze und lange Formulare für dieselbe Operation hinzugefügt werden.)

Interpreter für virtuelle Stack-Maschinen sind oft langsamer als Interpreter für andere Arten von virtuellen Maschinen. Diese Verlangsamung ist am schlimmsten, wenn sie auf Host-Rechnern mit tiefen Ausführungspipelines ausgeführt wird, wie z. B. aktuellen x86-Chips.

Bei einigen Interpretern muss der Interpreter einen N-Wege-Umschaltsprung ausführen, um den nächsten Opcode zu decodieren und zu seinen Schritten für diesen bestimmten Opcode zu verzweigen. Eine andere Methode zum Auswählen von Opcodes ist Threaded-Code . Die Vorabrufmechanismen der Hostmaschine sind nicht in der Lage, das Ziel dieses indizierten oder indirekten Sprungs vorherzusagen und abzurufen. Daher muss die Ausführungspipeline der Hostmaschine jedes Mal neu gestartet werden, wenn der gehostete Interpreter einen anderen virtuellen Befehl decodiert. Dies geschieht bei virtuellen Stack-Maschinen häufiger als bei anderen Arten von virtuellen Maschinen.

Ein Beispiel ist die Programmiersprache Java . Seine kanonische virtuelle Maschine wird als 8-Bit-Stack-Maschine angegeben. Die auf Android- Smartphones verwendete virtuelle Maschine von Dalvik für Java ist jedoch eine virtuelle 16-Bit-Registriermaschine - eine Wahl, die aus Effizienzgründen getroffen wurde. Arithmetische Befehle holen oder speichern lokale Variablen direkt über 4-Bit-Befehlsfelder (oder größer). In ähnlicher Weise ersetzte Version 5.0 von Lua seine virtuelle Stapelmaschine durch eine schnellere virtuelle Registermaschine.

Seit die Java Virtual Machine populär wurde, haben Mikroprozessoren fortschrittliche Verzweigungsprädiktoren für indirekte Sprünge verwendet. Dieser Fortschritt vermeidet die meisten Pipeline-Neustarts von N-Weg-Sprüngen und eliminiert einen Großteil der Kosten für die Befehlszählung, die Stapelinterpreter betreffen.

Siehe auch

Verweise

Externe Links