\documentclass[a4paper,11pt,titlepage]{article}
\usepackage{epsfig}
\usepackage{texdraw}
\usepackage{wasysym}
\usepackage{german}
\selectlanguage{\austrian}
\begin{document}
\titlepage
\title{Rechnerarchitekturen\\
Labor"ubung\\
Beispiel 3\\
}
\date{ SS 1998}
\author{Alexander "Olzant\\
9301547}
\maketitle

\section{Aufgabe 1}

C-Programm zur Erstellung des Traces
\begin{verbatim}
int i, ai, bi, ci, di, ei;
int a[1024], b[1024], c[1024], d[1024], e[1024];
void compute()
{

        ai=0; 
        bi=0; 
        ci=0; 
        di=0; 
        ei=0;
         printf("; compute:\n");
        printf("2 1000         ;move $9,0\n");
        printf("2 1004         ;la $8,a\n");
        printf("2 1008         ;la $7,b\n");
        printf("2 100c         ;la $6,c\n");
        printf("2 1010         ;la $5,d\n");
        printf("2 1014         ;la $4,e\n");

        for (i=0; i<1000; i++) {
                
                 printf("; $L11:\n");
                printf("2 1018         ;lw $3,0($6)\n");
                printf("0 %x         \n",0x4000+ci*4);
                printf("2 101c         ;addu $6, $6, (4*n)=28\n");
                printf("2 1020         ;lw $2,0($7)\n");
                printf("0 %x \n",0x3000+bi*4);
                printf("2 1024         ;addu $7, $7, 4\n");
                printf("2 1028         ;addu $2, $2, $3\n");
                printf("2 102c         ;sw $2,0($8)\n");
                printf("1 %x \n",0x2000+ai*4);
                printf("2 1030         ;addu $9, $9, 1\n");

                a[ai++] = c[ci] + b[bi++];
                ci += 7 /* (9301547 % 10)*4*/; /* 28 */

                printf("2 1034         ;lw $3,0($4)\n");
                printf("0 %x \n",0x6000+ei*4);
                printf("2 1038         ;addu $4, $4, 4\n");
                printf("2 103c         ;lw $2,0($5)\n");
                printf("0 %x \n",0x5000+di*4);
                printf("2 1040         ;addu $5, $5, 4\n");
                printf("2 1044         ;addu $2, $2, $3\n");
                printf("2 1048         ;sw $2,0($6)\n");
                printf("1 %x \n",0x4000+ci*4);
                printf("2 104c         ;addu $8, $8, 4\n");

                c[ci] = d[di++] + e[ei++];
                ci -= 6 /*((9301547 % 10) - 1) * (-4)*/; /* -24 */

                printf("2 104c         ;slt $2, $9, 1000\n");
                printf("2 1050         ;addu $6, $6, (-4*(n-1))=-24\n");
                printf("2 1054         ;bne $2, $0, $L11\n");

                
        };
        printf("2 1058         ;j $31\n");
        printf(".end        compute\n");
};                          

main()
{
        compute();
}
\end{verbatim}

\section{Aufgabe 2}

Hier ein Auszug aus dem Tracefile:
\begin{verbatim}

; compute:
2 1000 	;move $9,0
2 1004 	;la $8,a
2 1008 	;la $7,b
2 100c 	;la $6,c
2 1010 	;la $5,d
2 1014 	;la $4,e
; $L11:
2 1018 	;lw $3,0($6)
0 4000 	
2 101c 	;addu $6, $6, (4*n)=28
2 1020 	;lw $2,0($7)
0 3000 
2 1024 	;addu $7, $7, 4
2 1028 	;addu $2, $2, $3
2 102c 	;sw $2,0($8)
1 2000 
2 1030 	;addu $9, $9, 1
2 1034 	;lw $3,0($4)
0 6000 
2 1038 	;addu $4, $4, 4
2 103c 	;lw $2,0($5)
0 5000 
2 1040 	;addu $5, $5, 4
2 1044 	;addu $2, $2, $3
2 1048 	;sw $2,0($6)
1 401c 
2 104c 	;addu $8, $8, 4
2 104c 	;slt $2, $9, 1000
2 1050 	;addu $6, $6, (-4*(n-1))=-24
2 1054 	;bne $2, $0, $L11

...
\end{verbatim}
Ad nauseam ac infinitum\footnote{473143 Oktette, abrufbar unter http://prawda.oeh.net/\~{ }aoe/trash/prod.din}.


\section{Aufgabe 3}

\begin{table}
% GNUPLOT: LaTeX using TEXDRAW macros
\begin{texdraw}
\normalsize
\ifx\pathDEFINED\relax\else\let\pathDEFINED\relax
 \def\QtGfr{\ifx (\TGre \let\YhetT\cpath\else\let\YhetT\relax\fi\YhetT}
 \def\path (#1 #2){\move (#1 #2)\futurelet\TGre\QtGfr}
 \def\cpath (#1 #2){\lvec (#1 #2)\futurelet\TGre\QtGfr}
\fi
\drawdim pt
\setunitscale 0.24
\linewd 3
\textref h:L v:C
\linewd 4
\path (220 113)(240 113)
\path (1436 113)(1416 113)
\move (198 113)\textref h:R v:C \htext{5000}
\path (220 257)(240 257)
\path (1436 257)(1416 257)
\move (198 257)\htext{10000}
\path (220 401)(240 401)
\path (1436 401)(1416 401)
\move (198 401)\htext{15000}
\path (220 544)(240 544)
\path (1436 544)(1416 544)
\move (198 544)\htext{20000}
\path (220 688)(240 688)
\path (1436 688)(1416 688)
\move (198 688)\htext{25000}
\path (220 832)(240 832)
\path (1436 832)(1416 832)
\move (198 832)\htext{30000}
\path (220 113)(220 133)
\path (220 832)(220 812)
\move (220 68)\textref h:C v:C \htext{1}
\path (524 113)(524 133)
\path (524 832)(524 812)
\move (524 68)\htext{2}
\path (828 113)(828 133)
\path (828 832)(828 812)
\move (828 68)\htext{4}
\path (1132 113)(1132 133)
\path (1132 832)(1132 812)
\move (1132 68)\htext{8}
\path (1436 113)(1436 133)
\path (1436 832)(1436 812)
\move (1436 68)\htext{16}
\path (220 113)(1436 113)(1436 832)(220 832)(220 113)
\move (45 472)\vtext{Total Traffic}
\move (828 23)\htext{Associativity}
\move (828 877)\htext{unified cache 512 o}
\move (1306 767)\textref h:R v:C \htext{LRU}
\linewd 3
\path (1328 767)(1394 767)
\path (220 783)(220 783)(524 734)(828 769)(1132 172)(1436 172)
\move (1350 767)
\textref h:C v:C \rmove(0 4)\htext{$\Diamond$}
\move (220 783)
\rmove(0 4)\htext{$\Diamond$}
\move (524 734)
\rmove(0 4)\htext{$\Diamond$}
\move (828 769)
\rmove(0 4)\htext{$\Diamond$}
\move (1132 172)
\rmove(0 4)\htext{$\Diamond$}
\move (1436 172)
\rmove(0 4)\htext{$\Diamond$}
\move (1306 722)\textref h:R v:C \htext{random}
\linewd 4
\path (1328 722)(1394 722)
\path (220 783)(220 783)(524 728)(828 565)(1132 322)(1436 278)
\move (1350 722)
\textref h:C v:C \htext{$+$}
\move (220 783)
\htext{$+$}
\move (524 728)
\htext{$+$}
\move (828 565)
\htext{$+$}
\move (1132 322)
\htext{$+$}
\move (1436 278)
\htext{$+$}
\move (1306 677)\textref h:R v:C \htext{FIFO}
\linewd 6
\path (1328 677)(1394 677)
\path (220 783)(220 783)(524 737)(828 776)(1132 194)(1436 200)
\move (1350 677)
\textref h:C v:C \rmove(0 4)\htext{$\Box$}
\move (220 783)
\rmove(0 4)\htext{$\Box$}
\move (524 737)
\rmove(0 4)\htext{$\Box$}
\move (828 776)
\rmove(0 4)\htext{$\Box$}
\move (1132 194)
\rmove(0 4)\htext{$\Box$}
\move (1436 200)
\rmove(0 4)\htext{$\Box$}
\end{texdraw}
\\
\begin{tabular}{l@{\hspace{1cm}\hspace{1cm}}rrrrr}
Assoziativit"at &	LRU &	random &	FIFO \\
\hline 
1 &	28292 &	28292 &	28292\\
2 &	26576 &	26384 &	26704\\
4 &	27796 &	20732  & 28044\\
8 &	7040 &	12280 &	7812\\
16 &	7040 &	10728 &	8024
\end{tabular}
\end{table}
\\
\begin{table}
% GNUPLOT: LaTeX using TEXDRAW macros
\begin{texdraw}
\normalsize
\ifx\pathDEFINED\relax\else\let\pathDEFINED\relax
 \def\QtGfr{\ifx (\TGre \let\YhetT\cpath\else\let\YhetT\relax\fi\YhetT}
 \def\path (#1 #2){\move (#1 #2)\futurelet\TGre\QtGfr}
 \def\cpath (#1 #2){\lvec (#1 #2)\futurelet\TGre\QtGfr}
\fi
\drawdim pt
\setunitscale 0.24
\linewd 3
\textref h:L v:C
\linewd 4
\path (220 113)(240 113)
\path (1436 113)(1416 113)
\move (198 113)\textref h:R v:C \htext{6000}
\path (220 178)(240 178)
\path (1436 178)(1416 178)
\move (198 178)\htext{8000}
\path (220 244)(240 244)
\path (1436 244)(1416 244)
\move (198 244)\htext{10000}
\path (220 309)(240 309)
\path (1436 309)(1416 309)
\move (198 309)\htext{12000}
\path (220 374)(240 374)
\path (1436 374)(1416 374)
\move (198 374)\htext{14000}
\path (220 440)(240 440)
\path (1436 440)(1416 440)
\move (198 440)\htext{16000}
\path (220 505)(240 505)
\path (1436 505)(1416 505)
\move (198 505)\htext{18000}
\path (220 571)(240 571)
\path (1436 571)(1416 571)
\move (198 571)\htext{20000}
\path (220 636)(240 636)
\path (1436 636)(1416 636)
\move (198 636)\htext{22000}
\path (220 701)(240 701)
\path (1436 701)(1416 701)
\move (198 701)\htext{24000}
\path (220 767)(240 767)
\path (1436 767)(1416 767)
\move (198 767)\htext{26000}
\path (220 832)(240 832)
\path (1436 832)(1416 832)
\move (198 832)\htext{28000}
\path (220 113)(220 133)
\path (220 832)(220 812)
\move (220 68)\textref h:C v:C \htext{1}
\path (524 113)(524 133)
\path (524 832)(524 812)
\move (524 68)\htext{2}
\path (828 113)(828 133)
\path (828 832)(828 812)
\move (828 68)\htext{4}
\path (1132 113)(1132 133)
\path (1132 832)(1132 812)
\move (1132 68)\htext{8}
\path (1436 113)(1436 133)
\path (1436 832)(1436 812)
\move (1436 68)\htext{16}
\path (220 113)(1436 113)(1436 832)(220 832)(220 113)
\move (45 472)\vtext{Total Traffic}
\move (828 23)\htext{Associativity}
\move (828 877)\htext{non unified cache (256 o instruction/data)}
\move (1306 767)\textref h:R v:C \htext{LRU}
\linewd 3
\path (1328 767)(1394 767)
\path (220 765)(220 765)(524 752)(828 768)(1132 147)(1436 147)
\move (1350 767)
\textref h:C v:C \rmove(0 4)\htext{$\Diamond$}
\move (220 765)
\rmove(0 4)\htext{$\Diamond$}
\move (524 752)
\rmove(0 4)\htext{$\Diamond$}
\move (828 768)
\rmove(0 4)\htext{$\Diamond$}
\move (1132 147)
\rmove(0 4)\htext{$\Diamond$}
\move (1436 147)
\rmove(0 4)\htext{$\Diamond$}
\move (1306 722)\textref h:R v:C \htext{random}
\linewd 4
\path (1328 722)(1394 722)
\path (220 765)(220 765)(524 724)(828 486)(1132 308)(1436 239)
\move (1350 722)
\textref h:C v:C \htext{$+$}
\move (220 765)
\htext{$+$}
\move (524 724)
\htext{$+$}
\move (828 486)
\htext{$+$}
\move (1132 308)
\htext{$+$}
\move (1436 239)
\htext{$+$}
\move (1306 677)\textref h:R v:C \htext{FIFO}
\linewd 6
\path (1328 677)(1394 677)
\path (220 765)(220 765)(524 752)(828 768)(1132 155)(1436 156)
\move (1350 677)
\textref h:C v:C \rmove(0 4)\htext{$\Box$}
\move (220 765)
\rmove(0 4)\htext{$\Box$}
\move (524 752)
\rmove(0 4)\htext{$\Box$}
\move (828 768)
\rmove(0 4)\htext{$\Box$}
\move (1132 155)
\rmove(0 4)\htext{$\Box$}
\move (1436 156)
\rmove(0 4)\htext{$\Box$}
\end{texdraw}
\\
\begin{tabular}{l@{\hspace{1cm}\hspace{1cm}}rrrrr}
Assoziativit"at &	LRU &	random &	FIFO \\
                        \hline 
%% 256 o instruction, 256 o data chache:
1 &	25956 &	25956 &	25956\\
2 &	25552 &	24696 &	25552\\
4 &	26048 &	17404 &	26048\\
8 &	7040 &	11952 &	7288\\
16 &	7040 &	9848 &	7324 
\end{tabular}
\end{table}
\\
\\
\begin{table}

% GNUPLOT: LaTeX using TEXDRAW macros
\begin{texdraw}
\normalsize
\ifx\pathDEFINED\relax\else\let\pathDEFINED\relax
 \def\QtGfr{\ifx (\TGre \let\YhetT\cpath\else\let\YhetT\relax\fi\YhetT}
 \def\path (#1 #2){\move (#1 #2)\futurelet\TGre\QtGfr}
 \def\cpath (#1 #2){\lvec (#1 #2)\futurelet\TGre\QtGfr}
\fi
\drawdim pt
\setunitscale 0.24
\linewd 3
\textref h:L v:C
\linewd 4
\path (220 113)(240 113)
\path (1436 113)(1416 113)
\move (198 113)\textref h:R v:C \htext{25000}
\path (220 185)(240 185)
\path (1436 185)(1416 185)
\move (198 185)\htext{30000}
\path (220 257)(240 257)
\path (1436 257)(1416 257)
\move (198 257)\htext{35000}
\path (220 329)(240 329)
\path (1436 329)(1416 329)
\move (198 329)\htext{40000}
\path (220 401)(240 401)
\path (1436 401)(1416 401)
\move (198 401)\htext{45000}
\path (220 473)(240 473)
\path (1436 473)(1416 473)
\move (198 473)\htext{50000}
\path (220 544)(240 544)
\path (1436 544)(1416 544)
\move (198 544)\htext{55000}
\path (220 616)(240 616)
\path (1436 616)(1416 616)
\move (198 616)\htext{60000}
\path (220 688)(240 688)
\path (1436 688)(1416 688)
\move (198 688)\htext{65000}
\path (220 760)(240 760)
\path (1436 760)(1416 760)
\move (198 760)\htext{70000}
\path (220 832)(240 832)
\path (1436 832)(1416 832)
\move (198 832)\htext{75000}
\path (220 113)(220 133)
\path (220 832)(220 812)
\move (220 68)\textref h:C v:C \htext{10}
\path (403 113)(403 123)
\path (403 832)(403 822)
\move (403 68)\htext{}
\path (510 113)(510 123)
\path (510 832)(510 822)
\move (510 68)\htext{}
\path (586 113)(586 123)
\path (586 832)(586 822)
\move (586 68)\htext{}
\path (645 113)(645 123)
\path (645 832)(645 822)
\move (645 68)\htext{}
\path (693 113)(693 123)
\path (693 832)(693 822)
\move (693 68)\htext{}
\path (734 113)(734 123)
\path (734 832)(734 822)
\move (734 68)\htext{}
\path (769 113)(769 123)
\path (769 832)(769 822)
\move (769 68)\htext{}
\path (800 113)(800 123)
\path (800 832)(800 822)
\move (800 68)\htext{}
\path (828 113)(828 133)
\path (828 832)(828 812)
\move (828 68)\htext{100}
\path (1011 113)(1011 123)
\path (1011 832)(1011 822)
\move (1011 68)\htext{}
\path (1118 113)(1118 123)
\path (1118 832)(1118 822)
\move (1118 68)\htext{}
\path (1194 113)(1194 123)
\path (1194 832)(1194 822)
\move (1194 68)\htext{}
\path (1253 113)(1253 123)
\path (1253 832)(1253 822)
\move (1253 68)\htext{}
\path (1301 113)(1301 123)
\path (1301 832)(1301 822)
\move (1301 68)\htext{}
\path (1342 113)(1342 123)
\path (1342 832)(1342 822)
\move (1342 68)\htext{}
\path (1377 113)(1377 123)
\path (1377 832)(1377 822)
\move (1377 68)\htext{}
\path (1408 113)(1408 123)
\path (1408 832)(1408 822)
\move (1408 68)\htext{}
\path (1436 113)(1436 133)
\path (1436 832)(1436 812)
\move (1436 68)\htext{1000}
\path (220 113)(1436 113)(1436 832)(220 832)(220 113)
\move (45 472)\vtext{Total Traffic}
\move (828 23)\htext{Associativity}
\move (828 877)\htext{different cache sizes (1 - 512 octets)}
\move (1306 767)\textref h:R v:C \htext{"diagsize.plot"}
\linewd 3
\path (1328 767)(1394 767)
\path (344 789)(344 789)(527 674)(710 566)(893 301)(1076 208)
\cpath (1259 160)
\move (1350 767)
\textref h:C v:C \rmove(0 4)\htext{$\Diamond$}
\move (344 789)
\rmove(0 4)\htext{$\Diamond$}
\move (527 674)
\rmove(0 4)\htext{$\Diamond$}
\move (710 566)
\rmove(0 4)\htext{$\Diamond$}
\move (893 301)
\rmove(0 4)\htext{$\Diamond$}
\move (1076 208)
\rmove(0 4)\htext{$\Diamond$}
\move (1259 160)
\rmove(0 4)\htext{$\Diamond$}
\end{texdraw}

\begin{tabular}{l@{\hspace{1cm}\hspace{1cm}}rrrrr}
Cachegr"osse (Oktette)	& Traffic\\
                        \hline
16	& 72016\\
32	& 64012\\
64	& 56492\\
128	& 38056\\
256	& 31620\\
512	& 28292
\end{tabular}
\end{table}

\newpage
\section{Aufgabe 4}

Bei kleiner Assoziativit"at ist teilweise random besser,
ab 8-fach assoziativem cache schneidet LRU aber besser ab.

Unified caches sind oft die bessere Wahl (bessere Verteilung bei
unterschiedlicher lokalit"at), k"onnen aber die Leistung negativ 
beeinflussen, wenn die Daten sehr viel weniger lokalisiert sind
als der Programmcode, der dann st"andig ersetzt wird.

Meine Pr"aferenz: Mittelgrosser Non-unified Cache mit m"oglichst hoher 
Assoziativit"at

\subsection{Warum ist der Cache effizient?}

Grunds"atzlich ist der CPU-nahe, schnelle Speicher den in der 
Speicherhierarchie weiter unten stehenden immer vorzuziehen.
In diesem speziellen Fall ist ein großer Performancegewinn zwischen
4 und 8-facher Assoziativit"at festzustellen.

\subsection{Wie erkl"aren Sie die verschiedenen Steigungen derKurven bei
verschiedener Assoziativit"at?} 
signifikanter Sprung zwischen assoz=2 und assoz=4, da die adressen von
programm und daten (0x2000, 0x3000 ...) dann halbwegs gleichzeitig
im cache bahalten werden k"onnen. diese werden jeweils in das gleiche
set des cache geladen, soda"s viele conflict misses auftreten.

\subsection{Welche Vorteile haben die Replacementstrategien?}
random: leicht zu implmentieren, bei grossen Speichern sehr gut
LRU: weniger Gefahr des Replacement f"ur h"aufig verwendete code/datenteile:
  gut f"ur kleine caches; aufwendiger!
FIFO: durch temporal locality k"onnen wichtige bl"ocke relativ lange gecached
 werden, allerdings werden sie jedenfalls irgendwann ersatzt -- un
 unwichtige cacheteile bleiben relativ lange aktiv. kaum vorteile.

\subsection{Wie und warum teilen Sie die 512 Worte auf Daren- und 
Instruktionscache auf?}

Da Instruktionscaches "uber 256 Oktette keine signifikante Verbesserung
mehr bringen, scheint die f"ur dieses Programmst"uck beste Aufteilung
jeweils 256 Oktette Daten- und Instruktionscache darzustellen.


\end{document}