Barriers
The one-sided communication of the BSP model requires a global barrier synchronization Barriers are potentially costly, but have a number of attractions. They do not introduce the possibility of deadlock or livelock, since barriers do not create circular data dependencies. Therefore tools to detect and deal with them are unnecessary. Barriers also permit novel forms of fault tolerance.
The cost of barrier synchronization is influenced by a couple of issues:
- The cost imposed by the variation in the completion time of the participating concurrent computations. Take the example where all but one of the processes have completed their work for this superstep, and are waiting for the last process, which still has a lot of work to complete. The best that an implementation can do is ensure that each process works on roughly the same problem size.
- The cost of reaching a globally consistent state in all of the processors. This depends on the communication network, but also on whether there is special-purpose hardware available for synchronizing, and on the way in which interrupts are handled by processors.
The cost of a barrier synchronization is denoted by . In practice, a value of is determined empirically.
The presence of barriers makes the BSP model mostly a theoretical one: on large computers barriers are expensive, and this is increasingly so on large scales. In fact, there is a large body of literature on removing synchronization points from existing algorithms.
Read more about this topic: Bulk Synchronous Parallel
Famous quotes containing the word barriers:
“There are two barriers that often prevent communication between the young and their elders. The first is middle-aged forgetfulness of the fact that they themselves are no longer young. The second is youthful ignorance of the fact that the middle aged are still alive.”
—Jessamyn West (1902–1984)
“The principle that human nature, in its psychological aspects, is nothing more than a product of history and given social relations removes all barriers to coercion and manipulation by the powerful.”
—Noam Chomsky (b. 1928)
“... in love, barriers cannot be destroyed from the outside by the one to whom the cause despair, no matter what he does; and it is only when he is no longer concerned with them that, suddenly, as a result of work coming from elsewhere, accomplished within the one who did not love him, these barriers, formerly attacked without success, fall futilely.”
—Marcel Proust (1871–1922)