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 playing adult steps sideward into another reality; the playing child advances forward to new stages of mastery....Child’s play is the infantile form of the human ability to deal with experience by creating model situations and to master reality by experiment and planning.”
—Erik H. Erikson (20th century)
“Your home is regarded as a model home, your life as a model life. But all this splendor, and you along with it ... it’s just as though it were built upon a shifting quagmire. A moment may come, a word can be spoken, and both you and all this splendor will collapse.”
—Henrik Ibsen (1828–1906)