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á
    • plně asociativní cache
    • cache s omezeným stupněm asociativity
    • 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. 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 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

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í ebreak, 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 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ů?

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 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)
courses/b35apo/tutorials/04/start.txt · Last modified: 2023/03/15 13:13 by dupakjak