Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

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

Osnova cvičení

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

Co bych si měl na cvičení zopakovat/připravit

  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í.

Náplň cvičení

Motivační příklad

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.

Cache

Ú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.

Nastaveni cache Bubble sort Selection sort
Numb.sets Block size D.Assoc. Hit Miss Improved Hit Miss Improved
4 1 1
1 1 4
2 1 2
16 1 1

Přímo mapovaná cache

  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?
Ukázka

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

.globl    pole
.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

.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

hlavni_cyklus:
	beq $s0, $s1, hlavni_cyklus_end
	
	lw $s4, pole($s0)
	add $s3, $s0, $0
	add $s2, $s0, $0
	
	vnitrni_cyklus:
	beq $s2, $s1, vnitrni_cyklus_end
		
		lw $s5, pole($s2)
		
		bgt $s5, $s4, neni_minimum
			addi $s3, $s2, 0
			addi $s4, $s5, 0
neni_minimum:
		addi $s2, $s2, 4
		j vnitrni_cyklus
vnitrni_cyklus_end:
	lw $s5, pole($s0)
	sw $s4, pole($s0)
	sw $s5, pole($s3)
	
	addi $s0, $s0, 4
	j hlavni_cyklus
hlavni_cyklus_end:

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

.end _start

Rada: Pokud potřebujete projít dlouhý program a zajímá vás pouze výsledek na konci běhu programu, můžete použít tlačítko Run a rychlost simulace Max.

Aby byly výsledky reprodukovatelné, je program zakončený instrukcí, která vyprázdní vyrovnávací paměť a dále instrukcí break, na které se simulace zastaví.

Plně asociativní cache

  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?
Ukázka

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ů?

Cache s omezeným stupněm asociativity

  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?
Ukázka

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)
courses/b35apo/tutorials/04/start.txt · Last modified: 2019/03/19 17:44 by susta