Bulk Synchronous Parallel - Barriers

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:

1. 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.
2. 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.