07 - Princip činnosti počítače

•  počítač
  • vymyslel Turing - 30. léta
  • 1. počítač - ENIAC (1946), 2. počítač - EDVAC (1952)
  • dnes: je v informatice elektronické zařízení, které zpracovává data pomocí předem vytvořeného programu
    • data ovládají hardware ⇒ lze přeprogramovat pro jinou činnost
• algoritmus
  • je přesně definovaná konečná posloupnost příkazů (které jsou vybírány z předem definované konečné množiny elementárních příkazů), jejichž prováděním pro každé přípustné vstupní hodnoty získáme po konečném počtu kroků odpovídající hodnoty výstupní
  1. aplikačně specifický číslicový obvod - optimalizovaný, výkonný pro jeden algoritmus … dlouho se navrhuje, je drahý
  2. program pro procesor - univerzální pro více algoritmů, nízká cena … výkonnost nemusí být dostačující
• komponenty HW
  1. datové struktury - registry (proměnné)
  2. řídící struktury
     1. sekvence - komponenty seřazeny za sebou
     2. selekce - multiplexor
     3. iterace - čítač a řídící automat
     4. rekurze - NEJDE vyřešit v HW

• procesor
  • obvodová realizace algoritmu, který dokáže vykonávat libovolné programy (algoritmy), sestavené z předem definovaných elementárních operací (instrukcí)
  • vykoná program, který je uložen od zadané adresy v paměti
    • program transformuje data, uložená na zadané adrese v paměti, na jiná data, jejichž nové umístění musí být rovněž specifikováno
    • programy jsou uloženy v paměti jako posloupnosti instrukcí, vykonávají se sekvenčně
  • sekvenční (obvykle) synchronní číslicový obvod
• hlavní komponenty procesoru
  1. programový čítač - PC
     • určuje adresu, kde se nachází následující instrukce
     • po resetu dochází k inicializaci procesoru a mj. je definován obsah PC (např. PC = 0003h)
  2. instrukční registr - IR
     • uchovává právě zpracovávanou instrukci
     • neviditelný registr, v podstatě se jedná o aktuální stav konečného automatu
  3. řadič
     • řídí činnost procesoru - vykonává instrukce
     • konečný automat - FSM (konečný stavový stroj)
  4. aritmeticko-logická jednotka - ALU
     • slouží k provádění matematických operací
     • převádí vstup na výstup
  5. I/O jednotka
     • umožňuje vstup a výstup dat do/z procesoru (obvykle do jeho registrů) i jinak než pouze skrz paměť
     • TODO
  6. registry
     • klopné obvody, které ochovávají informace po dobu napájení
• Program a jeho uložení
  1. Harwardská koncepce procesoru
     • paměť pro data a programy je oddělena
  2. Von Neumannova (princetonská) koncepce procesoru
     • společná paměť pro data a programy

Ještě tu dodávám tuto poznámku:

• rozhraní procesoru
  1. RESET - definuje obsah PC a inicializuje procesor
  2. CLK - hodinový signál (v INP jsme řešili pouze synchronní procesory a obvody)
  3. adresová sběrnice - je připojena na paměť (procesor generuje adresy pro paměť)
  4. datová sběrnice
  5. řídící sběrnice

• vykonání instrukce
  • instrukce, která se vykoná je uložena v PC (programovém čítači)
  • vykoná se obvykle v několika hodinových taktech
  1. fetch - F: načtení instrukce
     1.  adresa určená obsahem PC je vystavena na adresovou sběrnici a je iniciováno čtení z paměti
     2. paměť dodá na datovou sběrnici kód instrukce, která se má vykonat
     3. instrukce je uložena do IR (instrukčního registru)
  2. instruction decode - ID: dekódování instrukce
     1. Instrukce je dekódována (tzn., že jsou nastaveny řídicí signály pro komponenty procesoru, které se podílí na vykonání instrukce – je např. vybrána operace sčítání a operandy ALU)
  3. execute - E: vykonání instrukce
     1. pokud instrukce vyžaduje pro své vykonání operand z paměti, musí být z příslušné adresy načten tento operand
     2. instrukce je vykonána (např. provede se sčítání), jsou nastaveny příznaky (např. přetečení)
     3. uloží se výsledek do registru, popř. se iniciuje zapsání výsledku do paměti
  • pro další instrukci se určí nový obsah PC
• obvodová realizace procesoru
  • při návrhu procesoru se vychází ze specifikace, která obsahuje požadavky na instrukční soubor, architekturu, šířku dat a adres, výkonnost, plochu na čipu, spotřebu atd.
  • používali jsme (na příkladech, v projektu) tzv. střádačovou architekturu - speciální registr střádač (acumulator) - do něj se ukládají výsledku z ALU (existuje i zásobníková, registrová a smíšená)
    1. zásobníková - má zásobník a registr SP (Stack pointer) a používají se operace PUSH m_a, POP m_a, nejsou registry
    2. registrová
       • sada registrů - připojeny k ALU + sada FP (plovoucí řádová čárka) registrů - připojeny k FPU (operace v plovoucí řádové čárce)
       • ADD R1, R2, R3

Mluvili jsme často o stavu vysoké impedance. Na INP to vysvětloval a na netu jsem našel obrázek: Vysokou impedanci značí první obrázek ⇒ zařízení je odpojeno. Pokud by byly zapojeny oba spínače, nastal by zkrat.

⇒ Třístavový budič ⇒ používá se například u sběrnic, pamětí, …

•  nepřímé adresování
  • například ACC = M[M[123]] ⇒ do akumulátoru vlož obsah paměti s adresou, která je uložena v paměti na adrese 123
  • potřebujeme registr IAR, který nám zjistí a uschová přímou
  • IAR proto má:
    1. výstup na adresovou sběrnici ⇒ pošle adresu do paměti (123)
    2. vstup z datové sběrnice ⇒ přijde mu obsah z paměti daný adresou 123 ⇒ adresa obsahu, který chceme nahrát do akumulátoru

• klasifikace moderních procesorů
  • parametr V - počet instrukcí, které se v jednom okamžiku vydají ke zpracování
  • parametr P - počet současně prováděných (rozpracovaných) instrukcí
  1. subskalární procesory - P = 1, V = 1 (286, 383) (bez zřetězeného zpracovaní)
  2. skalární procesory - P > 1, V = 1 - využívá řetězené zpracování (Pentium) (s zřetězeným zpracováním)
  3. superskalární procesory - P > 1, V > 1 (s zřetězeným zpracováním + multithreading/multicore)
• Flynnova klasifikace procesorů
  • je založena na sledování počtu instrukčních a datových proudů v počítači
  1. jeden (single) instrukční resp. datový proud označujeme symboly SI resp. SD
  2. více než jeden proud (multiple) označujeme analogicky zkratkami MI resp. MD
  • příklady:
    • SISD - von Neumannův počítač
    • SIMD - vektorový procesor - dva vektory (více čísel) sčítá jedna instrukce (např. grafická karta vykonává 1 instrukci na více datech[napr. pixelech])
    • MISD - více počítačů zpracovává stejná data (řídicí počítač Space Shuttle) - stehný problém řeší více počítačů ⇒ bezpečnost (výsledek všech počítačů se porovnává a vybírá výsledná hodnota [např. většina počítačů musí mít stejný výsledek])
    • MIMD - multiprocesorový systém (více instrukcí zpracovává více dat)
• Současné kategorie procesorů
  • Univerzální (Intel, AMD, HP, IBM, …)
  • Grafické (Nvidia, ATI, Matrox, …)
  • Signálové (TI, Fujitsu, …)
  • Aplikační, např. pro mobilní telefony (Intel PXA250, …)
  • Multimediální (TI, Mpact, …)
  • Speciální (šifrovací, kompresní, např. pro MPEG-2, I/O, šachové, hrací, …)

• techniky urychlování výpočtu v HW
  • speciální kódování dle potřeby dané úlohy (není to řešení pro univerzální procesory (nejsou na nich naimplementované aritmetické operace v kódu zbytkových tříd)
  • speciální výpočetní jednotky dle potřeby dané úlohy (FFT - rychlá fourierova transformace)
  • paralelní zpracování (násobné výpočetní jednotky)
  • zřetězené zpracování (=pipeling)

• něco k jednotlivým metodám
  • paralelní zpracování
    • více elementárních úloh běží současně
    • 

• zřetězené zpracování:

Jako vzorvný příklad se uvádí grafický filtr. Vstupem obvodu je pixel, který se po projití obvodu (filtrem) přefiltruje.

• původní filtr je rozdělen a do obvodu jsou přidány registry

• uvažujeme 9-ti stupňový filtr
  • stejně jakou u první obvodu počítame s 65 536 pixelů
  • zpoždění stupně filtru: 10 ns

• celkem tedy: 90 ns + (65535 x 10 ns) = 655 440 ns ⇒ zrychlení 8.9989 krát

• vytvoříme k stupňů oddělených registry
  • počet vstupů: N
  • počet stupňů: k
  • zpoždění stupně: t
  • zpoždění registru: d
  • zrychlení celkem:
  • je třeba položit si otázky
    • kdy má smysl zavést zřetězené zpracování?
      • Pokud je N dostatečně velké!
      • Pokud je zpoždění stupňů přibližně stejné
    • jaký je optimální počet stupňů?

• princip zřetězení se značně překrývá s principy procesorů RISC
• základní myšlenka:

• výhodnější by bylo implementovat pouze jednoduché, ale rychlé instrukce
• cílem je dosáhnout parametru instrukčního souboru CPI = 1
• toho lze dosáhnout pouze trikem - překrýváním cyklů (u jednoduchého procesoru má instrukce CPI minimálně 3)
• 
• Popis cyklů reálného procesoru
• 

• malý počet relativně jednoduchých instrukcí
• snaha o CPI = 1 (ideální teoretický případ) ⇒ v každém taktu se procesoru se většinou dokončí jedna instrukce (reálný průměr je CPI < 1,5)
• všechny instrukce mají stejnou složitost
• přístup k paměti mají pouze 2 instrukce: LOAD a STORE (zbytek pracuje s registry) → malý počet adresivých modů (3-5)
• registrová architektura (dostupných je 32-192)
• rychlý obvodový řadič
• oddělená pamět (cache) instrukcí a dat
• 
  • p.p. řadič = pevně propojený řadič
  • oddělené paměti cache pro instrukce (I) a data (D)

• výukový RISC procesor

• MX: multiplexor, DC: cache dat, =O?: detektor nuly, IC: cache instrukcí, ALU: aritmeticko-logická jednotka, PC: čítač instrukcí, IR: registr instruce, RF: soubor registrů, s.ex: jednotka rozšíření znaménka, dst: adresa cílového registru, src1 a scr2: adresy zdrojových registrů, imm: přímý operand, L/S: load/store
• paměť M je rozdělena na paměť instrukcí (IC) a paměť dat (DC)
• v každém taktu je celý stav zpracování instrukce obsažen úplně a výhradně v obvodech jen jednoho stupně → ostatní stupně jsou volné a dají se použít pro paralelní zpracování dalších nezávislých instrukcí

• tyto konflikty mohou vést ke zpomalení linky

1. Strukturální
   • obvodová struktura neumožňuje současné provedení určitých akcí (např. současné čtení dvou hodnot z paměti nebo současné provedení dvou sčítání, pokud má procesor jednu ALU)
   • 
2. Datové
   • když jsou zapotřebí data z předcházející instrukce, která ještě není dokončena
   • 
   • klasifikace (nechť máme dve instrukce v pořadí (i, j)), Pozn. k významu (AAB: operace A se začne vykonávat před dokončením operace B)
     • RAW - Read After Write (j se snaží o přečtení registru předtím, než do něj i zapíše, j pak dostává starou hodnotu)
     • WAW - Write After Write (j se snaží zapsat do registru předtím, než do něj zapíše i, takže dojde k přepisu instrukcí i a instrukce j jakoby se nevykonala)
     • WAR - Write After Read (j zapisuje do registru předtím, než ho i přečtě)
   • Bypassing
     • poskytnutí mezivýsledku dřív než bude zapsán do registru
     • je to umožněno přidáním speciálních datových cest (např. příklady na obrázku)
     • pomáhá řešit datové konflikty
     • 
3. Řídící
   • když skoková instrukce mění obsah PC nebo jiné
   • 
   • neví, kam skočit, protože adresa bude známa až po fázi M na řádku BC
   • řešení:

• experimenty bylo zjištěno, že četnost skoků v programech je značná - z toho se asi 83% povede
• u skoků je třeba zrychlit zjištění cílové adresy (kam skočit), proto se používá malá cache pamět pro uložení cílových adres (BTB - Branch Target Buffer)
• u podmíněných skoků jsou navíc ještě vyhodnocovány podmínky, o jejich splnění je možné spekulovat predikce skoků - ta může být statická (kompilátor nastaví bit predikce) nebo dynamická (pomocí speciálního HW)
• predikce (spekulace) probíhá podle předchozích směrů skoku (historii lze popsat binárním řetězcem několika bitů)
• nejjednodušší prediktor = Jednobitový prediktor
  • použí 1 bit z historie (tj. předchozí skok) a předpovídá následující
  • 
  • stav 0 = skok se minule neprovedl, předpověď je neskoč (-)
  • stav 1 = skok se minile provedl ⇒ předpověď je skoč (+)
  • pokud je předpověd špatná musí být špatná větev programu ukončena a musí začít načítání instrukcí ze správné větve (je třeba aktualizovat BTB, to stojí několik taktů zřetězené linky)

Zřetězené zpracování přináší urychlení výpočtu nejen v procesorech, ale i jiných číslicových obvodech (např. pro zpracování obrazu, bioinformatických dat apod.). Pokud použijeme zřetězené zpracování, musíme dodat řadu podpůrných obvodů a řešit řadu nových problémů. Moderní procesory používají kromě zřetězení i další koncepty:

• superskalární architektury
• VLIW procesory - má více ALU - tzn. může zároveň dělat více operací ⇒ k tomu slouží dlouhé instrukce
• vektorové procesory
• multivláknové procesory

• = procesory s komplexním instrukčním souborem
• vysoká složitost instrukcí ⇒ nutný systematický návrh řadiče procesoru
• vykonání strojové instrukce probíhá posloupností mikrooperací (předpepsána mikroinstrukcí v řídící paměti)
• řidící paměti byly pevné (Read-Only Memory = ROM) a mnohem rychlejší než RAM (je rychlejší načíst 1 složitou instrukci z RAM, která „obsahuje“ 10 obyčených instrukcí, které se už načítají z napr. EEPROM než všech 10 instrukcí načítat z RAM)
• díky vývoji mikrotechniky se řídící pamět přesuna na cache; to umožnilo držet krok s RISC architekturou
• patří mezi nejvíce rozšířené (486, Pentium)
•