4. Hierarchický koncept pamětí, cache - 1. část

• pro vyučující: cvičení 4

1. Motivační příklad
2. Návrh a princip práce cache

1. Zopakovat si jak pracuje cache
2. Zopakovat si co znamená
   1. plně asociativní cache
   2. cache s omezeným stupněm asociativity
   3. přímo mapovaná cache
3. Zopakovat si význam pojmů write-through a write-back.
4. Dokončit program pro Bubble sort z minulého cvičení.

A. Za jakou dobu provede procesor s taktovací frekvencí 1GHz 1000 instrukcí za předpokladu, že jednu instrukci provede za jeden takt?

B. Za jak dlouho provede tento procesor 1000 instrukcí za předpokladu, že 20% instrukcí jsou přístupy do paměti. Pro jednoduchost předpokládejme, že jeden přístup do paměti trvá 70 ns.

C. Jak se změní doba potřebná k vykonání instrukcí, když nahradíme procesor 2 GHz verzí, ale paměti zůstanou stejné?

D. Jak se změní doba, když ponechám původní 1 GHz procesor, ale přidám do systému cache? Tato cache má hit rate 80% pro daný program a doba nalezení záznamu v cache je 5ns.

Úkol na cvičení - cache zjistěte vlastnosti Selection sort a Bubble sort, v němž použijete stejné pole jako v Select sort. Pozor, Bubble sort nesmí obsahovat .set noreorder, aby využíval delay slot stejně jako Select sort. Vždy nastavte Replacement Policy = LRU a Writeback policy [Write through No-allocate] a vyplňte tabulku dole pro různé hodnoty počtu setů a stupňů asociativity.

1. Nakreslete přímo mapovanou cache s 4 záznamy.
2. Jak naleznu správný záznam pro uložení dat? Kolik bitů bude obsahovat tag?

Spusťte simulátor QtMips, v nastavení simulace zvolte v základním nastavení nejdříve procesor bez vyrovnávací paměti (No pipline no cache). Kompilovat program již budeme v režimu kompatibilním s reálnou procesorovou architekturou MIPS, to je s využitým delay-slotem, jeho plnění vhodnou instrukcí nebo NOP necháme na assembleru (vynecháme volbu .set noreorder).

Nahrajeme přeložený následující program (je k dispozici v adresáři /opt/apo/selection-sort), který řadí 15 čísel (algoritmem známým jako Selection sort). Nahrajte program do simulátoru QtMips a zobrazte okénka se statistikou přístupů do paměti (Window → Program cache a Window → Data cache) a poznamenejte si počty přístupů do paměti instrukcí a počet čtení a zápisů do paměti dat a kolik cyklů musel procesor čekat na data z paměti.

V dalším kroku nakonfigurujte simulátor se čtyřmi slovy přímo mapované vyrovnávací paměti pro program a data.

Velikost 4 čtyři slova = počet setů 4 x počet slov v bloku 1 x počet bloků v setu (asociativita) 1.

Označení v přednášce versus QtMips: S=počet setů totožné; B=délka bloku se v QtMips zadává ve 32-bitových slovech; E-počet řádků v setu odpovídá v QtMips=Degree of Associativity

Vyzkoušejte co nejvíce různých kombinací konfiguračních parametrů při zachování velikosti vyrovnávacích pamětí 4 slova (součin počtu sad, velikosti bloku a úrovně asociativity). Sledujte, jak se mění obsah cache a odpovězte na následující otázky:

1. Kolik je hit count/miss count?
2. Kolik přístupů do paměti se vykoná?
3. Jak se změní tyto počty pokud velikost cache zvýšíte na 8 a 16 záznamů?

// Jednoduchy tridici algoritmus - selection sort

// pri kompilaci internim assemblerem je nutne
// vypnout pipelining a delay slot nebo za skoky pridat nop

// Pri kompilaci intrenim assemblerem v QtMips zapni zobrazeni oken
#pragma qtmips show registers
#pragma qtmips show memory

.globl    pole

.text
.globl _start
.ent _start

_start:

addi $s0, $0, 0  //Pozice pro kterou se aktualne hleda minimum (offset do pole, zvysuje se po 4 bajtech)
addi $s1, $0, 60 //Maximalni hodnota indexu/offsetu. Slouzi k ukonceni cyklu = pocet prvku v poli * 4 (aktualne 15 * 4)
add  $s2, $0, $s0 //Pracovni pozice (offset), prvek 
// $s3 - offset nejmensiho nalezeneho prvku v aktualnim behu
// $s4 - hodnota nejmensiho nalezeneho prvku
// $s5 - tmp
// $at - pomocný registr pro kontrukce v assembleru

hlavni_cyklus:
	lw $s4, pole($s0)
	add $s3, $s0, $0
	add $s2, $s0, $0
	
vnitrni_cyklus:
	  lw $s5, pole($s2)
		
          slt  $at, $s4, $s5
          bne  $at, $0, neni_minimum
	  nop
	    addi $s3, $s2, 0
	    addi $s4, $s5, 0
neni_minimum:
	  addi $s2, $s2, 4
	  bne $s2, $s1, vnitrni_cyklus
          nop
vnitrni_cyklus_end:
	lw $s5, pole($s0)
	sw $s4, pole($s0)
	sw $s5, pole($s3)
	
	addi $s0, $s0, 4
	bne $s0, $s1, hlavni_cyklus
	nop
hlavni_cyklus_end:

//Koncova nekonecna smycka
end_loop:
	cache 9, 0($0)  // vyprazdneni pameti cache
	break       // zastaveni simulatoru
	j end_loop
	nop

.end _start

.org 0x2000

.data
//.align    2

// Pro spusteni je nutne nastavit jadro s delay-slotem

pole:
.word    5, 3, 4, 1, 15, 8, 9, 2, 10, 6, 11, 1, 6, 9, 12

// Nastav pozici na symbol "pole" v okne zobrazeni pameti
#pragma qtmips focus memory pole

1. Jak se liší plně asociativní cache od přímo mapované cache?
2. Nakreslete plně asociativni cache pro 4 záznamy (12 bitů adresa a 8bitů data).
3. Jak naleznu správné místo pro uložení dat?

V simulátoru Mips nastavte datovou cache podle obrázku, velikost 4 slova = počet setů 1 x počet slov v bloku 1 x počet bloků v setu (asociativita) 4.

Nyní spusťte program znovu a sledujte chování cache.

1. Kolik je hit count/miss count?
2. Kolik přístupů do paměti se vykoná?
3. Jak se změní tyto počty pokud velikost cache zvýšíte na 8 záznamů?

1. Jak se liší od předchozích variant cache? Je v něčem výhodnější, než předchozí varianty?
2. Nakreslete cache se stupněm asociativity omezeným na 2. Velikost cache jsou 4 záznamy (12 bitů adresa a 8bitů data).
3. Jak naleznu správné místo pro uložení dat?

V simulátoru Mips nastavte datovou cache podle obrázku, velikost 4 slova = počet setů 2 x počet slov v bloku 1 x počet bloků v setu (asociativita) 2.

Nyní spusťte program znovu a sledujte chování cache.

1. Kolik je hit count/miss count?
2. Kolik přístupů do paměti se vykoná?
3. Jak se změní tyto počty pokud velikost cache zvýšíte na 8 záznamů?
4. Jaký vliv má volba politiky pro výběr bloku v setu (zkuste politiku LRU a Random)