Design och analys av algoritmer för Parallelldatorsystem, 7,5 hp

Innehåll

Moment 1, teoridel, 4.5 högskolepoäng
Kursen behandlar design, analys, implementation och utvärdering av algoritmer för skalbara datorarkitekturer samt grundläggande kommunikationsoperationer, metoder för problem-partitionering (t.ex. blockning av 2-dimensionella datastrukturer), prestandamått för analys av kostnad och skalbarhet, grundläggande parallella algoritmer för numeriska och icke-numeriska problem inom grundläggande linjär algebra för täta och glesa matriser (matris-multiplikation, transponering och direkta och iterativa metoder för lösning av linjära ekvationssystem), ett antal av de vanligaste sorteringsalgoritmerna, grafteori (minimalt uppspännande träd, kortaste vägen, transitiv omslutning, sammanhängande komponenter och algoritmer för glesa grafer), sökning i diskret optimering (djupet-först, bäst-först samt relevanta algoritmer för dynamisk lastbalansering och termineringsdetektion), dynamisk programmering (monadiska och polyadiska problemformuleringar, t.ex. kortaste vägen och ryggsäckproblemet) och snabba Fouriertransformer (FFT).

Moment 2, laborationsdel, 3 högskolepoäng
Delmomentet utgörs av en laborationskurs med ett antal obligatoriska inlämningsuppgifter

Förväntade studieresultat

Efter avslutad kurs ska studenten kunna:

• förklara och härleda komplexitet för algoritmer för grundläggande och kollektiva kommunikationsoperationer
• tillämpa olika slags metoder och prestandamått för att analysera algoritmer m a p kostnad och skalbarhet, bl.a. med hjälp av den s.k. isoeffektivitetsfunktionen
• redogöra för grundläggande metoder för problem- och datapartitionering för att effektivisera minnesutnyttjandet och minimera kommunikationskostnader i parallelldatorer, t.ex. rekursivt blockade algoritmer för täta matriser och hybrida datatyper
• utföra design och analys av parallella algoritmer inom några av innehållsbeskrivningens områden
• använda och känna till standardprogramvara inom numerisk linjär algebra såsom BLAS, LAPACK och ScaLAPACK

Behörighetskrav

Univ: För tillträde till kursen krävs 60 hp i huvudområdet datavetenskap eller 2 års studier i båda fallen inkluderande kurserna Teknisk-vetenskapliga beräkningar (5DV005) och Parallelldatorsystem (5DV011) eller motsvarande kunskaper.
En A och svenska för grundläggande behörighet för högskolestudier (om kursen ges på svenska).

Undervisningens upplägg

Undervisningen bedrivs i form av föreläsningar, arbete i datorlabb och övningar i mindre grupper. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet.

Examination

Examinationen sker dels genom skriftlig tentamen (på teoridelen) dels genom ett laborationsmoment. På en skriftlig tentamen sätts något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). På laborationsmomentet ges endast betygen Underkänd (U) eller Godkänd (G). På hela kursen ges något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). För att bli godkänd på hela kursen krävs att samtliga prov och obligatoriska moment är godkända. Betyget utgör en sammanfattande bedömning av resultaten vid examinationens olika delar och sätts först när alla obligatoriska moment är godkända. Studerande som godkänts i ett prov får inte undergå förnyat prov för att få ett högre betyg.

För studerande som inte godkänns vid ordinarie provtillfälle anordnas ytterligare provtillfälle. En student som utan godkänt resultat har genomgått två prov för en kurs eller en del av en kurs, har rätt att få en annan examinator utsedd, om inte särskilda skäl talar emot det (HF 6 kap. 22 §). Begäran om ny examinator ställs till prefekten vid Institutionen för datavetenskap.

Övriga föreskrifter

Tillgodoräknande
I en examen får denna kurs ej ingå, helt eller delvis, samtidigt med en annan kurs med likartat innehåll. Vid tveksamheter bör den studerande rådfråga studievägledare vid Institutionen för datavetenskap.

Tillgodoräknande av studier prövas individuellt (se universitetets regelsamling och tillgodoräknandeordning). Ansökan om tillgodoräknande görs på speciell blankett och ställs till den Teknisk-naturvetenskapliga fakultetsnämnden, Umeå universitet.