BSP cost analysis and the implementation of skeletons
Jonathon M.D. Hill
The Bulk Synchronous Parallel (BSP) model provides a theoretical
framework for the development of _predictable_ architecture
independent parallel algorithms. One of the strengths of BSP compared
to alternative models of parallel computation is its simple yet
_realistic_ cost model that decomposes costs into communication and
computational parts. By placing an emphasis on these two fundamental
aspects of parallel algorithms, the aim of this talk is to show how
BSP cost analysis can be used to guide algorithm design towards
optimal solutions across a wide variety of machines.
In contrast to BSP, the skeletal approach to parallelism provides
an expressive way of encapsulating general patterns of computation and
communication, yet it lacks ``flesh''. The fundamental problem is the
naivity of skeletal cost analysis, which has produced a plethora of
techniques that are unusable on todays parallel machines.
The aim of this talk is to show how BSP cost analysis can be used
to develop architecture independent skeletons at a high level of
abstraction, whilst providing a basis for optimal performance on
todays (and future) parallel machines.