\documentclass[10pt,a4paper]{article}

% Packages
\usepackage{fancyhdr}           % For header and footer
\usepackage{multicol}           % Allows multicols in tables
\usepackage{tabularx}           % Intelligent column widths
\usepackage{tabulary}           % Used in header and footer
\usepackage{hhline}             % Border under tables
\usepackage{graphicx}           % For images
\usepackage{xcolor}             % For hex colours
%\usepackage[utf8x]{inputenc}    % For unicode character support
\usepackage[T1]{fontenc}        % Without this we get weird character replacements
\usepackage{colortbl}           % For coloured tables
\usepackage{setspace}           % For line height
\usepackage{lastpage}           % Needed for total page number
\usepackage{seqsplit}           % Splits long words.
%\usepackage{opensans}          % Can't make this work so far. Shame. Would be lovely.
\usepackage[normalem]{ulem}     % For underlining links
% Most of the following are not required for the majority
% of cheat sheets but are needed for some symbol support.
\usepackage{amsmath}            % Symbols
\usepackage{MnSymbol}           % Symbols
\usepackage{wasysym}            % Symbols
%\usepackage[english,german,french,spanish,italian]{babel}              % Languages

% Document Info
\author{Everdeen}
\pdfinfo{
  /Title (rechnersysteme-2.pdf)
  /Creator (Cheatography)
  /Author (Everdeen)
  /Subject (Rechnersysteme 2 Cheat Sheet)
}

% Lengths and widths
\addtolength{\textwidth}{6cm}
\addtolength{\textheight}{-1cm}
\addtolength{\hoffset}{-3cm}
\addtolength{\voffset}{-2cm}
\setlength{\tabcolsep}{0.2cm} % Space between columns
\setlength{\headsep}{-12pt} % Reduce space between header and content
\setlength{\headheight}{85pt} % If less, LaTeX automatically increases it
\renewcommand{\footrulewidth}{0pt} % Remove footer line
\renewcommand{\headrulewidth}{0pt} % Remove header line
\renewcommand{\seqinsert}{\ifmmode\allowbreak\else\-\fi} % Hyphens in seqsplit
% This two commands together give roughly
% the right line height in the tables
\renewcommand{\arraystretch}{1.3}
\onehalfspacing

% Commands
\newcommand{\SetRowColor}[1]{\noalign{\gdef\RowColorName{#1}}\rowcolor{\RowColorName}} % Shortcut for row colour
\newcommand{\mymulticolumn}[3]{\multicolumn{#1}{>{\columncolor{\RowColorName}}#2}{#3}} % For coloured multi-cols
\newcolumntype{x}[1]{>{\raggedright}p{#1}} % New column types for ragged-right paragraph columns
\newcommand{\tn}{\tabularnewline} % Required as custom column type in use

% Font and Colours
\definecolor{HeadBackground}{HTML}{333333}
\definecolor{FootBackground}{HTML}{666666}
\definecolor{TextColor}{HTML}{333333}
\definecolor{DarkBackground}{HTML}{C7C7C7}
\definecolor{LightBackground}{HTML}{F8F8F8}
\renewcommand{\familydefault}{\sfdefault}
\color{TextColor}

% Header and Footer
\pagestyle{fancy}
\fancyhead{} % Set header to blank
\fancyfoot{} % Set footer to blank
\fancyhead[L]{
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{C}
    \SetRowColor{DarkBackground}
    \vspace{-7pt}
    {\parbox{\dimexpr\textwidth-2\fboxsep\relax}{\noindent
        \hspace*{-6pt}\includegraphics[width=5.8cm]{/web/www.cheatography.com/public/images/cheatography_logo.pdf}}
    }
\end{tabulary}
\columnbreak
\begin{tabulary}{11cm}{L}
    \vspace{-2pt}\large{\bf{\textcolor{DarkBackground}{\textrm{Rechnersysteme 2 Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{Everdeen} via \textcolor{DarkBackground}{\uline{cheatography.com/57687/cs/15280/}}}
\end{tabulary}
\end{multicols}}

\fancyfoot[L]{ \footnotesize
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{LL}
  \SetRowColor{FootBackground}
  \mymulticolumn{2}{p{5.377cm}}{\bf\textcolor{white}{Cheatographer}}  \\
  \vspace{-2pt}Everdeen \\
  \uline{cheatography.com/everdeen} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Published 28th March, 2018.\\
   Updated 28th March, 2018.\\
   Page {\thepage} of \pageref{LastPage}.
\end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Sponsor}}  \\
  \SetRowColor{white}
  \vspace{-5pt}
  %\includegraphics[width=48px,height=48px]{dave.jpeg}
  Measure your website readability!\\
  www.readability-score.com
\end{tabulary}
\end{multicols}}




\begin{document}
\raggedright
\raggedcolumns

% Set font size to small. Switch to any value
% from this page to resize cheat sheet text:
% www.emerson.emory.edu/services/latex/latex_169.html
\footnotesize % Small font.

\begin{multicols*}{3}

\begin{tabularx}{5.377cm}{x{1.9908 cm} x{2.9862 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Pipelining}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{Instruction Fetch (IF)}} & nimmt Befehle vom HS auf \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
{\bf{Instruction Decode (ID)}} & decodiert Befehle \& Register; schaut in Register \& l{\"a}dt Inhalte \tn 
% Row Count 5 (+ 3)
% Row 2
\SetRowColor{LightBackground}
{\bf{Execute (EX)}} & führt Operation aus \tn 
% Row Count 6 (+ 1)
% Row 3
\SetRowColor{white}
{\bf{Memory Access (MA)}} & macht L/S Befehle im HS \tn 
% Row Count 8 (+ 2)
% Row 4
\SetRowColor{LightBackground}
{\bf{Write Back (WB)}} & schreibt in Register \tn 
% Row Count 10 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{{\bf{Vorteil:}} Parallelisierung von Operationen \newline {\bf{Nachteil:}} bei Pipelineflush müssen alle Befehle verwerfend neu geladen werden; ohne Cache immer Cachemiss}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.69218 cm} x{3.28482 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Konflikte}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{Write after Write}} & doppelte Überschreibung \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
{\bf{Write after Read}} & Wert, der noch gebraucht wird, wird überschrieben \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
{\bf{Read after Write}} & falscher Wert wird gelesen \tn 
% Row Count 6 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.69218 cm} x{3.28482 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Stalling}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{Pipeline Stalling}} & l{\"a}sst Operationen einen Takt warten \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
{\bf{Result Forwarding}} & Wert direkt weitergeben; {\emph{kein Zeitverlust, geht aber nur wenn Wert erreichbar}} \tn 
% Row Count 6 (+ 4)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{{\bf{Speculative Execution:}} raten}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{p{1.64241 cm} x{3.33459 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Befehlstypen}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{Abacus / MIPS} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
R / R & 3 Register \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
I / I & 2 Register \tn 
% Row Count 3 (+ 1)
% Row 3
\SetRowColor{white}
S / - & 1 Register \tn 
% Row Count 4 (+ 1)
% Row 4
\SetRowColor{LightBackground}
J / J & 0 Register \tn 
% Row Count 5 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{0.82386 cm} x{1.92234 cm} x{1.8308 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{3}{x{5.377cm}}{\bf\textcolor{white}{Stalls}}  \tn
% Row 0
\SetRowColor{LightBackground}
 & {\bf{\{\{ar\}\}ohne FW}} & {\bf{\{\{ar\}\}mit FW}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\seqsplit{arithm.} & \{\{ar\}\}2 & \{\{ar\}\}0 \tn 
% Row Count 3 (+ 1)
% Row 2
\SetRowColor{LightBackground}
L/S & \{\{ar\}\}2 & \{\{ar\}\}1 \tn 
% Row Count 4 (+ 1)
% Row 3
\SetRowColor{white}
Branch & \{\{ar\}\}3 & \{\{ar\}\}1 \tn 
% Row Count 5 (+ 1)
% Row 4
\SetRowColor{LightBackground}
Jump & \{\{ar\}\}3 & \{\{ar\}\}0 \tn 
% Row Count 6 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}---}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Nakata}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{* findet min. Anzahl an Registern, die für ein Programm n{\"o}tig sind \newline % Row Count 2 (+ 2)
* {\bf{Knoten == Variable:}} set RegNum = 1 \newline % Row Count 3 (+ 1)
* {\bf{Knoten un{\"a}re Operation}} und Kind Label r hat: set RegNum = r  \newline % Row Count 5 (+ 2)
* {\bf{Knoten bin{\"a}re Operation}}: *  \newline % Row Count 6 (+ 1)
{\emph{l==r:}} set RegNum = l+1 = r+1 \newline % Row Count 7 (+ 1)
* {\emph{l!=r:}} set RegNum = max\{l, r\} \newline % Row Count 8 (+ 1)
* funktioniert nicht bei geteilten Registern, z.B.: (c *\textasciitilde{}\textasciitilde{} x \textasciitilde{}\textasciitilde{} + b) *\textasciitilde{}\textasciitilde{} x \textasciitilde{}\textasciitilde{}+ a% Row Count 10 (+ 2)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Parsertabelle}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{a)}} ist das T in unserer FIRST-Menge drin? Dann suche Produktion, welche das T in die FIRST-Menge bringt \newline % Row Count 3 (+ 3)
{\bf{b)}} ist e in FIRST, dann schaue, ob unser T auch in der FOLLOW-Menge drin ist \newline % Row Count 5 (+ 2)
Falls ja, nehme e auf% Row Count 6 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{0.96117 cm} x{1.23579 cm} x{2.38004 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{3}{x{5.377cm}}{\bf\textcolor{white}{Byteorientierter Cache Beispiel}}  \tn
% Row 0
\SetRowColor{LightBackground}
 & {\bf{tag | adr}} & {\bf{valid}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
15 sti \$1, \$0, 0 & 1 in adr{[}0{]}  -\textgreater{} 00|00 & 0 -\textgreater{} 1 \tn 
% Row Count 5 (+ 3)
% Row 2
\SetRowColor{LightBackground}
16 sti \$2, \$0, 1 & 2 in adr{[}1{]} -\textgreater{} 00|01 & 0 -\textgreater{} 1 \tn 
% Row Count 7 (+ 2)
% Row 3
\SetRowColor{white}
17 ldi \$2, \$0, 1 & Mem{[}1{]} laden -\textgreater{} 00|01 & 1 -\textgreater{} hit \tn 
% Row Count 10 (+ 3)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{3}{x{5.377cm}}{18 sti \$3, \$0, 2} \tn 
% Row Count 11 (+ 1)
% Row 5
\SetRowColor{white}
\mymulticolumn{3}{x{5.377cm}}{19 sti \$4, \$0, 3} \tn 
% Row Count 12 (+ 1)
% Row 6
\SetRowColor{LightBackground}
\mymulticolumn{3}{x{5.377cm}}{20 ldi \$2, \$0, 1} \tn 
% Row Count 13 (+ 1)
% Row 7
\SetRowColor{white}
\mymulticolumn{3}{x{5.377cm}}{21 sti \$5, \$0, 7} \tn 
% Row Count 14 (+ 1)
% Row 8
\SetRowColor{LightBackground}
\mymulticolumn{3}{x{5.377cm}}{22 sti \$6, \$0, 8} \tn 
% Row Count 15 (+ 1)
% Row 9
\SetRowColor{white}
23 sti \$7, \$0, 9 & 7 in adr{[}9{]} -\textgreater{} 10|01 & valid = 1 \&\& tag{[}9{]} != 00 aus 16 -\textgreater{} miss \tn 
% Row Count 17 (+ 2)
% Row 10
\SetRowColor{LightBackground}
24 ldi \$2, \$0, 1 & Mem{[}1{]} laden & Cachemiss \tn 
% Row Count 19 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}---}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.09494 cm} x{3.88206 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Bitorientierter Cache}}  \tn
% Row 0
\SetRowColor{LightBackground}
\seqsplit{Datawidth} & 16 entspricht 2 Byte Wortgr{\"o}{\ss}e \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
MemSize & 32 HS Gr{\"o}{\ss}e \tn 
% Row Count 3 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\seqsplit{Cachesize} & 8 entspricht 4 W{\"o}rter \tn 
% Row Count 5 (+ 2)
% Row 3
\SetRowColor{white}
\seqsplit{Blocksize} & 2 entspricht 1 Wort \tn 
% Row Count 7 (+ 2)
% Row 4
\SetRowColor{LightBackground}
\seqsplit{SetAssoc} & 1 entsricht 1 Block pro Satz \tn 
% Row Count 8 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{{\bf{direct mapping:}} jedes Wort genau eine Zuteilung}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{p{0.71009 cm} p{0.54301 cm} x{0.87717 cm} x{2.04673 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{4}{x{5.377cm}}{\bf\textcolor{white}{CPI}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{Befehlstyp}} & \{\{ar\}\}{\bf{\%}} & \{\{ar\}\}{\bf{mit RAW}} & \{\{ar\}\}{\bf{CPI}} \tn 
% Row Count 3 (+ 3)
% Row 1
\SetRowColor{white}
\seqsplit{Sprungbefehl} & \{\{ar\}\}20\% & \{\{ar\}\}20\% & \{\{ar\}\}1 bei jump; 2 bei branch \tn 
% Row Count 5 (+ 2)
% Row 2
\SetRowColor{LightBackground}
\seqsplit{Arithmetik} & \{\{ar\}\}60\% & \{\{ar\}\}60\% & \{\{ar\}\}1 \tn 
% Row Count 7 (+ 2)
% Row 3
\SetRowColor{white}
\seqsplit{Ladebefehl} & \{\{ar\}\}20\% & \{\{ar\}\}0.5*20\% & \{\{ar\}\}1 wenn Wert darauf nicht gelesen, 2 \tn 
% Row Count 10 (+ 3)
% Row 4
\SetRowColor{LightBackground}
MAC &  & \{\{ar\}\}0.5*20\% & \{\{ar\}\}- \tn 
% Row Count 12 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}----}
\SetRowColor{LightBackground}
\mymulticolumn{4}{x{5.377cm}}{50\% der Ladebefehle erzeugen einen RAW Konflikt \newline {\bf{CPI}}= \seqsplit{CPI`A`*20+CPI`A`*60+CPI`L`*(20-10)} / 100-(20-10)}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}----}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Lokalit{\"a}ten}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{r{\"a}umlich:}} Adressen, die nah an dem genutzten sind, werden wahrscheinlich wieder genutzt -\textgreater{} {\emph{Bl{\"o}cke}} \newline % Row Count 3 (+ 3)
{\bf{zeitlich:}} eine Adresse, auf die zugegriffen wird, wird wahrscheinlich in n{\"a}chster Zeit wieder angesprochen% Row Count 6 (+ 3)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Zurückschreibmethoden}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{write through:}} schreibt immer durch \newline % Row Count 1 (+ 1)
{\bf{write back:}} nutzt dirtybit \newline % Row Count 2 (+ 1)
schreibt zurück, wenn etwas neues eingelagert wird vom HS (oder geladen) \newline % Row Count 4 (+ 2)
{\bf{least recently used:}} {\emph{für set-oriented:}} schreibt in Zeile, die am l{\"a}ngsten nicht genutzt wurde% Row Count 7 (+ 3)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Graph Coloring}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Spilling:}} nutzen den HS \newline % Row Count 1 (+ 1)
1. Berechnen Read / Write-Menge \& Zeilen / Bl{\"o}cke \newline % Row Count 3 (+ 2)
2. MayLive berechnen \newline % Row Count 4 (+ 1)
3. MayUsed bestimmen \newline % Row Count 5 (+ 1)
4. Zeilenweise den Schnitt nehmen \newline % Row Count 6 (+ 1)
5. alle in der selben Menge haben Beziehung zueinander \newline % Row Count 8 (+ 2)
6. Assembler-Code produzieren \newline % Row Count 9 (+ 1)
* werden x Farben ben{\"o}tigt, dann ist Codierung auch mit x Registern m{\"o}glich% Row Count 11 (+ 2)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{p{0.58478 cm} x{1.54549 cm} x{0.8354 cm} x{1.21133 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{4}{x{5.377cm}}{\bf\textcolor{white}{Cacheadressierung}}  \tn
% Row 0
\SetRowColor{LightBackground}
 & Byte & Block & N`k`-set \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\seqsplit{\#index} & \seqsplit{log`2`(Cachegr}.)\{\{ac\}\} & \{\{ac\}\}s`k` & \{\{ac\}\}s`k`-n`k` \tn 
% Row Count 3 (+ 2)
% Row 2
\SetRowColor{LightBackground}
\#tag & log`2`(HSGr) -\#adr\{\{ac\}\} & al- \seqsplit{(s`k`+b)} & al-(s`k`- n`k`+b) \tn 
% Row Count 5 (+ 2)
% Row 3
\SetRowColor{white}
\seqsplit{\#offset} & \{\{ac\}\}- & \{\{ac\}\}b & \{\{ac\}\}b \tn 
% Row Count 7 (+ 2)
% Row 4
\SetRowColor{LightBackground}
\#gl. tags & \{\{ac\}\}\#Zeilen im Cache & \{\{ac\}\}size`k` & size`k`/ N`k`\{\{ac\}\} \tn 
% Row Count 9 (+ 2)
% Row 5
\SetRowColor{white}
S{\"a}tze & \{\{ac\}\}- & \{\{ac\}\}size`k` & \{\{ac\}\}size`k`/ N`k` \tn 
% Row Count 11 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}----}
\SetRowColor{LightBackground}
\mymulticolumn{4}{x{5.377cm}}{size`k` = \#Bl{\"o}cke im Cache \newline s`k`: size`k`= 2\textasciicircum{}sk\textasciicircum{} Bl{\"o}cke; B = Blockgr{\"o}{\ss}e in Byte;  \newline b: B = 2\textasciicircum{}b\textasciicircum{}; a`l` = Bits für Adressraum \newline n`k`: N`k` = 2\textasciicircum{}n`k`\textasciicircum{}; N`k` = \#Bl{\"o}cke im Satz \newline  \newline Adressberechnung \newline adr(x) = x mod (Cachelines); tag(x) = x div (CL);  \newline adr(x) = (x div 2\textasciicircum{}b\textasciicircum{}) div 2\textasciicircum{}s`k`\textasciicircum{}; tag(x) = (x div 2\textasciicircum{}b\textasciicircum{}) mod 2\textasciicircum{}s`k`\textasciicircum{} \newline adr(x) = (x div 2\textasciicircum{}b\textasciicircum{}) div 2\textasciicircum{}s`k`-n`k`\textasciicircum{} \newline tag(x) = (x div 2\textasciicircum{}b\textasciicircum{}) mod 2\textasciicircum{}s`k`-n`k`\textasciicircum{}}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}----}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Blockorientierter Cache}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{* direct mapping \newline % Row Count 1 (+ 1)
* Laden \& Speichern gesamter Bl{\"o}cke \newline % Row Count 2 (+ 1)
{\bf{+}} nutzen aus, dass "nahe" Werte abh{\"a}ngig voneinander sind -\textgreater{} kein unn{\"o}tiges Laden \newline % Row Count 4 (+ 2)
{\bf{-}} bl{\"o}d, wenn diese unabh{\"a}ngig sind% Row Count 5 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Blockorientierter Cache Beispiel}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{15 sti \$1, \$0, 0}} \newline % Row Count 1 (+ 1)
Mem{[}0{]} -\textgreater{} 00|0|0 = tag | in welchem Block | in welcher Zeile im Block \newline % Row Count 3 (+ 2)
{\bf{21 sti \$5, \$0, 7}} \newline % Row Count 4 (+ 1)
Mem{[}7{]} -\textgreater{} 01|1|1 \newline % Row Count 5 (+ 1)
Cachemiss 00!=01 \newline % Row Count 6 (+ 1)
-\textgreater{} laden den Block on den HS zurück, um neuen Wert speichern zu k{\"o}nnen% Row Count 8 (+ 2)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Satzassoziativer Cache}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{* kein direct mapping \newline % Row Count 1 (+ 1)
* darf sich aussuchen, in welchen Block \newline % Row Count 2 (+ 1)
+ reinspeichern angenehmer, da freie Platzwahl \newline % Row Count 3 (+ 1)
- suchen aufw{\"a}ndiger, da wir alle Bl{\"o}cke im Set durchgehen müssen \newline % Row Count 5 (+ 2)
* 1-way -\textgreater{} blockorientiert, da nur ein Block und somit keine Platzwahl% Row Count 7 (+ 2)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.19002 cm} x{1.19002 cm} x{2.19696 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{3}{x{5.377cm}}{\bf\textcolor{white}{Top-Down-Parsing}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{Stack}} & {\bf{input}} & {\bf{action}} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\$S & bbabbbb\$ & expand S -\textgreater{} bSbb \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\$bbSb & bbabbbb\$ & match \tn 
% Row Count 3 (+ 1)
% Row 3
\SetRowColor{white}
\$bbS & babbbb\$ & expand S -\textgreater{} bSbb \tn 
% Row Count 4 (+ 1)
% Row 4
\SetRowColor{LightBackground}
\$bbbbSb & babbbb\$ & match \tn 
% Row Count 5 (+ 1)
% Row 5
\SetRowColor{white}
\$bbbbS & abbbb\$ & expand S -\textgreater{} A \tn 
% Row Count 6 (+ 1)
% Row 6
\SetRowColor{LightBackground}
\$bbbbA & abbbb\$ & expand A -\textgreater{} aB \tn 
% Row Count 7 (+ 1)
% Row 7
\SetRowColor{white}
\$bbbbBa & abbbb\$ & match \tn 
% Row Count 8 (+ 1)
% Row 8
\SetRowColor{LightBackground}
\$bbbbB & bbbb\$ & expand B -\textgreater{} \tn 
% Row Count 9 (+ 1)
% Row 9
\SetRowColor{white}
\$bbbb & bbbb\$ & match \tn 
% Row Count 10 (+ 1)
% Row 10
\SetRowColor{LightBackground}
\$bbb & bbb\$ & match \tn 
% Row Count 11 (+ 1)
% Row 11
\SetRowColor{white}
\$bb & bb\$ & match \tn 
% Row Count 12 (+ 1)
% Row 12
\SetRowColor{LightBackground}
\$b & b\$ & match \tn 
% Row Count 13 (+ 1)
% Row 13
\SetRowColor{white}
\$ & \$ & match \tn 
% Row Count 14 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}---}
\SetRowColor{LightBackground}
\mymulticolumn{3}{x{5.377cm}}{S -\textgreater{} bSbb | A \newline A -\textgreater{} aB \newline B -\textgreater{} A | \newline {\bf{bbabbba in Sprache?}}}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}---}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{p{0.4577 cm} x{0.9154 cm} x{3.2039 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{3}{x{5.377cm}}{\bf\textcolor{white}{First \& Follow Beispiel}}  \tn
% Row 0
\SetRowColor{LightBackground}
 & {\bf{FIRST}} & {\bf{FOLLOW}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
S & b, a & {\bf{\$}}, FIRST(b)\textbackslash{}e aus FOL(S): {\bf{b}} \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
A & a & FOL(S) aus FOL(A): {\bf{\$, b}} \tn 
% Row Count 5 (+ 1)
% Row 3
\SetRowColor{white}
B & a, & FOL(A) aus FOL(B): {\bf{\$, b}} \tn 
% Row Count 6 (+ 1)
% Row 4
\SetRowColor{LightBackground}
a & a & - \tn 
% Row Count 7 (+ 1)
% Row 5
\SetRowColor{white}
b & b & - \tn 
% Row Count 8 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}---}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Caches}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{* Cache wird bei L/S Befehlen angesprochen \newline % Row Count 1 (+ 1)
* alles in bin{\"a}r \newline % Row Count 2 (+ 1)
{\bf{dirtybit:}} Cache konsistent zum HS?  \newline % Row Count 3 (+ 1)
Ja: 0; Nein: 1 \newline % Row Count 4 (+ 1)
{\bf{validbit:}} ist ein Datum in der Adresse?  \newline % Row Count 5 (+ 1)
Ja: 1; Nein: 0 \newline % Row Count 6 (+ 1)
{\bf{Blockorientiert:}} es werden nur Teile im Block überschrieben \newline % Row Count 8 (+ 2)
{\bf{Set-orientiert:}} freie Auswahl in Adresse \newline % Row Count 9 (+ 1)
{\bf{Cache-hit:}} valid = 1 \& tag(i) == tag(i') \newline % Row Count 10 (+ 1)
{\bf{miss:}} valid = 0 || valid = 1 \& tag(i) != tag(i') \newline % Row Count 12 (+ 2)
{\bf{Trefferquote:}} \#hit/\#miss \newline % Row Count 13 (+ 1)
{\bf{Average Acces Time:}} Hitrate*time(hit) + (1-Hitrate*time(miss)) \newline % Row Count 15 (+ 2)
{\bf{Miss-Penalty:}} extra delay durch HS-Zugriff% Row Count 16 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{First \& Follow}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{FOLLOW:}}  \newline % Row Count 1 (+ 1)
\$ aus FOL(S) \newline % Row Count 2 (+ 1)
A-\textgreater{}aBb: FIRST(b)/e aus FOL(B) \newline % Row Count 3 (+ 1)
A-\textgreater{}aB: FOL(A) aus FOL(B) \newline % Row Count 4 (+ 1)
A-\textgreater{}aBb, e aus FIRST(b): FOL(A) aus FOL(B)% Row Count 5 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Data Flow Analyse}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Basic Block:}} * Zeile nach einem if bildet neuen Block \newline % Row Count 2 (+ 2)
* if goto a bildet neuen Block an Zeile a \newline % Row Count 3 (+ 1)
-\textgreater{} {\emph{erste Zeile im neuen Block}} \newline % Row Count 4 (+ 1)
-\textgreater{} *nur bei goto keine Beziehung zum nachfolgenden Block \newline % Row Count 6 (+ 2)
{\bf{Read-Menge:}} nehmen von allen Reads die raus, die wir im eigenen Block vorher schreiben \newline % Row Count 8 (+ 2)
{\bf{Write-Menge:}} alle geschriebenen Variablen% Row Count 9 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Variablen}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{* auf Klammerung achten \newline % Row Count 1 (+ 1)
* am Besten Formeln aufschreiben \newline % Row Count 2 (+ 1)
{\bf{May Live:}} * backwards analysis \newline % Row Count 3 (+ 1)
Live(l) = Read(l) ∪ ∪`l-\textgreater{}l'` (Live(l') \textbackslash{} Write(l)),  \newline % Row Count 5 (+ 2)
l' folgender Block \newline % Row Count 6 (+ 1)
{\bf{Must Live:}} * backwards \newline % Row Count 7 (+ 1)
MLive(l) = Read(l) ∪ ∩`l-\textgreater{}l'`(MLive(l') \textbackslash{} Write(l)) \newline % Row Count 9 (+ 2)
{\bf{MayUsed:}} * forwards \newline % Row Count 10 (+ 1)
U(l) = Read(l) ∪ ∪`l'-\textgreater{}l`(U(l') ∪ Write(l)) \newline % Row Count 11 (+ 1)
{\bf{MustUsed:}} * forwards \newline % Row Count 12 (+ 1)
MustU(l) = Read(l) ∪ ∩`l'-\textgreater{}l`(MustU(l') ∪ Write(l)) \newline % Row Count 14 (+ 2)
{\bf{Busy:}} * backwards \newline % Row Count 15 (+ 1)
B(l) = Read(l) ∪ ∩`l-\textgreater{}l'`(B(l') \textbackslash{} Write(l))% Row Count 16 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{0.84609 cm} x{4.13091 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Pipeline}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{CISC}} & register memory architecture {\emph{ machinewords different length * many }}complex* irregular instructions \tn 
% Row Count 4 (+ 4)
% Row 1
\SetRowColor{white}
{\bf{RISC}} & {\emph{ register register architecture }} as few as posible \& as regulas as possible instructions * machine words same length \tn 
% Row Count 8 (+ 4)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{shared subtrees in syntaxtrees: DAG \newline -\textgreater{} {\emph{optimaler code für DAGs ist NP-vollst{\"a}ndig}} \newline {\bf{MSB (Most Significant Bit):}} linkestes Bit (h{\"o}chste Potenz) \newline {\bf{LSB (Least):}} rechts \newline {\bf{vollassoziiert:}} wenn Cache 1 Satz (freie Speicherwahl) \newline n-fach assoziativ: n = N`k` \newline {\bf{Bootstrapping:}} Aneinanderschalten von Compilern \newline -\textgreater{} kein extra Compiler \newline {\bf{L/S-Architektur:}} Befehlssatz Daten-Speicherzugriffe nur mit L/S Befehlen \newline -\textgreater{} RISC \newline -\textgreater{} CISC hat auch ALU (arithmetic \& logic unit)}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Virtueller Speicher}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{* {\bf{TLB:}} Translation-Lookaside Buffer \newline % Row Count 1 (+ 1)
* {\bf{Pagetable}} ist im HS% Row Count 2 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


% That's all folks
\end{multicols*}

\end{document}