Rechnersysteme 2 Cheat Sheet

Pipelining

Instruction Fetch (IF)	nimmt Befehle vom HS auf
Instruction Decode (ID)	decodiert Befehle & Register; schaut in Register & lädt Inhalte
Execute (EX)	führt Operation aus
Memory Access (MA)	macht L/S Befehle im HS
Write Back (WB)	schreibt in Register

Vorteil: Parallelisierung von Operationen
Nachteil: bei Pipelineflush müssen alle Befehle verwerfend neu geladen werden; ohne Cache immer Cachemiss

Konflikte

Write after Write	doppelte Überschreibung
Write after Read	Wert, der noch gebraucht wird, wird überschrieben
Read after Write	falscher Wert wird gelesen

Stalling

Pipeline Stalling	lässt Operationen einen Takt warten
Result Forwarding	Wert direkt weitergeben; kein Zeitverlust, geht aber nur wenn Wert erreichbar

Speculative Execution: raten

Befehlstypen

Abacus / MIPS
R / R	3 Register
I / I	2 Register
S / -	1 Register
J / J	0 Register

Stalls

	ohne FW	mit FW
arithm.	2	0
L/S	2	1
Branch	3	1
Jump	3	0

Nakata

* findet min. Anzahl an Registern, die für ein Programm nötig sind
* Knoten == Variable: set RegNum = 1
* Knoten unäre Operation und Kind Label r hat: set RegNum = r
* Knoten binäre Operation: *
l==r: set RegNum = l+1 = r+1
* l!=r: set RegNum = max{l, r}
* funktioniert nicht bei geteilten Registern, z.B.: (c * x + b) * x + a

CPI

Befehlstyp	%	mit RAW	CPI
Sprungbefehl	20%	20%	1 bei jump; 2 bei branch
Arithmetik	60%	60%	1
Ladebefehl	20%	0.5*20%	1 wenn Wert darauf nicht gelesen, 2
MAC		0.5*20%	-

50% der Ladebefehle erzeugen einen RAW Konﬂikt
CPI= CPIA*20+CPIA*60+CPIL*(20-10) / 100-(20-10)

Bitorientierter Cache

Datawidth	16 entspricht 2 Byte Wortgröße
MemSize	32 HS Größe
Cachesize	8 entspricht 4 Wörter
Blocksize	2 entspricht 1 Wort
SetAssoc	1 entsricht 1 Block pro Satz

direct mapping: jedes Wort genau eine Zuteilung

Byteorientierter Cache Beispiel

	tag \| adr	valid
15 sti $1, $0, 0	1 in adr[0] -> 00\|00	0 -> 1
16 sti $2, $0, 1	2 in adr[1] -> 00\|01	0 -> 1
17 ldi $2, $0, 1	Mem[1] laden -> 00\|01	1 -> hit
18 sti $3, $0, 2
19 sti $4, $0, 3
20 ldi $2, $0, 1
21 sti $5, $0, 7
22 sti $6, $0, 8
23 sti $7, $0, 9	7 in adr[9] -> 10\|01	valid = 1 && tag[9] != 00 aus 16 -> miss
24 ldi $2, $0, 1	Mem[1] laden	Cachemiss

Parsertabelle

a) ist das T in unserer FIRST-Menge drin? Dann suche Produktion, welche das T in die FIRST-Menge bringt
b) ist e in FIRST, dann schaue, ob unser T auch in der FOLLOW-Menge drin ist
Falls ja, nehme e auf

Lokalitäten

räumlich: Adressen, die nah an dem genutzten sind, werden wahrscheinlich wieder genutzt -> Blöcke
zeitlich: eine Adresse, auf die zugegriffen wird, wird wahrscheinlich in nächster Zeit wieder angesprochen

Zurückschreibmethoden

write through: schreibt immer durch
write back: nutzt dirtybit
schreibt zurück, wenn etwas neues eingelagert wird vom HS (oder geladen)
least recently used: für set-oriented: schreibt in Zeile, die am längsten nicht genutzt wurde

Graph Coloring

Spilling: nutzen den HS
1. Berechnen Read / Write-Menge & Zeilen / Blöcke
2. MayLive berechnen
3. MayUsed bestimmen
4. Zeilenweise den Schnitt nehmen
5. alle in der selben Menge haben Beziehung zueinander
6. Assembler-Code produzieren
* werden x Farben benötigt, dann ist Codierung auch mit x Registern möglich

Cacheadressierung

	Byte	Block	N`k`-set
#index	log`2`(Cachegr.)	s`k`	s`k`-n`k`
#tag	log`2`(HSGr) -#adr	al- (s`k`+b)	al-(s`k`- n`k`+b)
#offset	-	b	b
#gl. tags	#Zeilen im Cache	size`k`	size`k`/ N`k`
Sätze	-	size`k`	size`k`/ N`k`

sizek = #Blöcke im Cache
sk: sizek= 2^sk Blöcke; B = Blockgröße in Byte;
b: B = 2^b; al = Bits für Adressraum
nk: Nk = 2^nk; Nk = #Blöcke im Satz

Adressberechnung
adr(x) = x mod (Cachelines); tag(x) = x div (CL);
adr(x) = (x div 2^b) div 2^sk; tag(x) = (x div 2^b) mod 2^sk
adr(x) = (x div 2^b) div 2^sk-nk
tag(x) = (x div 2^b) mod 2^sk-nk

Blockorientierter Cache

* direct mapping
* Laden & Speichern gesamter Blöcke
+ nutzen aus, dass "nahe" Werte abhängig voneinander sind -> kein unnötiges Laden
- blöd, wenn diese unabhängig sind

Blockorientierter Cache Beispiel

15 sti $1, $0, 0
Mem[0] -> 00|0|0 = tag | in welchem Block | in welcher Zeile im Block
21 sti $5, $0, 7
Mem[7] -> 01|1|1
Cachemiss 00!=01
-> laden den Block on den HS zurück, um neuen Wert speichern zu können

Satzassoziativer Cache

* kein direct mapping
* darf sich aussuchen, in welchen Block
+ reinspeichern angenehmer, da freie Platzwahl
- suchen aufwändiger, da wir alle Blöcke im Set durchgehen müssen
* 1-way -> blockorientiert, da nur ein Block und somit keine Platzwahl

Top-Down-Parsing

Stack	input	action
$S	bbabbbb$	expand S -> bSbb
$bbSb	bbabbbb$	match
$bbS	babbbb$	expand S -> bSbb
$bbbbSb	babbbb$	match
$bbbbS	abbbb$	expand S -> A
$bbbbA	abbbb$	expand A -> aB
$bbbbBa	abbbb$	match
$bbbbB	bbbb$	expand B ->
$bbbb	bbbb$	match
$bbb	bbb$	match
$bb	bb$	match
$b	b$	match
$	$	match

S -> bSbb | A
A -> aB
B -> A |
bbabbba in Sprache?

First & Follow Beispiel

	FIRST	FOLLOW
S	b, a	$, FIRST(b)\e aus FOL(S): b
A	a	FOL(S) aus FOL(A): $, b
B	a,	FOL(A) aus FOL(B): $, b
a	a	-
b	b	-

Caches

* Cache wird bei L/S Befehlen angesprochen
* alles in binär
dirtybit: Cache konsistent zum HS?
Ja: 0; Nein: 1
validbit: ist ein Datum in der Adresse?
Ja: 1; Nein: 0
Blockorientiert: es werden nur Teile im Block überschrieben
Set-orientiert: freie Auswahl in Adresse

Cache-hit: valid = 1 & tag(i) == tag(i')
miss: valid = 0 || valid = 1 & tag(i) != tag(i')
Trefferquote: #hit/#miss
Average Acces Time: Hitrate*time(hit) + (1-Hitrate*time(miss))
Miss-Penalty: extra delay durch HS-Zugriff

First & Follow

FOLLOW:
$ aus FOL(S)
A->aBb: FIRST(b)/e aus FOL(B)
A->aB: FOL(A) aus FOL(B)
A->aBb, e aus FIRST(b): FOL(A) aus FOL(B)

Data Flow Analyse

Basic Block: * Zeile nach einem if bildet neuen Block
* if goto a bildet neuen Block an Zeile a
-> erste Zeile im neuen Block
-> *nur bei goto keine Beziehung zum nachfolgenden Block
Read-Menge: nehmen von allen Reads die raus, die wir im eigenen Block vorher schreiben
Write-Menge: alle geschriebenen Variablen

Variablen

* auf Klammerung achten
* am Besten Formeln aufschreiben
May Live: * backwards analysis
Live(l) = Read(l) ∪ ∪l->l' (Live(l') \ Write(l)),
l' folgender Block
Must Live: * backwards
MLive(l) = Read(l) ∪ ∩l->l'(MLive(l') \ Write(l))
MayUsed: * forwards
U(l) = Read(l) ∪ ∪l'->l(U(l') ∪ Write(l))
MustUsed: * forwards
MustU(l) = Read(l) ∪ ∩l'->l(MustU(l') ∪ Write(l))
Busy: * backwards
B(l) = Read(l) ∪ ∩l->l'(B(l') \ Write(l))

Pipeline

CISC	register memory architecture machinewords different length many* complex* irregular instructions
RISC	register register architecture as few as posible & as regulas as possible instructions * machine words same length

shared subtrees in syntaxtrees: DAG
-> optimaler code für DAGs ist NP-vollständig
MSB (Most Significant Bit): linkestes Bit (höchste Potenz)
LSB (Least): rechts
vollassoziiert: wenn Cache 1 Satz (freie Speicherwahl)
n-fach assoziativ: n = Nk
Bootstrapping: Aneinanderschalten von Compilern
-> kein extra Compiler
L/S-Architektur: Befehlssatz Daten-Speicherzugriffe nur mit L/S Befehlen
-> RISC
-> CISC hat auch ALU (arithmetic & logic unit)

Virtueller Speicher

* TLB: Translation-Lookaside Buffer
* Pagetable ist im HS

Rechnersysteme 2 Cheat Sheet by Everdeen

Pipelining

Konflikte

Stalling

Befehlstypen

Stalls

Nakata

CPI

Bitorientierter Cache

Byteorientierter Cache Beispiel

Parsertabelle

Lokalitäten

Zurückschreibmethoden

Graph Coloring

Cacheadressierung

Blockorientierter Cache

Blockorientierter Cache Beispiel

Satzassoziativer Cache

Top-Down-Parsing

First & Follow Beispiel

Caches

First & Follow

Data Flow Analyse

Variablen

Pipeline

Virtueller Speicher

Created By

Metadata

Comments

Add a Comment

Latest Cheat Sheet

Random Cheat Sheet

About Cheatography

Behind the Scenes

Recent Activity

Rechnersysteme 2 Cheat Sheet by Everdeen

Pipelining

Konflikte

Stalling

Befehl­stypen

Stalls

Nakata

CPI

Bitori­ent­ierter Cache

Byteor­ien­tierter Cache Beispiel

Parser­tabelle

Lokali­täten

Zurück­sch­rei­bme­thoden

Graph Coloring

Cachea­dre­ssi­erung

Blocko­rie­nti­erter Cache

Blocko­rie­nti­erter Cache Beispiel

Satzas­soz­iativer Cache

Top-Do­wn-­Parsing

First & Follow Beispiel

Caches

First & Follow

Data Flow Analyse

Variablen

Pipeline

Virtueller Speicher

Created By

Metadata

Comments

Add a Comment

Latest Cheat Sheet

Random Cheat Sheet

About Cheatography

Behind the Scenes

Recent Activity

Befehlstypen

Bitorientierter Cache

Byteorientierter Cache Beispiel

Parsertabelle

Lokalitäten

Zurückschreibmethoden

Cacheadressierung

Blockorientierter Cache

Blockorientierter Cache Beispiel

Satzassoziativer Cache

Top-Down-Parsing