2. Beispiel RA-LU 1998 Alexander Oelzant, 9301547 Aufgabe 1 --------- Statistik: mit forwarding ohne forwarding takte 346 451 stalls: raw 203(58.7%) 313(69.4%) ld 23 br/j 6 fl 174(85.7% RAW) WAW 0 0 struct 14 9 control 11 11 trap 21 3 sum 249 336(74.5%) branches: ges 7 7 taken 6 6 not ta 1 1 load/store: ges 32 32 ld 25 25 st 7 7 floating point: ges 35 35 add 5 5 mult 23 23 div 7 7 traps: 1 1 Analyse Das Programm ist mit forwarding 105 instruktionen, also etwa 25 % schneller. Dabei werden die RAW-stalls sogar um 35 % (relativ noch 11 %) reduziert, ausser ld, branch/jump- ud floatingpoint-stalls werden RAW-stalls durch forwarding unterbunden. Aufgabe 2 --------- Aufschlüsselung von Stalltypen und deren Vorkommen im Programm a) im Forwardingbetrieb: raw-stall (ld) bei sequenz: ld f2, x(r0) multd f4, f2, f2 Beschreibung: kann durch forwarding nicht verhindert werden, da das ld-ergebnis erst nach der MEM-Stufe vorliegen kann. Aus der MEM-Stufe wird dann aber direkt geforwardet. raw-stall (branch/jump): lw r10,i bnez r10, L3 da das ergebnis von lw erst nach der MEM-Stufe vorliegt und sprünge bereits in der ID audgeführt werden (können), müssten dazu die zu analysierenden registerinhalte schon zur verfügung stehen, sodass hier 2 stalls anfallen. raw-stall (floating point): multd f4, f2, f2 divd f2, f4, f0 Dieser RAW-Stall kann durch Forwarding nicht gelöst werden, da die Ausführung der Multiplikation länger als einen Takt dauert, bis zum Forwarding sind stalls notwendig. Nachfolge-Stalls: Im Anschluss an das vorhergehende Codestück treten strukturelle Hazards und damit ein stall auf, da ID durch multd besetzt ist und divd nicht geladen werden kann. Structural stall: divd f2, f4, f0 ld f10, sign(r0) multd f2, f2, f10 multd f8 f10, f10 Hier kann die erste multd-Anweisung den stall (warten auf ld&divd) beenden, die Zweite gerät aber sofort in einen Structural Stall, da EXE von der Ersten besetzt ist. control-stall: durch falsch vorhergesagte sprünge. Dies ist eigentlich kein stall, die verworfene IF-stufe kommt einem solchen aber gleich. trap-stall: Durch Entleeren der Pipeline usw. entsteht ein Stall von 21 Instruktionen. Dies wird andererseits bei seltenen Traps kaum ins Gewicht fallen. nop-Befehle im Programm: bnez r10, L3 nop beqz r10,L1 nop und j L2 nop Die nops treten nach den Sprungbefehlen auf. Da die MIPS delayed branches kennt, werden Sprünge erst nach der nächsten Instruktion ausgeführt, die daher vorsorglich auf nop gesetzt wird. Aufgabe 3 --------- Superskalaroptimierung: Es gilt, die Integerbefehle so umzuschreiben, daß zwei gleichzeitig bearbeitet werden können, also im Speicher hintereinander stehen. addi r12, r0, 0x5 slli r12, r12, 3 ld f0, w(r12) ld f2, x(r0) multd f4, f2, f2 grundsätzlich ist dies bei den gezeigten instruktionen der Fall, allerdings greifen addi und slli auf r12 zu. Durch Vereinfachung ds Codes könnten entweder slli und ld oder -- bei geeigneter speicherarchitektur (glaichzeitiger zugriff auf zwei speicherplätze) -- die beiden ld glaichzeitig ausgeführt werden. auch cvti2d f0, f4 subi r12,r10,0x1 könnten eventuell zugleich ausgeführt werden. Sinnvoller wäre die Umordnung: addd f2,f2,f10 ld f4,x multd f2,f2,f4 multd f2,f2,f4 ld f10,sign multd f8,f8,f10 könnte als addd f2,f2,f10 ld f4,x ld f10,sign multd f2,f2,f4 multd f2,f2,f4 multd f8,f8,f10 ausgeführt werden. Laufzeitoptimierung: -vermeidung der zwischenspeicherung der Schleifenvariable: sw i, r10 L2: lw r10, i bnez r10, L3 Wenn lw gestrichen wird, fallen 18 Takte und 12 Stalls (6 ld, 6 branch/j) weg subi r10, r10, 0x1 sw i, r10 j L2 Hier kann die Speicherung der Schleifenvariable wegfallen, wenn wie oben i auch nicht mehr zurückgelesen wird. Verbesserung: 4 Taktzyklen L2: lw r10, i bnez r10, L3 nop beqz r10, L1 nop L3: addi r11. r0. 0x1 wird bnez und sein nop gestrichen, läuft das Programm wegen der geringeren Schachtelung um 7 Zyklen schneller. multd f4, f2, f2 divd f2, f4, f0 ld f10, sign(r0) multd f2, f2, f10 multd f8 f10, f10 kann umgeschrieben werden zu multd f4, f2, f2 ld f10, sign(r0) divd f2, f4, f0 multd f8 f10, f10 multd f2, f2, f10 Verbesserung: 1 fl-stall, 4 struct-stalls. Die multd behindern sich kaum, da das erste abschliesst, bis das zweite das divd-ergebnis erhält und aus dem stall erwacht. Beispiel 3 ---------- teil 1/2: programm zur erstellung eines traces fuer den angegebenen assembler code ----------------- beginn von prod.c ------------------- int i, ai, bi, ci, di, ei; int a[1024], b[1024], c[1024], d[1024], e[1024]; void shove_numbers() { for (i=0; i<1000; i++) { printf("2 1018 ;lw $3,0($6) $L11:\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 ;sw $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"); }; }; main() { 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"); shove_numbers(); printf("2 1058 ;j $31\n"); printf(".end compute\n"); } ----------------- ende von prod.c ------------------- ----------------- beginn von prod.din ------------------- 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 2 1018 ;lw $3,0($6) $L11: 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 ;sw $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 2 1018 ;lw $3,0($6) $L11: 0 4004 2 101c ;addu $6, $6, (4*n)=28 ... ----------------- nicht das ende von prod.din -- noch 500 k ------------------- das vollständige prod-file kann unter http://prawda.oeh.net/~aoe/trash/prod.din eingesehen werden (sicher nicht interessant, prod.c oben kompiliert mit gcc sehr schön) Analyse: (jeweils 4-fach assoziativer cache, 512 bzw 256+256 k, blocksize 16k, write-back, write-allocate, LRU-Strategie) non-unified cache: unified cache: words read 20036 22280 /demand fetches .8708 .9684 w copied back 5004 5004 /demand writes 2.5020 2.5020 total 25040 27284 /demand fetches 1.0883 1.1858 demand access: total 23008 23008 instr 17007 17007 data 6001 6001 read 4001 4001 write 2000 2000 misses: total 5009 5570 instr 6 567 data 5003 5003 read 3752 3752 write 1251 1251 conclusio: ---------- unified caches haben bei stark lokalisierten programmen (dichter code mit wenigen weitsprüngen) leichte nachteile (10 % cache misses gegen ca. 1 %. bei eigenem programm-cache) vergleich der cachegrösse: (jeweils 4-fach assoziativer cache, unified cache, blocksize 16k, write-back, write-allocate, LRU-Strategie) 64 k 128 k 512 k words read 44008 32524 22280 /demand fetches 1.9127 1.4136 .9684 w copied back 8000 7004 5004 /demand writes 4.0000 3.5020 2.5020 total 52008 39528 27284 /demand fetches 2.2604 1.7180 1.1858 demand access: total 23008 . 23008 instr 17007 . 17007 data 6001 . 6001 read 4001 . 4001 write 2000 . 2000 misses: total 11002 8131 5570 instr 5001 2628 567 data 6001 5503 5003 read 4001 3752 3752 write 2000 1751 1251 facit: ------ Grössere Caches bringen vor allem beim gut lokalisierten code etwas (der wird offenbar dann nicht so leicht ersetzt). Vergleich der Strategien: ------------------------- Random FIFO LRU words read 16136 22528 22280 /demand fetches 0.7013 0.98 .9684 w copied back 3876 5004 5004 /demand writes 1.9380 3.5020 2.5020 total 20012 27532 27284 /demand fetches 0.8698 1.1966 1.1858 demand access: total 23008 23008 instr 17007 . 17007 data 6001 6001 read 4001 . 4001 write 2000 . 2000 misses: total 4034 5632 5570 instr 484 629 567 data 3550 5003 5003 read 2581 3752 3752 write 969 1251 1251 Ergebnis für den Strategienvergleich: ------------------------------------- LRU schneidet etwas schlechter als FIFO ab, random bei weitem besser (25 % weniger misses ?!). Parameterübergabe an Dinero? Diagramme: siehe unten Aufgabe 4 --------- Geigneteste Cache-strategie ist m. e. LRU bei kleinen caches, random bei grösseren, die testergebnisse scheinem dem allerdings zu widersprechen. In der Grösse muß ein Mittelmaß zwischen Aufwand und Leistung getroffen werden, grössere Caches bringen nicht immer sehr viel mehr Leistung, es könnte etwa sinnvoll sein, die Speicherpyramide in der nächsten Dimension (Hauptspeicher, Plattensubsystem) weiter auszubauen. Unified caches sind oft die bessere Wahl (bessere Verteilung bei unterschiedlicher lokalität), können aber die Leistung negativ beeinflussen, wenn die Daten sehr viel weniger lokalisiert sind als der Programmcode, der dann ständig ersetzt wird. Meine Präferenz: Mittelgrosser Non-unified Cache mit möglichst hoher Assoziativität Effizienz: geringe Einschränkungen bezüglich modulo gleicher Speicherplätze Anstieg der Kurven bei Assoziativität: 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önnen. diese werden jeweils in das gleiche set des cache geladen, sodaß viele conflict misses auftreten. Vorteile der Replacementstrategien: random: leicht zu implmentieren, bei grossen speichern sehr gut lru: weniger gefahr des replacement für häufig verwendete code/datenteile -> gut für kleine caches; aufwendiger! fifo: durch temporal locality können wichtige blöcke relativ lange gecached werden, allerdings werden sie jedenfalls irgendwann ersatzt -- un unwichtige cacheteile bleiben relativ lange aktiv. kaum vorteile.