Nada

Nadas institutionssymbol

^ Upp till kursens hemsida

In English

Studiehandbokstext 1997/98 för

2D1443 Parallella beräkningar

Poäng4Föreläsning30
KursnivåDÖvning-
Betygsskala, KTHU, 3, 4, 5Lab-
Obligatorisk för-ÖvrigtEget arbete
Valbar förD, FPerioderGes ej 97/98
SpråkSvenska; på
engelska om
flera elever
så begär

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

Kursen mål är att för att eleverna ska

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 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 96/97 användes J. JáJá: An introduction to parallel algorithms, Addison Wesley, 1992.

Övrigt

Kursen ges vartannat år. Ges ej 97/98.

Länk till studiehandbokstexten 1996/97

^ Upp till kursens hemsida


Sidansvarig: <www-kurs@nada.kth.se>
Senast ändrad 9 juni 1997
Tekniskt stöd: <webmaster@nada.kth.se>