Bulk Synchronous Parallelism in Practice |
A Tutorial at the
ACM SAC 2000 Conference
Lake Como, Italy
Sunday March 19 2000, morning.
Presenter: D.B. Skillicorn
Department of Computing and Information Science
Queen's University, Kingston, Canada
skill@cs.queensu.ca
Intended Audience
Increasingly, users of high performance computing are moving to clusters
because of their cost-effectiveness. SPMD programming using a library for
interaction and communication has proven a popular model for exploiting
the power of clusters. Very often, the MPI library is used.
Bulk Synchronous Parallelism (BSP) has two main advantages over MPI:
-
Its structure enables it to perform better than MPI for communication-intensive
applications; and
-
It has a simple but accurate cost model, making it possible to design
parallel software with confidence about its performance.
This tutorial will be useful to those who use high-performance computing
to solve practical problems, especially
on clusters, because it will enable them to (a) get greater performance
from their existing software and hardware, and make better choices about
how to upgrade them, and (b) choose between different implementation
techniques for applications at a high level, without having to build
and benchmark many different variants.
Tutorial Outline
-
Introduction to the BSP programming model:
Superstep structure;
The cost model.
-
BSP design techniques:
The essential idea -- balance;
Example -- Broadcast algorithms;
Trading memory for performance;
Example -- Sorting.
-
The BSPlib library:
Communication operations;
Barriers;
Registration;
Other library operations;
Comparison with MPI;
Performance results.
-
Implementing the BSP abstract machine:
The BSP messaging layer;
Shared-memory implementation;
Distributed-memory implementation;
Transport layers for clusters.
-
BSP tools:
Cost prediction;
BSP profiling.
-
Examples of BSP applications:
CFD;
Data mining.
Presenter Background
David Skillicorn is a Professor in the Department of Computing and
Information Science at Queen's University in Kingston, Canada where he has
been for past sixteen years. His research interests centre around
architecture-independent parallel programming, cost modelling, and
non-numeric applications of parallelism. He has been involved with
the design and performance measurement of the BSPLib toolset, which is
the most popular implementation of the BSP approach. He uses parallel
computation for data mining, in application areas
such as process yield enhancement and legacy software comprehension.
Back to David Skillicorn's home page.