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:
“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)
“The barriers of conventionality have been raised so high, and so strangely cemented by long existence, that the only hope of overthrowing them exists in the union of numbers linked together by common opinion and effort ... the united watchword of thousands would strike at the foundation of the false system and annihilate it.”
—Mme. Ellen Louise Demorest 1824–1898, U.S. women’s magazine editor and woman’s club movement pioneer. Demorest’s Illustrated Monthly and Mirror of Fashions, p. 203 (January 1870)
“... so far from entrenching human conduct within the gentle barriers of peace and love, religion has ever been, and now is, the deepest source of contentions, wars, persecutions for conscience sake, angry words, angry feelings, backbitings, slanders, suspicions, false judgments, evil interpretations, unwise, unjust, injurious, inconsistent actions.”
—Frances Wright (1795–1852)