The BSP Model
Introduction
Informally, a BSP computer consists of a set of processor
-memory pairs connected by a communications
network, which delivers point-to-point messages.
A mechanism for providing barrier synchronization
is also available. Processors execute algorithms in a series of supersteps,
during which they process local data and initiate any requests to remote
memory locations. At the end of a superstep period all the processors must
synchronize using the barrier mechanism. During the barrier any unresolved
remote memory accesses are completed and then, and only then, the processors
can continue onto the next superstep.
Memory
A BSP computer has a 2-dimensional memory i.e. local and non-local. Uniform
efficiency is assumed, that is the time to access memory is the same whereevr
the data is in the network. A simplification of the model is to assume that
there is only one memory module on each processor. Memory management can be
direct (the programmer has control of data partitioning) or
indirect (compiler and operating system have control of distribution).
In the latter automatic distribution techniques are used to allocate memoy
such that 'hot spots' do not impede the performance.
Superstep
The granularity of synchronization in BSP computer is given by the period of
the superstep. The minimum size is given by the time taken to complete a
barrier synchronization.
Network
A h-relation is said to occur when each process has at most h packets
to send to other processes on the network and is itself due to receive at
most h packets. A packet is considered to be one machine word. The network's
task is to realize arbitrary h-relations. The model implies no ordering of
communication packets. The performance of the network is defined by the
maximum time required to perform a non-local memory access, and the maximum
number of such accesses at any one time.
Processor
It is often easier to consider one process running on each processor, but this
is not necessary. In fact, parallel slackness is required by the theory i.e.
there are more virtual processes running in the system than there are processors.
The model allows for only a fixed number of processors at the start of
run-time; i.e. static.
Synchronization
At end of each superstep processes enter a barrier at which point they are
all synchronized. The model does allow for a sub-set of processes to be
synchronized.
Complexity
The BSP model has a complexity defined using the following measurement factors:
P number of processors
l latency of synchronization
g Communication throughput.
g is defined as total operations performed by all processors in one second / total
number of packets delivered by network in one second.
l is the minimum number of operation between barrier synchronizations, i.e. the
cost of doing the barrrier.
A 3-d graph of these factors gives what is called the BSP space, as below:
The superstep complexity is given by the formula:
Cost of superstep = max{l,w,ghs,ghr}
where w is the work (maximum number of local operations executed by one
processor during superstep).
hs is maximum number of packets sent during superstep, hr is maximum received.
The total algorithm cost is the sum of all supersteps as they combinational.
Return to project home page
Last update: 7 March 1996.