The Model
A BSP computer consists of processors connected by a communication network. Each processor has a fast local memory, and may follow different threads of computation. A BSP computation proceeds in a series of global supersteps. A superstep consists of three components:
- Concurrent computation: Several computations take place on every participating processor. Each process only uses values stored in the local memory of the processor. The computations are independent in the sense that they occur asynchronously of all the others.
- Communication: The processes exchange data between themselves. This exchange takes the form of one-sided put and get calls, rather than two-sided send and receive calls.
- Barrier synchronisation: When a process reaches this point (the barrier), it waits until all other processes have finished their communication actions.
The computation and communication actions do not have to be ordered in time. The barrier synchronization concludes the superstep: it has the function of ensuring that all one-sided communications are properly concluded. This global synchronization is not needed in models based on two-sided communication, since these synchronize processes implicitly.
The figure below shows this in a diagrammatic form. The processes are not regarded as having a particular linear order (from left to right or otherwise), and may be mapped to processors in any way.
A further aspect of the BSP model is that of overdecomposition of the problem and oversubscription of the processors: the problem is divided into more logical processes than there are physical processors, and processes are randomly assigned to processors. This strategy can be shown statistically to lead to almost perfectly load balancing, both of work and communication.
Read more about this topic: Bulk Synchronous Parallel
Famous quotes containing the word model:
“The striking point about our model family is not simply the compete-compete, consume-consume style of life it urges us to follow.... The striking point, in the face of all the propaganda, is how few Americans actually live this way.”
—Louise Kapp Howe (b. 1934)
“There are very many characteristics which go into making a model civil servant. Prominent among them are probity, industry, good sense, good habits, good temper, patience, order, courtesy, tact, self-reliance, many deference to superior officers, and many consideration for inferiors.”
—Chester A. Arthur (1829–1886)