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:
“I’d like to be the first model who becomes a woman.”
—Lauren Hutton (b. 1944)
“I had a wonderful job. I worked for a big model agency in Manhattan.... When I got on the subway to go to work, it was like traveling into another world. Oh, the shops were beautiful, we had Bergdorf’s, Bendel’s, Bonwit’s, DePinna. The women wore hats and gloves. Another world. At home, it was cooking, cleaning, taking care of the kids, going to PTA, Girl Scouts. But when I got into the office, everything was different, I was different.”
—Estelle Shuster (b. c. 1923)