Assefaw Gebremedhin, Research, Parallel Computation Models

Note: This page describes previous work I have done on a parallel computation model inspired by the BSP model. I have not since then pursued research along the same direction. Given the current landscape of parallel architectures, where manycore-ness and heterogenity are increasingly becoming dominant features, radically different parallel computation models are likely to be needed.

The Bulk Synchronous Parallel (BSP) model, introduced by Valiant in 1990, is among the first parallel computation models to be suggested as a bridge between hardware and software. The revolutionary idea in the BSP model is the view that an algorithm be organized as a sequence of supersteps, each with distinct, rather than intermingled, computation and communication phases.

When I was a graduate student at the University of Bergen, Jens Gustedt and Isabelle Guerin Lassous (INRIA, France) visited the Algorithms Group in Bergen and presented their work on a variant of the BSP model that involved fewer parameters. After subsequent collaboration and further work, Gustedt, Guerin Lassous, Jan Arne Telle (University of Bergen) and I proposed the Parallel Resource-Optimal (PRO) model in 2002. PRO sought to make the relationship between algorithm design and analysis and the specifics of architecture less intimate than that in the BSP model. The model is fully described in the first of the following two papers, and it was first introduced in the second paper. Arriving at a parallel computation model that is close enough to the ideal---one that strikes the right balance between being simple, descriptive, and prescriptive---is a daunting task. The PRO model was an attempt to make a humble contribution to the debate in this search at the time the model was proposed.

Go back to Research Areas or go side-ways to
  • Network Science
  • Parallel Alagorithms
  • Coloring and Automatic Differentiation