DN2264 Parallella beräkningar för storskaliga problem, del 1 6,0 hp

• Utbildningsnivå

  Avancerad nivå

• Kursnivå (A-D)

  C

• Huvudområde

• Betygsskala

  A, B, C, D, E, FX, F

• Kursens hemsida

• Kurssida på KTH Social

Lärandemål

Det övergripande målet med kursen består i att förmedla en grundläggande förståelse av hur man utvecklar numeriska algoritmer och hur man implementerar dessa på datorer med fördelat minne genom att använda "message-passing" metoder.

Efter genomförd kurs ska du ha lärt dig att:

• förklara strategier för parallellisering
• välja ut och/eller utveckla en algoritm för att lösa ett givet problem som är anpassad till parallelliseringen
• välja ut och/eller utveckla datatstrukturer för att implementera parallella algoritmer
• teoretiskt analysera en given parallell algoritm med hänsyn till effektiviteten
• implementera en given algoritm på en dator med fördelat minne genom att använda MPI-biblioteket
• förstå flödet av informationen och undvika oönskade lägen (t ex deadlock, synkroniseringsfördröjning)
• modifiera och anpassa grundläggande rutiner till speciella situationer
• experimentellt uppskatta prestandan av parallella program
• förklara skillnader mellan den teoretiskt förväntade prestandan och den praktiskt uppmätta prestandan.

Kursens huvudsakliga innehåll

Grundläggande idéer: hårdvaruarkitektur, minneshierarkier, kommunikation, strategier för parallellisering, mätande av effektivitet;

Enkla numeriska algoritmer, bl. a. matrisoperationer, Gausseliminering;

Algoritmer på grafer, exempelvis grafpartitioneringsproblem;

Parallell sortering;

Mer avancerade parallella problem, exempelvis n-kroppsproblemet;

Avancerade numeriska metoder, exempelvis multigrid och FFT-metoder;

Standardbibliotek.

Behörighet

För fristående kursstuderande krävs 90 högskolepoäng varav 45 högskolepoäng inom matematik eller informationsteknik. Dessutom krävs engelska B eller motsvarande.

Rekommenderade förkunskaper

En grundläggande kurs i numerisk analys (DN1212, DN1240 eller motsvarande), datalogi (DD1320, DD1321 eller motsvarande), gärna erfarenheter av C, C++, Fortran. De som kan Java eller Python får en kort introduktion till C.

Litteratur

Barry Wilkinson, Michael Allen: Parallel Programming, 2nd ed., Pearson Education International 2005, ISBN 0-13-191865-6.
Peter S. Pacheco: A Users Guide to MPI, säljs på studentexpeditionen. Michael Hanke: Lecture Notes, säljs på studentexpeditionen.

Examination

• HEM1 - Hemuppgift, 3,0 hp, betygsskala: P, F
• LAB1 - Laborationer, 3,0 hp, betygsskala: A, B, C, D, E, FX, F

I denna kurs tillämpas skolans hederskodex, se: http://www.kth.se/csc/student/hederskodex.

Krav för slutbetyg

Hemuppgifter och en ”mid-term quiz” (HEM1, 3 hp)
Laborationsrapport (LAB1, 3 hp)

Ges av

SCI/Matematik

Kontaktperson

Michael Hanke, e-post: hanke@kth.se

Examinator

Michael Hanke <hanke@kth.se>

Övrig information

Observera att det är obligatorisk närvaro vid första föreläsningen!

Påbyggnad

DN2265 Parallella datorberäkningar för storskaliga problem, del 2.

Versionsinformation

Kursplan giltig från och med HT09.
Examinationsinformation giltig från och med HT07.