Show Menu
Cheatography

Rechnersysteme 2 Cheat Sheet by

Pipelining

Inst­ruction Fetch (IF)
nimmt Befehle vom HS auf
Inst­ruction 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
Vort­eil: Parall­eli­sierung von Operat­ionen
Nach­teil: bei Pipeli­neflush müssen alle Befehle verwerfend neu geladen werden; ohne Cache immer Cachemiss

Konflikte

Write after Write
doppelte Übersc­hre­ibung
Write after Read
Wert, der noch gebraucht wird, wird übersc­hrieben
Read after Write
falscher Wert wird gelesen

Stalling

Pipeline Stalling
lässt Operat­ionen einen Takt warten
Result Forwar­ding
Wert direkt weiter­geben; kein Zeitve­rlust, geht aber nur wenn Wert erreic­hbar
Spec­ulative Execut­ion: raten

Befehl­stypen

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 == Variab­le: set RegNum = 1
* Knoten unäre Operat­ion und Kind Label r hat: set RegNum = r
* Knoten binäre Operat­ion: *
l==r: set RegNum = l+1 = r+1
* l!=r: set RegNum = max{l, r}
* funkti­oniert nicht bei geteilten Registern, z.B.: (c * x + b) * x + a

CPI

Befe­hls­typ
%
mit RAW
CPI
Sprung­befehl
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 Ladebe­fehle erzeugen einen RAW Konflikt
CPI= CPIA­*2­0+C­PI­A­*60­+CP­I*­(20-10) / 100-(2­0-10)

Bitori­ent­ierter 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

Byteor­ien­tierter 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

Parser­tabelle

a) ist das T in unserer FIRST-­Menge drin? Dann suche Produk­tion, 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
 

Lokali­täten

räum­lich: Adressen, die nah an dem genutzten sind, werden wahrsc­hei­nlich wieder genutzt -> Blöcke
zeit­lich: eine Adresse, auf die zugegr­iffen wird, wird wahrsc­hei­nlich in nächster Zeit wieder angesp­rochen

Zurück­sch­rei­bme­thoden

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

Graph Coloring

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

Cachea­dre­ssi­erung

 
Byte
Block
Nk-set
#index
log2(Cachegr.)
sk
sk-nk
#tag
log2­(HSGr) -#adr
al- (sk+b)
al-(sk- nk+b)
#offset
-
b
b
#gl. tags
#Zeilen im Cache
sizek
sizek/ Nk
Sätze
-
sizek
sizek/ Nk
sizek = #Blöcke im Cache
sk: sizek= 2sk Blöcke; B = Blockgröße in Byte;
b: B = 2b; al = Bits für Adressraum
nk: Nk = 2nk; Nk = #Blöcke im Satz

Adress­ber­echnung
adr(x) = x mod (Cache­lines); tag(x) = x div (CL);
adr(x) = (x div 2b) div 2sk; tag(x) = (x div 2b) mod 2sk
adr(x) = (x div 2b) div 2sk­-nk
tag(x) = (x div 2b) mod 2sk­-nk

Blocko­rie­nti­erter Cache

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

Blocko­rie­nti­erter 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

Satzas­soz­iativer Cache

* kein direct mapping
* darf sich aussuchen, in welchen Block
+ reinsp­eichern angene­hmer, da freie Platzwahl
- suchen aufwän­diger, da wir alle Blöcke im Set durchgehen müssen
* 1-way -> blocko­rie­ntiert, da nur ein Block und somit keine Platzwahl

Top-Do­wn-­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 angesp­rochen
* alles in binär
dirt­ybit: Cache konsistent zum HS?
Ja: 0; Nein: 1
vali­dbit: ist ein Datum in der Adresse?
Ja: 1; Nein: 0
Bloc­kor­ien­tie­rt: es werden nur Teile im Block übersc­hrieben
Set-­ori­ent­iert: freie Auswahl in Adresse

Cach­e-h­it: valid = 1 & tag(i) == tag(i')
miss: valid = 0 || valid = 1 & tag(i) != tag(i')
Tref­fer­quo­te: #hit/#miss
Average Acces Time: Hitrat­e*­tim­e(hit) + (1-Hit­rat­e*­tim­e(m­iss))
Miss­-Pe­nal­ty: extra delay durch HS-Zugriff

First & Follow

FOLL­OW:
$ 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 nachfo­lgenden Block
Read­-Me­nge: nehmen von allen Reads die raus, die wir im eigenen Block vorher schreiben
Writ­e-M­enge: alle geschr­iebenen Variablen

Variablen

* auf Klammerung achten
* am Besten Formeln aufsch­reiben
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­'(­MLi­ve(l') \ Write(l))
MayU­sed: * forwards
U(l) = Read(l) ∪ ∪l'->­l(­U(l') ∪ Write(l))
Must­Used: * forwards
MustU(l) = Read(l) ∪ ∩l'->­l(­Mus­tU(l') ∪ Write(l))
Busy: * backwards
B(l) = Read(l) ∪ ∩l->l­'(­B(l') \ Write(l))

Pipeline

CISC
register memory archit­ecture machin­ewords different length * many complex* irregular instru­ctions
RISC
register register archit­ecture as few as posible & as regulas as possible instru­ctions * machine words same length
shared subtrees in syntax­trees: DAG
-> optimaler code für DAGs ist NP-vol­lst­ändig
MSB (Most Signif­icant Bit): linkestes Bit (höchste Potenz)
LSB (Least): rechts
voll­ass­ozi­iert: wenn Cache 1 Satz (freie Speich­erwahl)
n-fach assozi­ativ: n = Nk
Boot­str­app­ing: Aneina­nde­rsc­halten von Compilern
-> kein extra Compiler
L/S-­Arc­hit­ekt­ur: Befehl­ssatz Daten-­Spe­ich­erz­ugriffe nur mit L/S Befehlen
-> RISC
-> CISC hat auch ALU (arith­metic & logic unit)

Virtueller Speicher

* TLB: Transl­ati­on-­Loo­kaside Buffer
* Page­table ist im HS

Help Us Go Positive!

We offset our carbon usage with Ecologi. Click the link below to help us!

We offset our carbon footprint via Ecologi
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.