Nada

2D1443, Parallella beräkningar, 4 poäng


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).

Aktuell kursomgång: period 4 98/99

Aktuell information (senast ändrad 2 mars 1999) om den pågående kursen, kursledare Jens Lagergren (jensl@nada.kth.se). Studiehandbokstexten (om den finns tillgänglig).

^ Upp till kursöversikt.


Sidansvarig: <jensl@nada.kth.se>
Senast ändrad 2 mars 1999
Tekniskt stöd: <webmaster@nada.kth.se>