add ti-uebungsblatt-2HEADmaster

8 files changed, 286 insertions, 0 deletions

diff --git a/cache/cpuhitperf.tex b/cache/cpuhitperf.tex
new file mode 100644
index 0000000..92a6a81
--- /dev/null
+++ b/cache/cpuhitperf.tex
@@ -0,0 +1,56 @@
+\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
+
diff --git a/cpu/50yproc.tex b/cpu/50yproc.tex
new file mode 100644
index 0000000..206f263
--- /dev/null
+++ b/cpu/50yproc.tex
@@ -0,0 +1,34 @@
+\Aufgabe{Entwicklung der CPU Technologie}
+
+In Abbildung \ref{fig:50yproc} ist der zeitliche Verlauf von Technologieparametern der Mikroprozessortechnologie über die letzten 50 Jahre dargestellt. In der Abbildung fehlt die Legende.  
+
+\begin{figure}[H]
+\center
+\includegraphics[width=\textwidth]{cpu/50yprocqu}
+\caption{Entwicklung der Prozessortechnologie}
+\label{fig:50yproc}
+\end{figure}
+
+Ergänzen sie die Legende. Ordnen sie die Begriffe 
+
+\begin{itemize}
+\item Number of Logical Cores
+\item Single-Thread Performance (SpecINT x $10^3$)
+\item Frequency (MHz)
+\item Transistors (thousands)
+\item Typical Power (Watts)
+\end{itemize}
+
+den Datenpunkten zu.
+
+
+\ifloesung
+\begin{figure}[H]
+\center
+\includegraphics[width=\textwidth]{cpu/50yprocsol}
+\caption{Entwicklung der Prozessortechnologie - mit Legende}
+\label{fig:50yprocsol}
+\end{figure}
+
+{\tiny Karl Rupp, 42 years of Microprocessor Trend data, \url{https://www.karlrupp.net/2018/02/42-years-of-microprocessor-trend-data/}}
+\fi
diff --git a/cpu/50yprocqu.png b/cpu/50yprocqu.png
new file mode 100644
index 0000000..188a7a7
--- /dev/null
+++ b/cpu/50yprocqu.png
diff --git a/cpu/50yprocsol.png b/cpu/50yprocsol.png
new file mode 100644
index 0000000..fd17dba
--- /dev/null
+++ b/cpu/50yprocsol.png
diff --git a/cpu/cpumemcpy.tex b/cpu/cpumemcpy.tex
new file mode 100644
index 0000000..caad50e
--- /dev/null
+++ b/cpu/cpumemcpy.tex
@@ -0,0 +1,158 @@
+\Aufgabe{CPU MIPS Ausführungszeit}
+
+Der RP2040 Chip auf dem Raspberry PI Pico Board enthält einen ARM Cortex M0+ Prozessor. Nehmen Sie nun an, dass der Prozessor den MIPS Befehlssatz ausführen kann - eine fiktionale Annahme, denn in der Realität unterstützt der Prozessor den ARM Befehlssatz. Die Funktion \glqq memcpy\grqq kopiert \glqq num\grqq Elemente aus einem Array \glqq  src\grqq in ein Array \glqq dest\grqq. In Listing \ref{lst:memcpyrust} ist der Code in Rust und in Listing \ref{lst:memcpyc} ist der Code in C angegeben. Listing \ref{lst:memcpymips} zeigt den MIPS Assemblercode ohne die Checks im Rustcode in den Zeilen 2 und 3. Die Argumente der memcpy Funktion werden in den Prozessorregistern gemäß Tabelle \ref{tab:mipsregs} übergeben.
+
+\begin{lstlisting}[label=lst:memcpyrust, caption=memcpy in Rust,numbers=left]
+pub fn memcpy(num: usize, src: &[i32], dest: &mut [i32]) {
+    if num >= src.len() { return };
+    if num >= dest.len() { return };
+    for i in 0..num {
+        dest[i] = src[i];
+    }
+}
+\end{lstlisting} 
+\begin{lstlisting}[label=lst:memcpyc, caption=memcpy in C]
+void memcpy(unsigned int num, int src[], int dest[]) {
+    int i = 0;
+    while (i < num) {
+        dest[i] = src[i];
+        i = i + 1;
+    }
+}
+\end{lstlisting} 
+
+\begin{table}[h]
+\caption{Registerinhalte beim Funktionsaufruf von memcpy}
+\centering
+\begin{tabular}{ll}
+Register & Parameter \\\hline
+\$4 & num\\
+\$5 & Zeiger auf das erste Element des Arrays src\\
+\$6 & Zeiger auf das erste Element des Arrays dest
+\end{tabular}
+\label{tab:mipsregs}
+\end{table}
+
+\begin{lstlisting}[label=lst:memcpymips, caption=memcpy in MIPS Assembler]
+memcpy(unsigned int, int*, int*):
+        beq     $4,$0,$L9
+        sll     $4,$4,2
+        addu    $4,$5,$4
+$L3:
+        lw      $2,0($5)
+        sw      $2,0($6)
+        addiu   $5,$5,4
+        addiu   $6,$6,4
+        bne     $5,$4,$L3
+        nop
+$L9:
+        jr      $31
+        nop
+\end{lstlisting} 
+
+Schätzen Sie die Ausführungszeit für einen Aufruf von \glqq memcpy\grqq mit den folgenden Parametern memcpy(1000, 0x20010000, 0x20020000) ab.
+Geben sie in ihrer Antwort ausführlich ihre Annahmen an.
+
+\ifloesung
+\newpage
+\section*{Abschätzung der Ausführungszeit für \texttt{memcpy} auf dem RP2040}
+
+Um die Ausführungszeit für den Aufruf der \texttt{memcpy}-Funktion im MIPS-Assembler abzuschätzen, wenn der Parameter \texttt{num} den Wert 1000 hat, müssen wir die Anzahl der ausgeführten Befehle und deren Zyklen pro Befehl (CPI) bestimmen. Wir gehen davon aus, dass der Prozessor des RP2040 den MIPS Befehlssatz ausführen kann.
+
+
+\subsection*{Gegebener MIPS-Assemblercode (Auszug aus Listing 3)}
+\begin{verbatim}
+memcpy (unsigned int, int*, int*):
+beq $4,$0,$L9     # Branch if num == 0
+sll $4,$4,2       # num = num * 4 (shift left by 2 bits for byte offset)
+addu $4,$5,$4     # $4 = src + (num * 4) -> $4 holds end address of src
+$L3:              # Loop start
+lw $2,0($5)       # Load word from src[i] into $2
+sw $2,0($6)       # Store word from $2 into dest[i]
+addiu $5,$5,4     # Increment src pointer by 4 bytes
+addiu $6,$6,4     # Increment dest pointer by 4 bytes
+bne $5, $4,$L3    # Branch if src pointer != end address ($4)
+nop               # Branch delay slot
+$L9:              # Loop end / exit
+jr $31            # Jump to return address
+nop               # Branch delay slot
+\end{verbatim}
+
+\subsection*{Registerbelegung (gemäß Tabelle 1)}
+\begin{itemize}
+    \item \texttt{\$4}: \texttt{num} (Anzahl der zu kopierenden Elemente)
+    \item \texttt{\$5}: Zeiger auf das erste Element des Arrays \texttt{src}
+    \item \texttt{\$6}: Zeiger auf das erste Element des Arrays \texttt{dest}
+\end{itemize}
+
+\subsection*{Annahmen für die Abschätzung}
+\begin{enumerate}
+    \item \textbf{CPU-Taktfrequenz:} Der ARM Cortex-M0+ Prozessor auf dem RP2040 Chip kann standardmäßig mit bis zu \textbf{133 MHz} getaktet werden. Wir verwenden diesen Wert.
+        \[ \text{Taktfrequenz} = 133 \, \text{MHz} = 133 \times 10^6 \, \text{Hz} \]
+    \item \textbf{CPI (Cycles Per Instruction):}
+    Wir gehen von einem \textbf{idealen Pipelining} aus, bei dem jeder Befehl durchschnittlich \textbf{1 Taktzyklus (CPI = 1)} benötigt. Dies ist eine Vereinfachung. In der Realität können Befehle (insbesondere Ladebefehle wie \texttt{lw}) Pipeline-Stalls verursachen, und die tatsächlichen CPI-Werte können variieren.
+    \item \textbf{Speicherzugriff:} Wir nehmen an, dass alle Speicherzugriffe (für \texttt{lw} und \texttt{sw}) einen Taktzyklus benötigen.
+    \item \textbf{Parameter:} \texttt{num = 1000}.
+\end{enumerate}
+
+\subsection*{Analyse der Befehlsausführung}
+Die Ausführung des Codes kann in drei Phasen unterteilt werden: Initialisierung, Schleifendurchläufe und Abschluss.
+
+\subsubsection*{I. Initialisierungsphase (vor der Schleife)}
+Diese Befehle werden einmalig ausgeführt.
+\begin{enumerate}
+    \item \texttt{beq \$4,\$0,\$L9}: Wird ausgeführt. Da \texttt{num} (in \texttt{\$4}) 1000 ist, ist es nicht gleich 0, also wird nicht gesprungen.
+    \item \texttt{sll \$4,\$4,2}: Wird ausgeführt. \texttt{\$4} wird zu \texttt{1000 * 4 = 4000}. Dies konvertiert die Elementanzahl in eine Byte-Offset-Adresse, da jedes Element 4 Byte (ein Wort) groß ist.
+    \item \texttt{addu \$4,\$5,\$4}: Wird ausgeführt. \texttt{\$4} enthält nun die Endadresse des \texttt{src}-Arrays (\texttt{start\_src\_address + 4000}). Dieser Wert dient als Abbruchkriterium für die Schleife.
+\end{enumerate}
+\vspace{0.5em}
+\textbf{Anzahl Befehle Initialisierung:} 3 Befehle. \\
+\textbf{Ausführungszeit Initialisierung:} $3 \times 1 \, \text{Taktzyklus/Befehl} = 3$ Taktzyklen.
+
+\subsubsection*{II. Schleifenphase (\texttt{\$L3} bis \texttt{bne})}
+Diese Schleife wird \texttt{num} mal durchlaufen. Da \texttt{num = 1000}, wird die Schleife \textbf{1000 Mal} ausgeführt. In jedem Schleifendurchlauf werden folgende Befehle ausgeführt:
+\begin{enumerate}
+    \item \texttt{lw \$2,0(\$5)}: (Load Word) Lädt ein Element aus dem \texttt{src}-Array.
+    \item \texttt{sw \$2,0(\$6)}: (Store Word) Speichert das Element in das \texttt{dest}-Array.
+    \item \texttt{addiu \$5,\$5,4}: Inkrementiert den \texttt{src}-Zeiger um 4 Bytes (zum nächsten Element).
+    \item \texttt{addiu \$6,\$6,4}: Inkrementiert den \texttt{dest}-Zeiger um 4 Bytes (zum nächsten Element).
+    \item \texttt{bne \$5, \$4,\$L3}: (Branch if not equal) Vergleicht den aktuellen \texttt{src}-Zeiger mit der berechneten Endadresse. Wenn nicht gleich, wird zurück zum Schleifenanfang gesprungen.
+    \item \texttt{nop}: (No Operation) Dieser Befehl füllt den Branch-Delay-Slot des \texttt{bne}-Befehls und wird immer ausgeführt, auch wenn der Sprung nicht genommen wird.
+\end{enumerate}
+\vspace{0.5em}
+\textbf{Anzahl Befehle pro Schleifendurchlauf:} 6 Befehle. \\
+\textbf{Ausführungszeit pro Schleifendurchlauf (angenommener CPI=1 für alle):} $6 \times 1 \, \text{Taktzyklus/Befehl} = 6$ Taktzyklen. \\
+\textbf{Gesamtausführungszeit Schleife:} $1000 \, \text{Durchläufe} \times 6 \, \text{Taktzyklen/Durchlauf} = 6000$ Taktzyklen.
+
+\subsubsection*{III. Abschlussphase (nach der Schleife)}
+Diese Befehle werden einmal ausgeführt, nachdem die Schleife beendet ist (wenn \texttt{num} ursprünglich 0 war oder nach dem letzten Schleifendurchlauf).
+\begin{enumerate}
+    \item \texttt{jr \$31}: (Jump Register) Kehrt zur aufrufenden Funktion zurück.
+    \item \texttt{nop}: (No Operation) Füllt den Branch-Delay-Slot des \texttt{jr}-Befehls.
+\end{enumerate}
+\vspace{0.5em}
+\textbf{Anzahl Befehle Abschluss:} 2 Befehle. \\
+\textbf{Ausführungszeit Abschluss:} $2 \times 1 \, \text{Taktzyklus/Befehl} = 2$ Taktzyklen.
+
+\subsection*{Gesamtzahl der Taktzyklen}
+Die Gesamtzahl der Taktzyklen für den gesamten Funktionsaufruf ist die Summe der Zyklen aus allen Phasen:
+\[ \text{Gesamt-Taktzyklen} = 3 \, (\text{Init}) + 6000 \, (\text{Schleife}) + 2 \, (\text{Abschluss}) = \textbf{6005 Taktzyklen} \]
+
+\subsection*{Berechnung der Ausführungszeit}
+Mit der angenommenen Taktfrequenz von 133 MHz:
+\[ \text{Ausführungszeit} = \frac{\text{Gesamt-Taktzyklen}}{\text{Taktfrequenz}} \]
+\[ \text{Ausführungszeit} = \frac{6005 \, \text{Taktzyklen}}{133 \times 10^6 \, \text{Taktzyklen/Sekunde}} \]
+\[ \text{Ausführungszeit} \approx 45.149 \times 10^{-6} \, \text{Sekunden} \]
+\[ \text{Ausführungszeit} \approx \textbf{45.149 Mikrosekunden (µs)} \]
+
+\subsection*{Zusammenfassung und wichtige Hinweise}
+Unter den genannten Annahmen (RP2040-Taktfrequenz von 133 MHz, idealisiertes Pipelining mit CPI=1 und Speicherzugriff innerhalb eines Taktes) beträgt die geschätzte Ausführungszeit für den \texttt{memcpy}-Aufruf mit \texttt{num = 1000} Elementen ungefähr \textbf{45.149 Mikrosekunden}.
+
+Es ist zu beachten, dass diese Schätzung idealisiert ist. In der Praxis können Faktoren wie tatsächliche Pipeline-Stalls (insbesondere durch Lade-/Speicherbefehle), Branch-Prediction-Fehler und die spezifische Implementierung der MIPS-Architektur auf dem ARM Cortex-M0+ (falls es eine Emulation oder Transkompilierung gäbe) die tatsächliche Ausführungszeit beeinflussen. Diese Faktoren würden die Ausführungszeit in der Regel erhöhen.
+
+\vspace{1cm}
+{\tiny Antwort KI generiert mit Gemini 2.5 Flash am 29.6.2025 (angepasst)}
+\fi
+
+
+
diff --git a/ti-uebungsblatt-2-beck-lsg.pdf b/ti-uebungsblatt-2-beck-lsg.pdf
new file mode 100644
index 0000000..0ca0346
--- /dev/null
+++ b/ti-uebungsblatt-2-beck-lsg.pdf
diff --git a/ti-uebungsblatt-2-beck.pdf b/ti-uebungsblatt-2-beck.pdf
new file mode 100644
index 0000000..661d8b3
--- /dev/null
+++ b/ti-uebungsblatt-2-beck.pdf
diff --git a/ti-uebungsblatt-2.tex b/ti-uebungsblatt-2.tex
new file mode 100644
index 0000000..83e224e
--- /dev/null
+++ b/ti-uebungsblatt-2.tex
@@ -0,0 +1,38 @@
+%% =========================================
+\input{setup.tex}
+
+\newcommand{\uetitel}{Technische Informatik Übung 2}
+\newcommand{\sem}{SS2025}
+
+
+%\loesungtrue    %% Aufgaben mit Lösungen
+\loesungfalse  %% Aufgaben ohne Lösungen
+
+%% =========================================
+\ifloesung
+\title{\uetitel  \textit{Lösungen}}
+\else
+\title{\uetitel}
+\fi
+\date{\sem}
+\author{Prof. Dr.-Ing. Friedrich Beckmann}
+
+%% =========================================
+\begin{document}
+\ifloesung
+\setHeaderFooter{\uetitel \, - Lösungen, \sem}
+\else
+\setHeaderFooter{\uetitel, \sem}
+\fi%loesung
+%\maketitle
+
+\input{cpu/cpumemcpy.tex}
+\newpage\input{cache/cpuhitperf.tex}
+\newpage\input{cpu/50yproc.tex}
+%\newpage\input{cpu/cpudbus64.tex}
+%\newpage\input{cpu/cpumulti.tex}
+%\newpage\input{vhdl/edgevhdl}
+%\newpage\input{vhdl/vhdlholdcnt}
+%\newpage\input{vhdl/vhdlunsigned}
+
+\end{document}
\ No newline at end of file