Computational Power of BSP Computers
by Martin Beran

Abstract:

We show how the speed of a BSP computer depends on the parameters p,
g, and l of the model. According to the values of parameters, BSP
belongs among the first (sequential) or the second (parallel) class models
or neither of these classes. The relation between BSP and the class of
weak parallel machines is also examined. It turns out that BSP does not
fit to the concept to weak (or pipelined) parallelism. Consequences of
membership in different machine classes to the physical feasibility of BSP
computers are discussed. The main conclusion is that BSP with parameters
properly chosen qualifies itself as a practical model, but it is unable to
exploit all the parallelism allowed by laws of physics.