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:
“Emancipation should make it possible for woman to be human in the truest sense. Everything within her that craves assertion and activity should reach its fullest expression; all artificial barriers should be broken, and the road towards greater freedom cleared of every trace of centuries of submission and slavery.”
—Emma Goldman (1869–1940)
“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)
“In America the majority raises formidable barriers around the liberty of opinion; within these barriers an author may write what he pleases, but woe to him if he goes beyond them.”
—Alexis de Tocqueville (1805–1859)