Show Menu
Cheatography
  1. Home >
  2. Cheat Sheets >

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­IL­*­(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
 

Metadata

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.