Detail předmětu

Paralelní a distribuované algoritmy

FIT-PRLAk. rok: 2024/2025

Vlastnosti paralelních a distribuovaných architektur a abstraktní modely paralelismu. Základní typy topologií, synchronní a asynchronní algoritmy. Komunikace v paralelních a distribuovaných systémech. Distribuované a paralelní algoritmy a jejich složitost. Řešení typických problémů paralelismu. Algoritmy řazení, algoritmy vyhledávání, vektorové a maticové algoritmy. Model PRAM (Parallel Random Access Machine), suma prefixů a její aplikace. Algoritmy nad seznamy, stromy a grafy.

Proč je předmět vyučován

Cílem předmětu je naučit studenty vytvářet paralelní algoritmická řešení základních úloh jako jsou řazení, vyhledávání, práce se seznamy a pod. Dále student bude schopen vytvářet správně paralelní a distribuované aplikace a správně využívat synchronizačními mechanismy.

Jazyk výuky

čeština

Počet kreditů

Garant předmětu

doc. Ing. František Zbořil, Ph.D.

Zajišťuje ústav

Ústav inteligentních systémů (UITS)

Vstupní znalosti

Základní znalosti algoritmizace.

Pravidla hodnocení a ukončení předmětu

Bodové hodnocení výsledků půlsemestrálního testu a vypracovaného projektu.
Písemný půlsemestrální test, průběžná kontrola a hodnocení projektů. Test nemá náhradní termín a závěrečná zkouška má dva možné náhradní termíny. Pro získání bodů ze zkoušky je nutné zkoušku vypracovat tak, aby byla hodnocena více body, než je minimální hranice uvedená v informačním systému. V opačném případě bude zkouška hodnocena 0 body.

Podmínky zápočtu
Získání alespoň jednoho bodu z každého projektu a získání alespoň 15 bodů v průběhu semestru. Jakákoli forma plagiátorství nebo nesamostatné práce vede k neudělení zápočtu. Zápočty uděluje cvičící, který opravuje půlsemestrální zkoušku.

Učební cíle

Seznámení studentů se základními obraty paralelních a distribuovaných výpočtů. Obecné principy paralelních a distribuovaných algoritmů a jejich časová složitost.
Studenti se seznámí se základy paralelních a distribuovaných výpočtů a s obecnými principy paralelních a distribuovaných algoritmů a jejich časovou složitostí.
Studenti se naučí obecné principy a možnosti paralelizace algoritmů.

Doporučená literatura

Akl, S.: The Design and Analysis of Parallel Algorithms, Prentice-Hall International, ISBN 0-13-200073-3
Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar: Introduction to Parallel Computing, Addison Wesley, 2003, ISBN: 0-201-64865-2
Jaja, J.: An Introduction to Parallel Algorithms, Addison-Wesley, 1992, ISBN 0-201-54856-9
Reif, J: Synthesis of Parallel Algorithms, Morgan Kaufmann, 1993, ISBN:155860135X

Elearning

eLearning: aktuální otevřený kurz

Zařazení předmětu ve studijních plánech

  • Program MITAI magisterský navazující

    specializace NGRI , 1 ročník, letní semestr, povinný
    specializace NADE , 1 ročník, letní semestr, povinný
    specializace NISD , 1 ročník, letní semestr, povinný
    specializace NMAT , 1 ročník, letní semestr, povinný
    specializace NSEC , 1 ročník, letní semestr, povinný
    specializace NISY do 2020/21 , 1 ročník, letní semestr, povinný
    specializace NNET , 1 ročník, letní semestr, povinný
    specializace NMAL , 1 ročník, letní semestr, povinný
    specializace NCPS , 1 ročník, letní semestr, povinný
    specializace NHPC , 1 ročník, letní semestr, povinný
    specializace NVER , 1 ročník, letní semestr, povinný
    specializace NIDE , 1 ročník, letní semestr, povinný
    specializace NISY , 1 ročník, letní semestr, povinný
    specializace NEMB do 2023/24 , 1 ročník, letní semestr, povinný
    specializace NSPE , 1 ročník, letní semestr, povinný
    specializace NEMB , 1 ročník, letní semestr, povinný
    specializace NBIO , 1 ročník, letní semestr, povinný
    specializace NSEN , 1 ročník, letní semestr, povinný
    specializace NVIZ , 1 ročník, letní semestr, povinný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

doc. Ing. František Zbořil, Ph.D.
doc. Dr. Ing. Petr Hanáček

Osnova

  • Úvod, vlastnosti paralelních a distribuovaných architektur.
  • Abstraktní modely paralelismu, PRAM (Parallel Random Access Machine). 
  • Distribuované a paralelní algoritmy a jejich složitost.
  • Komunikace v paralelních a distribuovaných systémech.
  • Základní typy topologií, synchronní a asynchronní algoritmy.
  • Algoritmy řazení.
  • Algoritmy vyhledávání.
  • Maticové algoritmy.
  • Sumy prefixů a jejich aplikace.
  • Algoritmy nad seznamy a grafy.
  • Synchronizační algoritmy a úlohy.
  • Mechanismy pro synchronizaci.
  • Jazyky pro paralelní a distribuované výpočty.

Projekt

13 hod., povinná

Vyučující / Lektor

Ing. Petr Veigend, Ph.D.

Osnova

  1. Samostatné projekty v paralelním programovacím jazyce.

Elearning

eLearning: aktuální otevřený kurz