Paralelno
računanje i optimizacija
| |
Smjer: |
Teorijska kompjuterska nauka |
| |
Semestar: |
VIII |
| |
Tip kursa: |
Obavezni |
| |
Fond sati: |
3+2+0 |
| |
Broj
ECTS kredita: |
8 |
Nastavni program:
-
Uvod u paralelno programiranje; Motivacija,
ciljevi i istorija; Naučne, inžinjerske i komercijalne primjene;
-
Platforme za paralelno programiranje; VLIWP;
Von Neumman-ovo usko grlo;
-
Dihotomija paralelnih računara; Fizička
organizacija računara; Mrežne topologije; Troškovi komunikacije;
-
Principi dizajna paralelnih algoritama;
Dekompozicija, zadaci i graf zavisnosti; Tehnike dekompozicije; Zadaci i
zavisnosti; Data-paralel; Zadatak-paralel; master-slave;
-
Osnovni operatori komunikacije: One-to-all;
All-to-one; All-to-all;
-
Mjerenje kvalitete i performansi paralelnih
algoritama; asimptotska analiza;
-
Eratosthene-ovo sito;
-
Algoritmi za guste matrice; Množenje matrica;
Canon i DNS algoritmi; Rješavanje sistema linearnih jednačina;
-
Paralelni algoritmi za sortiranje: Kako
upoređivati elemente; Bubble sortiranje i varijante; Quick sortiranje; Radix
sortiranje;
-
Osnovni paeralelni algoritmi na grafovima:
Prim-ov algoritam; Dijkstra algoritam; Floyd algoritam; Tranzitivno
zatvorenje; Algoritmi na rijetkim grafovima;
-
Pretraživanje za diskretne probleme
optimizacije: Paralelni branch-and bound; Paralelni DFS; Analiza i
eksperimentalni rezultati za LDFS; Paralelni BFS;
-
Paralelno dinamičko programiranje: Najkraći
put, 0/1 knapsack problem; Najduži zajednički podstring, Floyd all-pairs
shortest problem; Optimalno množenje matrica;
-
Diskretna Fourier transformacija; Paralelni
FFT;
Literatura:
-
Michael Quinn: Parallel programming in C
with MPI and OpenMp
-
Anannth Grama, Anshul Gupta, George Karypis,
Vipin Kumar: Introduction to Parallel Computing
-
Thomas Corman, Charles Leiserson, Ronald
Rivest: Introduction to Algorithms
-
Robert Sedgewick: Algorithms in C/C++,
Addison-Wisley, 1999.
-
William Gropp: Beowulf Cluster Computing
with Linux