# 2D1443 Parallel Computations

 KTH credits 4 Lectures 30 Level D Tutorials - Grading, KTH U, 3, 4, 5 Lab work - Compulsory for - Elective for D, F Periods 4 Language Swedish; if requested by several students in English Web info www.nada.kth.se/kurser/kth/2D1443
Coordinator

Jens Lagergren, +46 - 8 - 790 7327, jensl@nada.kth.se

Abstract

Advanced course in theoretical computer science focusing on the parallel computational model PRAM.

Goals

The goal of the course is to give the students

• an orientation on the parallel computational model PRAM (Parallel Random Access Machine) and so called NC algorithms.
so that they will be able to
• get a deeper understanding of the concept parallelity,
• design and analyze NC algorithms,
• read research articles from the area.
Syllabus

The course will describe the PRAM model. In this model a number of processors work synchronously in a loop: read-think-write. The time that a PRAM algorithm demands is the number of read-think-write phases. An algorithm is called a NC algorithm if it uses at most the time O(logk n) och at most O(nc) processors on any input data of size n (where k and c are constants).

The course first introduces the model and a number of basic techniques like: pointer jumping, accelerated cascading, and symmetry breaking. Then the course moves on to parallel algorithms for problems of about the same type that will be considered in an ordinary algorithm course: lists, evaluation of expressions, search and sorting, lower bounds for search and sorting (comparison models), graphs, strings, and arithmetic.

If there is time probabilistic, parallel algorithms and lower bounds for parallel PRAM algorithms (general) will be studied.

Prerequisites

One of the courses 2D1353 Algorithms, Data Structures, and Complexity and 2D1354 Algorithms and Complexity or the equivalent.

Follow-up

Examination

Written exercises (OVN1; 4 cr.).

Course material

Reading list available at the department. In 96/97: J. JáJá, An introduction to parallel algorithms, Addison Wesley, 1992.

Remarks

The course is given every second year. Will be given in 98/99.