FOI Nastava - Paralelno programiranje

Sadržaj se učitava...

FOI Nastava

apps

mdi-login

Paralelno programiranje

Parallel Progamming
2022/2023

4 ECTSa

Informacijski i poslovni sustavi 1.2 (IPS)

Katedra za teorijske i primijenjene osnove informacijskih znanosti

6. semestar

Osnovne informacijemdi-information-variant

Izvođači nastavemdi-account-group

Nastavni plan i programmdi-clipboard-text-outline

Model praćenjamdi-human-male-board

Ispitni rokovimdi-clipboard-check-outline

Rasporedmdi-calendar-clock

Konzultacijemdi-account-voice

Izvođenje kolegija

Studij	Studijski program	Semestar	Obavezan
Informacijski i poslovni sustavi 1.2 (IPS)	Razvoj programskih sustava	6	izborni
Informacijski i poslovni sustavi 1.2 (IPS)	Umreženi sustavi i računalne igre	6	izborni
Informacijski i poslovni sustavi 1.2 (IPS)	Umjetna inteligencija u poslovanju	6	izborni
Informacijski i poslovni sustavi 1.2 (IPS)	Analiza i dizajn poslovnih sustava	6	izborni

Cilj kolegija

Upoznati studente s temeljima paralelnog programiranja u višejezgrenim i višeprocesorskim sustavima te grodzovima računala, metoda paralelizacije algoritama, komuniciranja između jezgri, procesor ili računala u grozdu. Upoznati studente s mogućnostima izgradnje paralelnih računalnih programa u standardnim programskim jezicima.

Preduvjeti

Matematika 2 (IPS 1.2)
Programiranje 2 (IPS 1.2)
Operacijski sustavi (IPS 1.2)
Strukture podataka i algoritmi (IPS 1.2)

Norma kolegija

Predavanja

30 sati

Vježbe u praktikumu

15 sati

Nastavnik	Uloga na kolegiju	Oblik nastave	Tjedana	Sati	Grupa
Lovrenčić Alen	Nositelj	Predavanja Vježbe u praktikumu	0 0	2 1	1 1

Sadržaj predavanja

Uvod
Platforme za paralelno programiranje. Vrste paralelizma. Pipelining. Višedretvenost. Paralelizacija memorije. Procesna paralelizacija. (2 sata)
Principi izgradnje paralelnih algoritama
Tehnike dekompozicije.Karakteristike zadaća i interakcija. Mapiranje i balansiranje opterećenja. Modeli paralelnih algoritama (2 sata)
Temelji komunikacije među procesima
Objavljivanje „jedan za sve“ i redukcija „svi za jednoga“. Objavljivanje „svi za sve“ i personalizacija. (2 sata)
Analiza paralelnih programa
Mjere složenosti paralelnih sustava. Granularnost. Skalabilnost. Asimptotska analiza paralelnih programa (4 sata)
Programiranje pomoću paradigme prosljeđivanja poruka
Sučelje za prenošenje poruka. Kartezijeve topologije. (2 sata)
Programiranje za sustave s dijeljenim adresnim prostorom
Sustavi dretvi i sinkronizacija. Asinkroni programi. Prevencija i otkrivanje međusobnog zaključavanja. (2 sata)
Paralelno sortiranje
Paralelno sortiranje temeljeno na prenošenju poruka. Mreže za sortiranje. Paralelno Shellovo sortiranje. Paralelni quicksort. Paralelno sortiranje prebrojavanjem. Paralelni radix sort. (4 sata)
Paralelni matrični algoritmi
Strassenovo množenje matrica. Cannonovo množenje matrica. Množenje matrice vektorom.DNS algoritam (4 sata)
Paralelni algoritmi pretraživanja
Paralelno pretraživanje polja. Paralelno pretraživanje i ophodnja stabala i grafova. (2 sata)
Paralelni algoritmi na grafovima
Traženje najkraćeg puta. Dijkstrin algoritam. Floyd-Warshalow algoritam. Algoritmi za minimalno razapinjuće stablo. Algoritam za tranzitivno zatvorenje. Algoritam za traženje maksimalnog nezavisnog skupa. (4 sata)
Paralelno dinamičko programiranje
Floydov algoritam za traženje svih najkraćih puteva. Problem najduže zajedničke sekvence. 0/1 ranac. Dinamički algoritmi za traženje najkraćeg puta. (4 sata)

Sadržaj seminara/vježbi

Ishodi učenja kolegija

Objasniti konkurentnost rada s memorijom kod računalnih programa s paralelnim procesima te strategije rješavanja konflikata rada sa zajedničkom memorijom.
Definirati različite konfiguracije računalnih mreža sa stajališta izgradnje paralelnih algoritama.
Organizirati sustav poruka u višeprocesorskom sustavu pri izradi paralelenog algoritma.
Izgraditi paralelni algoritam, za zadani problem, temeljen na metodi rekurzivne paralelizacije, dekompozicije ulaznih podataka i dekompozicije prostora pretraživanja.
Ocijeniti vremensku i prostornu složenost izgrađenog paralelnog algoritma.
Izgraditi paralelni algoritam iz važnih područja paralelizacije (rijetke matrice, sortiranje, algoritmi na grafovima, optimizacijski algoritmi, dinamičko programiranje) u skladu s teorijom paralelnih algoritama
Odabrati adekvatnu strategiju dijeljenja memorijskog prostora u višejezgrenom paralelnom algoritmu na temelju prednosti i nedostataka različitih strategija dijeljenja memorije i potreba algoritma.

Ishodi učenja programa

razumjeti stanje i trendove razvoja suvremenih informacijskih i komunikacijskih tehnologija (ICT), razumjeti njihov utjecaj na pojedinca, organizaciju i društvo te procijeniti njihovu primjenjivost u zadanom kontekstu
razumjeti i primijeniti ključne aspekte informacijske tehnologije (programiranje, algoritmi, strukture podataka, baze podataka i znanja
razumjeti i primijeniti suvremene tehničke koncepte i prakse u informacijskim tehnologijama (arhitektura računala, operacijski sustavi, mreže računala)
razumjeti i primijeniti matematičke metode, modele i tehnike primjerene rješavanju problema iz područja informacijskih i poslovnih sustava
razumjeti bitne čimbenike koji utječu na poslovanje organizacije i pojedinaca te primijeniti osnovne metode i koncepte planiranja, upravljanja i obračuna poslovanja
analizirati stanje, identificirati prilike i definirati probleme s kojima se susreću organizacije i pojedinci u primjeni ICT, te formulirati rješenja uz primjenu ICT
razumjeti osnovna vertikalna područja primjene ICT (industrija, zdravstvo, promet, turizam, država i sl.), te horizontalne aplikacije (uredski sustavi, DSS, CRM, ERP, DMS i sl.)
razumjeti i primijeniti suvremene metodološke pristupe razvoja organizacijskih i informacijskih sustava, te oblikovanja organizacije i organizacijske strukture
razumjeti suvremene organizacijske koncepte i upravljati organizacijskom kulturom
modelirati poslovne procese i podatke u organizacijama i primijeniti modele u razvoju informacijskih i poslovnih sustava
razumjeti i primijeniti metode, tehnike razvoja informacijskih i programskih sustava u suvremenim razvojnim okolinama
razumjeti i primijeniti procese, metode i tehnologije upravljanja IT uslugama i resursima te podrške i pružanja različitih vrsta usluga vezanih uz ICT
razumjeti i primijeniti etička načela, zakonsku regulativu i norme koje se primjenjuju u struci
razumjeti osnovna načela i metode upravljanja organizacijom i uspješno raditi u timu
uspješno komunicirati s klijentima, korisnicima i kolegama na verbalan i pisani način uz primjenu odgovarajuće terminologije uključujući i sposobnost komunikacije o struci na stranom jeziku
pratiti stručnu literaturu na hrvatskom i stranom jeziku, pripremiti i samostalno održati prezentacije na hrvatskom i stranom jeziku stručnoj i općoj publici, te kritičku evaluaciju prezentirane stručne teme
razumjeti i primijeniti vještine učenja potrebne za cjeloživotno učenje i nastavak obrazovanja na diplomskom studiju.
razumjeti i primijeniti osnovne principe planiranja i razvoja karijere u struci i vlastitih poduzetničkih poduhvata

Osnovna literatura

Casanova, H; Legrand, A; Robert, Y: Parallel Algorithms, CRC Press, boca Ratin, 2014.
Grama, A et. al. Introduction to Parallel Computing, Addison-Wesley, Harlow, 2003.

Dopunska literatura

Slični kolegiji

Redoviti studenti

Izvanredni studenti

U kalendaru ispod se nalaze konzultacije predmetnih nastavnika, no za detalje o konzultacijama možete provjeriti na profilu pojedinog predmetnog nastavnika.