\documentclass[10pt,a4paper]{article}

\usepackage{ngerman}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{thumbpdf}
\usepackage{graphicx}
\usepackage{float}
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage[latin1]{inputenc}
\usepackage[pdftex,             
            pdfpagelabels,
            colorlinks=true,           % Links nicht farbig umrahmen, sondern als farbigen Text
            urlcolor=colorBlue,        % Farbe für externe Verweise, \href{...}{...}
            filecolor=colorGreen,      % Farbe für lokale Verweise, \href{...}{...}
            linkcolor=colorRed,        % Farbe für interne Verweise, \ref{...} und \pageref{...}
            pdftitle={(Titel)},
            pdfauthor={(Autor)},
            pdfsubject={(Thema)},
            pdfkeywords={(Schlagwörter)},
            pdfpagemode=None,          % Navigationsleiste beim Start ausblenden 
            % pdfpagemode=UseThumbs,     % Thumbnails beim Start anzeigen
            % pdfpagemode=UseOutlines,   % Lesezeichen beim Start anzeigen
            % pdfpagemode=FullScreen,    % im Vollbildmodus starten
            % pdfstartpage=2,            % spezielle Startseite festlegen
            bookmarks,
            % bookmarksopen,             % alle Lesezeichen aufklappen
            % bookmarksopenlevel=2,      % Tiefe, bis zu welcher die Lesezeichen aufgeklappt werden sollen
            bookmarksnumbered,         % Lesezeichen nummerieren
            pdfstartview=FitH,         % Seite auf voller Breite anzeigen
            pagebackref
           ]{hyperref}

\DeclareMathOperator{\CSA}{CSA}
\DeclareMathOperator{\FA}{FA}
\DeclareMathOperator{\FF}{FF}
\DeclareMathOperator{\MUX}{MUX}
\DeclareMathOperator{\Enc}{Enc}
\DeclareMathOperator{\Dec}{Dec}
\DeclareMathOperator{\FDec}{FDec}
\DeclareMathOperator{\BCD}{BCD}
\DeclareMathOperator{\BA}{BA}
\DeclareMathOperator{\PP}{PP}
\DeclareMathOperator{\alu}{alu}
\DeclareMathOperator{\testi}{testi}
\DeclareMathOperator{\shifta}{shifta}
\DeclareMathOperator{\IR}{IR}
\DeclareMathOperator{\CLA}{CLA}

\floatstyle{ruled}
\newfloat{schematic}{p}{los}
\floatname{schematic}{Schaltkreis}

\begin{document}

\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetI}{\ensuremath{\mathbb{I}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}} 
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\Set}[1]{\ensuremath{\mathbb{#1}}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\Inv}[1]{\ensuremath{\frac{1}{#1}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\With}{\ensuremath{\:\:|\:\:}}
\newcommand{\BigWith}{\ensuremath{\:\:\Big|\:\:}}
\newcommand{\Vector}[3]{\ensuremath{\left(\begin{array}{c}#1\\#2\\#3\end{array}\right)}}
\newcommand{\degree}{\ensuremath{^\circ}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}

\newcommand{\hrefold}{} \let\hrefold=\href
\renewcommand{\href}[2]{\hrefold{#1}{\textbf{#2}}}
\newcommand{\hyperlinkold}{} \let\hyperlinkold=\hyperlink
\renewcommand{\hyperlink}[2]{\hyperlinkold{#1}{\textbf{#2}}}
\newcommand{\refold}{} \let\refold=\ref
\renewcommand{\ref}[1]{\textbf{\refold{#1}}}
\newcommand{\pagerefold}{} \let\pagerefold=\pageref
\renewcommand{\pageref}[1]{\textbf{\pagerefold{#1}}}

\thispagestyle{empty}

\title{Rechnerarchitektur - Übungsblatt 11 \\
	Übungsgruppe 8 - Di, 15-17 Uhr \\
	Steffen Heil}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
	Carsten Saar (Matrikelnummer 2030107) \\
	Thomas Ospelt (Matrikelnummer 2029959) \\
	Timo Adam (Matrikelnummer 2031946)}
\date{}

\maketitle

\newpage

\section*{Aufgabe 1}
Definiere Signale $g_i$ und $p_i$, die besagen, ob die Pipeline-Stufe $i$ ein stall-Signal generiert bzw. propagiert.
Sei $\text{stall}_{i+1}$ gegeben. Dann ergibt sich der Wert von $\text{stall}_i$ aus folgender Tabelle
\\[0.5cm]
\begin{tabular}{c|c|c}
  $\text{lstall}_i$ & $\text{full}_i$ & $\text{stall}_i$ \\ \hline
  0 & 0 & 0 \\ \hline
  0 & 1 & $\text{stall}_{i+1}$ \\ \hline
  1 & 0 & 0 \\ \hline
  1 & 1 & 1 \\
\end{tabular}
\\[0.5cm]
Wie aus der Tabelle offensichtlich hervorgeht, gelten folgende Äquivalenzen
\begin{itemize}
  \item Die Pipeline-Stufe $i$ generiert genau dann ein stall-Signal, wenn $\text{lstall}_i=1$ und $\text{full}_i=1$ gilt. \\[0.1cm]
        $ g_i=1 \quad\Longleftrightarrow\quad \text{lstall}_i \;\wedge\; \text{full}_i $
  \item Die Pipeline-Stufe $i$ propagiert genau dann das stall-Signal der Pipeline-Stufe $(i+1)$, wenn $\text{lstall}_i=0$ und $\text{full}_i=1$ gilt. \\[0.1cm]
        $ p_i=1 \quad\Longleftrightarrow\quad \overline{\text{lstall}_i} \;\wedge\; \text{full}_i $
\end{itemize}
Definiere analog zur Konstruktion des Carry Lookahead Adders die Funktion
$$ \circ: \{0,1\}^2 \times \{0,1\}^2 \rightarrow \{0,1\}^2 $$
$$ (g_2,p_2) \circ (g_1,p_1) := (g_2 \vee (g_1 \wedge p_2), p_2 \wedge p_1) $$
welche nach dem Beweis auf Übungsblatt 8 assoziativ ist.
Ebenfalls analog zur Konstruktion des CLA ergibt sich dann für die geforderte Schaltfunktion ein Schaltkreis nach Abbildung 1.
Die Einhaltung der Grenzen für die Kosten und die Tiefe des Schaltkreises ergeben sich trivial, da Kosten und Tiefe des PP bekannt sind.

\newpage
\section*{Aufgabe 2}
\textbf{Anmerkung:} Es wird keine Prüfung vorgenommen, ob der Ausdruck den geforderten Eigenschaften entspricht (z.B. gültige
Klammersetzung). Ist der Ausdruck nicht regelkonform, ist das Verhalten des Programms nicht definiert. \\[0.5cm]
\begin{tabular}{ll}
  \quad\quad\texttt{R1 = 1000}        & // Zeiger auf die betrachtete Stelle des Ausdrucks \\
  \quad\quad\texttt{R2 = 10000}       & // Zeiger auf das nächste freie Element im Stack \\
  \texttt{loop:}                      & // Schleifenbeginn, nächstes Symbol ist noch zu laden \\
  \quad\quad\texttt{R3 = M$_4$(R1)}   & // lade erstes Wort (Symbolklasse) in \texttt{R3} \\
  \quad\quad\texttt{R4 = M$_4$(R1+4)} & // lade zweites Wort (Wert, Zeiger oder Operator) in \texttt{R4} \\
  \quad\quad\texttt{R1 = R1 + 8}      & // setze Zeiger auf nächstes Symbol \\
  \texttt{looploaded:}                & // Schleifenbeginn, nächstes Symbol ist bereits geladen \\
\end{tabular}
\\[0.5cm]
\begin{tabular}{ll}
  \quad\quad\texttt{R5 = (R3$\le$2 ? 1 : 0)}             & // ist Symbol eine Konstante oder Variable ? \\
  \quad\quad\texttt{PC = PC + (R5=0 ? noconstnovar : 4)} & // wenn nein, auf nächste Regel testen \\
                                                         & // aktuelles Symbol ist Konstante oder Variable \\
  \quad\quad\texttt{PC = PC + (R3=0 ? const : 4)}        & // wenn Konstante, Variablen-Auswertung überspringen \\
  \quad\quad\texttt{R4 = M$_4$(R4)}                      & // überschreibe Variablenadresse mit Variablenwert \\
  \texttt{const:}                                        & // aktuelles Symbol ist Konstante \\
                                                         & // (oder ausgewertete Variable) \\
  \quad\quad\texttt{M$_4$(R2) = R0}                      & // es wird eine Konstante auf den Stack gepusht, \\
                                                         & // erstes Wort 0 \\
  \quad\quad\texttt{M$_4$(R2+4) = R4}                    & // Wert der Konstanten auf den Stack pushen \\
  \quad\quad\texttt{R2 = R2 + 8}                         & // setze Stackpointer auf nächstes freies Element \\
  \quad\quad\texttt{PC = PC + loop}                      & // nächstes Symbol auswerten \\
  \texttt{noconstnovar:} \\
\end{tabular}
\\[0.5cm]
\begin{tabular}{ll}
                                                           & // Symbol ist in jedem Fall ein Operator \\
  \quad\quad\texttt{PC = PC + (R4$\neq$0 ? nobracket : 4)} & // wenn keine öffnende Klammer, \\
                                                           & // auf nächste Regel testen \\
  \quad\quad\texttt{R5 = 2}                                & // Symbolklasse für Operatoren ist 2 \\
  \quad\quad\texttt{$M_4$(R2) = R5}                        & // Symbolklasse pushen \\
  \quad\quad\texttt{M$_4$(R2+4) = R0}                      & // offnende Klammer auf den Stack pushen \\
  \quad\quad\texttt{R2 = R2 + 8}                           & // setze Stackpointer auf nächstes freies Element \\
  \quad\quad\texttt{PC = PC + loop}                        & // nächstes Symbol auswerten \\
  \texttt{nobracket:} \\
\end{tabular}
\\[0.5cm]
\begin{tabular}{ll}
                                                                & // Erinnerung: Symbol ist in jedem Fall ein Operator \\
  \quad\quad\texttt{R5 = (R4=1 ? 1 : 0)}                        & // ist Symbol eine schließende Klammer ? \\
  \quad\quad\texttt{PC = PC + (R5=0 ? nobracketconst : 4)}      & // wenn nein, auf nächste Regel testen \\
                                                                & // \textbf{Achtung!} der Fall, dass sich nicht mindestens \\
                                                                & // zwei Symbole auf dem Stack befinden, wird \\
                                                                & // vernachlässigt, da dieser Fall nur bei einem \\
                                                                & // ungültigen Ausdruck auftreten kann \\
  \quad\quad\texttt{R5 = M$_4$(R2-16)}                          & // lade Symbolklasse des vorletzten Symbols \\
                                                                & // auf dem Stack \\
  \quad\quad\texttt{PC = PC + (R5=0 ? nobracketconst : 4)}      & // wenn kein Operator, auf nächste Regel testen \\
  \quad\quad\texttt{R5 = M$_4$(R2-12)}                          & // lade Operator-Identifikation des vorletzten \\
                                                                & // Symbols auf dem Stack \\
  \quad\quad\texttt{PC = PC + (R5$\neq$0 ? nobracketconst : 4)} & // wenn keine öffnende Klammer, nächste Regel \\
  \quad\quad\texttt{R5 = M$_4$(R2-8)}                           & // lade Symbolklasse des letzten Symbols \\
                                                                & // auf dem Stack \\
  \quad\quad\texttt{PC = PC + (R5$\neq$0 ? nobracketconst : 4)} & // wenn keine Konstante, auf nächste Regel testen \\
                                                                & // es liegt ein Ausdruck der Form ,,\texttt{( C )}`` vor \\
  \quad\quad\texttt{M$_4$(R2-16) = R5}                          & // kopiere letztes Symbol des Stacks an die \\
                                                                & // vorletzte Stelle, hier die Symbolklasse = 0 \\
  \quad\quad\texttt{R5 = M$_4$(R2-4)}                           & // lade Wert des letzten Symbols des Stacks, \\
                                                                & // hier Wert der Konstanten \\
  \quad\quad\texttt{M$_4$(R2-12) = R5}                          & // setze Wert des vorletzten Symbols des Stacks, \\
                                                                & // Kopiervorgang beendet \\
  \quad\quad\texttt{R2 = R2 - 8}                                & // entferne letztes Symbol von Stack, \\
                                                                & // Klammer entfernt, Konstante jetzt letzter Wert \\
  \quad\quad\texttt{R5 = (R2=10008 ? 1 : 0)}                    & // ist die Konstante auf dem Stack \\
                                                                & // das einzige Symbol ? \\
  \quad\quad\texttt{PC = PC + (R5=1 ? ready : 4)}               & // wenn ja, Auswertung des kompletten \\
                                                                & // Ausdrucks abgeschlossen \\
  \quad\quad\texttt{PC = PC + loop}                             & // ansonsten nächstes Symbol bearbeiten \\
  \texttt{nobracketconst:}                                      & // es liegt keine Ausdruck der Form ,,\texttt{( C )}`` vor \\
\end{tabular}
\\[0.5cm]
\begin{tabular}{ll}
                                                                & // Erinnerung: Symbol ist in jedem Fall ein Operator \\
  \quad\quad\texttt{R5 = M$_4$(R2-24)}                          & // lade Symbolklasse des vorvorletzten Symbols \\
                                                                & // auf dem Stack \\
  \quad\quad\texttt{PC = PC + (R5$\neq$0 ? noconstopconst : 4)} & // wenn keine Konstante, dann Fehler \\
  \quad\quad\texttt{R5 = M$_4$(R2-16)}                          & // lade Symbolklasse des vorletzten Symbols \\
                                                                & // auf dem Stack \\
  \quad\quad\texttt{PC = PC + (R5=0 ? noconstopconst : 4)}      & // wenn kein Operator, dann Fehler \\
  \quad\quad\texttt{R5 = M$_4$(R2-8)}                           & // lade Symbolklasse des letzten Symbols \\
                                                                & // auf dem Stack \\
  \quad\quad\texttt{PC = PC + (R5$\neq$0 ? noconstopconst : 4)} & // wenn keine Konstante, dann Fehler \\
                                                                & // es gilt \texttt{prio(op) = zweites Wort - 1} außer \\
                                                                & // für den Operator ,,\texttt{-}`` \\
                                                                & // $\Longrightarrow$ die Prioritätsauswertung läßt sich \\
                                                                & // wie folgt vereinfachen: \\
                                                                & // ,,\texttt{C$_1$ op C$_2$}`` wird genau dann ausgewertet, wenn \\
                                                                & // - \texttt{op'} $\le$ \texttt{op} (Operator-IDs werden verglichen) \\
                                                                & // - oder \texttt{op' = },,\texttt{-}`` $\quad\wedge\quad$ \texttt{op = },,\texttt{+}`` \\
  \quad\quad\texttt{R6 = M$_4$(R2-12)}                          & // lade Operator-ID des vorletzten Symbols \\
                                                                & // auf dem Stack \\
  \quad\quad\texttt{R5 = (R4$\le$R6  ? 1 : 0)}                  & // ist \texttt{op' $\le$ op} ? \\
  \quad\quad\texttt{PC = PC + (R5$\neq$0 ? eval : 4)}           & // wenn ja, wird ausgewertet \\
  \quad\quad\texttt{R5 = (R4=6 ? 1 : 0)}                        & // ist \texttt{op' = },,\texttt{-}`` ? (Sonderfall) \\
  \quad\quad\texttt{PC = PC + (R5=0 ? noeval : 4)}              & // wenn nein, keine Auswertung \\
  \quad\quad\texttt{R5 = (R6=5 ? 1 : 0)}                        & // ist \texttt{op = },,\texttt{+}`` ? (Sonderfall) \\
  \quad\quad\texttt{PC = PC + (R5$\neq$0 ? eval : 4)}           & // wenn ja, wird ausgewertet \\
\end{tabular}
\\[0.5cm]
\begin{tabular}{ll}
  \texttt{noeval:}                                              & // keine Auswertung, \\
                                                                & // neuen Operator auf Stack pushen \\
  \quad\quad\texttt{M$_4$(R2) = R3}                             & // Symbolklasse auf Stack bringen \\
  \quad\quad\texttt{M$_4$(R2+4) = R4}                           & // Operator-ID auf Stack bringen \\
  \quad\quad\texttt{R2 = R2 + 8}                                & // setze Stackpointer auf nächstes freies Element \\
  \quad\quad\texttt{PC = PC + loop}                             & // nächstes Symbol bearbeiten \\
\end{tabular}
\\[0.5cm]
\begin{tabular}{ll}
  \texttt{eval:}                                                & // Auswertung durchführen \\
  \quad\quad\texttt{R5 = M$_4$(R2-20)}                          & // lade Konstante $C_1$ \\
                                                                & // (vorvorletztes Symbol auf dem Stack) \\
  \quad\quad\texttt{R7 = M$_4$(R2-4)}                           & // lade Konstante $C_2$ \\
                                                                & // (letztes Symbol auf dem Stack) \\
                                                                & // es werden nur die Fälle \texttt{op = $\vee$/$\wedge$/=/+/-} bzw. \\
                                                                & // \texttt{R6 = 2/3/4/5/6} berücksichtigt; alle anderen \\
                                                                & // Fälle dürfen an dieser Stelle nicht \\ 
                                                                & // auftreten, wenn der Ausdruck zulässig ist \\
  \quad\quad\texttt{R6 = R6 - 2}                                & // vermindere \texttt{op} um 2, im folgenden \\
                                                                & // nur noch Dekrements und Tests auf 0 nötig \\
  \quad\quad\texttt{R8 = R5 $\vee$ R7}                          & // vorsorglich Oder berechnen \\
  \quad\quad\texttt{PC = PC + (R6=0 ? saveresult : 4)}          & // wenn wirklich Oder zu berechnen, speichern \\
  \quad\quad\texttt{R6 = R6 - 1}                                & // prüfe auf nächsten Operator \\
  \quad\quad\texttt{R8 = R5 $\wedge$ R7}                        & // vorsorglich Und berechnen \\
  \quad\quad\texttt{PC = PC + (R6=0 ? saveresult : 4)}          & // wenn wirklich Und zu berechnen, speichern \\
  \quad\quad\texttt{R6 = R6 - 1}                                & // prüfe auf nächsten Operator \\
  \quad\quad\texttt{R8 = (R5=R7 ? 1 : 0)}                       & // vorsorglich Gleich berechnen \\
  \quad\quad\texttt{PC = PC + (R6=0 ? saveresult : 4)}          & // wenn wirklich Gleich zu berechnen, speichern \\
  \quad\quad\texttt{R6 = R6 - 1}                                & // prüfe auf nächsten Operator \\
  \quad\quad\texttt{R8 = R5 + R7}                               & // vorsorglich Plus berechnen \\
  \quad\quad\texttt{PC = PC + (R6=0 ? saveresult : 4)}          & // wenn wirklich Plus zu berechnen, speichern \\
  \quad\quad\texttt{R8 = R5 - R7}                               & // Minus berechnen, denn nur dieser Operator \\
                                                                & // kann es an dieser Stelle noch sein \\
  \texttt{saveresult:} \\
  \quad\quad\texttt{R2 = R2 - 16}                               & // entferne die letzten zwei Symbole vom Stack \\
  \quad\quad\texttt{M$_4$(R2-4) = R8}                           & // ersetze Konstante (letztes Symbol auf Stack) \\
                                                                & // durch berechnete Konstante \\
                                                                & // Symbolklasse ist bereits auf Konstante gesetzt \\
  \quad\quad\texttt{PC = PC + looploaded}                       & // bereits geladenes Symbol auswerten \\
  \texttt{noconstopconst:} \\
\end{tabular}
\\[0.5cm]
\quad\quad // wird diese Programmstelle erreicht, ist der Ausdruck ungültig \\
\quad\quad // da ein gültiger Ausdruck vorausgesetzt wurde, hier keine weitere Aktion \\[0.5cm]
\texttt{ready:} \\
\quad\quad // Auswertung des Ausdrucks abgeschlossen

\newpage
\section*{Aufgabe 3}
\textbf{Anmerkung:} Die vorzeichenlose Integer-Division wird durch wiederholtes Subtrahieren des Divisors vom Dividenden erreicht,
wobei die Anzahl der Subtraktionen mitgezählt wird und nur solange subtrahiert wird, bis der Dividend kleiner als der Divisor ist. \\[1cm]
\begin{tabular}{ll}
                                                        & // in \texttt{R1} steht nach Voraussetzung der Dividend \\
                                                        & // und in \texttt{R2} der Divisor $\neq 0$ \\
  \quad\quad\texttt{R3 = 0}                             & // initialisiere den Quotienten mit 0 \\
  \quad\quad\texttt{R4 = R1}                            & // und den Rest mit dem Dividenden \\
  \quad\quad\texttt{PC = PC + test}                     & // vor Eintritt in die Schleife Bedingung prüfen \\
  \texttt{loop:} \\
  \quad\quad\texttt{R3 = R3 + 1}                        & // ansonsten Quotient inkrementieren \\
  \quad\quad\texttt{R4 = R4 - R2}                       & // und den Rest um den Divisor vermindern \\
  \texttt{test:} \\
  \quad\quad\texttt{R5 = (R4<R2 ? 1 : 0)}               & // ist der Rest kleiner dem Divisor ? \\
  \quad\quad\texttt{PC = PC + (R5=0 ? loop : 4)}        & // wenn nein, dann Schleife erneut durchlaufen \\
\end{tabular}

\newpage
\section*{Aufgabe 4}
\textbf{Anmerkung:} Das Kommando \texttt{M$_2$(writecmd+2) = R1} evaluiert unter der Voraussetzung, dass das Programm ab Speicheradresse
0 beginnt, zum Kommando \texttt{M$_2$(10) = R1}. \\[1cm]
\begin{tabular}{ll}
  \quad\quad\texttt{R1 = 32768}                  & // beginne mit inkrementierter Endadresse, da zu \\
                                                 & // Beginn der Schleife sofort dekrementiert wird \\
  \texttt{loop:} \\
  \quad\quad\texttt{R1 = R1 - 1}                 & // dekrementiere Adresse \\
  \quad\quad\texttt{M$_2$(writecmd+2) = R1}      & // überschreibe die Immediate-Konstante des Speicher- \\
                                                 & // zugriffes bei \texttt{writecmd}, welche sich im hinteren \\
                                                 & // Halbwort des Instruktionswortes befindet, mit der aktuellen \\
                                                 & // Adresse, so dass beim Erreichen des Schreibkommandos bei \\
                                                 & // \texttt{writecmd} der Wert aus \texttt{R1} an die Adresse \texttt{R0+R1 = R1} \\
                                                 & // geschrieben wird \\
  \texttt{writecmd:} \\
  \quad\quad\texttt{M$_1$(0) = R1}               & // \textbf{Achtung!} selbstmodifizierender Code, siehe letzte Zeile \\
                                                 & // schreibe an Adresse \texttt{R1} den Wert \texttt{R1 mod $2^8$} (beim Byte- \\
                                                 & // Schreibzugriff werden die oberen 24 Bit abgeschnitten) \\
  \quad\quad\texttt{R2 = (R1$\le$1024 ? 1 : 0)}  & // soeben schon der Anfang des Speicherblocks bearbeitet? \\
  \quad\quad\texttt{PC = PC + (R2=0 ? loop : 4)} & // wenn nein, Schleife ab \texttt{loop} erneut durchlaufen \\
\end{tabular}

\end{document}