Komplett pensumoversikt for parallellberegning ved NTNU — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.
Denne studieguiden dekker pensum i TDT4200 Parallell databehandling (Parallel Computing) ved NTNU (7,5 studiepoeng). Kurset gir en praktisk og teoretisk innføring i parallellprogrammering på tvers av de tre dominerende programmeringsmodellene: MPI (distribuert minne, prosessbasert), OpenMP og Pthreads (delt minne, trådbasert) og CUDA (massivt parallelle GPU-er). Sentralt står forståelsen av maskinvaren — minnehierarki, cache, båndbredde og latens — og hvordan denne styrer hvilke algoritmer som faktisk skalerer.
Eksamen er en 4-timers digital skoleeksamen i Inspera uten hjelpemidler som teller 50 % av karakteren (problem sets står for resten). Settet består av en stor seksjon med sant/usant- og flervalgsspørsmål (negativ skåring for feil svar) som tester begrepsforståelse, etterfulgt av kortsvars- og kodeoppgaver der du skal skrive eller debugge MPI-, OpenMP- og CUDA-kode, samt regne på speedup og koalesert minneaksess. Eksamenstekstene er på engelsk, men du kan svare på norsk. Studieguiden følger de fem hovedtemaene som også quiz og flashcards er bygd rundt.
Message Passing Interface for distribuert minne: kommunikatorer og rank, punkt-til-punkt vs. kollektiv kommunikasjon, deadlock og MPI_Sendrecv, deriverte datatyper og kartesiske topologier.
MPI er standarden for parallellisering på distribuert minne, der hver prosess har sitt eget adresserom og kommuniserer ved å sende meldinger. Programmeringsmodellen er SPMD (Single Program, Multiple Data): én og samme kildekode kjøres av alle prosessene, og oppførselen styres av prosessens rank. Dette er ikke det samme som SIMD eller MIMD i Flynns taksonomi — MPI er en programmeringsstil, ikke en maskinvareklasse.
Hver prosess får en unik rank innen en kommunikator (oftest MPI_COMM_WORLD). De grunnleggende kallene er:
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank); // hvem er jeg?
MPI_Comm_size(MPI_COMM_WORLD, &size); // hvor mange er vi?
// ... arbeid ...
MPI_Finalize();MPI_Send og MPI_Recv er blokkerende. En klassisk feilkilde er at to prosesser begge starter med MPI_Send til hverandre: hvis meldingene er store nok til at de ikke bufres internt, blokkerer begge for alltid — deadlock. Løsningen er enten å bytte rekkefølge (en sender mens den andre mottar) eller å bruke MPI_Sendrecv, som lar MPI-runtime håndtere rekkefølgen trygt i ett kall:
MPI_Sendrecv(send_buf, n, MPI_DOUBLE, dest, tag,
recv_buf, n, MPI_DOUBLE, src, tag,
comm, MPI_STATUS_IGNORE);Et annet vanlig kodefeilmønster: en for-løkke som sender uten å inkrementere telleren, eller å plassere MPI_Bcast inne i en if (rank == 0)-blokk. Kollektiver må kalles av alle prosesser i kommunikatoren, ellers henger programmet. Merk også at man ikke kan bruke MPI_ANY_TAG som tag på sender-siden — den er kun en jokertegn ved mottak.
Kollektiver erstatter manuelle løkker med sjelden punkt-til-punkt-kall: MPI_Bcast (kringkast), MPI_Scatter/MPI_Gather (fordel/samle), MPI_Reduce/MPI_Allreduce (reduksjon, f.eks. global sum) og MPI_Barrier. De er bedre optimalisert (ofte tre-strukturert, trinn) og mer lesbare enn håndskrevne løkker. Kollektiver bruker ikke tags.
Med MPI_Type_vector og MPI_Type_create_struct kan man beskrive ikke-sammenhengende data (f.eks. en matrisediagonal eller en kolonne) og sende dem i ett kall. Kartesiske topologier (MPI_Cart_create, MPI_Cart_shift) gir naturlig nabokommunikasjon i et 2D-rutenett — sentralt når man parallelliserer stencil-beregninger som den grunne vannlikningen.
Anta en -matrise lagret radvis i double *a, med makroen #define A(i,j) a[(i)*N+(j)]. Rank 0 har de ønskede diagonalverdiene og skal kringkaste kun diagonalen til alle uten å overskrive resten.
MPI_Type_vector(N, 1, N+1, MPI_DOUBLE, &diag); — blokker á 1 element, avstand .MPI_Type_commit(&diag);MPI_Bcast(a, 1, diag, 0, MPI_COMM_WORLD); — sender én diagonal-type fra rank 0.MPI_Type_free(&diag);Resultat: kun de diagonalelementene oppdateres på alle rank; resten av matrisen forblir urørt.
Nøkkelformler
MPI_Comm_rank / MPI_Comm_size — identitet og antall prosesser i kommunikatorenMPI_Sendrecv(...) — trygg toveis-utveksling som unngår deadlockMPI_Type_vector(antall, blokklengde, stride, type, &ny) — strided derivert typeMPI_Cart_create + MPI_Cart_shift(comm, dir, disp, &src, &dest) — nabofinning i rutenettVanlige feil
Eksamenstips
Laster...