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

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. 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 QtRVSim, v nastavení simulace zvolte v základním nastavení nejdříve procesor bez vyrovnávací paměti (No pipline no cache).

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 QtRVSim 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 QtRVSim: S=počet setů totožné; B=délka bloku se v QtRVSim zadává ve 32-bitových slovech; E-počet řádků v setu odpovídá v QtRVSim=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ů?

// Simple sorting algorithm - selection sort

// Directives to make interesting windows visible
#pragma qtrvsim show registers
#pragma qtrvsim show memory

.option norelax

.globl  array
.globl  _start

.text

_start:

la   a0, array
addi s0, zero, 0  //Minimum value from the rest of the array will be placed here. (Offset in the array, increasing by 4 bytes).
addi s1, zero, 60 // Maximal index/offset value. Used for cycle termination = number of values in array * 4.
add  s2, zero, s0 //Working position (offset)
// s3 - offset of the smallest value found so far in given run
// s4 - value of the smallest value found so far in  given run
// s5 - temporary

main_cycle:
        beq  s0, s1, main_cycle_end

        add  t0, a0, s0
        lw   s4, 0(t0)   // lw  s4, array(s0)
        add  s3, s0, zero
        add  s2, s0, zero

inner_cycle:
        beq  s2, s1, inner_cycle_end
                add  t0, a0, s2
                lw   s5, 0(t0) // lw s5, array(s2)

                // expand bgt s5, s4, not_minimum
                slt  t0, s4, s5
                bne  t0, zero, not_minimum

                        addi s3, s2, 0
                        addi s4, s5, 0
not_minimum:
                addi s2, s2, 4
                j inner_cycle
inner_cycle_end:
        add  t0, a0, s0
        lw   s5, 0(t0)  // lw s5, array(s0)
        sw   s4, 0(t0)  // sw s4, array(s0)
        add  t0, a0, s3
        sw   s5, 0(t0)  // sw s5, array(s3)

        addi s0, s0, 4
        j main_cycle
main_cycle_end:

//Final infinite loop
end_loop:
        fence            // flush cache memory
        ebreak           // stop the simulator
        j end_loop

.org 0x400

.data
// .align    2 // not supported by QtRVSsim

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

// Specify location to show in memory window
#pragma qtrvsim focus memory array

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 RISC-V 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 RISC-V 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)