Parallel Algorithms

Credits	8 credit points
Instructors	Bisseling, R.H. (Universiteit Utrecht)
E-mail	R.H.Bisseling@uu.nl
Aim	The course aims to provide a thorough knowledge of designing and implementing parallel algorithms for problems in the area of scientific computing.
Description	Today, parallel computers are appearing on our desktops. The advent of dual-core and quad-core computers and the expected increase in the number of cores in the coming years, inevitably will cause a major change in our approach to software, such as the mathematical software we use in scientific computations. Parallel computers drastically increase our computational capabilities and thus enable us to model more realistically in many application areas. To make efficient use of parallel computers, it is necessary to reorganise the structure of our computational methods. In particular, attention must be paid to the division of work among the different processors solving a problem in parallel and to the communication between them. Suitable parallel algorithms and systems software are needed to realise the capabilities of parallel computers. We will discuss extensively the most recent developments in the area of parallel computers, ranging from multi-core desktop PCs, to clusters of PCs connected by switching devices, to massively parallel computers with distributed memory such as our national supercomputer Huygens at SARA in Amsterdam. The following subjects will be treated: Types of existing parallel computers Principles of parallel computation: distributing the work evenly and avoiding communication The Bulk Synchronous Parallel (BSP) model as an idealised model of a parallel computer Use of BSPlib software as the basis for architecture-independent programs Parallel algorithms for the following problems: prime number sieving, LU decomposition, Fast Fourier Transform, sparse matrix-vector multiplication, iterative solution of linear systems. Analysis of the computation, communication, and synchronisation time requirements of these algorithms by the BSP model. Hands-on experience in the laboratory class, using the Huygens supercomputer.
Organization	14 Meetings, Wednesdays 10.15-13.00 hour (starting September 9, 2009, and ending December 16; no class on Nov. 4). Each meeting consists of 2 hours lecture and 1 hour exercise class (or computer laboratory class or question hour).
Examination	The examination is in the form of two assignments during the course, each with a weight of 45%, and a small written examination with a weight of 10% which must be passed with grade >=6. The two assignments are carried out in the laboratory classes and at home.
Literature	Parallel Scientific Computation: A Structured Approach using BSP and MPI, by Rob H. Bisseling, Oxford University Press, 2004. ISBN 0-19-852939-2. Supplementary course material including all lecture slides can be found on the Algorithms course page.
Prerequisites	Introductory course in linear algebra. Some knowledge of algorithms and programming.

Last changed: 08-09-2010 09:56