Pokročilé architektury počítačů

• Stránky předmětu: https://service.felk.cvut.cz/courses/A4M36PAP/
• Přednášející: Ing. Michal Štěpanovský, Ph.D., Doc.Ing. Miroslav Šnorek, CSc.
• Cvičící: Ing. Michal Štěpanovský, Ph.D.

Stránky předmětu X36SKD Stránky předmětu X36APS

Verilog Tutorials

• Cvičení 1
• Cvičení 2
• Cvičení 3
• Cvičení 4
• Cvičení 5
• Cvičení 6
• První semestrální úloha
• Druhá semestrální úloha - B
• Třetí semestrální úloha

Semestralka MPI-OMP

• Cvičení 2 (v iverilogu + testy)

• Přednáška 2
• Přednáška 3

• (2b) Vyjmenujte alespoň 3 techniky statické predikce větvení a 3 techniky dynamické predikce větvení. Porovnejte výhody a nebáhody statické a dynamické predikce.
• (3b) Uvažujte základní Schmithův algoritmus predikce větvení a 2-bitové počítadlo, tj. záznam v BHT má 2 bity. Určete počet správných a špatných predikců pro níže uvedený program. Předpokládejte, že nedochází k interferenci, počáteční stav je WNT. Výsledek zdůvodněte, jak jste k němu přišli.

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

správný výsledek je 503, jinak interference je to, že každý cyklus má své počítadlo a ty se neovlivňují

• (3b) Uvažujte dvou-úrovňový paměťový systém tvořený jednou skrytou pamětí (L1 cache) a hlavní pamětí. Přístupová doba nechť je 1 a 100 cyklů pro L1 cache a hlavní pamět, přičmež jeden cyklus trvá 1 ns. Předpokládejte, že L1 cache miss rate je 5%. Jaký bude pruměrný čas přístupu do paměti (AMAT)?

pozor na chyták, když je miss, sahá i do té cache, tj. započítat i čas přístupu do ní, tj. průměr je 6 ns (ne 5,95 ns, jak by si někdo spočítal)

• (1b) Klasifikujte hazardy v zřetězeném procesoru. Jak lze tyto hazardy řešit (uveďte techniky)? Kdy dochází k hazardům?

• (4b) Určete miss rate vykonávání následovné části programu při pouřití přímo mapované INSTRUKČNÍ cache o velikosti 16 slov, velikost bloku 2 slova. Předpokládejte paměť slovně zarovnanou, velikost slova 4B, tj. nejnižší bity adresy jsou 00. Cache je na počátku prázdná.

ADDRESS      CONTENT
8002FFFFC    00 00 00 00   NOP
800200000    3C ...        LUI ...
800200004    26 ...        ADDIU ...
800200008    28 ...        ADDI ...
80020000C    06 ...        RLL ...

princip je takový, ze podle obrázku jsou nejnižší dva bity nepodstatné, pak je bit určující slovo (sloupec) a další tři bity pak řádek. Zbytek je tag. Vyplněné tak jsou první dva řádky instrukcemi v pořadí

3C … 26 …
28 … 06 …
a vpravo dole je pak NOP

• (1b) Pro PC-relativní skokové instrukce je adresa skoku vždy stejná (pokud nepředpokládáme samomodifikující program). Nicméně nepřímé skoky můžou mít různé cílové adresy. BTB zaznamenává pouze nejaktuálnějsí cílové adresy, proto může být značně neefektivní pro predikce často měnícíh cílových adres nepřímých skoků. Jak můžeme modifikovat strukturu BTB, abychom zlepšili predikci pro tyto případy?
• (1b) Vyjmenujte metody pro zajištění koherence skrytých pamětí víceprocoserového systému.
• (2b) Vyjmenujte modely paměťové konzistence. Jak lze zajistit konzistenci (obecně)?
• (1b) Klasifikujte závislosti v programech. Jak lze eliminovat závislosti (ne hazardy!) a kterého typu (uveďte používané techniky)
• (1b) Nakreslete graf datových závislostí níže uvedeného programového fragmentu

P1: X = D+S
P2: S = G*X
P3: A = B-X
P4: S = A+S
P5: A = G/Y

• (2b) Nastiňte základní myšlenky, jak se vypořádat se zotavením po chybné predikci skoku (co všCechno musíme zabezpečit pro podporu spekulace a jaké HW prostředky použijete?)
• (1b) K čemu slouží Load bypassing a Load forwarging? Uveďte základní myšlenku těchto technik!
• (3b) Uveďte, zda souhlasíte či nesouhlasite s tvrzením a v krátkosti svůj postoj zdůvodněte a přípasdně doplňte. Podtrhněte spornou část věty.
  • Multicast, Broadcas, Rediction a Allreduce patří mezi tzv. point-to-point kolektivní neblokující komunikaci. ANO, NE, Proč?
  • Prodpora přesného přerušení se dosahuje speciálními instrukcemi vloženými kompilátorem při překladu programu a slouží k dosažení okamžité odezvy procesoru na danou událost, ANO, NE, Proč? (Pokud NE? jak se podle Vás dosahuje přesného přerušení?)
  • Programy komunikující pomocí Message Passing se nehodí pro systémy se sdílenou pamětí, ANO, NE, Proč?

• příklady:
  1. MESI (co se bude dit kdyz)
  2. pocet chyb predikce skoku (1 bitovy prediktor)
  3. zadan kod na tri procesu, jaka muze byt sekcence vypisu pri paralelnim behu
  4. stav instrukcni CACHE po vykonani programu
• otázky:
  1. obecne otazky o vsem s variantami, ale i bez variant

• Průběh zkoušky: něco přes hodinu času na test. Času bylo hodně. Ústní byla dobrovolná, bez ní šlo získat nejlépe B.

• Příklady:

1) (3 body)

1. Klasifikace datových závislostí (raw, war, waw),
2. nakreslit diagram závislostí,
3. rozvrhnutí na superskalárním počítači tak, aby se operace vykonaly co nejrychleji

2) Výpis paměti ram, kde byl uložen program v MIPS assembleru. Vyřešit se mělo to, co bude uloženo v registru 18 po vykonání programu. Byly tam nějaké load/strore instrukce, posun, sčítání (1 bod).

3) (3 body)

1. Obrázek cache ze slajdů APS. Určit co to je za cache, byla to přímo mapovaná.(možnosti přímomapovaná, plně asociovaná, s omezenou asociací a nepřímo mapovaná)
2. Příklad na který řádek se uloží jedna instrukce a jak bude tento řádek vypadat. Na jednom řádku byly uloženy dva datové bloky, každý blok měl 32 bitů.
3. Dopočítat šířku tagu. Viz kurz APS.
4. Jaký stupeň asociace má tato cache. (Byla to přímo mapovaná cache, takže stupeň asociace byl 1)

• Teorie: Té tam bylo více než bylo očekáváno. Na vše si nevzpomínám.

1) HyperTransport - trvzení, že to je sběrnice, dvoubodovej spoj, paketový přenos, jednosměrný, mustiplexovaná,…. Označit, co platí. (2 body).

2) Charakteristika NUMA

3) Zajišťuje se v NUMA konzistence pomocí zasílání zpráv. (NE)

4) Přesné přerušení.

5) Pokud výsledek v pipeline vzniká dříve, než ho potřebuje následují tak vzniká hazard. Jak se tento hazard řeší? (Mělo být forwardingem).

6) Bersteinovy podmínky - jsou postačující pro paralelní (korektní) provedení instrukcí? (Nutné ale ne dostačující)

7) Něco o out-of-order jak funguje(dispatcher a reorder Buffer) a proč se používá.

8) Používá se v superskaláru diverzifikované vynovávací jednotky nebo se od nich ustupuje?

9) Multithreadig zvyšuje propustnost každého vlákna? (NE, pouze celkovou propustnost)

10) 3 podmínky pro korektní spekulaci.

11)…..

12)…..

Ahoj, doufám, že mě někdo dopní, ale pro ty co ještě na zkoušce nebyli, tak aby tušili do čeho jdou…

• Začíná se písemnou částí, která má čtyři úkoly:
  1. Zadáno, že jedna instrukce trvá jeden takt, pokud se podaří načíst nebo uložit data. 50% všech instrukcí je čtení - ukládání dat. Miss rate je 2% a když je miss, tak je penalizace 25 cyklů. Vypočítat, jak bude rychlejší vykonávání, když nebude žádný miss. (Nevím, jak se to má správně počítat, ale já na to šel selsky… řekl jsem si, že mám třeba 100 instrukcí, to znamená, že 50 je jich Load/Save a 50 ostatních. Těch 50 ostatních je 50 cyklů. Z těch 50 Load/Save může být taky 50 cyklů, pokud neni miss = 100 cyklů. Nebo 2% z 50 je 1, to znamená, že může nastat 1 miss, takže k těm 50 cyklů přidám penalizaci 25, to je dohromady 50 cyklů ostatní instrukce, 50 Load/Save a 25 penalizace = 125 cyklů. Takže vidim, že se mi to zvýší 1,25x)
  2. Zadáno pár instrukcí, prázdná cache o 8 volných místech a byla to takov8 ta cache, co ukládá vždycky na jedno místo „adresa mod velikost cache = místo v cache“. Měli jste zjistit miss rate pro ten kus kódu. Byl to cyklus, kterej 5x proběhnul a při každým průchodu načítal 2x z paměti. Prvn9 z adresy 0x4 a druhý z 0x14. (Mělo to vyjít 100%. 0x4 se ptá na 4. buňku a 0x14 je dec 20 a ta se prá taky na 4 buňku, takže to pokaždý vyhodí miss. Já to zapomněl převést z hex na dec a proto jsem měl miss jenom 20%, protože 14 mi dávalo, že se ptá na buňku 6, čili to při prvním průchodu je dvakrát miss a dohromady je těch načítání 10. Ale na ústní jsem to ukecal, že jsem se jenom přehlídl a nepřevedl to :))
  3. Udělat graf datových závislostí, to samý, co je v přednášce 2.
  4. Bylo tam pár tvrzení a napsat k tomu jestli jsou nebo nejsou pravdivý, proč to tak je, nebo byla vynechaná věta a měli jste ji doplnit. Už si nepamatuju, co tam přesně bylo. Vim, že dvě byly lehký a čtyři jsem si nějak tipnul.
• pak jste si vylosovali otázku a udělali si na papír přípravu. Oboje si pak vybral. Protože přišel o půlhodinu později, tak jsme nakonec byli v tý učebně s nějakym jinym předmětem a na ústní se šlo ke Štěpanovskýmu do kanceláře. Jednoho zkoušel a zbytek čekal na chodbě, takže si šlo ještě něco dostudovat. Já tam šel s t9m, že bych rád za E. Napsal mi za A :) Když nevíte, což se mi stávalo u tý teorie skoro pořád, tak to z vás páčí a páčí a páčí. Ale jinak je podle mě zlatej. Přeju všem hodně štěstí!