Nada

Nadas institutionssymbol

^ Upp till kursens ingångssida

In English

Studiehandbokstext 1999/2000 för

2D1443 Parallella beräkningar

Poäng

4

Föreläsning

30

Kursnivå

D

Övning

-

Betygsskala, KTH

U, 3, 4, 5

Labb

-

Obligatorisk för

-

   

Valbar för

D, F

Perioder

Ges ej 99/00

Språk

Svenska

Webbinfo

www.nada.kth.se/kurser/kth/2D1443

Kursansvarig

Jens Lagergren, 08 - 790 7327, jens@nada.kth.se

Kortbeskrivning

En avancerad kurs i teoretisk datalogi som behandlar den parallella beräkningsmodellen PRAM.

Mål

Kursens mål är att

• ge en orientering om den parallella beräkningsmodellen PRAM (Parallel Random Access Machine) samt så kallade NC-algoritmer

för att studenterna ska

• få en fördjupad förståelse för begreppet parallellitet,

• kunna konstruera och analysera NC-algoritmer,

• kunna läsa forskningsartiklar från området.

Kursinnehåll

Kursen kommer att beskriva PRAM-modellen. I denna arbetar ett antal processorer synkront i en slinga: läs-tänk-skriv. Med den tid en PRAM algoritm kräver menas antalet läs-tänk-skrivfaser. En algoritm är en NC algoritm om den använder högst tiden O(logk n) och högst O(nc) processorer på varje indata av storlek n (där k och c är konstanter).

Kursen börjar med att introducera modellen och ett antal tekniker. Bland dessa tekniker kan nämnas pointer jumping, accelerated cascading och symmetry breaking. Därefter studeras parallella algoritmer för problem av ungefär samma typ som på en vanlig algoritmkurs. Här kan nämnas algoritmer för: listor, evaluering av uttryck, sökning och sortering, undre gränser för sökning och sortering (i jämförelsemodell), grafer, strängar och aritmetik.

I mån av tid behandlas även probabilistiska parallella algoritmer och undre gränser för parallella PRAM algoritmer (generella).

Förkunskaper

Motsvarande en av kurserna 2D1352/2D1353 Algoritmer, datastrukturer och komplexitet och 2D1354 Algoritmer och komplexitet.

Påbyggnad

Diskuteras med kursledaren.

Examination

Inlämningsuppgifter (ÖVN1; 4 p).

Kurslitteratur

Enligt förteckning på institutionen. Läsåret 98/99 användes J. JáJá: An introduction to parallel algorithms, Addison Wesley, 1992.

Övrigt

Kursen ges vartannat år. Ges ej 99/00.

Länk till studiehandbokstexten 1998/1999

^ Upp till kursens ingångssida


Sidansvarig: <www-kurs@nada.kth.se>
Senast ändrad 6 april 1999
Tekniskt stöd: <webmaster@nada.kth.se>