IBM Israel Research Seminars

The Bulk Synchronous Parallel (BSP) model proposed by Valiant has stimulated the development of algorithms and software that balance computation work loads as well as communication loads among the processors of a parallel computer.

The BSP model provides a nice theoretical foundation for one-sided communications which are supported by modern Direct Remote Memory Access (DRMA) hardware. Furthermore, the BSP model is useful in practical applications, as it provides a cost model for prediction of computation time, communication time, and synchronisation time.

This talk will discuss recent developments in BSP computing and will present as an example the parallel computation of the Google PageRank of a web page. In this application, a sparse matrix with nonzeros representing links between web pages is repeatedly multiplied by a vector. The data are partitioned using Mondriaan, a two-dimensional, multilevel, hypergraph-based partitioning package.

About the Speaker
Rob Bisseling is an associate professor in computational science at the Mathematics Department of Utrecht University, the Netherlands. His main research field is parallel computing and his current research interests are sparse matrix computations, information retrieval, bioinformatics, and fast Fourier transforms. He is coauthor of the BSPlib communication library and the Mondriaan sparse matrix partitioning package. He has recently published a book, "Parallel Scientific Computation: A Structured Approach using BSP and MPI", Oxford University Press, March 2004.