Résumé de section

  • Replier Déplier

    Généralités

    Tout replier Tout déplier

    • Vážení študenti,

      vitajte v kurze Úvod do paralelného programovania.

      Koncom minulého storočia bolo paralelné programovanie doménou relatívne úzkej skupiny ľudí. Hlavným dôvodom bola skutočnosť, že pre vykonávanie takýchto programov bol potrebný špeciálny hardvér, ktorý nebol bežne dostupný širokému spektru používateľov. Od tých čias však nastalo mnoho zmien a hardvér umožňujúci paralelné výpočty sa dnes bežne dostáva ku každému používateľovi. Za jeden z významných míľnikov možno považovať aj použitie Beowulf klastra, čo otvorilo možnosti paralelného počítania za relatívne nízke náklady. V súčasnosti je takýto hardvér bežne dostupný a poskytovaný pre vedecké a komerčné účely výpočtovými strediskami a univerzitami v podobe superpočítačov a vysokovýkonných klastrov. Zároveň si ale treba uvedomiť, že hardvér umožňujúci paralelné počítanie sa dostal aj do rúk bežných používateľov v podobe viacjadrových procesorov, bežne používaných v stolových a prenosných počítačoch alebo v podobe grafických kariet disponujúcich nezanedbateľným výpočtovým výkonom. V neposlednom rade je potrebné sa zmieniť aj o stále stúpajúcom trende nasadzovania cloudových riešení, ktoré dokážu poskytnúť používateľom širokú škálu infraštruktúry pre paralelné počítanie.

      Tieto zmeny si vyžadujú aj zmenu pohľadu na paralelné programovanie ako také a je potrebné sa zamerať na vzdelávanie v tejto oblasti. Veľké množstvo študentov si často ani len neuvedomuje potenciál hardvéru, ktorý dennodenne používajú. Samozrejme existuje nespočetne veľa aplikácií, ktoré si vystačia aj bez potreby znalosti akéhokoľvek paralelného programovania, avšak v momente, kedy už výkon jedného jadra procesora nie je postačujúci, je potrebné poznať zákonitosti a nástroje pre paralelné programovanie umožňujúce plne využiť výpočtový potenciál súčasného hardvéru.

      S cieľom umožniť študentom naučiť sa základy paralelného programovania sme zaviedli nový kurz určený pre študentov bakalárskeho stupňa aplikovanej informatiky. Absolvovaním tohto kurzu nadobudnú potrebné vedomosti a zručnosti, ktoré môžu ďalej využiť v rámci iných predmetov alebo vo svojej ďalšej profesii. Absolvovanie tohto predmetu si vyžaduje znalosti z programovania v jazyku C, ako aj niektoré poznatky z oblasti počítačových sietí a operačných systémov, najmä týkajúce sa oblasti procesov a vlákien. Preto odporúčame absolvovanie tohto kurzu až po absolvovaní základného kurzu z programovania, počítačových sietí a operačných systémov.

      Táto učebnica pozostáva z niekoľkých celkov. V prvej časti sa oboznámime s dôvodmi a historickým vývojom hardvéru, ktorý zohrával významnú úlohu pri rozvoji paralelného programovania a počítania. Tiež sa budeme zaoberať architektúrami paralelných počítačov vhodných pre vysokovýkonné počítanie. V ďalších častiach sa budeme zaoberať základnými technikami používanými pri navrhovaní paralelných programov a efektivite paralelných programov. Čitateľ sa bude môcť oboznámiť so základnou syntaxou používanou v rámci štandardu MPI alebo OpenMP, ako aj so stručným úvodom k platforme a programovému rozhraniu CUDA pre programovanie GPGPU. V jednotlivých kapitolách sa nachádzajú rôzne poznámky a teoretické alebo praktické úlohy na precvičenie a lepšie pochopenie danej problematiky.

      Radi by sme poznamenali, že problematika paralelného programovania a vysokovýkonného počítania je svojim rozsahom komplexná a rozsiahla téma, ktorú nie je možné pokryť jednou učebnicou. Našim cieľom je poskytnúť čitateľovi základné poznatky a možnosť oboznámiť sa s bežnými programátorskými technikami používanými v praxi, ktoré sú nevyhnutne potrebné na vývoj a implementáciu efektívnych paralelných programov. Preto by sme radi povzbudili čitateľa k ďalšiemu štúdiu manuálov a dokumentácie.


      Autori

    • Tento kurz vznikol s podporou Kultúrnej a edukačnej grantovej agentúry (KEGA) MŠVVaŠ SR v rámci projektu KEGA 011UMB-4/2017, ktorého hlavným cieľom je prispieť k efektívnemu využívaniu prostriedkov pre vysokovýkonné počítanie, ako aj motivovať nových používateľov k vývoju efektívnych paralelných programov.

      © Miroslav Melicherčík, Michal Pitoňák, Pavel Neogrády


    • Fóra a chaty
    • Oznámenia Forum
    • Otázky a odpovede k obsahu kurzu Forum

      V tomto fóre diskutujeme o otázkach, ktoré potrebujete zodpovedať počas štúdia v kurze, týkajúci sa študijného obsahu.

    • On-line diskusia Chat

      V dohodnutých časoch je možné diskutovať priamo s tútorom.

  • Replier Déplier

    Úvod

    • Úvod Fichier
      164.1 Ko · Modifié 13 janv. 20, 13:04
  • Replier Déplier

    Hardvér pre paralelné počítanie

    V tejto kapitole sa budeme zaoberať nasledujúcimi témami:

    • Historický vývoj
      • Rýchla vyrovnávacia pamäť
      • Virtuálna pamäť
      • Inštrukčný paralelizmus
    • Paralelné architektúry
      • Flynnova taxonómia
      • Architektúra SIMD
      • Architektúra MIMD
    • Viacjadrové procesory
      • Systém so zdieľanou pamäťou
      • Systém s distribuovanou pamäťou
    • Počítačový klaster
    • Prepojovacie siete
      • Systémy so zdieľanou pamäťou
      • Systémy s distribuovanou pamäťou
    • Akcelerátory GPGPU
    • Cloudové počítanie

  • Replier Déplier

    Základy paralelizácie

    V tejto kapitole sa budeme zaoberať nasledujúcimi témami:

    • Paralelizmus
      • Dekompozícia problému
      • Granularita výpočtu
    • Výkonnosť paralelných algoritmov
      • Zrýchlenie a efektívnosť paralelného programu
      • Amdahlovo pravidlo
    • Škálovateľnosť
    • Vyvažovanie záťaže
      • Statické vyvažovanie záťaže
      • Dynamické vyvažovanie záťaže
    • Návrh paralelného programu
      • Rozdelenie
      • Komunikácia
      • Aglomerácia
      • Mapovanie

    • Materiál k štúdiu
    • Základy paralelizácie Fichier
      1.5 Mo · Modifié 18 févr. 20, 19:09
  • Replier Déplier

    Programovanie pre model s distribuovanou pamäťou - MPI

    V tejto kapitole sa budeme zaoberať nasledujúcimi témami:

    • Jednoduchý program v prostredí MPI
      • Inicializácia a ukončenie paralelného programu
      • Kompilovanie a spúšťanie MPI programov
      • Práca so vstupmi a výstupmi
      • Komunikátor
    • Komunikácia
      • Blokujúca komunikácia dvoch procesov
      • Riešená úloha
      • Neblokujúca komunikácia dvoch procesov
      • Riešená úloha
      • Kolektívna komunikácia procesov
      • Riešená úloha
      • Jednostranná komunikácia procesov
    • Odvodené údajové typy
      • Zbaľovanie a rozbaľovanie
      • Nové údajové typy
    • Paralelné vstupno-výstupné operácie
    • Meranie času v MPI programe
    • Efektívnosť paralelného MPI programu
      • Komunikácia
      • Synchronizácia a serializácia

  • Replier Déplier

    Rozdelený globálny adresný priestor

    V tejto kapitole sa budeme zaoberať nasledujúcimi témami:

    • Global Arrays
      • Prehľad a história
      • Základné funkcie
      • Riešená úloha
    • GASPI
      • Prehľad a história
      • Segmenty, komunikácia a synchronizácia
      • Kolektívne operácie
      • Odolnosť voči chybám pri vykonávaní paralelného programu
      • Riešená úloha

    • Materiál k štúdiu
    • Rozdelený globálny adresný priestor Fichier
      261.1 Ko · Modifié 7 janv. 20, 09:57
    • Zdrojové kódy k textu
    • PGASexample1 Fichier
      1.7 Ko · Déposé le 2 janv. 20, 12:01
    • PGASexample2 Fichier
      2.0 Ko · Déposé le 2 janv. 20, 12:01
  • Replier Déplier

    Programovanie pre model so zdieľanou pamäťou - OpenMP

    V tejto kapitole sa budeme zaoberať nasledujúcimi témami:

    • Jednoduchý program v prostredí OpenMP
      • Paralelná oblasť
      • Kompilovanie a spúšťanie OpenMP programov
      • Knižnica OpenMP
    • Rozdeľovanie práce
      • Direktíva for
      • Riešená úloha
      • Direktíva sections
      • Direktíva task
      • Direktíva single
      • Klauzuly direktív
    • Synchronizácia
      • Direktíva master
      • Direktíva barrier
      • Direktíva taskwait
      • Direktíva critical
      • Direktíva ordered
      • Direktíva atomic
      • Direktíva flush
    • Meranie času v OpenMP programe
      • Riešená úloha
    • Efektívnosť paralelného OpenMP programu
      • Optimalizácia paralelného programu

    • Materiál k štúdiu
    • Programovanie pre model so zdieľanou pamäťou - OpenMP Fichier
      400.3 Ko · Modifié 13 janv. 20, 13:05
    • Zdrojové kódy k textu
    • OMPhello Fichier
      131 octets · Déposé le 2 janv. 20, 12:01
    • OMPhello2 Fichier
      504 octets · Déposé le 2 janv. 20, 12:01
    • OMPfor Fichier
      320 octets · Déposé le 2 janv. 20, 12:02
    • OMPpi Fichier
      554 octets · Déposé le 2 janv. 20, 12:02
    • OMPsections Fichier
      857 octets · Déposé le 2 janv. 20, 12:02
    • OMPtask Fichier
      847 octets · Modifié 7 janv. 20, 01:03
    • OMPsingle Fichier
      446 octets · Déposé le 2 janv. 20, 12:02
    • OMPmaster Fichier
      343 octets · Déposé le 2 janv. 20, 12:02
    • OMPbarrier Fichier
      358 octets · Déposé le 2 janv. 20, 12:02
    • OMPordered Fichier
      486 octets · Déposé le 2 janv. 20, 12:02
    • OMPsort Fichier
      1.5 Ko · Déposé le 2 janv. 20, 12:02
  • Replier Déplier

    Programovanie akcelerátorov GPGPU - CUDA

    V tejto kapitole sa budeme zaoberať nasledujúcimi témami:

    • Jednoduchý program pre GPGPU
      • Kompilovanie a spúšťanie programov pre GPGPU
    • Pamäť zariadenia GPGPU
      • Alokácia pamäte
      • Prenos údajov
      • Riešená úloha
    • Hierarchia pamäte GPGPU
      • Hostiteľská pamäť
      • Globálna pamäť
      • Registre
      • Zdieľaná pamäť
      • Pamäť konštánt
      • Pamäť textúr
    • Synchronizácia
      • Atomické operácie

    • Materiál k štúdiu
    • Programovanie akcelerátorov GPGPU - CUDA Fichier
      503.6 Ko · Modifié 13 janv. 20, 13:05
    • Zdrojové kódy k textu
    • CUDAprint Fichier
      596 octets · Modifié 7 janv. 20, 01:03
    • CUDAvecadd Fichier
      1.6 Ko · Modifié 7 janv. 20, 01:04
    • CUDAmatmul Fichier
      4.8 Ko · Déposé le 7 janv. 20, 01:04
  • Replier Déplier

    Úlohy na precvičenie

    V tejto časti ponúkame niekoľko zadaní úloh, ktoré je možné riešiť pomocou rôznych metód a nástrojov. Úlohy je možné riešiť pomocou paralelných programov s distribuovanou pamäťou, ako aj so zdieľanou pamäťou. Väčšina dostupných systémov vhodných pre vysokovýkonné počítanie umožňuje spúšťať tzv. hybridné paralelné programy, ktoré pri implementácií využívajú oba prístupy, ako s distribuovanou, tak aj so zdieľanou pamäťou. Kombináciou týchto dvoch prístupov je možné zväčša dosiahnuť vyššiu výkonnosť paralelných programov.

    Vytvorené programy je možné otestovať aj na bežne dostupných stolových alebo prenosných počítačoch, ktoré sú vybavené viacjadrovými procesormi. Vhodnejším riešením je však použitie vysokovýkonného klastra alebo superpočítača, ktorý disponuje vysokorýchlostným prepojením viacerých výpočtových uzlov a umožní rozsiahlejšie meranie efektívnosti a škálovania paralelného programu.

    Odhadnutie správneho počtu použitých výpočtových jadier niekedy priamo súvisí s návrhom samotného algoritmu. V iných prípadoch môže byť zvolenie vhodného počtu procesov a vlákien pre vykonávanie paralelného programu náročnejšie a vyžaduje určité skúsenosti a znalosti špecifík používaného výpočtového systému pre vysokovýkonné počítanie.


    • Hodnotené úlohy na domáce riešenie
    • Úloha 1 - Monte Carlo π Devoir

      V jazyku C navrhnite a vytvorte paralelný program na odhad hodnoty konštanty π pomocou metódy "Monte Carlo".

    • Úloha 2 - Násobenie matice a vektora Devoir

      V jazyku C navrhnite a vytvorte paralelný program, ktorý vynásobí maticu a vektor, pričom maticu rozblokuje po stĺpcoch.

    • Úloha 3 - Eratostenovo sito Devoir

      V jazyku C navrhnite a vytvorte paralelný program na hľadanie prvočísel pomocou Eratostenovho sita po číslo 2n, pričom číslo n bude zadané ako vstup.

    • Úloha 4 - Mandelbrotová množina Devoir

      V jazyku C navrhnite a vytvorte paralelný program na výpočet Mandelbrotovej množiny M.

    • Úloha 5 - Producent, konzument Devoir

      V jazyku C navrhnite a vytvorte paralelný program, ktorý implementuje program typu producent-konzument.

    • Úloha 6 - Aproximácia π. Devoir

      V jazyku C navrhnite a vytvorte paralelný program, na aproximáciu π.