From 682a6011fb877093ac8c8d92fa22ccdc3ed30a72 Mon Sep 17 00:00:00 2001
From: Friedrich Beckmann <friedrich.beckmann@gmx.de>
Date: Sun, 29 Jun 2025 17:45:27 +0200
Subject: add ti-uebungsblatt-2

---
 cpu/cpumemcpy.tex | 158 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 158 insertions(+)
 create mode 100644 cpu/cpumemcpy.tex

(limited to 'cpu/cpumemcpy.tex')

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
+
+
+
-- 
cgit v1.2.3

