Die Darstellungen in unserem Beitrag Grundlagen der RISC-Architektur und Klassifizierungssysteme für Prozessoren beruhen im Wesentlichen auf einer Abstimmung zwischen dem Befehlssatz, den notwendigen Adressierungsarten, dem Registersatz einschließlich der Special-Purpose-Register sowie der Pipeline-Grundstruktur. Letztere spielt insofern eine Rolle, weil die Beschränkung auf vier Pipeline-Stufen die Zusammenfassung von Execute und Memory Access bedeutet. Eine 5-stufige Pipeline mit den Phasen Fetch, Decode/Load, Execute, Memory Access und Write back böte beispielsweise die Möglichkeit zu erweiterten Adressberechnungen (indizierte Adressierung) in der Execute-Phase. Dies muss aus Zeitgründen im Rahmen der 4-stufigen Pipeline entfallen.
Die Grundstruktur der RISC-Pipeline ist in Bild dargestellt. Eine Instruktion, die durch die Fetch-/Predecode-Unit geladen wird, durchläuft diese Pipeline in vier aufeinander folgenden Takten. Die jeweils durchlaufene Pipeline-Stufe bearbeitet im nächsten Takt bereits den nächsten Befehl. Dieses Grundprinzip bedeutet eine mögliche Beschleunigung um den Faktor vier.
Das Bild zeigt ebenfalls die übrigen Einheiten der Modell-CPU MPM3 in der Basisversion. Diese Einheiten haben teilweise reinen Support-Charakter (wie etwa die Takterzeugung), wirken teilweise jedoch auch Pipeline-übergreifend (Bus Interface Unit, Register File) und sind dadurch besonders zu betrachten.
Daten-Hazards
Bei der Ausführung von Programmen kommt es aber niemals zu einer Beschleunigung um den Faktor vier gegenüber einer Version ohne Phasen-Pipelining. In der Praxis treten immer wieder Störungen (Hazards) auf. Diese Hazards lassen sich in drei Kategorien einteilen: Kontrollfluss-, Daten- und strukturelle Hazards
Der in folgendem Bild dargestellte Codeabschnitt, in der Assembler-Sprache von MPM3 verfasst, zeigt Datenabhängigkeiten zwischen unmittelbar aufeinander folgenden Befehlen. In dieser Sequenz tritt zweifach der Fall auf, dass die Decode-/Load-Phase einer Instruktion Daten benötigt, die am Ende der Write-back-Phase der vorangegangenen Instruktion erst mit Sicherheit in den Registern stehen. Eine Pipeline, die auf diese Abhängigkeiten keine Rücksicht nimmt, würde falsche Ergebnisse liefern.
Das falsche Ergebnis verhindert man am einfachsten, indem man den Ablauf in der Pipeline so lange stoppt, bis die korrekten Inhalte vorliegen. Die weiter unten beschriebenen alternativen Maßnahmen erschweren das Design einer CPU erheblich. Das Stoppen des Ablaufs in der Pipeline erfolgt durch Einfügen von Verzögerungen, meist als Bubble (Blase) oder Injected Instruction bezeichnet.
Im Fall des Beispielprogramms ergibt dies das im unteren Bild dargestellte Verhalten. Die Performance des Prozessors leidet unter der Injected Instruction erheblich. Im Beispiel verlängert sie den Ablauf von theoretisch drei Zyklen für die drei Befehle auf sieben Zyklen (0,43 Instruktionen/Takt, IPC, Instructions per Cycle).
Read-after-Write-Hazard
Eine Analyse der möglichen Ursachen für diese Form von Daten-Hazards ergibt für die RISC-Architekturen den so genannten Read-after-Write-Hazard (RAW). Er tritt in dem ursprünglichen Assembler-Programm nicht auf, da hier von einer zeitlich sequenziellen Folge ausgegangen wird. Durch das Pipelining macht er sich im realen Programmablauf aber massiv bemerkbar. Dieser RAW-Hazard tritt auch bei der superskalaren CPU als einziger nicht behebbarer Hazard in Erscheinung.
Bei Pipelining-CPUs (RISC) existieren außer dem Einbau von Wartezyklen in der Pipeline zwei weitere Varianten zur Vermeidung des Leistungsverlusts:
Der Assembler-Programmierer oder der Compiler verhindert durch eine Analyse des Codes, dass es überhaupt zu Read-after-Write-Hazards mit ihren Verzögerungen kommt. Dies ist durch eine geschickte Umsortierung der Befehle fast immer möglich.
In die CPU wird zusätzliche Hardware integriert, die die Auswirkungen minimiert. In diesem Fall kann man auf ein Anhalten der Pipeline verzichten.
Durch eine zusätzliche Data Forwarding Unit, die neben den bisher vorhandenen Einheiten innerhalb der Mikroarchitektur eingefügt wird, lassen sich die Auswirkungen eines RAW-Hazards mildern oder sogar ganz beseitigen. Damit muss die Execute-Pipeline-Stufe nicht auf das Schreiben in ein Register warten, sondern kann das am Ausgang der ALU vorhandene Ergebnis direkt nutzen.
Das Bild zeigt das für die vierstufige Pipeline der MPM3-Modell-CPU. In diesem Fall lässt sich der negative Einfluss von Datenabhängigkeiten im Programm nahezu gänzlich vermeiden, was für Prozessoren mit hoher Anzahl von Pipeline-Stufen nicht mehr gilt. Die einzige unvermeidbare Ausnahme sind Registerinhalte, die ein Sprungbefehl (Jump registerindirekt) benötigt. Da der Sprung in der Fetch-Unit zu einem neuen Program-Counter-Wert führt, erreicht der Datenwert diese Einheit zwei Takte zu spät, falls der vorangegangene Befehl den Wert noch berechnet.
Der Aufwand für das Data Forwarding erscheint relativ gering. In der Praxis nimmt das jedoch einen erheblichen Anteil des Mikroprozessorkerns in Anspruch, da der Kern in einem komplexen Regelwerk detektieren muss, ob er die Register-inhalte oder einen Wert aus dem Forwarding nutzen kann. Dennoch wird dieses Verfahren bei allen gängigen Prozessoren eingesetzt, weil die Performance-Verbesserung erheblich ist.
Strukturelle Hazards
Ein vollkommen anderer Konflikt entsteht, wenn zwei Einheiten in der Pipeline zeitgleich eine dritte nutzen müssen, um ihre Aufgabe zu erfüllen. Ein Beispiel ist die Bus Interface Unit: In der Pipeline existieren zwei Einheiten (Fetch und Execute), die diese gegebenenfalls gleichzeitig nutzen wollen. Diese Form von Störung wird struktureller Hazard genannt.
Der Speicherzugriff ist wirklich konkurrierend: In jedem Takt wird gemäß Pipeline-Ablaufstruktur ein Fetch (Laden einer kodierten Instruktion) durchgeführt. Der Zugriff auf den Datenspeicher ist zwar seltener, führt jedoch garantiert zu einem Konflikt.
Dieses Problem ist sehr ernst zu nehmen und tritt bei Spezialprozessoren wie DSPs (Digitalen Signalprozessoren) noch wesentlich verschärfter auf. Dort sind häufig Algorithmen (zum Beispiel Filterfunktionen, Echounterdrückung et cetera) mit sehr hohem Datenaufkommen implementiert.
Das Einfügung der beiden (bei DSPs drei oder vier) gewünschten Speicherzugriffe in eine zeitliche Sequenz innerhalb eines Takts scheidet aus, weil Speicherzugriffe zu den langsamsten Aktionen im Instruktionsablauf gehören. Wie in weiter führenden Artikeln noch zu lesen sein wird, ist es lediglich über Speicherhierarchien möglich, mit ungebremster Geschwindigkeit im Speicher zu arbeiten. Eine zeitliche Sequenz mehrerer Zugriffe pro Takt würde den Takt selbst stark limitieren.
Um dennoch Auswirkungen dieses strukturellen Hazards zu verhindern oder wenigstens zu mindern, sind RISC-Architekturen mit einer möglichst großen Anzahl von Registern ausgestattet, um externe Speicherzugriffe zu minimieren. Das Prinzip beruht darauf, lokale Variablen möglichst lange im Register zu halten. Alle Rechenoperationen wie Addition oder logische Verknüpfungen sind auf Registern als Operanden definiert, der Speicherzugriff erfolgt ausschließlich via Load- und Store-Befehlen (LD, ST, PUSH, POP).
Dieses Verfahren minimiert zumindest die Anzahl der Zugriffe. Weiter führende Architekturen (SPARC, Intel IA-64) nutzen sehr große Register Files, auch um Übergabewerte (Aufrufparameter) für Unterprogramme abzulegen (globale und lokale Registerfenster). Dies spart das umständliche Kopieren der Registerinhalte auf den Stack.
Harvard-Architektur
Die Harvard-Architektur bietet einen aufwendigen, jedoch perfekten Ausweg bei strukturellen Hazards. Das Bild zeigt die ursprüngliche Definition mit getrennten Adressräumen für Instruktionen und Daten. Diese Definition wurde so gewählt, um Konflikte bei Instruktions- und Datenzugriffen auszuschließen. Die modifizierte Variante hingegen kennt lediglich einen Adressraum, allerdings zwei (oder mehrere) Zugriffswege. Man spricht auf den Speicher bezogen auch von Multiporting.
Die modifizierte Harvard-Architektur kommt heute meist auf Cache-Speicher-Ebene im Level-1-Cache zum Einsatz, nicht jedoch auf Hauptspeicherebene. Die Gründe dafür sind einfach: Die Kosten für externes Multiporting sind sehr hoch, darüber hinaus ist der Hauptspeicher in der Regel so langsam, dass der Prozessor ohnehin schon Wartezyklen einfügen muss und damit ein Multiporting sinnlos ist.
Auf L1-Cache-Ebene hingegen finden alle Zugriffe in einem Takt statt, der Cache ist mittlerweile fast schon integraler Bestandteil des Prozessorkerns. Hier wirkt sich Multiporting sehr beschleunigend aus. Für DSPs wird ausschließlich Multiporting genutzt, da deren immense Datenmengen jeden Register File (Variante 1) überfordern würden.
Weitere strukturelle Hazards
Ein weiterer struktureller Hazard tritt auf, wenn die Folgen eines Kontrollfluss-Hazards in der Pipeline gemindert werden sollen. Dies wird im nachfolgenden Abschnitt besprochen.
Kontrollfluss-Hazards
Die dritte Störungsart bei der Ausführung von Programmen in Prozessoren mit Pipelining wird als Kontrollfluss-Hazards bezeichnet. Diese Art ist die aktuell wichtigste, da sich Datenabhängigkeiten sowie strukturelle Hazards im Wesentlichen auflösen oder entscheidend mildern lassen.
Kontrollfluss-Hazards entstehen an den Stellen im Programm, an denen der Kontrollfluss (der Programmverlauf) von der üblichen Sequenz abweicht. Hierfür muss ein Sprungbefehl (unkonditionierter oder bedingter Sprung) wie JMP (jump), BNE (branch if not equal) oder ein Unterprogrammaufruf wie CALL und RET (return) im Programmcode vorliegen. Diese Störungen kommen zum Leidwesen der Entwickler recht häufig vor. Man geht aktuell davon aus, dass alle vier bis fünf Befehle ein Kontrollflussbefehl auftritt, in der überwiegenden Anzahl der Fälle ein bedingter Verzweigungsbefehl (conditional branch).
Zwei vorrangige Probleme entstehen bei der Ausführung eines Kontrollflussbefehls. Zum einen muss der Prozessor die neue PC-Adresse berechnen, zum anderen ist die Sprungrichtung bei den bedingten Befehlen meist unbekannt und von der Ausführung des direkten Vorgängerbefehls abhängig.
Berechnung der Sprungadresse
Die Komplexität der Ermittlung der neuen PC-Adresse hängt von der verwendeten Adressierungsart ab. Die Angabe einer absoluten Sprungadresse (kodiert als vollständige Adresse) entfällt meist bei RISC-Architekturen, da sie nicht genügend Kodierungsplatz im Befehlsformat bieten (siehe Grundlagen der RISC-Architektur). Jedes andere Format benötigt hingegen Zusatzinformationen sowie Rechenkapazität oder zusätzliche Hardware im Prozessor:
Die verkürzte absolute Adressierung (absolut short, im MPM3 nicht implementiert) speichert nur einen Teil der Adresse (die niederwertigen k-Bits), die höherwertigen Bits des PCs bleiben erhalten. Dieses Adressierungsformat benötigt die geringste Rechenkapazität und ist im Rahmen der Fetch-/Predecode-Phase direkt ausführbar. Nachteilig ist, dass auf diese Weise nur ein Teil des Adressraums erreichbar ist.
Die indirekte Adressierung (registerindirekt) legt die neue PC-Adresse zuvor in einem Register ab und überträgt sie beim Sprung in den PC. Hier ist keine Rechenkapazität erforderlich, aber eventuell ein Data Forwarding (Weg von Execute- in Fetch-Einheit). Dieses Forwarding kann im Fall des MPM3 die Anzahl der Wartezyklen auf eins begrenzen.
Bei relativer Adressierung (PC-relative), die für bedingte Verzweigungen sehr beliebt ist, muss der Prozessor die neue PC-Adresse durch vorzeichenbehaftete Addition des Program Counters und des Offsets berechnen. Dies könnte im Programmablauf bereits in der Phase 2 (eigentlich Decode/Load) geschehen, benötigt aber die ALU, die zu diesem Zeitpunkt mit dem Vorläuferbefehl befasst ist (struktureller Hazard). Aus diesem Grund muss man bei relativer Adressierung ohne weitere Maßnahmen mit zwei Wartezyklen rechnen, bevor das Ergebnis vorliegt.
Das relative Adressierungsformat ist sehr beliebt, da es sehr kompakt ist und durch den ortsunabhängigen Offset im Gegensatz zum verkürzten absoluten Format an jeder Stelle unter gleichen Voraussetzungen einsetzbar ist. Die Programmlokalität erlaubt eine häufige Nutzung auch bei eingeschränktem Versatz (+127/-128 Programmadressen bei 8-Bit-Offset). Konsequenterweise versuchen Prozessorarchitekturen gerade die Ausführung dieser Adressierung mit möglichst geringer Verzögerung auszuführen.
Um die Adressrechnung vorzuziehen, nutzen sie zur Auflösung des strukturellen Hazards eine extra Addierereinheit (Look-ahead Resolution). Dieses Verfahren verkürzt die Anzahl der Wartezyklen (im Rahmen der vierstufigen Pipeline) auf eins, so dass jeder Branch-Befehl in der MPM3-Architektur in zwei Zyklen ausführbar ist.
Weiterentwicklung der Verzweigungsbefehle
Die Häufigkeit von Verzweigungsbefehlen lässt es als sinnvoll erscheinen, weitere Maßnahmen zur Reduktion auf einen Ausführungstakt (0 Wartezyklen) zu ergreifen. Die Motivation ist einfach: Allein durch die 20-prozentige Häufigkeit der Verzweigungsbefehle mit einem Wartezyklus reduziert sich die theoretische Befehlsrate von 1 IPC (Instruction per Clock) auf 0,83 IPC (6 Takte für 5 Befehle). Die Maßnahmen gliedern sich in zwei Kategorien: die Definition neuer Branch-Befehle ohne Wartezyklen und die Einführung einer Verzweigungsvorhersage.
Die so genannten Delayed-Branch-Befehle führen die Verzweigung erst nach dem unmittelbar nachfolgenden Befehl aus. Dieser steht im Delay-Slot und muss also in jedem Fall ausführbar sein, weil er sowohl im verzweigenden als auch im nicht verzweigenden Fall zur Ausführung kommt.
Diesen Delay-Slot kann in jedem Fall ein NOP-Befehl (No Operation) belegen, wodurch allerdings kein Vorteil für die Ausführungsgeschwindigkeit entsteht. Meistens ist die Verwendung der Befehle im Delay-Slot auch eingeschränkt, beispielsweise dürfen dort keine weiteren Branch-Befehle stehen.
Die Delayed-Branch-Befehle führen zu unleserlichem Assembler-Code, weil der Mensch bei der Interpretation des Codes auch den nachfolgenden Befehl hinzurechnen muss. Die automatische Generierung eines nicht trivialen Befehls im Delay-Slot durch einen Compiler erweist sich meist ebenfalls als schwierig. Da zudem die Delayed-Branch-Befehle für superskalare Prozessoren keinen Vorteil bringen, ist diese Technik wenig verbreitet.
Eine Variation der Branch-Befehle mit Delay-Slot sind die Branch-Likely-Befehle mit Delay-Slot. Sie arbeiten prinzipiell ähnlich, auch hier wird die nachfolgende Instruktion ausgeführt. Diese Ausführung beendet der Prozessor jedoch nur, wenn die Verzweigung wirklich durchgeführt wird. Im Fall der Nichtverzweigung mutiert der Befehl im Delay-Slot nachträglich zum NOP-Befehl und schreibt keine Ergebnisse.
Die Branch-Likely-Befehle zielen vor allem auf Schleifen, und zwar auf die Verzweigung am Ende. Diese wird gewöhnlich häufig durchlaufen, und nur einmal - am Ende der Ausführung der Schleife - nicht ausgeführt. Wie das Codebeispiel zeigt, ist in diesem Fall die automatische Besetzung des Delay-Slots mit einem nicht trivialen Befehl immer möglich, so dass die Branch-Likely-Befehle relevante Leistungssteigerungen ergeben. Die Bemerkung zum Einsatz in superskalaren Prozessoren gilt allerdings auch hier.
Verzweigungs-Vorhersage
Die Einführung und Verwendung von Branch-Befehlen mit Delay-Slot stellt im Allgemeinen keine befriedigende Lösung dar, insbesondere im Hinblick auf superskalare Mikroprozessoren. Aus diesem Grund hat man schon frühzeitig eine Verzweigungsvorhersage (Branch Prediction) entwickelt. Deren Ziel ist es, mit hoher (statistischer) Wahrscheinlichkeit den Verlauf des Programms bei einem Sprung vorherzubestimmen.
Die Verzweigungsvorhersage stützt sich entweder auf Annahmen über den Programmverlauf (statische Sprungvorhersage) oder auf Rückschlüsse aus dem bisherigen Verlauf (dynamische Sprungvorhersage).
Über alle Sprung- und Verzweigungsbefehle (auch die unkonditionierten) gemittelt verzweigen etwa zwei Drittel aller Fälle, während ein Drittel den Kontrollfluss nicht ändert. Rückwärtssprünge stammen zudem häufig aus Schleifen (Loop) und verzweigen nahezu immer. Vorwärtssprünge stammen meistens aus bedingten Kontrollstrukturen mit einer Gleichverteilung der Sprungwahrscheinlichkeiten ("Branch taken"/"Branch not taken").
Eine statische Sprungvorhersage (Static Branch Prediction) nimmt daher im einfachsten Fall an, dass sich der Kontrollfluss nicht ändert. Der Prozessor führt die nachfolgenden Befehle aus, speichert die Ergebnisse jedoch erst, wenn sicher ist, dass die Verzweigung nicht eingetreten ist. Im anderen Fall deklariert er alle Operationen nachträglich als "No Operation" und verwirft die Ergebnisse. Dies führt im Fall der vierstufigen Pipeline (MPM3) zu einem Mittel von 1,67 CPI (Clocks per Instruction) oder einem IPC von 0,6 pro Verzweigungsbefehl.
Eine erweiterte statische Sprungvorhersage nimmt für Vorwärtssprünge ein "Branch not taken" (keine Kontrollflussänderung), für Rückwärtssprünge hingegen ein "Branch taken" an. Dies bedeutet jedoch, dass der Prozessor das Sprungziel in einem Branch Target Buffer oder Branch Target Cache speichern muss, da die Look-ahead Resolution einen Takt zur Adressberechnung benötigt. Daher wird die erste Rückwärtsverzweigung meist verzögert ausgeführt und das Sprungziel für weitere Durchläufe gespeichert.
Dynamische Sprungvorhersage
Eine dynamische Sprungvorhersage (Dynamic Branch Prediction) und ein interner Speicher für die letzten Sprungziele (Branch Target Cache) ermöglicht eine weitere Verringerung der mittleren Wartezeit durch Kontrollfluss-Hazards. Die Sprungvorhersage wird häufig in Form eines Zustandsautomaten (1- oder k-Bit Vorhersageautomat, k-Bit Predictor) realisiert. Die folgenden Bilder zeigen diesen als 1- und 2-Bit-saturierenden Zähler mit den Zuständen "Taken / Not taken" und "Strongly Taken / Weakly taken / Weakly not taken / Strongly not taken".
Die Anzahl der Vorhersageautomaten und der Einträge im Branch Target Cache bestimmt die Anzahl der möglichen optimierten Verzweigungen. Um also mehrere Sprünge in einem Bereich, etwa eine Schleife, berücksichtigen und vorhersagen zu können, werden mehrere dieser Automaten benötigt. Die Unterscheidung zwischen den einzelnen Verzweigungen im Programmkontext erfolgt dann meist über die niederwertigen Bits der Programmadresse (Beispiel: untere 10 Bit bei 1024 Sprungvorhersageautomaten mit Branch Target Cache).
(m,n)-korrelationsbasierter Vorhersageautomat
Wechselwirkungen zwischen den einzelnen Sprüngen und Muster in dem Sprungverhalten (= Wechselwirkung mit sich selbst) berücksichtigt der bislang vorgestellte Automat jedoch nicht. In der Praxis treten diese allerdings häufig auf. Deshalb hat man als Weiterentwicklung die korrelationsbasierten Vorhersagen (Correlation-based Predictors) eingeführt.
Ein (m,n)-korrelationsbasierter Vorhersageautomat besteht aus 2m Vorhersageautomaten für jeweils eine Verzweigung, und jeder dieser Vorhersageautomaten ist wiederum als n-Bit-Vorhersageautomat aufgebaut. Ein Branch History Register (BHR) speichert das globale Verhalten der m letzten Verzweigungen in Form eines m-bit-Shift-Registers. Die entstehenden 2m Muster dienen als Index in der Pattern History Table (PHT), dem Array der 2m Vorhersageautomaten mit typischerweise 2-Bit-Auflösung. Um die getroffene Vorhersage für verschiedene Verzweigungen im Programm nutzen zu können, existieren in der Regel eine ganze Reihe derartiger (m,n)-korrelationsbasierter Vorhersageautomaten pro Prozessor (typischerweise 1024, jeder Verzweigung wird dann anhand der unteren zehn Adressbits ein Automat zugewiesen, und zu jedem Eintrag gehört ein Branch-Target-Cache-Eintrag). Zu dem korrelationsbasierten Vorhersageautomaten existieren eine Reihe von ähnlichen Varianten [siehe Silc, J.; Robic, B.; Ungerer, T.: Processor Architecture - Berlin, Heidelberg, New York: Springer, 1999].
Unterprogrammsprünge und Ausnahmebehandlung bei Pipelining
Die Ausnahmebehandlung (Exception Handling) wie auch die Unterstützung bei externen Unterbrechungen (Interrupt Requests) müssen ebenso wie Unterprogrammaufrufe in das Pipeline-System eingebunden werden. Beide Aktionen sind aber - der Natur der Sache entsprechend - in gewissem Sinn "Pipeline-feindlich". Daher bedarf es hier besonderer Aufmerksamkeit.
Das MPM2-Modell als Beispiel für CISC-Architekturen zeigt eine erhebliche Busaktivität beim Aufrufen von Unterprogrammen (CALL-Befehl) sowie beim Eintritt in die Interrupt Service Routine. Der Grund hierfür liegt in der Sicherung der Rücksprungadresse und - bei Interrupt Request - des Statusregisters auf dem Stack. Auch die Rückkehr aus den angesprungenen Routinen über RTS beziehungsweise RTI erzeugt erhebliche lesende Aktivitäten am Bus.
Der MPM3, als Prototyp für einen Prozessor mit Phasen-Pipelining, muss diesen Bustransfer verhindern, um den Nachschub an neuen Instruktionen nicht zu blockieren. Dazu dienen die Link-Register für Status und Adresse (R10/R11), in denen der Prozessor bei einer CALL-Instruktion und bei dem Aufruf einer Interrupt Service Routine die entsprechenden Register sichert. Beim Rücksprung werden die Prozessor-Register (Status und Programmzähler) mit dem Inhalt dieser Register zurückgeschrieben. Diese Operationen benötigen daher keinen externen Speicherzugriff und belasten dadurch nicht den Bus.
Dieses Verfahren erscheint zunächst unvollständig, da ein zweiter rekursiver Aufruf den Inhalt der Link-Register überschreiben würde. Deshalb ist die Sicherung der Registerinhalte die Aufgabe des Programmierers. Falls er eine weitere Funktion aufruft oder den Interrupt während der Interrupt Service Routine wieder freigibt, muss er vorab mit Hilfe der PUSH-Instruktionen die Register auf den Stack retten. Bei sorgfältiger Programmierung kann er so eine Datenzerstörung etwa durch IRQs sicher verhindern.
Interrupt Request
Bei der Behandlung von Ausnahmesituationen - der Interrupt Request gehört in diese Kategorie - muss ferner ein jederzeit deterministischer Zustand des Prozessors gewährleistet sein. Dies ist für Architekturen ohne Pipelining kein Problem. Die Ausnahme kann erst nach vollständiger Beendigung eines Befehls durch eine besondere Instruktion in die Bearbeitung eintreten. Hierdurch ist ein deterministischer Zustand jederzeit gesichert.
Der MPM3 muss jedoch den Start der Ausnahmebehandlung in die Pipeline einfügen, während sich noch andere Befehle in der Ausführung befinden. Dies kann unter Umständen zu einem Konflikt führen. So ist der Interrupt-Request-Vektor, also die Startadresse der zugehörigen Service-Routine, aus Performance-Gründen in einem Register (R12) abgelegt. Das Programm darf ihn deshalb nicht unmittelbar vor einem IRQ verändern. Geschieht dies dennoch, muss der MPM3 diesen Schreibvorgang bei der Bearbeitung des IRQ berücksichtigen (RAW-Hazard). Gleiches gilt für einen SEI-Befehl: Liegt dieser vor dem IRQ-Aufruf in der Pipeline, ist jedoch noch nicht in Bearbeitung, so muss der MPM3 den Aufruf der Service-Routine nachträglich annullieren.
Eine fallende Flanke am IRQ-Eingang des MPM3 kann jederzeit einen Interrupt Request anfordern. Um einen deterministischen Zustand sicherzustellen, leert der MPM3 bei einem Interrupt Request und dem Vorliegen eines gelöschten Interrupt Disable Flags die Pipeline. Hierzu fügt er drei Pipeline Stalls ein. Ist am Ende dieser drei Wartezyklen das Interrupt Flag immer noch gelöscht, springt er in die Service-Routine. Ansonsten muss die Behandlung des Interrupts wieder von vorne beginnen und erneut drei Wartezyklen einfügen.
Beispielprogramme zur Bestimmung des CPI beim MPM3
Die hier aufgeführten Beispielprogramme für das MPM3 dienen ausschließlich als Testprogramme zur Bestimmung der Performance.
INIT_ARR.ASM: Dieses Programm initialisiert ein eindimensionales Integer-Array mit 0. Der zulässige Wertebereich des Index ist 0 ... 255.
MOV_AVRG.ASM: Für die insgesamt 64 Elemente eines eindimensionalen Integer-Arrays wird für jeweils vier Elemente ein Mittelwert berechnet. Anschließend verschiebt das Programm den Startpunkt jeweils um ein Element. Insgesamt entstehen so 61 Mittelwerte in einem zweiten Array.
PARITY.ASM: Dieses Programm bestimmt die gerade Parität aller Bitmuster (für 8 Bit) und gibt sie mit dem originalen Byte als Bit 8 am Outputport aus.
WORDCOUN.ASM: Dieses Programm entspricht der inneren Routine von Wordcount, wie es als Tool für Unix-Betriebssysteme bekannt ist. Es zählt Character, Wörter und Zeilen in dem Text, der als Programmkonstante im Assembler-Code angefügt ist. Durch die stark zergliederte Programmstruktur nutzt WORDCOUN.ASM zahlreiche Branch-Befehle. Ziel dieses Tests ist es, die Rückwirkungen der Sprünge auf das CPI zu bestimmen.
CRC-8.ASM: Dieses Programm berechnet Checksummen, wie sie etwa im Header der ATM-Zellen vorkommen. Hierin befinden sich drei Abschnitte:
Der erste Abschnitt füllt die Syndromtabelle auf. Diese Tabelle dient der schnellen Berechnung der CRC-8-Checksumme für 4-Byte-Header (diese CRC wird als fünftes Byte angefügt). Der zweite Teil besteht in der Generierung der Fehlertabelle. Die 256 Einträge hier lassen eine Bestimmung des zu korrigierenden Fehlers im Header (5 Byte, also einschließlich CRC-8) zu. Der dritte Teil testet dann einen korrekten Zell-Header, 40 Header mit korrigierbarem 1-Bit-Fehler sowie 40 unkorrigierbare, aber detektierbare Header.
SEL_SORT.ASM: Das Programm testet das bekannte Sortierverfahren Selection Sort an zwei Arrays mit je 100 Elementen.
QUICKSRT.ASM: Dieser Code testet das bekannte Sortierverfahren Quicksort an zwei Arrays mit je 100 Elementen.
Performance-Werte
Die folgenden Tabellen liefern einige Aussagen zur Performance. Die Werte für NoPipe (ohne Pipelining), Safe (Pipelining, Waitstates werden bereits bei der Möglichkeit einer Datenabhängigkeit eingefügt) und Data Forwarding (Datenabhängigkeiten werden entsprechend aufgelöst) stammen aus einem Instruktionssatzsimulator. Die Version mit Branch Target Cache (BTC) beinhaltet auch noch eine Look-ahead-Resolution und wurde als VHDL-Modell simuliert. Deutlich sichtbar sind die Geschwindigkeitsgewinne in Richtung der theoretischen Performance-Grenze von 1 Instruktion/Takt (IPC) insbesondere für das Harvard-Modell mit Multiporting und Branch Target Cache.
Programm | # Instr. | NoPipe #Clocks /CPI | Safe #Clocks /CPI | Data F. #Clocks /CPI | BTC #Clocks / CPI |
|---|---|---|---|---|---|
| |||||
INIT_ARR | 1030 | 4120 / 4,0 | 2310 / 2,24 | 1541 / 1,50 | 1287 / 1,25 |
MOV_AVRG | 1114 | 4456 / 4.0 | 2470 / 2,22 | 1422 / 1.28 | 1363 / 1.22 |
PARITY | 13317 | 53268 / 4.0 | 25861 / 1,94 | 17925 / 1,34 | 15365 / 1,15 |
WORDCOUN | 23974 | 95896 / 4.0 | 49610 / 2,07 | 33953 / 1,42 | 26880 / 1,12 |
CRC-8 (1. Tab) | 17172 | 68688 / 4.0 | 33821 / 1,97 | 22809 / 1,32 | 20249 / 1,18 |
CRC-8 (2. Tab) | 4141 | 16564 / 4.0 | 8542 / 2,06 | 5550 / 1,34 | 4999 / 1,21 |
CRC-8 (run) | 16981 | 67924 / 4.0 | 32880 / 1,94 | 21881 / 1,29 | 20962 / 1,23 |
SEL_SORT | 114379 | 457516 / 4.0 | 250139 / 2,19 | 155999 / 1,36 | 145673 / 1,27 |
QUICKSRT | 24808 | 99232 / 4.0 | 56804 / 2,29 | 35819 / 1,44 | 33812 / 1,36 |
Mean (Sum) | 216916 | 867664 / 4.0 | 462437 / 2,13 | 296899 / 1,37 | 270590 / 1,25 |
Programm | # Instr. | NoPipe #Clocks / CPI | Safe #Clocks / CPI | Data F. #Clocks / CPI | BTC #Clocks / CPI |
|---|---|---|---|---|---|
| |||||
INIT_ARR | 1030 | 4120 / 4,0 | 2054 / 2,00 | 1285 / 1,25 | 1032 / 1,00 |
MOV_AVRG | 1114 | 4456 / 4.0 | 2223 / 2,00 | 1175 / 1,05 | 1116 / 1,00 |
PARITY | 13317 | 53268 / 4.0 | 25605 / 1,92 | 17669 / 1,33 | 15108 / 1,13 |
WORDCOUN | 23974 | 95896 / 4.0 | 47709 / 1,99 | 32052 / 1,33 | 24978 / 1,04 |
CRC-8 (1. Tab) | 17172 | 68688 / 4.0 | 33562 / 1,95 | 22550 / 1,31 | 19991 / 1,16 |
CRC-8 (2. Tab) | 4141 | 16564 / 4.0 | 8115 / 1,96 | 5123 / 1,24 | 4605 / 1,11 |
CRC-8 (run) | 16981 | 67924 / 4.0 | 30519 / 1,80 | 19520 / 1,15 | 18683 / 1,10 |
SEL_SORT | 114379 | 457516 / 4.0 | 228727 / 2,00 | 134587 / 1,18 | 124262 / 1,09 |
QUICKSRT | 24808 | 99232 / 4.0 | 49177 / 1,98 | 28591 / 1,15 | 27048 / 1,09 |
Mean (Sum) | 216916 | 867664 / 4.0 | 427691 / 1,97 | 262552 / 1,21 | 236823 / 1,09 |
Wechselwirkungen zwischen Technologie und Architektur
In den ersten Jahrzehnten der Halbleiterentwicklung galten Technologie und Architektur der Bausteine als weit gehend unabhängig voneinander. Mittlerweile ist diese Trennung aufgehoben, und Technologie sowie Architektur beeinflussen sich gegenseitig. Diese Effekte lassen sich allerdings selten quantifizieren.
Für das Pipelining einer RISC-CPU (und für superskalare CPUs) existiert jedoch ein Modell, das zu quantitativen Aussagen führt. Ideal wäre es, die Strukturbreite mit der optimalen Anzahl der Pipeline-Stufen verbinden zu können. Dies ist zurzeit unerreichbar, dennoch sind die Aussagen des Modells sehr interessant.
Nach [Märtin, C. (Hrsg.): Rechnerarchitekturen - CPUs, Systeme, Software-Schnittstellen - 2. Auflage - München, Wien: Carl Hanser Verlag, 2000] wird für eine CPU eine (konstante) Bearbeitungszeit T pro Instruktion angenommen. Die Unterteilung in eine Anzahl von S Schritten (Phasen-Pipelining) liefert in erster Näherung eine verringerte Bearbeitungszeit T/S. Dies ergäbe für die Bearbeitungszeit ein Optimum bei möglichst hoher Anzahl von Pipeline-Stufen, allerdings wirken zwei Effekte dieser linearen Erhöhung entgegen: Im Programmfluss treten bedingte Sprungbefehle mit unbekannter Sprungrichtung und unbekanntem Sprungziel auf, so dass der aktuelle Instruktionsfluss an dieser Stelle häufig nur angenommen werden kann. Dies führt zu Fehlvorhersagen mit einem daraus resultierenden Zeitverlust.
Optimale Anzahl an Stufen
Zur Quantifizierung dieses Effekts wird in diesem Modell angenommen, dass über alle Instruktionen gemittelt eine fehlerhafte Vorhersage des Programmflusses mit einer Wahrscheinlichkeit b vorliegt und die falsche Annahme in jedem Fall zu einem Verlust von S-k (k = 1, 2, ...S) Takten führt. Hierdurch vergrößert sich die durchschnittliche Anzahl der Takte pro Instruktion (CPI, Clocks per Instruction) von theoretisch 1 auf
Der andere Effekt blieb bislang unbeachtet und tritt durch die innere Struktur eines Prozessors mit Pipelining auf. Die einzelnen Stufen werden durch Registersätze (Flipflops) voneinander getrennt. Diese Register speichern die Daten zwischen den Pipeline-Stufen, und hieraus resultiert ein zusätzlicher Zeitbedarf C (Setup- und Hold-Time der Register). Quantitativ wird damit die effektive Zeit pro Pipelining-Stufe durch
beschrieben, da zwischen S Pipeline-Stufen die Daten (S-1)fach gespeichert werden. Dadurch ist die gesamte Zeit pro Instruktion (TPI) durch
bestimmt. Die Invertierung hiervon, also die Instruktionsrate pro Zeiteinheit, wird als Pipeline-Durchsatz G bezeichnet:
In diesem Modell sind nunmehr die Kontrollfluss-Hazards durch b wie die (Silizium-) Technologie durch C/T sowie T selbst berücksichtigt. Leitet man G nach S ab, so erhält man
Für die optimale Anzahl der Pipelining-Stufen S(opt) folgt daraus die Formel:
Die Gleichung zeigt, dass man die Speicherzeit zwischen zwei Pipeline-Stufen in jedem Fall berücksichtigen muss: C = 0 bedeutet, dass kein Speicher vorhanden ist oder berücksichtigt werden muss. In diesem Fall wäre die optimale Anzahl der Pipeline-Stufen nach unendlich strebend, was der Beobachtung widerspricht.
Abhängigkeiten des Pipeline-Durchsatzes
Um die Abhängigkeiten des Pipeline-Durchsatzes von den wesentlichen Parametern b und C/T darstellen zu können, lässt man einen dieser Parameter konstant und nutzt den anderen als Parameter der entstehenden Kurvenschar.
Oben stehendes Bild zeigt die Abhängigkeit des Pipeline-Durchsatzes für einen RISC-Prozessor gemäß dem Modell. Hier wurden k = 1 und b = 0,1 als feste Parameter gewählt, während C/T und T über die verschiedenen Kurven variieren. Diese Darstellung des Modells geht davon aus, dass die Gesamtberechnungszeiten T in erster Näherung konstant bleiben (abgesehen von Änderungen in der Siliziumtechnologie, die hier unberücksichtigt bleiben), während sich die Verzögerung durch die Zwischenspeicher C und damit C/T verringert.
Das zweite Diagramm variiert nicht die Technologieparameter, sondern b für C/T = 0.05, T = 1 und k = 2. Diese Grafik zeigt die Abhängigkeit der optimalen Anzahl der Pipelining-Stufen gegenüber dem Aufwand für eine Look-ahead-Resolution und vor allem für die Sprungvorhersage.
Man kann die Aussagen dieses Modells etwa so zusammenfassen, dass die Technologie in erster Linie die Anzahl der Pipeline-Stufen erhöht. Dies liegt daran, dass sich bei Verkleinerung der Strukturen die Laufzeiten in den Transistoren ebenfalls verkürzen. Die Laufzeiten in den Verbindungsleitungen bleiben jedoch etwa konstant und dominieren dadurch heutzutage.
Die Verringerung des Verhältnisses zwischen C und T ist damit tatsächlich Realität. Lokale Strukturen wie Register sind wesentlich schneller als globale wie die komplette Bearbeitung eines Befehls, so dass sich C/T mit dem Fortschritt der Technologie verkleinert. Hieraus folgt der Zwang zu kleinen Blöcken innerhalb des Designs, also zu kleinen und damit mehr Pipeline-Stufen.
Das Modell zeigt somit deutlich den Einfluss einer Technologiegröße auf eine Architekturgröße, hier die optimale Anzahl der Pipeline-Stufen. Letztere können als ein blockorientiertes Design angesehen werden.
Ausblick
Um die Pipeline-Stufen optimal auszunutzen, ohne drastische Verluste durch Fehlvorhersagen in Kauf zu nehmen, müssen die Designer die Verzweigungsvorhersage verbessern. Dadurch nimmt die Wahrscheinlichkeit einer falschen Vorhersage des Programmflusses ab. Dies muss insbesondere geschehen, weil sich die Anzahl der verlorenen Zyklen mit der Pipelinelänge S erhöht.
Welche Schritte bei real existierenden Prozessoren nötig sind, um die Verluste einer langen Pipeline zu vermindern, zeigt der Beitrag Intels Pentium 4 Prescott im Detail. Mit seinen 31 Stufen hält er einen einsamen Rekord. Inzwischen ist Intel mit diesem Design auch überhaupt nicht mehr glücklich und hat die Weiterentwicklung eingestellt - zu Gunsten eines Designs mit deutlich weniger Pipelinestufen und mehr Instruktionen pro Clock.
Diesen Artikel und eine ganze Reihe weiterer Grundlagenthemen zu Prozessoren finden Sie auch in unserem tecCHANNEL-Compact "Prozessor-Technologie". Die Ausgabe können Sie in unserem Online-Shop versandkostenfrei bestellen. Ausführliche Infos zum Inhalt des tecCHANNEL-Compact "Prozessor-Technologie" finden Sie hier. (ala)