13. Seminar - Exam task examples...

Příklad 1.
Uvažujte tří-procesorový systém SMS dle obrázku níže a protokol MESI. Popište sled událostí pro tyto případy:

Procesor P1 chce zapsat data a nastane write miss v jeho vlastní cache (C1). Data neobsahuje žádná cache.
Procesor P1 chce zapsat data a nastane write miss v jeho vlastní cache (C1). Data obsahuje cache C3 a jsou označena M.
Procesor P1 chce číst data a nastane read miss v jeho vlastní cache, přičemž data obsahuje cache C3 a jsou označena M.

Příklad 2.
Uvažujte základní Smithův algoritmus predikce větvení a 1bitové počítadlo, tj. záznam v BHT (Branch History Table) má 1 bit. Určete počet správných a špatných predikcí pro níže uvedený program. Výsledek zdůvodněte – jak jste k němu přišli.

Program v jazyku C:

int i, j, c=0;
for (i=0; i<500; i++) 
  for (j=0; j<4; j++) 
     c++;

Předpokládejte program v assembleru:

// i = s0, j = s1, c = s2, 
// t0 = limit vnejsi smycky, 
// t1 = limit vnitrni smycky, 
// t3 - pomocna promenna

  addi s1, $0, 0     // c = 0;
  addi t0, $0, 500   // t0 = 500;
  addi t1, $0, 4     // t1 = 4;

  addi s0, $0, 0     // i = 0;
L1:
  addi s1, $0, 0     // j = 0;
L2:
  addi s2, s2, 1     // c++;

  addi s1, s1, 1     // j++;
  slt  t3, s1, t1    // t3 = (s1 < t1) ? 1 : 0;
  bne  t3, $0, L2
  addi s0, s0, 1     // i++;
  slt  t3, s0, t0    // t3 = (s0 < t0) ? 1 : 0;
  bne  t3, $0, L1

Příklad 3.
Určete miss rate vykonání následovné části programu při použití PŘÍMO MAPOVANÉ DATOVÉ CACHE o velikosti 8 slov, velikost bloku 1 slovo. Předpokládejte paměť slovně zarovnanou, velikost slova 4B, tj. nejnižší bity adresy jsou 00. Cache je na počátku prázdná. Ukončení programu předpokládejte dosažením návěstí done. Registry i instrukce jsou 32-bitové.

0x1000		addi t0, $0, 4
0x1004	loop: beq t0,$0,done
0x1008		nop
0x100C 		lw   t1, 0x4($0)
0x1010		lw   t2, 0xC($0)
0x1014		addi t0, t0, -1
0x1018		j    loop
0x101C		nop
0x1020	done:

Jak bude vypadat cache těsně před dokončením programu?

Příklad 4.
Předpokládejte, že skoková instrukce má následující vzor chování: T T T N N T T T N N T T T N N.

Jakou dosáhneme přesnost predikce, pokud předpokládáme 2-bitový základní Smithův prediktor? Počáteční stav prediktoru je Strongly taken.
Jakou musí mít minimální délku lokální historie abychom dosáhli co nejlepší predikcí? Zakreslete obsah PHT. T (taken), NT (not take), X (nezáleží).

Příklad 5.
Pro PC-relativní skokové instrukce je adresa skoku (adresa instrukce v případě skoku) vždy stejná (pokud nepředpokládáme samomodifikující se program). Nicméně nepřímé skoky můžou mít různé cílové adresy. BTB zaznamenává pouze nejaktuálnější cílové adresy, proto může být značně neefektivní pro predikci často se měnících cílových adres nepřímích skoků. Jak můžeme modifikovat strukturu BTB abychom zlepšili predikci pro tyto případy?

Příklad 6.
Na konci 50-tých let byl při návrhu procesorů považován limit 23 úrovní hradel v logické cestě. Později bylo uvažováno již 20 úrovní hradel v jednom stupni zřetězení (1995, UltraSPARC-I). V pozdějších procesorech byl stanoven cíl pouze 5 až 8 úrovní hradel (UltraSPARC-III). Vysvětlete co vedlo vývojáře k těmto krokům!

Příklad 7.
Uvažujte níže uedený testovací program. Předpokládejte virtuálně adresovanou plně asociativní cache s délkou bloku 64B. Spočítejte celkový miss-rate! Předpokládejte, že všechny proměnné s výjimkou polí jsou již v registrech procesoru, a že pole A, B a C jsou uloženy za sebou v paměti.

double A[1024], B[1024], C[1024];
for(i=0;i<1000; i+=2 )
  A[i] = 10*B[i] - C[i+1];

Příklad 8.
Slovně popište jak bude vypadat program s velmi velkým stupněm prostorové lokality. Napište pseudoprogram takového programu a diskutujte miss-rate.

Příklad 9.
Existuje nějaký důvod proč realizovat out-of-order skalární zřetězený procesor? Pokud ano, vymyslete scénář kdy takové vykonání přináší lepší výkon v porovnání s in-order skalárním procesorem.

Příklad 10.
Jaká je nejduležitější výhoda použití centralizovaných stanic oproti distribuovaným?