*Barriers*

Our last synchronization system is planned for groups of processes rather than two-process producer-consumer type situations. Some applications are divided into phases and have the rule that no process may proceed into the next phase until all processes are ready to proceed to the next phase. This behavior may be attained by placing a barrier at the end of each phase. When a process reaches the barrier, it is blocked until all processes have reached the barrier. The operation of a barrier is demonstrated in Figure 1.

In Figure 1(a) we see four processes approaching a barrier. What this means is that they are just computing and have not reached the end of the current phase yet. After a while, the first process finishes all the computing required of it during the first phase. It then executes the barrier primitive, usually by calling a library procedure. The process is then suspended. A little later, a second and then a third process finish the first phase and also execute the barrier primitive. This situation is demonstrated in Figure 1(b). Finally, when the last process, C, hits the barrier, all the processes are released, as shown in Figure 1(c).

As an example of a problem requiring barriers, examine a typical relaxation problem in physics or engineering. There is typically a matrix that includes some initial values. The values might represent temperatures at different points on a sheet of metal. The idea might be to calculate how long it takes for the effect of a flame placed at one corner to propagate throughout the sheet.

Starting with the current values, a transformation is applied to the matrix to get the second version of the matrix, for instance, by applying the laws of thermodynamics to see what all the temperatures are ∆T later. Then the process is repeated over and over, giving the temperatures at the sample points as a function of time as the sheet heats up. The algorithm creates a series of matrices over time.

Now consider that the matrix is very large (say, 1 million by 1 million), so that parallel processes are required (possibly on a multiprocessor) to speed up the calculation. Different processes work on different parts of the matrix, calculating the new matrix elements from the old ones according to the laws of physics. However, no process may start on iteration n + 1 until iteration n is complete, that is, until all processes have finished their current work. The way to achieve this goal is to program each process to carry out a barrier operation after it has finished its part of the current iteration. When all of them are done, the new matrix (the input to the next iteration) will be ended, and all processes will be concurrently released to start the next iteration.