קולוקוויום בביה"ס למדעי המחשב - Thinking in sync: bulk-synchronous parallel graph algorithms
Rob H. Bisseling (Utrecht University)
Abstract:
We present a gentle introduction to the topic of parallelising graph algorithms through the example of an approximation algorithm for matching in big weighted graphs. This algorithm is based on locally dominant edges and partial edge sorting.
We will discuss how to parallelise the algorithm with special attention to load balancing in an irregular setting, tie-breaking between edge weights as a feature, not a bug, and the virtues of 2D (edge) vs. 1D (vertex) partitioning.
We use the Bulk Synchronous Parallel (BSP) model to structure the computation, to analyse the time complexity, and to reason about the correctness of the algorithm.
Bio:
Rob Bisseling is a full professor in Scientific Computing at the Mathematics Institute of Utrecht University, the Netherlands. He is author of the book "Parallel Scientific Computation: A Structured Approach using BSP and MPI", Oxford University Press, 2004, and he is currently working on a second edition, with new material on graph algorithms.
His research focuses on parallel algorithms for sparse matrix and graph computations, on self-avoiding walks, and on models for parallel computation. He is (co-)designer of the open-source software packages Mondriaan, SAWdoubler, MulticoreBSP, and BSPedupack.
