% !TEX root = dt-slides-cpu.tex

\section{CPU Pipelining}

\begin{frame}
\frametitle{CPU Pipelining}
\begin{center}
\Huge CPU Pipelining
\end{center}
\end{frame}

\begin{frame}
\frametitle{Pipelining am Beispiel Wäschereinigung}
Am Beispiel der Wäschereinigung lässt sich das Pipelining erläutern. In diesem Bespiel besteht der Ablauf aus vier Schritten.
\vspace{0.5cm}
\begin{enumerate}
\item Dreckige Wäsche in die Waschmaschine füllen und Maschine starten.
\item Nach dem Waschen die Wäsche in den Wäschetrockner geben und den Trockner starten.
\item Nach dem Trocknen die Wäsche zusammenlegen.
\item Nach dem Zusammenlegen die Wäsche in den Schrank räumen.
\end{enumerate}
\vspace{0.5cm}
\begin{block}{Ohne Pipelining}
Sie beladen die Waschmaschine erst wieder, wenn die Wäsche im Schrank liegt. Wenn jeder Schritt 30 Minuten dauert, dann sind Sie nach zwei Stunden mit der ersten Ladung fertig. Alle zwei Stunden ist eine weitere Ladung Wäsche fertig. Jede Station ist zu einem Viertel der Zeit in Betrieb. Für vier Waschladungen benötigen Sie acht Stunden Zeit.
\end{block}

\begin{block}{Mit Pipelining}
Sobald die Waschmaschine fertig ist und die Wäsche im Trockner ist, laden Sie die Waschmaschine sofort wieder neu. So machen Sie das an allen Stationen. Nach zwei Stunden ist die erste Ladung Wäsche fertig. Danach wird alle 30 Minuten eine Ladung fertig. Allerdings nur, wenn ein Mitbewohner die Wäsche in den Schrank räumt... Nach 90 Minuten sind alle Stationen in Betrieb. Für vier Waschladungen benötigen Sie 3 1/2 Stunden Zeit. Die reinste Fließbandarbeit.
\end{block}
\end{frame}

\begin{frame}
\frametitle{Pipelining am Beispiel Wäsche waschen}
%\begin{center}
\includegraphics[width=0.7\textwidth]{cpu-pipeline/waschmaschine-pipeline}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
%\end{center}
\end{frame}

\begin{frame}
\frametitle{Pipelining im Prozessor}
Beim Pipelining im MIPS Prozessor kann man die Ausführung beispielsweise in fünf Schritte aufteilen.
\vspace{0.3cm}
\begin{enumerate}
\item Befehl aus dem Befehlsspeicher holen (Instruction Fetch)
\item Register lesen und Befehl dekodieren (Instruction Decode)
\item Ausführen der Operation oder Berechnung der Adresse (Execute)
\item Lesen oder Schreiben eines Operanden im Datenspeicher (Memory Access)
\item Schreiben des Ergebnisses in eine Register (Write Back)
\end{enumerate}
\vspace{0.3cm}
\begin{block}{Pipelining im Prozessor}
Damit hat dieser Prozessor fünf Pipelinestufen. Ohne Pipelining ist die Taktperiode durch die maximale Ausführungszeit beschränkt (800 ps). Mit Pipelining durch die maximale Zeit einer Stufe (200 ps).
\end{block}
\begin{center}
\includegraphics[width=1.0\textwidth]{cpu-pipeline/mips-stage-times}
\end{center}
\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Pipelining im Prozessor}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/mips-pipeline-vergleich}
\end{center}

\begin{block}{Vergleich mit/ohne Pipelining ideal}
Ohne Pipelining werden für jeden Befehl 800 ps benötigt. Mit Pipelining dauert die Ausführung eines Befehls 1000 ps, aber die Rate hat sich erhöht. Im Idealfall kann alle 200 ps ein Befehl bearbeitet werden. Die Rate hat sich damit vervierfacht.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}[fragile]
\frametitle{Konflikte und Pipelinestall}
\begin{lstlisting}
add $s0, $t0, $t1
sub $t2, $s0, $t3
\end{lstlisting}
\begin{block}{Datenkonflikt}
Bei der Ausführung wird das Register s0 im ersten Befehl geschrieben und im folgenden sub Befehl wird der s0 verwendet. In der Pipeline wird das Register allerdings erst in der letzten Stufe geschrieben, d.h. im Registerfile sind die Daten noch nicht angekommen, wenn der zweite Befehl die Daten schon benötigt.
\end{block}
\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/add-pipeline}
\end{center}
\begin{block}{Pipelinestall}
Durch Einfügen von "no operation = nop = sll $0, $0, 0" Befehlen kann man solange warten, bis das Ergebnis des ersten Befehls im Registerfile angekommen ist. Diese "nop" könnten vom Compiler eingefügt werden. Praktisch wird dies von der Hardware realisiert, indem die vorherigen Stufen angehalten werden.
\end{block}
\begin{lstlisting}
add $s0, $t0, $t1
nop
nop
nop
sub $t2, $s0, $t3
\end{lstlisting}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}[fragile]
\frametitle{Register Forwarding}
\begin{lstlisting}
add $s0, $t0, $t1
sub $t2, $s0, $t3
\end{lstlisting}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/add-register-forwarding}
\end{center}
\begin{block}{Registerforwarding}
Um die zusätzlichen Wartezyklen zu vermeiden kann man das Ergebnis der ALU in der Executionstage gleich für den nächsten Befehl verwenden, wenn man bemerkt, dass das Ergebnis schon vorher benötigt wird. Dieses Verfahren nennt sich Registerforwarding und ist eine Alternative zum Einfügen von Wartezyklen.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Steuerkonflikt}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/beq-stall}
\end{center}
\begin{block}{Steuerkonflikt}
Bei einem bedingten Sprung "beq"  ist die Adresse des nächsten Befehls erst nach Executionstage bekannt, da die Register verglichen werden müssen. Der Instructionfetch muss also verzögert werden.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Pipeline Aufteilung in der Hardware}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/pipeline-aufteilung}
\end{center}
\begin{block}{Aufteilung}
Die Hardwareblöcke, die bei Instruction Fetch, Instruction Decode, Execution, Memory Read und Write Back beteiligt sind.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Pipeline mit Registern}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/pipeline-register}
\end{center}
\begin{block}{Aufteilung mit Einfügen von Pipelineregistern}
Zwischen die Blöcke werden zusätzliche Pipelineregister eingefügt, die die Zwischenergebnisse der einzelnen Blöcke speichern können. Dadurch wird die Logiktiefe der Logik zwischen den Registern reduziert und die Taktgeschwindigkeit kann erhöht werden.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{lw Beispiel - fetch}

\begin{center}
\includegraphics[width=1.0\textwidth]{cpu-pipeline/lw-fetch}
\end{center}
\begin{block}{Instruction Fetch}
Der Befehl wird aus dem Befehlsspeicher geladen und IF/ID Pipelineregister gespeichert.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{lw Beispiel - decode}

\begin{center}
\includegraphics[width=1.0\textwidth]{cpu-pipeline/lw-decode}
\end{center}
\begin{block}{Instruction Decode}
Der Befehl wird dekodiert, d.h. die Steuerleitungen für die Alu werden berechnet. Gleichzeitig werden die Register aus dem Registerfile gelesen. Die Operanden und die Steuerleitung für die ALU werden im ID/EX Pipelineregister gespeichert.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{lw Beispiel - execute}

\begin{center}
\includegraphics[width=1.0\textwidth]{cpu-pipeline/lw-execute}
\end{center}
\begin{block}{Execute}
Die ALU berechnet die Operation. Die Ergebnisse werden im EX/MEM Pipelineregister gespeichert.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{lw Beispiel - Memory}

\begin{center}
\includegraphics[width=1.0\textwidth]{cpu-pipeline/lw-mem}
\end{center}
\begin{block}{Memory}
Mit der berechneten Adresse werden die Daten aus dem Datenspeicher gelesen und im MEM/WB Pipelineregister gespeichert.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{lw Beispiel - Write Back}

\begin{center}
\includegraphics[width=1.0\textwidth]{cpu-pipeline/lw-writeback}
\end{center}
\begin{block}{Write Back}
Die Daten aus dem Datenspeicher werden in die Register zurückgeschrieben. Problem: Registeradresse
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{lw Beispiel - Speicherung des Zielregisters in den Pipelinestufen}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/lw-destreg}
\end{center}
\begin{block}{Zielregister in die Pipelineregister}
Die Daten beim lw Befehl werden im Zielregister abgespeichert. Dazu muss das Zielregister nach dem Instruction Fetch in den Pipelineregistern zwischengespeichert werden, damit die Zieladresse in der Write Back Stufe bekannt ist.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Beispiel - Fünf Befehle in der Pipeline}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/pipe-5inst}
\end{center}
\begin{block}{Fünf Befehle in der Pipeline}
Bei einer Befehlsfolge werden in den Pipelinestufen zu einem Zeitpunkt jeweils andere Befehle bearbeitet
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Beispiel - Fünf Befehle in der Pipeline - alternative Darstellung}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/pipe-5inst-text}
\end{center}
\begin{block}{Fünf Befehle in der Pipeline}
Bei einer Befehlsfolge werden in den Pipelinestufen zu einem Zeitpunkt jeweils andere Befehle bearbeitet
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Beispiel - Fünf Befehle in der Pipeline - Zyklus 5}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/pipe-5inst-lastcycle}
\end{center}
\begin{block}{Prozessor wenn alle Pipelinestufen gefüllt sind}
Wenn der letzte Befehl der Folge in der Write Back Stufe ist, wird der erste Befehl gerade gefetcht. In diesem Beispiel gibt es keine Konflikte in der Pipeline.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Konflikte in der Pipeline}

\begin{center}
\includegraphics[width=0.7\textwidth]{cpu-pipeline/pipe-5inst-konflikt}
\end{center}
\begin{block}{Datenkonflikt }
Der erste Befehl sub schreibt in das Register 2. Der Registerinhalt ändert sich aber erst wenn der Befehl sub in der WriteBack Stufe in Taktzyklus 5 angekommen ist. Der nächste Befehl "and" benötigt aber den neuen Inhalt von Register 2. Ohne Änderungen würde der Prozessor jetzt mit dem alten Wert "10" rechnen und Fehler produzieren. Erst der "add" Befehl in Zyklus 5 würde mit den korrekten Daten "-20" rechnen.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Konflikte in der Pipeline - Forwarding}

\begin{center}
\includegraphics[width=0.7\textwidth]{cpu-pipeline/pipe-5inst-konflikt-forwarding}
\end{center}
\begin{block}{Datenkonflikt lösen durch Register Forwarding }
Das Ergebnis der Berechnung aus der Executionstufe für Register 2 liegt schon im Prozessor vor. Die Idee ist das Ergebnis schon zu verwenden. Dazu benötigt man eine Logik, die überprüft ob das Ergebnis schon im Register ist oder sich erst in einer der Pipelinestufen befindet.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Konflikte in der Pipeline - Forwarding}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/pipe-5inst-konflikt-forwarding-arch}
\end{center}
\begin{block}{Register Forwarding - Architektur }
Die Architektur muss überprüfen ob Register verwendet werden, deren Ergebnisse noch nicht im Registerfile sind. Wenn das so ist, dann werden die Ergebnisse aus dem EX/MEM oder MEM/WB Pipelineregister verwendet.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Konflikte in der Pipeline - Load}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/pipe-loadkonflikt}
\end{center}
\begin{block}{Daten aus Datenspeicher können nicht geforwarded werden }
Der erste Befehl "lw" lädt Daten aus dem Datenspeicher in Register 2. Der folgende "and" Befehl verwendet die Daten aus Register 2 schon. "Forwarding" kann nicht eingesetzt werden, da die Daten im Datenspeicher noch nicht bekannt sind. Deshalb muss die Pipeline angehalten werden, bis die Daten aus der MEM Stufe vorhanden sind.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Konflikte in der Pipeline - Architektur Konflikterkennung}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/pipe-loadkonflikt-stall}
\end{center}
\begin{block}{Anhalten der Pipeline "Stall"}
Für den "and" Befehl wird die Executionstufe angehalten, bis die Daten aus dem Datenspeicher vorhanden sind und mit Forwarding in der ALU verwendet werden können. Dazu wird eine eine Konflikterkennung benötigt.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Konflikte in der Pipeline - Load}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/pipe-loadkonflikt-arch}
\end{center}
\begin{block}{Anhalten der Pipeline "Stall"}
Der Konflikt durch den Zugriff auf den Datenspeicher muss erkannt werden. Bei einem Konflikt wird das IF/ID Register angehalten und eine 0 = NOP für die EX, MEM und WB Stufe eingefügt.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Konflikte in der Pipeline - Steuerkonflikt bei bedingtem Sprung}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/pipe-branch}
\end{center}
\begin{block}{Steuerkonflikt - branch}
Bei dem bedingten Sprung kann erst in der MEM Phase entschieden werden ob gesprungen wird oder nicht. Bis dahin sind schon drei neue Befehle in der Pipeline.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}

\begin{frame}
\frametitle{Pipelining bei verschiedenen Prozessorgenerationen}

\begin{center}
\includegraphics[width=0.8\textwidth]{cpu-pipeline/pipeline-prozessoren}
\end{center}
\begin{block}{Entwicklung der Anzahl der Pipelinestufen}
Die Anzahl der Pipelinestufen wurde zunächst immer größer bis mit dem Einsatz von mehreren Cores auf eine Chip die Anzahl wieder geringer wurde.
\end{block}

\tiny{source: Patterson und Hennessy, Rechnerorganisation und Rechnerentwurf, 2014}
\end{frame}