Today, parallel programming is easy and parallel computing is available for the masses. The bulk synchronous parallel (BSP) model allows a structured approach to designing parallel algorithms and the BSPlib communication library offers an easy entry into writing parallel programs.

In this talk, we examine the parallelisation of three applications:

• Latent semantic indexing, a method used in search engines. This requires the solution of large sparse SVD problems. A new method is presented for the distribution of sparse matrices for such computations.
• Cage model for gel electrophoresis, a model used to study the movement of DNA in sequencing machines. This requires finding the steady state of a Markov model. Such a system also gives rise to a sparse matrix, with a hierarchical structure that can be exploited to reduce communication.
• Construction of low-energy atomic configurations of amorphous silicon, used as input for simulation methods. This 3D computation is based on simulated annealing, with phases of local relaxation, global relaxation, and information exchange.

Finally, we will give a survey of BSP applications by other groups.

About the speaker

Rob H. Bisseling is an associate professor in Computational Science at the Mathematics Department of Utrecht University, the Netherlands, since 1993. In Spring 2000, he was an EPSRC visiting fellow at Oxford University Computing Laboratory. Previously, he was a research mathematician at the Koninklijke/Shell-Laboratorium, Amsterdam (1987-1993). He is co-author of the BSPlib standard (1997) and is currently working on a book on scientific computation using BSP.

Return to main HLPP2001 page.