Flynnova klasifikace paralelních systémů

Flynnova klasifikace paralelních systémů (SIMD, MIMD, SISD, MISD), Amdahlův zákon, měření výkonnosti počítačů, benchmarky

Michael J. Flynn, narozen 20. května 1934 navrhl v roce 1996 tzv. Flynnovu Taxonomii, která nabízí kategorizaci pro strukturu počítače na základě toku instrukcí a toku dat. Tedy na počtu instrukcí a datových položek, které lze paralelně (najednou) zpracovat.

  • Tok instrukcí
    • jedná se o sekvenci instrukcí čtenou z paměti (program)
  • Tok dat
    • jedná se o operace prováděně na datech v procesoru

Můžeme paralelně zpracovávat tok instrukcí, tok dat, nebo obojí. Toto nám dává dohromady 4 kombinace, v závislosti na tom, zdali jsou toky sériové (jeden tok) nebo paralelní (více toků).

Rozdělení počítačů podle Flynnovy klasifikace

  • Single Instruction Stream, Single Data Stream (SISD)
  • Single Instruction Stream, Multiple Data Streams (SIMD)
  • Multiple Instruction Streams, Single Data Stream (MISD)
  • Multiple Instruction Streams, Multiple Data Streams (MIMD)

Single Instruction Stream, Single Data Stream (SISD)

Tato architektura reprezentuje tradiční výpočetní systém. Jeden program (tok instrukcí) se provádí na jednom setu dat (toku dat). Toto odpovídá programu napsanému pomocí procedurálního programovacího jazyka. Program běží na jedno-jádrovém CPU.

Reprezentace SISD
obr. 1: Reprezentace SISD. Každá barva bloku odpovídá jiné instrukci.
Dostupné z: https://study.com/academy/lesson/flynns-architecture-taxonomy-types-alternatives.html

Single Instruction Stream, Multiple Data Streams (SIMD)

Jedna z nejčastějších paralelních architektur, díky její efektivitě. Je napsán jeden program, jehož kopie běží na různých CPU jádrech. V této architektuře musí být dosažena synchronizace na úrovni instrukcí. Jinak řečeno, v určitý moment by měla totožná instrukce běžet na všech procesorech a každý procesor vykoná tuto instrukci na datech, která má k dispozici.

Reprezentace SIMD
obr. 2: Reprezentace SIMD. Každá barva bloku odpovídá jiné instrukci. Ve stejnou chvíli se vykonává na různých datech tatáž instrukce
Dostupné z: https://study.com/academy/lesson/flynns-architecture-taxonomy-types-alternatives.html

Multiple Instruction Streams, Single Data Stream (MISD)

Toto není příliš používaná architektura. Je používána pokud chceme aplikovat nebo testovat různé algoritmy na totožných datech. Například aplikace různých grafických filtrů na stejný obrázek.

Reprezentace MISD
obr. 3: Reprezentace MISD. Každá barva bloku odpovídá jiné instrukci. Ve stejnou chvíli se vykonává na stejných datech různá instrukce
Dostupné z: https://study.com/academy/lesson/flynns-architecture-taxonomy-types-alternatives.html

Multiple Instruction Streams, Multiple Data Streams (MIMD)

Toto je v dnešní době nejvíce využívaná architektura. Různé instrukce jsou vykonávány na různých datech. Dnes jsou všechny více-jádrové CPU považovány za MIMD, neboť každé CPU může vykonávat jiný tok instrukcí (program) na různých datech.

Reprezentace MIMD
obr. 4: Reprezentace MIMD. Každá barva bloku odpovídá jiné instrukci. Ve stejnou chvíli se vykonává na různých datech různá instrukce
Dostupné z: https://study.com/academy/lesson/flynns-architecture-taxonomy-types-alternatives.html

Amdahlův zákon

Jedná se o pravidlo, k vyjádření maximálního předpokládaného zlepšení systému poté, co je vylepšena pouze některá z jeho částí.

Využívá se např. u víceprocesorových systémů k předpovězení teoretického maximálního zrychlení při přidávání dalších procesorů.

Velikost zlepšení ze značí S a můžeme ji vypočítat následovně:

Výpočet maximálního zlepšení
obr. 5: Výpočet maximálního zlepšení
Dostupné z: https://cs.wikipedia.org/wiki/Amdahlův_zákon

Pokud chceme zjistit maximální zlepšení celého systému při vylepšení pouze některých částí, postup je následovný:

Výpočet maximálního zlepšení při vylepšení některé z jeho částí
obr. 6: Výpočet maximálního zlepšení při vylepšení některé z jeho částí
Dostupné z: https://cs.wikipedia.org/wiki/Amdahlův_zákon

Platí, že: Zvýšení výkonnosti dosažitelné nějakým zlepšením je omezené mírou používání tohoto zlepšení. Je zde tedy omezení, pokud budeme zlepšovat algoritmus, který tvoří 10% výpočtů programu. Největšího zlepšení dosáhneme, pokud budeme zlepšovat nejčastěji používané části.

Měření výkonnosti počítačů

Při měření výkonnosti musíme vzít v potaz dva hlavní parametry:

  • taktovací frekvence
  • počet taktů nutný na vykonání instrukce

Jen jeden parametr nám nestačí, protože nebudeme schopni porovnat různé architektury na různých programech.

Ale co když máme různé programy, každý s jinými instrukcemi. Pokud spočítáme rychlost výkonu na nějakém programu, tak tato hodnota nebude odpovídat skutečnému výkonu (například zpracování jiného programu).

Máme dva způsoby jak měřit výkonnost počítače:

  • Workload
    • Jedná se o simulování typické zátěže počítače pomocí spouštění typických programů. Je to složité na automatizování (opakované a opakovatelné spouštění).
  • Benchmarky
    • Jsou programy, které jsou specificky určeny k měření výkonnosti. Často se používají sady benchmarků, které testují různé aspekty a doufáme, že měření předpoví chování počítače při stejné zátěži.

Časem vznikl cíl, vytvořit sady benchmarků, které budou vhodné pro jednoduché porovnání výkonnosti. Tyto sady obsahují testy, které pokrývají běžné úkony procesoru pro co nejvíce optimální výsledek.

  • existují různé sady pro měření různých věcí (CPU, GPU, překladače, emaily, databázové vyhledávače, atd.)

Máme sady benchmarků, které měří výkonnost celočíselných výpočtů (překladač C, šachový algoritmus, simulace kvantového počítače, atd.) nebo i sady pro měření výkonnosti operací s plovoucí čárkou (metoda konečných prvků, molekulární dynamika, atd.).

Problémy při měření výkonnosti

  1. Očekáváme, že při při zlepšení výkonnosti části systému dojde k úměrnému zlepšení výkonnosti celého systému.
  2. Používáme špatná měřítka výkonnosti
    • nemůžeme použít pouze jednu či dvě metriky (taktovací frekvence, počet instrukcí, atd.)
    • existuje závislost mezi těmito metrikami (taktovací frekvence závisí na chlazení; počet taktů na vykonání instrukce závisí na konkrétní instrukci, atd.)

Zdroje