\Aufgabe{Ausführungszeit vs. Cache Hit Rate}

Ein Rechnersystem ist mit einem 2kB großen L1 Datencache, einem 4kB großen L1 Befehlscache und einem DRAM mit einer Größe von 16 Gigabyte  aufgebaut. Ein Zugriff auf den L1 Cache dauert 2 Taktzyklen. Ein Zugriff auf das DRAM dauert 300 Taktzyklen. Sie haben ein Programm zur Positionsschätzung aus LiDAR Daten geschrieben. Sie haben ein Codeprofiling mit Testdaten durchgeführt. Dabei haben sie die Cachezugriffsdaten aus Tabelle \ref{tab:cachemiss} gemessen. Zusätzlich haben sie mit dem Profiling herausgefunden, dass 15 Prozent aller Instruktionen load oder store Befehle sind. Nehmen sie eine einfache MIPS Prozessorarchitektur an. Bei einem Cachehit dauert die Ausführung eines Befehls inklusive des Speicherzugriffs im Durchschnitt 2 Takte.

\begin{table}[h]
\caption{Zugriffsfehler auf den Instruction- Datacache }
\centering
\begin{tabular}{ll}
Cache & Missrate \\\hline
Instruktion & 0.4\% \\
Data & 3.7\% \\
\end{tabular}
\label{tab:cachemiss}
\end{table}

Schätzen Sie ab wie sich die Ausführungszeit ihres Programm im Vergleich zu einem idealen Cacheverhalten verhält.

\ifloesung
\subsection*{Ideales Verhalten}
Bei einem idealen Cacheverhalten sind alle Befehls- und alle Datenzugriffe Treffer im Cache. Man hat also eine Cache Hit Rate von 100 Prozent. Im Durchschnitt dauert die Bearbeitung eines Befehls dann zwei Taktzyklen. Damit ergibt sich ein idealer CPI (Cycles per Instruction) Wert von CPI = 2.

\subsection*{Verhalten aufgrund von Zugriffsfehlern auf den Befehlscache}
Bei einem Instructionfetch auf einen Befehl, der nicht im Cache ist, muss der Befehl aus dem DRAM geholt werden. In diesem Fall dauert es 298 Takte länger bis der Befehl in der CPU ist. Das tritt in 0.4 Prozent aller Zugriffe auf den Befehlsspeicher ein. In Bezug auf die durchschnittlich benötigte Anzahl von Taktzyklen für die Ausführung eines Befehls aufgrund der Fehlzugriffe auf den Befehlscache ergibt sich

\begin{align*}
CPI_{act,B} &= CPI_{ideal} + \text{Missrate,B} \times \text{Misspenalty,DRAM} \\
&= 2 + 0.004 \times 298 = 2 + 1.192 = 3.192
\end{align*}

Nur aufgrund der Fehlzugriffe auf den Befehlscache dauert die Ausführung eines Befehls 3.192 Taktzyklen statt 2 Taktzyklen. Die Ausführungszeit wird damit etwa 60 Prozent größer.

\subsection*{Verhalten aufgrund von Zugriffsfehlern auf den Datencache}
15 Prozent aller Befehle sind load oder store Befehle, die einen Zugriff auf den Datencache beinhalten. Wenn die Daten bei dem Zugriff nicht im Cache sind, dann dauert die Ausführung des Befehls 298 Takte länger. Das tritt in 3.7 Prozent aller Datenzugriffe ein. Damit ergibt sich für die durchschnittlich benötigte Anzahl von Taktzyklen für die Ausführung eines Befehls aufgrund von Wartezeiten bei Datenzugriffen:

\begin{align*}
CPI_{act,D} &= CPI_{ideal} + \text{Anteil Befehle mit Datenzugriff} \times \text{Missrate,D} \times \text{Misspenalty,DRAM} \\
&= 2 + 0.15 \times 0.037 \times 298 \\
&= 2 + 1.654 = 3.654 
\end{align*}

Aufgrund von Fehlzugriffen auf den Datencache erhöht sich die durchschnittlich benötigte Anzahl von Takten für die Ausführung eines Befehls von 2 auf 3,654 Takte. Dies entspricht einer Erhöhung der Ausführungszeit um 83 Prozent.

\subsection*{Verhalten mit Auswirkungen von Befehls- und Datencache}

Die Fehlzugriffe auf Befehls- und Datencache wirken unabhängig voneinander. Die Anzahl von benötigten Taktzyklen pro Befehl ist dann

\begin{align*}
CPI_{act} &= CPI_{ideal} + \text{Zusatzzyklen Fehlzugriffe Befehlscache} +  \text{Zusatzzyklen Fehlzugriffe Datencache} \\
&= 2 + 1.192 + 1.654 = 2 + 2.846 = 4.846
\end{align*}

Es dauert im Durchschnitt also 4,846 Taktzyklen statt 2 Taktzyklen um einen Befehl auszuführen wenn die Zugriffsfehler auf den Befehls- und Datencache berücksichtigt werden. Die Ausführungszeit steigt auf das 2,4 fache der Ausführungszeit mit einem idealen Cache. Das entspricht einer Steigerung der benötigten Ausführungszeit für das Programm um 142 Prozent.
\else%loesung
\loesungsbox{15cm} {}
\fi%loesung

