Stapelmaschine

Für Stack -Maschinen in der Automatentheorie siehe Pushdown -Automaten.

Im Informatik, Technische Informatik und Programmiersprache Implementierungen, a Stapelmaschine ist ein Computerprozessor oder ein virtuelle Maschine in dem sich die primäre Wechselwirkung kurzlebige temporäre Werte zu und von einem Druck nach unten bewegen Stapel. Im Falle eines Hardwareprozessors a Hardware -Stack wird genutzt. Die Verwendung eines Stacks reduziert die erforderliche Anzahl von erheblich Prozessorregister. Stapelmaschinen erstrecken sich Push-Down-Automaten mit zusätzlichen Last-/Speichervorgängen oder mehreren Stapeln und daher sind Turing-Complete.

Entwurf

Die meisten oder alle Stapelmaschinenanweisungen gehen davon aus, dass Operanden aus dem Stapel stammen und die Ergebnisse im Stapel platziert werden. Der Stapel enthält problemlos mehr als zwei Eingänge oder mehr als ein Ergebnis, sodass ein reichhaltiger Vorgänge berechnet werden kann. Im Stack -Maschinencode (manchmal genannt P-Code) Anweisungen haben häufig nur eine Opcode einen Betrieb befehlen, ohne zusätzliche Felder, die eine Konstante, Registrier- oder Speicherzelle identifizieren, die als a bezeichnet wird Null Adressformat.[1] Dies vereinfacht die Unterrichtskodierung erheblich. Zweige, Sofortlastanweisungen und Last-/Speicheranweisungen erfordern ein Argumentfeld, aber Stapelmaschinen ordnen häufig an, dass die häufigen Fälle von diesen noch mit dem Opcode in eine kompakte Gruppe von Bits passen. Die Auswahl der Operanden aus früheren Ergebnissen erfolgt implizit durch Bestellung der Anweisungen. Einige Stack -Maschinenanweisungssätze sind für die Interpretation einer virtuellen Maschine vorgesehen, anstatt Hardware direkt zu fahren.

Ganzzahl konstante Operanden werden durchgeschoben Push oder Load Immediate Anweisungen. Speicher wird oft durch separate Zugriff Load oder Store Anweisungen, die eine Speicheradresse enthalten oder die Adresse aus Werten im Stapel berechnen. Alle praktischen Stack -Maschinen haben Varianten der Last -Store -Opcodes zum Zugriff Lokale Variablen und formale Parameter ohne explizite Adressberechnungen. Dies kann durch Offsets von der aktuellen Top-of-Stack-Adresse oder durch Offsets aus einem stabilen Frame-Base-Register erfolgen.

Das Befehlssatz führt die meisten ALU -Aktionen mit Postfix aus (Polnische Notation umgekehrt) Operationen, die nur am Expressionsstapel funktionieren, nicht auf Datenregistern oder Hauptspeicherzellen. Dies kann sehr bequem für die Ausführung von Sprachen auf hoher Ebene sein, da die meisten arithmetischen Ausdrücke leicht in 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), in umgekehrter polnischer Notation geschrieben als A B C - * D E + +. Das Kompilieren und Ausführen dieser auf einer einfachen imaginären Stapelmaschine würde das Formular annehmen:

                 # Stack-Inhalt (links = top = letztes): Push A # A Push B # B A Push C # C B A Subtrahieren # b-c a multiply # a*(b-c) push d # d a*(b-c) push e # e d a*(b-c ) # d+e a*(b-c) hinzufügen # a*(b-c)+(d+e)

Die arithmetischen Operationen "Subtrahieren", "multiplizieren" und "Hinzufügen" auf die beiden obersten Operanden des Stapels. Der Computer nimmt beide Operationen aus den obersten (neuesten) Werten des Stapels. Der Computer ersetzt diese beiden Werte durch die berechnete Differenz, Summe oder Produkt. Mit anderen Worten, die Operanden der Anweisungen werden vom Stapel "gestoßen", und ihre Ergebnisse werden dann wieder auf den Stapel "gedrückt", und bereit für die nächste Anweisung.

Stapelmaschinen können ihren Ausdrucksstapel und ihre haben Call-Return Stack getrennt oder als eine integrierte Struktur. Wenn sie getrennt sind, können die Anweisungen der Stapelmaschine sein Pipeline Mit weniger Interaktionen und weniger Designkomplexität, so dass es normalerweise schneller läuft.

Die Optimierung des kompilierten Stackcodes ist durchaus möglich. Es wurde gezeigt, dass die Back-End-Optimierung des Compiler-Ausgangs den Code signifikant verbessert.[2][3] und möglicherweise Leistung, während die globale Optimierung innerhalb des Compilers selbst weitere Gewinne erzielt.[4]

Stapelspeicher

Einige Stack -Maschinen verfügen über einen Stapel mit begrenzter Größe, der als Registerdatei implementiert wird. Die ALU wird mit einem Index darauf zugreifen. 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 verfügen über einen Stapel unbegrenzter Größe, das als Array in RAM implementiert wird, das von einer beliebigen Anzahl "Top of Stapel" -Andadressregister zwischengespeichert wird, um den Speicherzugriff zu reduzieren. Mit Ausnahme expliziter "Lastanweisungen aus dem Speicher" ist die Reihenfolge der Operandenverwendung mit der Reihenfolge der Operanden im Datenstapel identisch, sodass ein hervorragendes Vorabbruch problemlos erreicht werden kann.

In Betracht ziehen X+1. Es kompiliert zu Load X; Load 1; Add. Mit einem Stack, der vollständig im RAM gespeichert ist, schreibt und liest dies im Memory Stack implizit:

  • Laden Sie x, drücken Sie in den Speicher
  • Laden 1, in den Speicher drücken
  • Pop 2 -Werte aus Speicher, Hinzufügen und Drücken von Ergebnis in den Speicher

Für insgesamt 5 Datencache -Referenzen.

Der nächste Schritt davon ist ein Stapelmaschine oder ein Interpreter mit einem einzigen Top-of-Stapel-Register. Der obige Code tut dann:

  • Laden Sie X in leeres TOS -Register (wenn Hardwaremaschine) oder Drücken Sie das TOS -Register in den Speicher und laden Sie X in das TOS -Register (wenn Interpreter).
  • Drücken Sie das TOS -Register in den Speicher und laden Sie 1 in das TOS -Register
  • Pop links Operand aus dem Speicher, fügen Sie zum TOS -Register hinzu und lassen Sie es dort

Für insgesamt 5 Datencache-Referenzen, Worst-Case. Im Allgemeinen verfolgen Dolmetscher die Leere nicht, weil sie nicht müssen-alles unter dem Stapelzeiger ist ein nicht leerer Wert, und das TOS-Cache-Register wird immer heiß gehalten. Typische Java-Dolmetscher puffern jedoch nicht den Top-of-Stapel auf diese Weise, da das Programm und der Stack eine Mischung aus kurzen und breiten Datenwerten haben.

Wenn der festverdrahtete Stack-Computer 2 oder mehr Top-Stack-Register oder eine Registerdatei enthält, wird in diesem Beispiel alle Speicherzugriffszugriffs vermieden und es gibt nur 1 Datencache-Zyklus.

Geschichte und Implementierungen

Beschreibung einer solchen Methode, die nur zwei Werte erfordert, die in Registern gehalten werden müssen, mit einer begrenzten Reihe von vordefinierten Operanden, die per Definition weiterer Operanden, Funktionen und Unterprogramme erweitert werden konnten Robert S. Barton 1961.[5][6]

Werbedackmaschinen

Siehe auch: Hochrangige Sprachcomputerarchitektur

Beispiele für Stapelanweisungssätze, die direkt in der Hardware ausgeführt wurden

  • das Z4 (1945) Computer von Konrad Zuse.[7][8]
  • das Burroughs große Systeme Architektur (seit 1961)
  • das English Electric KDF9 Maschine. Der KDF9 wurde erstmals 1964 geliefert und hatte einen 19-stufigen Tiefenstapel arithmetischer Register und einen 17-Level
  • das Collins Radio Collins Adaptive Processing System Minicomputer (Caps, seit 1969) und Rockwell Collins Erweiterter Architektur -Mikroprozessor (AAMP, seit 1981).[9]
  • das Xerox -Löwenzahn Einführung am 27. April 1981 verwendete eine Stack Machine -Architektur, um Speicher zu sparen.[10][11]
  • das UCSD Pascal p-machine (als die Pascal Microengine und viele andere) unterstützten eine vollständige Student-Programmierumgebung in frühen 8-Bit-Mikroprozessoren mit schlechten Unterrichtssätzen und wenig RAM, indem sie zu einer virtuellen Stapelmaschine zusammengestellt wurden.
  • Mu5 und ICL 2900 -Serie. Hybridstapel- und Akkumulatormaschinen. Der Akkumulatorregister hat den Top -Datenwert des Speicherstapels gepuffert. Varianten von Last- und Speichern von Opcodes, die gesteuert wurden, wenn dieses Register an den Speicherstapel verschüttet oder von dort neu geladen wurde.
  • HP 3000 (Klassiker, nicht PA-RISC)
  • Tandem -Computer T/16. Wie HP 3000, außer dass Compiler, nicht Mikrocode, gesteuert, wenn der Registerstapel am Speicherstapel verschüttet wurde oder aus dem Speicherstapel nachgefüllt wurde.
  • das Atmel Marc4 Mikrocontroller[12]
  • Mehrere "vorhips"[13] wie der RTX2000, die RTX2010, der F21[14] und die PSC1000[15][16]
  • Das Setun Ternärer Computer durchgeführt ausgewogener Ternär mit einem Stapel.
  • Der 4 -Stack -Prozessor von Bernd Paysan hat vier Stapel.[17]
  • Patriot Scientific's Entzünden Stapelmaschine entworfen von von Charles H. Moore hält eine Führung Funktionsdichte Benchmark.
  • Saab Ericsson Raum Thor Strahlung verhärtet Mikroprozessor[18]
  • Inmos transputers.
  • ZPU Eine körperlich-smallische CPU, die zur Überwachung entwickelt wurde FPGA Systeme.[19]
  • Die F18A-Architektur des 144-Prozessors GA144 Chip von Greenarrays, Inc.[20][21][22]
  • Einige technische Handheld -Taschenrechner verwenden in ihrer Tastaturschnittstelle umgekehrte polnische Notation, anstatt Klammentasten zu haben. Dies ist eine Form von Stack Machine. Der Plus-Schlüssel basiert auf seinen beiden Operanden, die sich bereits an den richtigen obersten Positionen des benutzerfreundlichen Stacks befinden.

Virtuelle Stack -Maschinen

Beispiele von virtuell In Software interpretierte Stack -Maschinen:

Hybridmaschinen

Nicht zu verwechseln mit Hybrid Computer Das kombiniert sowohl digitale als auch analoge Merkmale.

Reine Stack -Maschinen sind für Verfahren, die aus demselben Objekt auf mehrere Felder zugreifen, recht ineffizient. Der Stack -Maschinencode muss den Objektzeiger für jede Zeiger+Offset -Berechnung neu laden. Dies ist eine übliche Lösung dafür, einige Funktionen für Register-Maschinen zum Stapelmaschine hinzuzufügen: Eine sichtbare Registerdatei, die den Anweisungen von Adressen und Anweisungen im Registerstil für Lasten und einfache Adressberechnungen gewidmet ist. Es ist ungewöhnlich, dass die Register einen vollständigen Zweck haben, denn dann gibt es keinen starken Grund, einen Ausdrucksstapel- und Postfix -Anweisungen zu haben.

Ein weiterer häufiger Hybrid besteht darin, mit einer Registermaschinenarchitektur zu beginnen und einen weiteren Speicheradressmodus hinzuzufügen, der die Push- oder Pop -Operationen von Stack -Maschinen emuliert: 'memaddress = reg; reg += instr.displ '. Dies wurde zum ersten Mal in verwendet Dez's PDP-11 Minicomputer. Diese Funktion wurde in vorgenommen Vax Computer und in Motorola 6800 und M68000 Mikroprozessoren. Dies ermöglichte die Verwendung einfacherer Stapelmethoden in frühen Compilern. Es unterstützte auch virtuelle Maschinen mit Stackinterpretern oder effizient Thread -Code. Diese Funktion half jedoch nicht dem eigenen Code des Registers Maschine, so kompakt wie Pure Stack Machine Code zu werden. Außerdem war die Ausführungsgeschwindigkeit geringer als beim Kompilieren der Registerarchitektur. Es ist schneller, den Top-of-Stapel-Zeiger nur gelegentlich (einmal pro Anruf oder Rückkehr) zu ändern, anstatt ihn während jeder Programmaussage ständig auf und ab zu treten, und es ist noch schneller, Speicherreferenzen vollständig zu vermeiden.

In jüngerer Zeit haben sogenannte Stack-Maschinen der zweiten Generation eine dedizierte Sammlung von Registern eingesetzt, um als Adressregister zu dienen und die Aufgabe des Speicheradressings aus dem Datenstapel auszuladen. Zum Beispiel stützt sich MUP21 auf ein Register mit dem Titel "A", während die neueren Greenarrays -Prozessoren auf zwei Register angewiesen sind: A und B.[21]

Die Intel X86-Familie von Mikroprozessoren verfügt über einen Anweisungssatz (Accumulator) für die meisten Operationen, verwenden jedoch Stack-Anweisungen für seine x87, Intel 8087 Floating Point Arithmetic, aus dem IAPX87 (8087) -Koprozessor für den 8086 und 8088 zurück. Der X87 ist stark auf die X86 -CPU angewiesen, um ihre Operationen auszuführen.

Computer, die Anrufstacks und Stapelrahmen verwenden

Die meisten aktuellen Computer (eines Anweisungssatzstils) und die meisten Compiler verwenden eine große Call-Return Stack im Speicher, um die kurzlebigen lokalen Variablen zu organisieren und Links für alle derzeit aktiven Prozeduren oder Funktionen zurückzugeben. Jeder verschachtelte Anruf schafft eine neue Stapelrahmen im Gedächtnis, was bis zu diesem Anruf bestehen bleibt. Dieser Call-Return-Stack kann von der Hardware vollständig über spezielle Adressregister und Sonderadressmodi in den Anweisungen verwaltet werden. Oder es kann sich lediglich um eine Reihe von Konventionen handeln, gefolgt von den Compilern unter Verwendung generischer Register und Register+Offset -Adressmodi. Oder es kann etwas dazwischen sein.

Da diese Technik jetzt nahezu universell ist, selbst bei Registermaschinen, ist es nicht hilfreich, all diese Maschinen als Stack -Maschinen zu bezeichnen. Dieser Begriff ist üblicherweise Maschinen reserviert, die auch einen Ausdrucksstapel und nur arithmetischen Anweisungen für Stapel verwenden, um die Teile einer einzelnen Aussage zu bewerten.

Computer bieten üblicherweise einen direkten und effizienten Zugriff auf das Programm des Programms globale Variablen und zu den lokalen Variablen nur des aktuellen innersten Verfahrens oder der obersten Stapelrahmen. Die ad -Level -Adressierung des Inhalts der Anrufer -Stack -Frames wird normalerweise nicht benötigt und nicht wie direkt von der Hardware unterstützt. Bei Bedarf unterstützen Compiler dies, indem sie Rahmenzeiger als zusätzliche, versteckte Parameter übergeben.

Einige Burroughs-Stack-Maschinen unterstützen auf UP-Level-Refs direkt in der Hardware mit speziellen Adressmodi und einer speziellen "Display"-Registerdatei, die die Frame-Adressen aller äußeren Bereiche enthält. Keine nachfolgenden Computerlinien haben dies in Hardware getan. Wann Niklaus Wirth entwickelte das erste Pascal Compiler für die CDC 6000Er stellte fest, dass es insgesamt schneller war, die Rahmenzeiger als Kette zu übergeben, anstatt die vollständigen Arrays von Rahmenzeigern ständig zu aktualisieren. Diese Softwaremethode fügt auch keinen Overhead für gemeinsame Sprachen wie C hinzu, denen Refs auf hohem Niveau fehlen.

Die gleichen Burroughs -Maschinen unterstützten auch die Verschachtelung von Aufgaben oder Fäden. Die Aufgabe und ihr Schöpfer teilen die zum Zeitpunkt der Aufgabenerstellung existierenden Stapelrahmen, aber nicht die nachfolgenden Frames des Schöpfers oder die eigenen Rahmen der Aufgabe. Dies wurde von a unterstützt Kaktusstapel, dessen Layout -Diagramm dem Kofferraum und den Armen von a ähnelte Saguaro Kaktus. Jede Aufgabe hatte ihr eigenes Speichersegment, das ihren Stapel und die Rahmen hielt, die sie besitzt. Die Basis dieses Stapels ist mit der Mitte des Stapels seines Schöpfers verbunden. In Maschinen mit einem herkömmlichen flachen Adressraum wären der Schöpferstapel und die Aufgabenstapel separate Haufen Objekte in einem Haufen.

In einigen Programmiersprachen sind die Datenumgebungen der Außenkope nicht immer rechtzeitig verschachtelt. Diese Sprachen organisieren ihre Prozedur "Aktivierungsaufzeichnungen" eher als separate Heap -Objekte als als Stapelrahmen, die an einen linearen Stapel angehängt sind.

In einfachen Sprachen wie Weiter In diesem fehlenden lokalen Variablen und der Benennung von Parametern würden Stapelrahmen nichts anderes enthalten, als Niederlassung Adressen und Rahmenverwaltungsaufwand. Ihr Rückgabestapel enthält also eher bloße Rückgabedressen als Rahmen. Der Rückgabestapel ist vom Datenwertstapel getrennt, um den Aufruffluss zu verbessern und zurückzutreten.

Vergleich mit Registermaschinen

Stapelmaschinen werden oft verglichen mit Maschinen registrieren, die Werte in einem Array von enthält Register. Registermaschinen speichern Stack-ähnliche Strukturen in diesem Array, aber eine Registermaschine enthält Anweisungen, die die Stapelschnittstelle umgehen. Registrieren Sie Maschinen routinemäßig Stapelmaschinen,[24] Und Stack -Maschinen sind ein Nischenspieler in Hardware -Systemen geblieben. Stack -Maschinen werden jedoch häufig zur Implementierung verwendet virtuelle Maschinen wegen ihrer Einfachheit und einfachen Implementierung.[25]

Anweisungen

Stapelmaschinen haben höher Codedichte. Im Gegensatz zu gängigen Anweisungen für Stack-Maschinen, die leicht in 6 Bits oder weniger passen können, benötigen Registermaschinen zwei oder drei Registrierungsfelder pro ALU-Anweisung, um Operanden auszuwählen. Die dichtesten Registermaschinen durchschnittlich 16 Bit pro Anweisung zuzüglich der Operanden. Registermaschinen verwenden auch ein breiteres Offset-Feld für Last-Store-Opcodes. Der kompakte Code eines Stack -Computers passt natürlich zu mehr Anweisungen in Cache und könnte daher besser erreichen Zwischenspeicher Effizienz, Reduzierung der Speicherkosten oder das Ermöglichen von schnelleren Speichersystemen für eine bestimmte Kosten. Darüber hinaus sind die meisten Stapel-Maschinen-Anweisungen sehr einfach und bestehen nur aus einem Opcode-Feld oder einem Operandenfeld. Daher benötigen Stapelmaschinen nur sehr wenig elektronische Ressourcen, um jede Anweisung zu dekodieren.

Ein Programm muss mehr Anweisungen ausführen, wenn sie mit einem Stapelmaschine kompiliert werden, als wenn sie mit einem Registermaschine oder Speicher-Memory-Computer kompiliert werden. Jede variable Last oder Konstante erfordert einen eigenen separaten Lastanweis, anstatt innerhalb der Anweisung gebündelt zu werden, die diesen Wert verwendet. Die getrennten Anweisungen können einfach und schneller ausgeführt werden, aber die Gesamtanweisungsanzahl ist immer noch höher.

Die meisten Registerdolmetscher geben ihre Register nach Anzahl an. Auf die Register eines Host -Geräts kann jedoch nicht in einem indizierten Array zugegriffen werden. Daher wird ein Speicherarray für virtuelle Register zugeteilt. Daher müssen die Anweisungen eines Registers Interpreter Speicher zum Übergeben generierter Daten an die nächste Anweisung verwenden. Diese Kräfte registrieren Dolmetscher als viel langsamer auf Mikroprozessoren, die mit einer feinen Prozessregel hergestellt wurden (d. H. schnellere Transistoren ohne Verbesserung der Schaltungsgeschwindigkeiten wie dem Haswell X86). Diese erfordern mehrere Uhren für den Speicherzugriff, jedoch nur eine Uhr für den Registerzugriff. Bei einer Stackmaschine mit einer Datenweitschaltung anstelle einer Registerdatei können Stack -Dolmetscher die Register des Host -Computers für die oberen Operanden des Stacks anstelle des Speicher des Host -Geräts zuweisen

In einer Stackmaschine befinden sich die in den Anweisungen verwendeten Operanden immer an einem bekannten Versatz (im Stapelzeiger festgelegt) von einem festen Ort (unten im Stapel, der in einem Hardwaredesign immer an Speicherort Null liegt). kostbare sparenZwischenspeicher oder in-Zentralprozessor Lagerung von der Verwendung von so vielen Speichern Speicheradressen oder Indexnummern. Dies kann solche Register und Cache für die Verwendung in der Berechnung ohne Fluss erhalten.

Temporäre / lokale Werte

Einige in der Branche glauben, dass Stack -Maschinen mehr ausführen Datencache Zyklen für temporäre Werte und lokale Variablen als Registrierungsmaschinen.[26]

Bei Stack -Maschinen werden vorübergehende Werte häufig in den Speicher verschüttet, während auf Maschinen mit vielen Registern diese Temperaturen normalerweise in Registern verbleiben. (Diese Werte müssen jedoch häufig in "Aktivierungsrahmen" am Ende der Definition eines Prozesses, des Basisblocks oder zumindest in einen Speicherpuffer während der Interrupt -Verarbeitung verschüttet werden.) Werte, die zum Speicher verschüttet wurden, fügen Sie mehr Cache -Zyklen hinzu. Dieser Verschüttungseffekt hängt von der Anzahl der versteckten Register ab, mit denen erstklassige Werte gepuffert werden, von der Häufigkeit verschachtelter Verfahrensanrufe und bei den Verarbeitungsraten für Host-Computer unterbrechen.

Bei Registermaschinen mit optimierenden Compilern ist es sehr häufig, dass die am häufigsten verwendeten lokalen Variablen eher in Registern als in Stapelrahmen-Speicherzellen bleiben. Dadurch werden die meisten Daten -Cache -Zyklen zum Lesen und Schreiben dieser Werte beseitigt. Die Entwicklung der "Stapelplanung" für die Durchführung von Live-Variable-Analysen und die Aufbewahrung der wichtigsten Variablen im Stapel für längere Zeiträume hilft diesem Anliegen.

Andererseits müssen Registermaschinen viele ihrer Register in den Speicher von verschachtelten Verfahrensanrufen verschütten. Die Entscheidung, welche Register zu verschütteten, und wenn, wird statisch zu Kompilierungszeit und nicht in der dynamischen Tiefe der Anrufe getroffen. Dies kann zu mehr Datencache -Verkehr führen als in einer Implementierung für erweiterte Stack -Maschine.

Gemeinsame Unterexpressionen

In Registermaschinen a Häufige Unterexpression (Eine Suberpression, die mehrmals mit demselben Ergebniswert verwendet wird) kann nur einmal bewertet und sein Ergebnis in einem schnellen Register gespeichert werden. Die nachfolgenden Rückverwussen haben keine Zeit- oder Codekosten, nur eine Registerreferenz. Diese Optimierung beschleunigt einfache Ausdrücke (z. B. Ladevariable x oder Zeiger P) sowie weniger komplexe Ausdrücke.

Mit Stack -Maschinen können die Ergebnisse auf zwei Arten gespeichert werden. Zunächst können Ergebnisse unter Verwendung einer temporären Variablen im Speicher gespeichert werden. Das Speichern und die anschließenden Abrufen kosten zusätzliche Anweisungen und zusätzliche Datencache -Zyklen. Dies ist nur ein Gewinn, wenn die Suberpressionsberechnung mehr rechtzeitig kostet als das Abholen des Speichers, was in den meisten Stack -CPUs fast immer der Fall ist. Es lohnt sich nie für einfache Variablen und Zeigerabrufe, da diese bereits die gleichen Kosten für einen Datencache -Zyklus pro Zugriff haben. Es lohnt sich nur geringfügig 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 wurden. Ein optimierender Compiler kann nur bei Entlassungen gewinnen, die der Programmierer im Quellcode hätte vermieden können.

Der zweite Weg hinterlässt einen berechneten Wert auf dem Datenstapel und dupliziert ihn nach Bedarf. Damit werden Operationen verwendet, um Stapeleinträge zu kopieren. Der Stapel muss für die verfügbaren Kopieranweisungen der CPUs flach genug sein. Der handgeschriebene Stapelcode verwendet diesen Ansatz häufig und erreicht Geschwindigkeiten wie allgemeine Registermaschinen.[27][8] Leider werden Algorithmen für eine optimale "Stapelplanung" durch Programmiersprachen nicht weit verbreitet.

Pipelining

In modernen Maschinen ist die Zeit zum Abholen einer Variablen aus dem Datencache oft mehrmals länger als die Zeit, die für grundlegende ALU -Operationen benötigt wird. Ein Programm läuft schneller ohne Stände, wenn seine Speicherlasten vor dem Befehl, der diese Variable benötigt, mehrere Zyklen gestartet werden kann. Komplexe Maschinen können dies mit einer tiefen Pipeline und einer "Ausführung außerhalb der Ordnung" tun, die viele Anweisungen gleichzeitig untersucht und ausführt. Registermaschinen können dies sogar mit viel einfacherer "In-Ordnung" -Hardware, einer flachen Pipeline und leicht intelligenteren Compilern tun. Der Lastschritt wird zu einer separaten Anweisung, und diese Anweisung ist in der Codesequenz statisch viel früher geplant. Der Compiler macht unabhängige Schritte dazwischen.

Die Planungsspeicherzugriffe erfordert explizite, Ersatzregister. Auf Stack-Maschinen ist es nicht möglich, ohne dem Programmierer einen Aspekt der Mikroarchitektur zu vermitteln. Für den Ausdruck A B -muss B unmittelbar vor dem Minusschritt bewertet und gedrückt werden. Ohne Stackpermutation oder Hardware -Multithreading kann ein relativ wenig nützlicher Code dazwischen eingesetzt werden, während das Last B wartet. Stack-Maschinen können die Speicherverzögerung durch eine tiefe Ausführungspipeline außerhalb der Bestellung abdecken, die viele Anweisungen gleichzeitig abdeckt, oder wahrscheinlicher, dass sie den Stapel so durchdringen können, dass sie während des Abschlusses der Last an anderen Arbeitsbelastungen arbeiten können, oder sie oder sie Kann die Ausführung verschiedener Programmthreads wie im UNISYS A9 -System verbinden.[28] Die heutigen zunehmend parallele rechnerischen Lasten deutet darauf hin, dass dies jedoch möglicherweise nicht der Nachteil ist, der in der Vergangenheit ausgewiesen wurde.

Stack -Maschinen können die Operand -Abholphase einer Registermaschine weglassen.[27] Zum Beispiel in der Java optimierte Prozessor (JOP) Mikroprozessor Die Top -2 -Operanden des Stacks geben direkt eine Datenweitschaltung ein, die schneller als die Registerdatei ist.[29]

Ausführende Ausführung

Das Tomasulo -Algorithmus Funde Parallelität auf Befehlsebene Durch die Ausgabe von Anweisungen, wenn ihre Daten verfügbar sind. Konzeptionell unterscheiden sich die Adressen von Positionen in einem Stapel nicht von den Registerindizes einer Registerdatei. Diese Ansicht erlaubt die Ausführende Ausführung des Tomasulo -Algorithmus, der mit Stapelmaschinen verwendet werden soll.

Ausführende Ausführung in Stack-Maschinen scheint viele theoretische und praktische Schwierigkeiten zu verringern oder zu vermeiden.[30] Die zitierte Untersuchung zeigt, dass eine solche Stapelmaschine die Parallelität auf Befehlsebene ausnutzen kann und die resultierende Hardware Daten für die Anweisungen zwischenspeichern kann. Solche Maschinen umgehen die meisten Speicherzugriffe auf den Stapel effektiv. Das Ergebnis erreicht den Durchsatz (Anweisungen pro Anweisungen pro Uhr) vergleichbar mit RISC Registerautomaten mit viel höheren Codedichten (da Operand -Adressen implizit sind).

Ein Problem in der Untersuchung war, dass etwa 1,88 Stapel-Maschine-Anweisungen erforderlich sind, um die Arbeit eines RISC-Anweisungen einer Registermaschine zu erledigen. Wettbewerbsfähige Stack-Maschinen außerhalb der Bestellung erfordern daher etwa doppelt so viele elektronische Ressourcen, um Anweisungen zu verfolgen ("Problemstationen"). Dies kann durch Einsparungen im Befehls -Cache, Speicher- und Anweisungs -Dekodierungsschaltungen kompensiert werden.

Verbirgt eine schnellere Registermaschine im Inneren

Einige einfache Stack -Maschinen verfügen über ein Chip -Design, das bis hin zu dem Niveau der einzelnen Register vollständig angepasst ist. Das oberste Stapeladressregister und die N -Oberseite der Stapeldatenpuffer werden aus separaten einzelnen Registerkreisen mit separaten Addierern und Ad -hoc -Verbindungen erstellt.

Die meisten Stack -Maschinen werden jedoch aus größeren Schaltungskomponenten erstellt, in denen die N -Datenpuffer in einer Registerdatei zusammen gespeichert werden und Lese-/Schreibbusse teilen. Die dekodierten Stapelanweisungen werden in eine oder mehrere sequentielle Aktionen in dieser versteckten Registerdatei abgebildet. Ladungen und Alu -Ops wirken auf einige erstklassige Register und implizite Verschüttungen und Füllungen wirken auf den Bottommost -Registern. Mit dem Decoder kann der Befehlsstrom kompakt sein. Wenn der Code-Stream stattdessen explizite Registerauswahlfelder hatte, die die zugrunde liegende Registerdatei direkt manipulierten, könnte der Compiler alle Register besser nutzen und das Programm würde schneller ausgeführt.

Mikroprogrammiert Stack -Maschinen sind ein Beispiel dafür. Der innere Mikrocode-Engine ist eine Art RISC-ähnliche Registermaschine oder a VLIW-Bliebenen Maschine mit mehreren Registerdateien. Wenn diese Engine direkt von aufgabenspezifischem Mikrocode gesteuert wird, erhält die Engine viel mehr Arbeit pro Zyklus als bei indirekter Stapelcode für dieselbe Aufgabe.

Die Objektcode -Übersetzer für die HP 3000 und Tandem T/16 sind ein weiteres Beispiel.[31][32] Sie übersetzten Stack -Code -Sequenzen in äquivalente Sequenzen des RISC -Code. Kleinere "lokale" Optimierungen haben einen Großteil des Overhead einer Stapelarchitektur entfernt. Ersatzregister wurden verwendet, um wiederholte Adressberechnungen zu berücksichtigen. Der übersetzte Code behielt immer noch viel Emulationsaufwand aus der Nichtübereinstimmung zwischen Original- und Zielmaschinen. Trotz dieser Belastung stimmte die Zyklusffizienz des übersetzten Code mit der Zyklusffizienz des ursprünglichen Stapelcodes überein. Und als der Quellcode direkt über die Optimierung von Compilern in die Registermaschine neu kompiliert wurde, verdoppelte sich die Effizienz. Dies zeigt, dass die Stack-Architektur und ihre nicht optimierenden Compiler mehr als die Hälfte der Macht der zugrunde liegenden Hardware verschwendeten.

Registerdateien sind gute Tools für die Berechnung, da sie im Vergleich zu Speicherreferenzen über Daten -Caches eine hohe Bandbreite und eine sehr geringe Latenz haben. In einer einfachen Maschine ermöglicht die Registerdatei das Lesen von zwei unabhängigen Registern und das Schreiben eines dritten, alle in einem Alu-Zyklus mit einem Zyklus oder weniger Latenz. Während der entsprechende Datencache nur eine Lektüre oder einen Schreib- (nicht beides) pro Zyklus starten kann, und die Lesung typischerweise eine Latenz von zwei Alu -Zyklen aufweist. Das ist ein Drittel des Durchsatzes bei der doppelten Pipeline -Verzögerung. In einer komplexen Maschine wie Athlon Damit werden zwei oder mehr Anweisungen pro Zyklus abgeschlossen. Die Registerdatei ermöglicht das Lesen von vier oder mehr unabhängigen Registern und das Schreiben von zwei anderen, die alle in einem Alu-Zyklus mit einer Latenz mit einem Zyklus sind. Während der entsprechende doppelte Datencache nur zwei Lesevorgänge pro Zyklus mit mehreren Latenzzyklen starten kann. Auch hier ist das ein Drittel des Registerdurchsatzes. Es ist sehr teuer, einen Cache mit zusätzlichen Ports zu erstellen.

Da ein Stack eine Komponente der meisten Softwareprogramme ist, kann ein Hardware -Stack -Computer die inneren Arbeiten seiner Programme besser nachahmen, selbst wenn die verwendete Software nicht ausschließlich ein Stapelmaschine ist. Prozessorregister haben hohe thermische Kosten, und eine Stapelmaschine kann eine höhere Energieeffizienz beanspruchen.[20]

Interrupts

Bei der Reaktion auf einen Interrupt beinhaltet das Speichern der Register auf einem Stapel und dann auf den Interrupt -Handler -Code. Oft reagieren Stapelmaschinen schneller auf Unterbrechungen, da die meisten Parameter bereits auf einem Stapel sind und sie nicht dort drücken müssen. Einige Registergeräte befassen sich damit, indem Sie mehrere Registerdateien haben, die sofort ausgetauscht werden können[33] Dies erhöht die Kosten und verlangsamt die Registerdatei.

Dolmetscher

Dolmetscher für virtuelle Stapelmaschinen sind einfacher zu erstellen als Dolmetscher für Registergeräte. Die Logik für den Umgang mit Speicheradressmodi liegt nur an einem Ort und nicht an vielen Anweisungen. Stack -Maschinen haben auch tendenziell weniger Variationen eines Opcode. Ein verallgemeinerter OPCODE wird sowohl häufige Fälle als auch dunkle Eckfälle von Speicherreferenzen oder Funktionsaufruf -Setup behandeln. (Die Codedichte wird jedoch häufig durch Hinzufügen von kurzen und langen Formen für denselben Betrieb verbessert.)

Dolmetscher für virtuelle Stapelmaschinen sind oft langsamer als Dolmetscher für andere Stile der virtuellen Maschine.[34] Diese Verlangsamung ist am schlimmsten, wenn Sie auf Host -Maschinen mit tiefen Ausführungsleitungen wie aktuellen X86 -Chips ausgeführt werden.

In einigen Dolmetschern muss der Interpreter einen N-Way-Switch-Sprung ausführen, um den nächsten Opcode zu dekodieren und auf seine Schritte für diesen bestimmten Opcode zu verzweigen. Eine andere Methode zur Auswahl von Opcodes ist Thread -Code. Die Präfet -Mechanismen der Wirtsmaschine können das Ziel dieses indizierten oder indirekten Sprung nicht vorhersagen und abrufen. Daher muss die Ausführungspipeline des Host -Computers jedes Mal neu starten, wenn der gehostete Interpreter einen anderen virtuellen Anweisungen dekodiert. Dies geschieht häufiger für virtuelle Stapelmaschinen als für andere Stile der virtuellen Maschine.[35]

Ein Beispiel ist das Java Programmiersprache. Es ist kanonisch virtuelle Maschine wird als 8-Bit-Stapelmaschine angegeben. Allerdings die Dalvik virtuelle Maschine für Java verwendet auf Android Smartphones ist eine 16-Bit-Virtual-Register-Maschine-eine Auswahl aus Effizienzgründen. Arithmetische Anweisungen holen lokale Variablen direkt über 4-Bit- (oder größere) Befehlsfelder ab oder speichern sie.[36] In ähnlicher Weise ersetzte Version 5.0 von Lua seine virtuelle Stapelmaschine durch eine schnellere virtuelle Registermaschine.[37][38]

Seit Java Virtual Machine populär wurde, haben Mikroprozessoren Fortschritte eingesetzt Zweigprädiktoren für indirekte Sprünge.[39] Dieser Fortschritt vermeidet die meisten Pipeline-Neustarts von N-Way-Sprüngen und beseitigt einen Großteil der Anweisungskosten, die sich auf Stapeldolmetscher auswirken.

Siehe auch

Verweise

  1. ^ Bart, Bob (Herbst 1997). "Der KDF9 -Computer - 30 Jahre an". Computerauferstehung.
  2. ^ Koopman, Jr., Philip John (1994). "Eine vorläufige Untersuchung der optimierten Stapelcodegenerierung" (PDF). Journal of Forth Applications und Forschung. 6 (3).
  3. ^ Bailey, Chris (2000). "Inter-Grenzenplanung von Stack Operanden: Eine vorläufige Studie" (PDF). Verfahren der EuroForth 2000 -Konferenz.
  4. ^ Shannon, Mark; Bailey, Chris (2006). "Globale Stack Allocation: Registrieren Sie die Allokation für Stack -Maschinen" (PDF). Proceedings of EuroForth Conference 2006.
  5. ^ Barton, Robert S. (1961). "Ein neuer Ansatz zum funktionalen Design eines digitalen Computers". Papiere, die auf der vom 9. bis 11. Mai 1961, Western Joint Ire-Aiee-ACM-Computerkonferenz vorgestellt wurden. 1961 Western Joint Ire-Aiee-ACM-Computerkonferenz. S. 393–396. doi:10.1145/1460690.1460736. ISBN 978-1-45037872-7. S2CID 29044652.
  6. ^ Barton, Robert S. (1987). "Ein neuer Ansatz zum funktionalen Design eines digitalen Computers". IEEE Annals of the History of Computing. 9: 11–15. doi:10.1109/mahc.1987.10002.
  7. ^ Blaauw, Gerrit Anne; Brooks, Jr., Frederick Phillips (1997). Computerarchitektur: Konzepte und Evolution. Boston, Massachusetts, USA: Addison-Wesley Longman Publishing Co., Inc.
  8. ^ a b Laforest, Charles Eric (April 2007). "2.1 lukasiewicz und die erste Generation: 2.1.2 Deutschland: Konrad Zuse (1910–1995); 2.2 Die erste Generation von Stapelcomputern: 2.2.1 Zuse Z4". Stack-Computerarchitektur der zweiten Generation (PDF) (These). Waterloo, Kanada: Universität von Waterloo. S. 8, 11, ... Archiviert (PDF) vom Original am 2022-01-20. Abgerufen 2022-07-02. (178 Seiten) [1]
  9. ^ Greve, David A.; Wilding, Matthew M. (1998-01-12). "Der erste Java -Prozessor der Welt". Elektrotechnik Zeiten.
  10. ^ "MESA -Prozessorprinzipien des Betriebs". Digibarn -Computermuseum. Xerox. Abgerufen 2019-12-23.
  11. ^ "Digibarn: The Xerox Star 8010" Löwenzahn "". Digibarn -Computermuseum. Abgerufen 2019-12-23.
  12. ^ Marc4 4-Bit-Mikrocontrollers-Programmierhandbuch (PDF). Atmel.
  13. ^ "Forth Chips". ColorForth.com. Archiviert von das Original am 2006-02-15. Abgerufen 2017-10-08.
  14. ^ "F21 -Mikroprozessorübersicht". Ultratechnology.com. Abgerufen 2017-10-08.
  15. ^ "Forthfreak Wiki". Github.com. 2017-08-25. Abgerufen 2017-10-08.
  16. ^ "Ein Java -Chip verfügbar - jetzt!". Entwickler.com. 1999-04-08. Abgerufen 2022-07-07.
  17. ^ "4 -Stack -Prozessor". bernd-paysan.de. Abgerufen 2017-10-08.
  18. ^ "Portierung des GNU C -Compilers auf den Thor -Mikroprozessor" (PDF). 1995-12-04. Archiviert von das Original (PDF) Am 2011-08-20. Abgerufen 2011-03-30.
  19. ^ "ZPU-Die kleinste 32-Bit-CPU der Welt mit einer GCC-Toolkette: Übersicht". opencores.org. Abgerufen 2015-02-07.
  20. ^ a b "Unterlagen". Greenarrays, Inc. F18A -Technologie. Abgerufen 2022-07-07.
  21. ^ a b "Coloreforth -Anweisungen". ColorForth.com. Archiviert von das Original am 2016-03-10. Abgerufen 2017-10-08. (Anweisungssatz der F18A -Kerne, ColorForth aus historischen Gründen.)
  22. ^ "Greenarrays, Inc". Greenarraychips.com. Abgerufen 2017-10-08.
  23. ^ Randell, Brian; Russell, Lawford John (1964). Algol 60 Implementierung (PDF). London, Vereinigtes Königreich: Akademische Presse. ISBN 0-12-578150-4.
  24. ^ Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertl, M. Anton (2005). "Virtual Machine Showdown: Stack gegen Register". Verfahren der 1. ACM/Usenix Internationalen Konferenz über virtuelle Ausführungsumgebungen - VEE '05: 153. doi:10.1145/1064979.1065001. S2CID 811512.
  25. ^ Hyde, Randall (2004). Schreiben Sie Great Code, vol. 2: Nachdenken auf niedriger Ebene, Schreiben von hoher Ebene. Vol. 2. Keine Stärkepresse. p. 391. ISBN 978-1-59327-065-0. Abgerufen 2021-06-30.
  26. ^ "Computerarchitektur: Ein quantitativer Ansatz", John L. Hennessy, David Andrew Patterson; Siehe die Diskussion von Stack -Maschinen.
  27. ^ a b Koopman, Jr., Philip John. "Stack Computers: Die neue Welle". Ece.cmu.edu. Abgerufen 2017-10-08.
  28. ^ Einführung in ein Seriensystem (PDF). Burroughs Corporation. April 1986. Abgerufen 2022-07-07.
  29. ^ "Design und Implementierung einer effizienten Stapelmaschine" (PDF). Jopdesign.com. Abgerufen 2017-10-08.
  30. ^ Chatterji, Satrajit; Ravindran, Kaushik. "Boost: Berkeley ist außerhalb der Bestellung Stapel Thingie". Forschungstor. Kaushik Ravindran. Abgerufen 2016-02-16.
  31. ^ Bergh, Arndt; Keilman, Keith; Magenheimer, Daniel; Miller, James (Dezember 1987). "HP3000 -Emulation auf HP -Präzisionsarchitektur Computern" (PDF). Hewlett-Packard Journal. Hewlett Packard: 87–89. Abgerufen 2017-10-08.
  32. ^ Migration einer CISC -Computerfamilie über Objektcodeübersetzung auf RISC. Kristy Andrews, Duane Sand: Proceedings of Asplos-V, Oktober 1992
  33. ^ 8051 CPU -Handbuch, Intel, 1980
  34. ^ Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertle, M. Anton. "Virtual Machine Showdown: Stack vs. Register Machine" (PDF). Usenix.org. Abgerufen 2017-10-08.
  35. ^ Davis, Brian; Beatty, Andrew; Casey, Kevin; Gregg, David; Waldron, John. "Der Fall für virtuelle Registermaschinen" (PDF). Scs.tcd.ie. Abgerufen 2017-10-08.
  36. ^ Bornstein, Dan (2008-05-29). "Präsentation von Dalvik VM -Interna" (PDF). p. 22. Abgerufen 2010-08-16.
  37. ^ "Die Implementierung von LuA 5.0" (PDF). Lua.org. Abgerufen 2017-10-08.
  38. ^ "Die virtuelle Maschine von Lua 5.0" (PDF). Inf.puc-rio.br. Abgerufen 2017-10-08.
  39. ^ "Branchenvorhersage und die Leistung von Dolmetschern - Vertrauen Sie der Folklore nicht". Hal.inria.fr. Abgerufen 2017-10-08.

Externe Links