Prädikation (Computerarchitektur) – Wikipedia

Posted on by
before-content-x4

In der Informatik Prädikation ist ein Architekturmerkmal, das eine Alternative zur bedingten Übertragung der Steuerung bietet und durch Maschinenanweisungen wie bedingte Verzweigung, bedingten Aufruf, bedingte Rückgabe und Verzweigungstabellen implementiert wird. Die Prädikation funktioniert, indem Anweisungen von beiden Pfaden des Zweigs ausgeführt werden und nur diese Anweisungen vom genommenen Pfad zugelassen werden, um den Architekturstatus zu ändern.[1] Die Anweisungen aus dem genommenen Pfad dürfen den Architekturstatus ändern, da sie verknüpft wurden (basiert) mit einer PrädikatEin boolescher Wert, der von der Anweisung verwendet wird, um zu steuern, ob die Anweisung den Architekturstatus ändern darf oder nicht.

after-content-x4

Table of Contents

Überblick[edit]

Die meisten Computerprogramme enthalten bedingten Code, der nur unter bestimmten Bedingungen ausgeführt wird, abhängig von Faktoren, die nicht im Voraus bestimmt werden können, z. B. abhängig von Benutzereingaben. Da die meisten Prozessoren einfach den nächsten Befehl in einer Sequenz ausführen, besteht die traditionelle Lösung darin, ihn einzufügen Ast Anweisungen, die es einem Programm ermöglichen, bedingt zu einem anderen Codeabschnitt zu verzweigen und so den nächsten Schritt in der Sequenz zu ändern. Dies war ausreichend, bis die Designer begannen, die Leistung durch die Implementierung von Anweisungs-Pipelining zu verbessern, eine Methode, die durch Zweige verlangsamt wird. Eine ausführlichere Beschreibung der aufgetretenen Probleme und eine beliebte Lösung finden Sie unter Branch Predictor.

Glücklicherweise hat eines der gebräuchlichsten Codemuster, das normalerweise auf Verzweigungen beruht, eine elegantere Lösung. Betrachten Sie den folgenden Pseudocode:[1]

if condition
    {dosomething}
else
    {dosomethingelse};

Auf einem System, das bedingte Verzweigung verwendet, kann dies zu Maschinenanweisungen führen, die ähnlich aussehen wie:[1]

branch-if-condition to label1
dosomethingelse
branch-to label2
label1:
dosomething
label2:
...

Bei der Prädikation werden alle möglichen Verzweigungspfade inline codiert, einige Anweisungen werden jedoch ausgeführt, während andere dies nicht tun. Die Grundidee ist, dass jeder Befehl einem Prädikat zugeordnet ist (das Wort wird hier ähnlich wie in der Prädikatenlogik verwendet) und dass der Befehl nur ausgeführt wird, wenn das Prädikat wahr ist. Der Maschinencode für das obige Beispiel mit Prädikation könnte ungefähr so ​​aussehen:[1]

(condition) dosomething
(not condition) dosomethingelse

Neben der Eliminierung von Verzweigungen wird insgesamt weniger Code benötigt, vorausgesetzt, die Architektur bietet vorgegebene Anweisungen. Dies garantiert zwar im Allgemeinen keine schnellere Ausführung, wird es aber tun, wenn die etwas tun und mach etwas anderes Codeblöcke sind kurz genug.

Die einfachste Form der Prädikation ist teilweise Prädikation, wo die Architektur hat bedingte Bewegung oder bedingte Auswahl Anleitung. Bedingte Verschiebungsanweisungen schreiben den Inhalt eines Registers nur dann über ein anderes, wenn der Wert des Prädikats wahr ist, während bedingte Auswahlbefehle basierend auf dem Wert des Prädikats auswählen, welches von zwei Registern in ein drittes Register geschrieben wird. Eine allgemeinere und fähigere Form ist volle Prädikation. Die vollständige Prädikation verfügt über einen Satz von Prädikatenregistern zum Speichern von Prädikaten (wodurch mehrere verschachtelte oder sequentielle Verzweigungen gleichzeitig entfernt werden können), und die meisten Anweisungen in der Architektur verfügen über ein Registerspezifiziererfeld, um anzugeben, welches Prädikatenregister das Prädikat liefert.[2]

 after-content-x4

Vorteile[edit]

Der Hauptzweck der Prädikation besteht darin, Sprünge über sehr kleine Abschnitte des Programmcodes zu vermeiden, die Effektivität der Pipeline-Ausführung zu erhöhen und Probleme mit dem Cache zu vermeiden. Es hat auch eine Reihe subtilerer Vorteile:

  • Funktionen, die traditionell mit einfachen arithmetischen und bitweisen Operationen berechnet werden, lassen sich möglicherweise schneller mit vorhergesagten Anweisungen berechnen.
  • Prädikierte Anweisungen mit unterschiedlichen Prädikaten können miteinander und mit bedingungslosem Code gemischt werden, was eine bessere Befehlsplanung und damit eine noch bessere Leistung ermöglicht.
  • Das Eliminieren unnötiger Verzweigungsbefehle kann die Ausführung notwendiger Verzweigungen, wie z. B. solcher, die Schleifen bilden, beschleunigen, indem die Belastung der Verzweigungsvorhersagemechanismen verringert wird.
  • Eliminierung der Kosten einer Branchenfehlvorhersage, die bei Architekturen mit tiefen Pipelines hoch sein kann.

Nachteile[edit]

Der Hauptnachteil von Predication liegt im vergrößerten Codierungsraum. In typischen Implementierungen reserviert jeder Befehl ein Bitfeld für das Prädikat, das angibt, unter welchen Bedingungen dieser Befehl eine Wirkung haben soll. Wenn der verfügbare Speicher wie bei eingebetteten Geräten begrenzt ist, können diese Platzkosten unerschwinglich sein. Einige Architekturen wie Thumb-2 können dieses Problem jedoch vermeiden (siehe unten). Andere Nachteile sind die folgenden:[3]

  • Die Prädikation verkompliziert die Hardware, indem sie kritischen Pfaden Logikstufen hinzufügt und möglicherweise die Taktrate verschlechtert.
  • Ein vorhergesagter Block enthält Zyklen für alle Operationen, sodass kürzere Pfade länger dauern und bestraft werden können.
  • Prädikation wird nicht spekuliert und führt zu einer längeren Abhängigkeitskette. Für geordnete Daten bedeutet dies einen Leistungsverlust im Vergleich zu einer vorhersehbaren Verzweigung.[4]

Die Vorhersage ist am effektivsten, wenn Pfade ausgeglichen sind oder wenn der längste Pfad am häufigsten ausgeführt wird.[3] Das Bestimmen eines solchen Pfads ist jedoch zum Zeitpunkt der Kompilierung sehr schwierig, selbst wenn Profilinformationen vorhanden sind.

Geschichte[edit]

Prädizierte Anweisungen waren in europäischen Computerdesigns der 1950er Jahre beliebt, darunter Mailüfterl (1955), Zuse Z22 (1955), ZEBRA (1958) und Electrologica X1 (1958). Das IBM ACS-1-Design von 1967 hat ein “Überspring” -Bit in seinen Befehlsformaten zugewiesen, und der CDC Flexible Processor hat 1976 drei bedingte Ausführungsbits in seinen Mikrobefehlsformaten zugewiesen.

Die PA-RISC-Architektur von Hewlett-Packard (1986) hatte eine Funktion namens Aufhebung, wodurch die meisten Anweisungen durch die vorherige Anweisung vorhergesagt werden konnten. Die POWER-Architektur von IBM (1990) enthielt Anweisungen für bedingte Verschiebungen. Der Nachfolger von POWER, PowerPC (1993), ließ diese Anweisungen fallen. Die Alpha-Architektur der Digital Equipment Corporation (1992) enthielt auch Anweisungen für bedingte Bewegungen. MIPS erhielt 1994 mit der MIPS IV-Version Anweisungen für bedingte Bewegungen. und SPARC wurde in Version 9 (1994) um bedingte Verschiebungsanweisungen sowohl für Ganzzahl- als auch für Gleitkommaregister erweitert.

In der Hewlett-Packard / Intel IA-64-Architektur sind die meisten Anweisungen prädiziert. Die Prädikate werden in 64 speziellen Prädikatenregistern gespeichert. und eines der Prädikatregister ist immer so wahr nicht vorhergesagt Anweisungen sind einfach Anweisungen, die mit dem Wert true prädiziert werden. Die Verwendung von Prädikation ist für die Implementierung von Software-Pipelining durch IA-64 von entscheidender Bedeutung, da kein separater Code für Prologe und Epilogs geschrieben werden muss.[clarification needed]

In der x86-Architektur wird eine Familie von Anweisungen für bedingte Verschiebungen (CMOV und FCMOV) wurden der Architektur vom Intel Pentium Pro (1995) -Prozessor hinzugefügt. Das CMOV Anweisungen kopierten den Inhalt des Quellregisters in das Zielregister in Abhängigkeit von einem Prädikat, das durch den Wert des Flagregisters geliefert wird.

In der ARM-Architektur bietet der ursprüngliche 32-Bit-Befehlssatz eine Funktion namens bedingte Ausführung Dadurch können die meisten Befehle von einem von 13 Prädikaten vorhergesagt werden, die auf einer Kombination der vier durch den vorherigen Befehl festgelegten Bedingungscodes basieren. Der Thumb-Befehlssatz (1994) von ARM hat die bedingte Ausführung eingestellt, um die Größe der Befehle so zu verringern, dass sie in 16 Bit passen. Sein Nachfolger Thumb-2 (2003) hat dieses Problem jedoch durch Verwendung eines speziellen Befehls überwunden, der keine andere Wirkung hat als die Bereitstellung Prädikate für die folgenden vier Anweisungen. Der in ARMv8-A (2011) eingeführte 64-Bit-Befehlssatz ersetzte die bedingte Ausführung durch bedingte Auswahlbefehle.

Einige SIMD-Befehlssätze wie AVX2 können mithilfe einer logischen Maske Werte bedingt in den Speicher laden / speichern, eine parallele Form der bedingten Verschiebung. Diese Form der Prädikation wird auch beim GPU-Computing mit einem Befehl und mehreren Threads verwendet, bei dem ein Computerkern den Code eines Zweigs mit nicht erfüllter Bedingung ausführt, die in diesem Ausführungspfad berechneten Ergebnisse jedoch nicht festschreibt.

Siehe auch[edit]

Verweise[edit]

  1. ^ ein b c d Rick Vinyard (26.04.2000). “Prädikation”. cs.nmsu.edu. Abgerufen 2014-04-22.
  2. ^ Mahlke, Scott A.; Hank, Richard E.; McCormick, James E.; August, David I.; Hwn, Wen-mei W. (22.-24. Juni 1995). “Ein Vergleich der vollständigen und teilweisen Unterstützung der vorausgesagten Ausführung für ILP-Prozessoren”. Das 22. Internationale Symposium für Computerarchitektur.
  3. ^ ein b Joseph A. Fischer, Paolo Faraboschi, Cliff Young (2004) Embedded Computing – Ein VLIW-Ansatz für Architektur, Compiler und Tools. Seite 172.
  4. ^ Cordes, Peter. “Assembly – Wie funktioniert die Ausführung außerhalb der Reihenfolge mit bedingten Anweisungen, Beispiel: CMOVcc in Intel oder ADDNE (Add ungleich) in ARM”. Paketüberfluss. Anders als bei Kontrollabhängigkeiten (Verzweigungen) sagen sie nicht voraus oder spekulieren nicht, wie die Flags aussehen werden. Daher kann ein cmovcc anstelle eines jcc eine schleifenübertragene Abhängigkeitskette erstellen und am Ende schlechter sein als ein vorhersagbarer Zweig. [1] ist ein Beispiel dafür.

Weiterführende Literatur[edit]

after-content-x4