Parallel Computer Architecture

7.9 Synchronization 543

^ - Contention Little contention

Flat

Tree

structured

FIGURE 7.41 Replacing a flat arrival structure for a barrier by an arrival tree (here of degree

2).

A deeper tree with smaller branching utilizes the many paths through the network of a large-scale

machine to avoid serialization.

tree and so does a fetch&increment on the counter at that level. In this way, each

tree node sends only a single representative process up to the next higher level in the

tree when all the processes represented by that node's children have arrived. For a

tree of degree Je, it takes log^ p levels and hence that many steps to complete the