% TI II: Rechnerarchitektur SoSe 2010 % MMIX - Seitenverdrängungsstrategie LRU % von Matthias Dräger % % Aufgabe: % Implementieren Sie die Seitenverdrängungsstrategie LRU (Least Recently Used) % für einen Cache mit vier Seiten. % % Hinweis: % Das Programm fragt in einer Endloschleife nach Zahlen und kann mit der Eingabe q % beendet werden. % % Dieses Programm enhält folgende Unterprogramme: % cacheLookup - Sucht im Cache eine Zahl und gibt ggfs. die Position zurück % Input - Einlesen von der Standardeingabe % atoi - Konvertierung der Eingabe in eine Zahl % % Die Unterprogramme countDigits, showCache, printChar und printNo werden für % die graphische Ausgabe benutzt. Deren Funktionsweise ist nicht von Bedeutung. % % Falls Warnungen beim Assemblieren auftreten, dann den Parameter -b 200 benutzen. % mmixal -b 200 rahmen.mms LOC Data_Segment GREG @ % Konfiguration CacheSize IS 4 % der Cache besteht aus 4 Seiten Cache OCTA 5,2,4,9 % Anfangswerte im Cache % Hinweis: An der ersten Position des Caches steht die zuletzt referenzierte (benutzte) Seite (Zahl). % Kommt es zu einem Cache-Miss, so verschwindet die letzte Seite (Zahl) aus dem Cache und die neue % Zahl kommt an die erste Posision des Caches. maxLength IS 3 % Zahlen sollen maximal drei Digits lang sein InputBufSize IS 200 AdrBuffer IS @ InputBuffer BYTE 0,0 LOC @+InputBufSize+10 GREG @ InputParam OCTA AdrBuffer,InputBufSize % Parameter für die Standard-Eingabe StdIn erstellen % Texte für die Ausgabe anlegen Request BYTE "Gib eine Zahl ein, die im Cache gesucht werden soll (max. 3 Stellen): ",0 ErrZahlTxt BYTE #a,"Bei der Eingabe handelt es sich nicht um eine dreistellige Zahl!",#a,#a,0 TxtHit BYTE #a,"Cache-HIT",#a,0 TxtMiss BYTE #a,"Cache-MISS",#a,0 TxtStat BYTE #a,#a,"Statistik",#a,"---------------",0 % Ausgabe Statisitik TxtStatHit BYTE #a,"Hits: ",0 TxtStatMiss BYTE #a,"Misses: ",0 % Deklarationen für die Ausgabe OutputBuf BYTE 0,0 % Ein Zeichen für die Ausgabe einer Ziffer reservieren TxtNL BYTE #a,0 % Zeilenumbruch Txt1Trenn BYTE "| ",0 % erste senkrechte Linie TxtTrenn BYTE " | ",0 % Trennzeichen zwischen den Zahlen Fuellung IS 2 % Anzahl Leerzeichen bei TxtTrenn LOC #100 % Das Programm beginnt, wir springen zur Adresse #100 % % Hier beginnt das Hauptprogramm % char IS $7 tmp IS $6 eingabe IS $5 % Benutzereingabe zahl IS $4 % gesuchte Zahl cacheres IS $3 % Antwort von LRU hits IS $0 % zählt die Cache-Hits misses IS $1 % zählt die Cache-Misses Main SET hits,0 PUSHJ $0,:showCache:begin % Cache zeigen % Eingabe der Zahl anfrage PUSHJ eingabe,:Input:begin % Eingabe vom Benutzer LDB char,eingabe % lade erstes Zeichen CMP tmp,char,'q' % vergleiche mit q BZ tmp,quit % wenn gleich, verlasse Programm PUSHJ zahl,:atoi:begin % Zahl konvertieren BNN zahl,insert % kein Fehler? -> springen LDA $255,ErrZahlTxt % Fehlertext laden TRAP 0,Fputs,StdOut % und ausgeben JMP anfrage % nochmal Anfrage stellen insert PUSHJ cacheres,:LRU:begin % Cache-Anfrage stellen BP cacheres,cachehit % Cache-Hit? -> springe LDA $255,TxtMiss % Text Cache-Miss laden TRAP 0,Fputs,StdOut % und ausgeben ADD misses,misses,1 % Miss-Counter erhöhen JMP show cachehit LDA $255,TxtHit % Text Cache-Hit laden TRAP 0,Fputs,StdOut % und ausgeben ADD hits,hits,1 % Hit-Counter erhöhen show PUSHJ $10,:showCache:begin % Cache zeigen JMP anfrage % neue Anfrage stellen quit LDA $255,TxtStat % Text laden TRAP 0,Fputs,StdOut % und ausgeben LDA $255,TxtStatHit TRAP 0,Fputs,StdOut SET $3,hits % Hits nach $3 speichern PUSHJ $2,:printNo:begin % Zahl ausgeben LDA $255,TxtStatMiss TRAP 0,Fputs,StdOut SET $3,misses PUSHJ $2,:printNo:begin % Zahl ausgeben LDA $255,TxtNL % Zeilenumruch ausgeben TRAP 0,Fputs,StdOut TRAP 0,Halt,0 % Programm beenden % Unterprogramm: LRU % Dieses Unterprogramm erwartet eine Zahl, die im Cache gesucht wird. Wurde die % gefunden, so wird der Cache nach dem LRU-Prinzip umsortiert und eine 1 % zurückgegeben. Wenn nicht, dann wird umsortiert, wobei die neue Zahl an % die erste Position im Cache landet und die letzte verschwindet. Es wird eine 0 % zurückgeliefert. % Eingabe-Parameter: $0 - Anfrage an den Cache (ganze Zahl) % Rückgabewerte: $0 - 1 bei Erfolg (Hit), 0 bei Misserfolg (Miss) PREFIX :LRU: number IS $0 % zu suchende Nummer im Cache CacheAddr IS $1 % Adresse des Caches im Speicher CacheNo IS $2 % Zahl aus dem Cache rJAdr IS $3 % Rücksprungadresse begin GET rJAdr,:rJ % Rücksprungadresse sichern LDA CacheAddr,:Cache % Adresse des Caches holen % % Hier muss der LRU-Algorithmus implementiert werden % PUT :rJ,rJAdr POP 1,0 % Unterprogramm: cacheLookup % Die übergebene Zahl wird im Cache gesucht und bei Fund dessen Position % zurückgegeben. Wurde die Zahl nicht gefunden, wird -1 zurückgeliefert. % Eingabe-Parameter: $0 - zu suchende Zahl % Rückgabewerte: $0 - Position im Cache (Erfolg), -1 (Misserfolg) PREFIX :cacheLookup: number IS $0 % zu suchende Nummber CacheAddr IS $1 % Adresse des Caches CacheNo IS $2 % Zahl aus dem Cache pos IS $3 % Position im Cache tmp IS $4 % Hilfsvariable begin LDA CacheAddr,:Cache % Adresse des Caches holen loop 8ADDU tmp,pos,CacheAddr % berechne Octa-Adresse LDO CacheNo,tmp % hole Zahl aus Cache an Position pos CMP tmp,number,CacheNo % vergleiche Zahlen BZ tmp,success % sind gleich? -> pos zurückgeben ADD pos,pos,1 % Position inkrementieren CMP tmp,pos,:CacheSize % vergleiche Position mit Cachegröße PBN tmp,loop % wiederhole solange pos < CacheSize NEG $0,1 % Zahl nicht im Cache gefunden -> -1 zurück geben POP 1,0 success SET $0,pos % liefere Position also Rückgabewert POP 1,0 % Unterprogramm: input % Dieses Unterprogramm fordert den Benutzer auf eine Zahl einzugeben % und speichert die Eingabe in einem Buffer. Die Adresse des Buffers wird zurück % gegeben. % Eingabe-Parameter: keine % Rückgabewerte: $0 - Adresse der eingegebenen Zeichenkette PREFIX :Input: BufferAddr IS $0 ParamAddr IS $1 i IS $2 begin LDA BufferAddr,:InputBuffer SET i,:InputBufSize SET $3,0 loop STB $3,BufferAddr,i % Buffer zurücksetzen, also mit 0en auffüllen SUB i,i,1 PBNN i,loop XOR $255,$255,$255 % Register 255 zurücksetzen LDA $255,:Request % Useranfrage ausgeben TRAP 0,:Fputs,:StdOut XOR $255,$255,$255 % Register 255 zurücksetzen LDA $255,:InputParam % Adresse des Parameters laden TRAP 0,:Fgets,:StdIn % von der Standardeingabe werden die Zeichen in den Buffer gespeichert POP 1,0 % BufferAddr an das Hauptprogramm zurückgeben % Unterprogramm: atoi % Konvertiert eine Zeichenkette in eine positive Zahl. Sollte ein Fehler auftreten, % gibt das Programm -1 zurück. % Eingabe-Parameter: $0 - Adresse der Zeichenkette, die umgewandelt werden soll % Rückgabewerte: $0 - die konvertierte Zahl oder -1 bei Fehler PREFIX :atoi: StringAddr IS $0 % enthält die Adresse der zu konvertierenden Zeichenkette number IS $1 i IS $2 % Laufvariable char IS $3 % das aktuelle zu konvertierende Zeichen tmp IS $4 % Hilfsvariable begin SET i,0 % Laufvariable mit 0 initialisieren SET number,0 % Zahl mit 0 initialisieren Loop LDB char,StringAddr,i % lade i-tes Zeichen (wir fangen bei 0 an!) BZ char,endloop % prüfe auf terminierendes Zeichen (0) -> springe zum Schleifenende CMP tmp,char,#a % prüfe, ob Zeichen ein Zeilenumbruch ist BZ tmp,endloop % wenn ja, springe zum Schleifenende % Es wird nun überprüft, ob sich das aktuelle Zeichen im ASCII-Bereich % zwischen 48 (der '0') und 57 (der '9') befindet. CMP tmp,char,'0' % Vergleiche char mit dem ASCII-Zeichen '0' BN tmp,ErrorZahl % falls das Zeichen kleiner 48 -> keine Zahl, springe zur Fehlerausgabe CMP tmp,char,'9' % Vergleiche nun mit ASCII-zeichen '9' BP tmp,ErrorZahl % falls das Zeichen größer 57 -> keine Zahl, springe zur Fehlerausgabe % das aktuelle Zeichen ist im ASCII-Bereich 48-57 % es werden nun 48 abgezogen, um die richtige Ziffer zu besitzen SUB char,char,48 MUL number,number,10 % unsere Ergebnis-Zahl wird erst mit 10 multipliziert ADD number,number,char % und anschließend die eben konvertierte Ziffer hinzuaddiert (Horner-Schema) ADD i,i,1 % erhöhe die Zählvariable CMP tmp,i,:maxLength % prüfen, ob die Maximallänge erreicht BP tmp,ErrorZahl JMP Loop % springe zum Schleifenanfang endloop BZ i,ErrorZahl % falls nicht eingegeben wurde -> Fehler zurückgeben SET $0,number % die konvertierte Zahl ins Rückgaberegister $0 schreiben POP 1,0 % den Wert von $0 dem Hauptprogramm zurückliefern % beim Auftreten eines Fehlers -> -1 zurückgeben ErrorZahl NEG $0,1 % -1 in $0 schreiben POP 1,0 % -1 zurückliefern % Unterprogramm: countDigits % Gibt die Anzahl der Stellen von der übergegebenen Zahl zurück. % Eingabe-Parameter: $0 - Ganze Zahl % Rückgabewerte: $0 - Anzahl Stellen PREFIX :countDigits: number IS $0 i IS $1 % Laufvariable begin SET i,0 % Laufvariable mit 0 initialisieren loop ADD i,i,1 % Variable um 1 erhöhen DIV number,number,10 % Zahl durch 10 teilen PBNZ number,loop % Zahl > 0? dann weiter rechnen SET $0,i % Rückgabewert in $0 schreiben POP 1,0 % den Wert von $0 zurückliefern % Unterprogramm: showCache % Gibt den derzeitigen Cache graphisch aus. % Eingabe-Parameter: keine % Rückgabewerte: keine PREFIX :showCache: CacheAddr IS $0 % enthält die Adresse der zu konvertierenden Zeichenkette rJAdr IS $1 % Rücksprungadresse pos IS $2 % Cache-Position anzahl IS $3 tmp IS $4 % Hilfsvariable number IS $5 % Zahl aus dem Cache char IS $6 % das aktuelle zu konvertierende Zeichen begin SET pos,0 % Position initialisieren SET anzahl,0 LDA CacheAddr,:Cache % Adresse des Caches holen GET rJAdr,:rJ % Rücksprungadresse sichern loop 8ADDU tmp,pos,CacheAddr % berechne Octa-Adresse LDO number,tmp % hole Zahl an Position pos PUSHJ tmp,:countDigits:begin ADD anzahl,anzahl,tmp % für jedes Digit einen Strich ausgeben ADD anzahl,anzahl,:Fuellung % Leerzeichen-Auffuellung beachten ADD pos,pos,1 % pos inkrementieren CMP tmp,pos,:CacheSize % vergleiche Position mit Cache-Größe PBN tmp,loop % wiederhole solange pos < CacheSize ADD anzahl,anzahl,:CacheSize % Anzahl Cache-Elemente hinzuaddieren SET $10,'-' SET $11,anzahl PUSHJ $9,:printChar:begin % Erste Zeile ausgeben LDA $255,:TxtNL % Adresse des Zeilenumbruchs holen TRAP 0,:Fputs,:StdOut % Zeilenumbruch ausgeben LDA $255,:Txt1Trenn % Trenner zwischen den Zahlen TRAP 0,:Fputs,:StdOut % Zeilenumbruch ausgeben % hier folge die Ausgabe der Zahlen aus dem Cache SET pos,0 % position mit 0 initialisieren loopZahl 8ADDU tmp,pos,CacheAddr % berechne Octa-Adresse LDO number,tmp PUSHJ tmp,:printNo:begin % Zahl ausgeben LDA $255,:TxtTrenn % Trenner zwischen den Zahlen TRAP 0,:Fputs,:StdOut % Zeilenumbruch ausgeben ADD pos,pos,1 % pos incrementieren CMP tmp,pos,:CacheSize % vergleiche Position mit Cache-Größe PBN tmp,loopZahl % wiederhole solange pos < CacheSize LDA $255,:TxtNL % Adresse des Zeilenumbruchs holen TRAP 0,:Fputs,:StdOut % Zeilenumbruch ausgeben SET $10,'-' SET $11,anzahl PUSHJ $9,:printChar:begin % Letzte Zeile ausgeben LDA $255,:TxtNL % Adresse des Zeilenumbruchs holen TRAP 0,:Fputs,:StdOut % Zeilenumbruch ausgeben PUT :rJ,rJAdr % Rücksprungadresse zurück schreiben POP 0,0 % Unterprogramm: printChar % Gibt den derzeitigen Cache grafisch aus. % Eingabe-Parameter: $0 - auszugegebenes Zeichen % $1 - n-mal ausgeben % Rückgabewerte: keine PREFIX :printChar: char IS $0 % auszugegebenes Zeichen n IS $1 % Zeichen n-mal ausgeben adr IS $2 % Adresse des Output-Buffers begin LDA adr,:OutputBuf % Adresse holen STB char,adr % Zeichen in Buffer speichern loop SET $255,adr % Auszugebene Adresse in $255 speichern TRAP 0,:Fputs,:StdOut % Zeichen ausgeben SUB n,n,1 % n dekrementieren PBNN n,loop % wiederhole solange n >= 0 POP 0,0 % Unterprogramm verlassen % Unterprogramm: printNo % Gibt die übergebene Zahl auf die Standard-Ausgabe aus. % Hinweis: Dieses Unterprogramm ruft sich selbst rekursiv auf. % Eingabe-Parameter: $0 - positive ganze Zahl, die ausgegeben wird. % Rückgabewerte: keine PREFIX :printNo: number IS $0 digit IS $1 Adr_rJ IS $2 begin DIV number,number,10 % Zahl durch 10 teilen -> letzte Ziffer steht jetzt in rR GET digit,:rR % Divisionsrest aus Spezialregister rR laden ADD digit,digit,'0' % um die Ziffer in ein ASCII-Zeichen umzuwandeln, '0' (=48) dazuaddieren BZ number,prntEnd % prüfen, ob die Zahl nun 0 ist (Rekursionsanker, d.h. zum Ende springen) GET Adr_rJ,:rJ % Rücksprungadresse aus Spezialregister rJ sichern SET $4,number % Zahl in $4 speichern, um rekursiver Aufruf zu ermöglichen PUSHJ $3,:printNo:begin % printNo rekursiv aufrufen -> $4 wird übergeben PUT :rJ,Adr_rJ % zwischengespeicherte Rücksprungadresse zurückschreiben prntEnd STBU digit,:OutputBuf % Ziffer in den Buffer schreiben LDA $255,:OutputBuf % Adresse des Buffers ins globale Register laden TRAP 0,:Fputs,:StdOut % Buffer (Ziffer) ausgeben POP 0,0 % Unterprogramm verlassen