\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 8}
\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 2}
The signal $hit[j]$ is supposed to indicate that the register accessed by the instruction in stage 1 is modified by the instruction in stage $j$. Except for the first four clock cycles all pipeline stages are full. During the initial cycles, an empty stage is prevented from signaling a hit by its full flag. The signal
$$top.j = hit[j] \AND \bigwedge_{x=2}^{j-1} \neg hit[x]$$
indicates, that there occurs no hit in stages above $j$. \\
If we assume that $hit[j]$ is defined like this
$$hit[j] = GPRw.j \AND (ad \ne 0) \AND (ad = Cad.j)$$
instead of
$$hit[j] = (full.j \AND GPRw.j) \AND (ad \ne 0) \AND (ad = Cad.j)$$
the signal $top.j$ is not generated correctly. \\
The data hazard signal $dhaz$ is defined like this
\begin{eqnarray*}
	dhaz & = & dhazA \OR dhazB \\
	dhazA & = & topA.2 \AND \neg v[2].2 \OR topA.3 \AND \neg v[3].3 \\
	dhazB & = & topB.2 \AND \neg v[2].2 \OR topB.3 \AND \neg v[3].3 \\
\end{eqnarray*}
If the signal $top.j$ is not generated correctly, the $dhaz$ signal won't be correct, too. \\
We track true instructions and dummy instructions in stage $j$ by a single bit $full.j$, where $full.j=1$ signals a true instruction and $full.j=0$ signals a dummy instruction.
\begin{itemize}
\item {\bfseries We assume that we have a dummy instruction and we use the signal $full.j$}. \\
The signal $hit[j]$ will be equal to 0 because of $full.j=0$. If we look at the signal $top.j$ we see that it is also equal to 0 because of $hit[j]=0$. \\
Now let's have a look at the signals $dhazA$ and $dhazB$. Because of $top.j=0$, $dhazA=0$ and $dhazB=0$. For this reason, the signal $dhaz$ also equals 0. \\
A dummy instruction cannot activate the signal $dhaz$.
\item {\bfseries Now we assume that we have a dummy instruction and we do not use the signal $full.j$}. \\
The signal $hit[j]$ could now be different to the $hit[j]$ signal from our assumption above. Because of the fact, that the $hit[j]$ signal is used to compute $top.j$ this signal might be different, too. If we have a 'wrong' signal $top.j$, the signal $dhaz$ could be activated by $dhazA$ or $dhazB$ or both.
Now we see that the signal $dhaz$ could be activated by a dummy instruction if we do not use $full.j$ to generate $hit[j]$.
\end{itemize}

\newpage
\section*{Aufgabe 3}
\begin{eqnarray*}
	movi2s(c) & = & rtype(c) \AND opc(c)=0^6 \AND fu(c)=10001 \\
	movs2i(c) & = & rtype(c) \AND opc(c)=0^6 \AND fu(c)=10000 \\[0.5cm]
	movi2s(c) & \Leftrightarrow & \left\{\begin{array}{ll}c'.SPR(SA(c)) = c.GPR(RS1(c)) & : MODE = 0_{32} \\ c'.SPR(x) = c.SPR(x) & : MODE = 1_{32}\end{array}\right. \\
	movs2i(c) & \Leftrightarrow & \left\{\begin{array}{ll}c'.GPR(RD(c)) = c.SPR(SA(c)) & : MODE = 0_{32} \\ c'.GPR(x) = c.GPR(x) & : MODE = 1_{32}\end{array}\right.
\end{eqnarray*}

\section*{Aufgabe 4}
\begin{itemize}
	\item Instructions in the pipeline do not overtake each other.
		$$\left.\begin{array}{l}I_i(k,t) \\ I_j(k-1,t)\end{array}\right\} \stackrel{\delta}{\rightarrow} \left\{\begin{array}{l}I_i(k+1,t+1) \\ I_j(k,t+1)\end{array}\right. \quad \forall i,j \; \forall k \; \forall t$$
		
	\item We have never two instructions in the same stage at the same time.
		$$I_i(k,t) \Rightarrow \neg I_j(k,t) \quad \forall i,j \; \forall k \; \forall t$$
\end{itemize}

\end{document}