\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}

\thispagestyle{empty}

\title{Computer Architecture 1 - Übungsblatt 5}
\author{Dirk Heine, 2030941 \\
	Jan Hendrik Dithmar, 2031259 \\
	Steffen Heil, 2019358
}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage

\section*{Aufgabe 1}
\bild{14}{dec.jpg}{$n$-Decoder}{ndec}
\begin{itemize}
	\item $n=1$:
		\begin{eqnarray*}
		  Y_0 & = & / x_0 \\
  		Y_1 & = & x_0
		\end{eqnarray*}
		
	\item $n>1$:
		\begin{eqnarray*}
		  m & := & \lceil n/2 \rceil \\
  		k & := & n-m \\
		  A[2^k-1:0] & := & dec_k(x[n-1:m]) \\
  		B[2^m-1:0] & := & dec_m(x[m-1:0])
  	\end{eqnarray*}
  	$\forall a \in \{0,...2^k-1\}, \forall b \in \{0,...,2^m-1\}$: \\
  	$$Y_{a \cdot 2^m + b} := A_a \AND B_b$$
\end{itemize}
Proof:
\begin{itemize}
	\item $n=1$: trivial
	\item $n>1$:
		\begin{eqnarray*}
		  a & := & \left\lfloor \frac{i}{2^m}\right\rfloor \\
		  b & := & i - a \cdot 2^m \\
		  \Rightarrow i & = & a \cdot 2^m + b
		\end{eqnarray*}
		\begin{eqnarray*}
			Y_i = 1 & \stackrel{def. a,b}{\Leftrightarrow} & Y_{a \cdot 2^m + b} \\
			& \Leftrightarrow & A_a = 1 \AND B_b = 1 \\
			& \Leftrightarrow & dec_k(x[n-1:m])_a = 1 \AND dec_k(x[m-1:0])_b = 1 \\
			& \stackrel{IA}{\Leftrightarrow} & \langle x[n-1:m]\rangle = a \AND \langle x[m-1:0]\rangle = b \\
			& \Leftrightarrow & \langle x[n-1:0]\rangle = a \cdot 2^m + b \\
			& \stackrel{def. a,b}{\Leftrightarrow} & \langle x\rangle = i
		\end{eqnarray*}
\end{itemize}

\newpage

\section*{Aufgabe 3}
%\begin{verbatim}
%         subi  r2 r1 1
%         lw    r3 r2 0
%check:   beqz  r2 finish
%next:    subi  r2 r2 1
%         lw    r4 r2 0
%         sgr   r5 r3 r4
%         beqz  r5 check
%         addi  r3 r4 0
%         bnez  r2 next
%finish:  sw    r3 r1 0
%\end{verbatim}
Notation:
\begin{verbatim}
  mnemonic rd rs1 rs2
  mnemonic rd rs1 imm
  mnemonic rs1 label
\end{verbatim}
Sequentiell:
\begin{verbatim}
*
* Grundannahme: Mindestens ein Wert! (Sonst kein Maximum...)
*
* R1: Anzahl der Werte
* R2: Adresse des zuletzt gelesenen Wertes
*     zugleich Anzahl der noch zu lesenden Werte
* R3: Bisheriges Maximum
* R4: Zuletzt gelesener Werte (außer erster)
*
* Wir durchlaufen das Feld rückwärts, damit die Adresse dem
* Zähler entspricht.
* Wir sparen dadurch eine Register bzw. einen Vergleich.
*
          subi  r2 r1 1      * Addresse des letzten Wertes
          lw    r3 r1 -1     * letzten Wert als inital-Maximum
check:    beqz  r2 finish    * stehen noch Werte aus?
next:     subi  r2 r2 1      * nächste Adresse
          lw    r4 r2 0      * nächster Wert
          sge   r5 r3 r4     * Ist das alte Maximum größer
                             * oder gleich ?
          bnez  r5 check     * ja => unverändert lassen
                             * (nächsten Wert holen)
          addi  r3 r4 0      * nein => neues Maximum merken
          bnez  r2 next      * Weitere Werte?
finish:   sw    r3 r1 0      * Ergebniss speichern
\end{verbatim}

\newpage

\section*{Aufgabe 4a}
Mit delayed branch:
\begin{verbatim}
*
* Grundannahme: Mindestens ein Wert! (Sonst kein Maximum...)
*
* R1: Anzahl der Werte
* R2: Adresse des zuletzt gelesenen Wertes
*     zugleich Anzahl der noch zu lesenden Werte
* R3: Bisheriges Maximum
* R4: Zuletzt gelesener Werte (außer erster)
*
* Wir durchlaufen das Feld rückwärts, damit die Adresse dem
* Zähler entspricht.
* Wir sparen dadurch eine Register bzw. einen Vergleich.
*
          subi  r2 r1 1      * Addresse des letzten Wertes
          lw    r3 r2 0      * letzten Wert als inital-Maximum
check:    beqz  r2 finish    * stehen noch Werte aus?
next:     subi  r2 r2 1      * nächste Adresse
          lw    r4 r2 0      * nächster Wert
          sge   r5 r3 r4     * Ist das alte Maximum größer
                             * oder gleich ?
          bnez  r5 check     * ja => unverändert lassen
                             * (nächsten Wert holen)
          bnez  r2 next      * Weitere Werte?
          addi  r3 r4 0      * nein => neues Maximum merken
finish:   sw    r3 r1 0      * Ergebniss speichern
\end{verbatim}

\newpage

\section*{Aufgabe 4b}
\begin{verbatim}

      beqz r0 db
dpc:  beqz r0 +4
      <command2>
      ...
db:   <command1>
      <command3>
      ...

Evaluation order: 

Delayed PC:
1. beqz r0 db
2. beqz r0 +4
3. <command1>
   (when executing 2. the address for 4. is 
   calculated based on the delayed pc to be dpc + 4.)
4. <command2>
5. ...

Delayed Branch:
1. beqz r0 db
2. beqz r0 +4
3. <command1>
   (when executing 2. the address for 4. is 
   calculated based on the current pc to be db + 4.)
4. <command3>
5. ....
\end{verbatim}

\newpage

\section*{Aufgabe 5}
%\begin{eqnarray*}
%	\forall i \; (lb \OR lb \OR lw \OR lbu \OR lhu)(IR(c^i)) & \Rightarrow & \neg(sb \OR sh \OR sw)(IR(c^{i-1})) \\
%	& & \AND \neg(sb \OR sh \OR sw)(IR(c^{i-2})) \\
%	& & \AND \neg(sb \OR sh \OR sw)(IR(c^{i-3}))
%\end{eqnarray*}
Wir definieren:
\begin{eqnarray*}
	GPRr(c,x) & := & itype  \AND c.IR[20:16]=x \\
	& & \OR rtype  \AND ( c.IR[20:16]=x \OR c.IR[15:11]=x ) \\
	& & \OR itype  \AND c.IR[31:29]=101 \AND c.IR[25:21]=x \\
	GPRw(c,x) & := & itype  \AND c.IR[31:29]<>101 \AND c.IR[25:21]=x \AND c.IR[31,29:28] = 001 \\
	& & \OR rtype \AND c.IR[25:21]=x
\end{eqnarray*}
$$SC6:  \forall i. \forall x \in \{0...31\}. \forall n \in \{1...3\}. GPRr(c^i,x) \Rightarrow \neg GPRw(c^{i-n},x)$$

\end{document}