| | 2 | == A Dissemination Barrier == |
| | 3 | |
| | 4 | Designing efficient barriers is a big problem in concurrency theory. |
| | 5 | A barrier is a synchronization operation that is invoked by all threads or processes |
| | 6 | in a concurrent system. The defining property is that no process can leave |
| | 7 | the barrier until every process has entered the barrier. A barrier should also |
| | 8 | be re-useable, i.e., it can be invoked more than once. |
| | 9 | |
| | 10 | The dissemination barrier works as follows. There are n processes, numbered |
| | 11 | 0 .. n-1. The ordered is treated as cyclical. The protocol goes through |
| | 12 | ceil(log_2(n)) stages. At stage i, each process sends a message to the process |
| | 13 | 2^i to its "right", and waits to receive a message from the process 2^i to its "left". |
| | 14 | The content of the message is irrelevant (and can be empty). |
| | 15 | |
| | 16 | Challenge 1: Design a dissemination barrier using MPI. Verify it up to some |
| | 17 | bound on the number of processes using CIVL. |
| | 18 | |
| | 19 | Challenge 2: Design a dissemination barrier using semaphores. Verify it up |
| | 20 | to some bound on the number of threads using CIVL. |
| | 21 | |
| | 22 | In both cases, there should be a function named `barrier` (possibly with |
| | 23 | parameters) that all processes/threads call in order to participate in a barrier. |
| | 24 | The function could use global variables. |
| | 25 | |
| | 26 | In both cases, part of the challenge is to come up with an appropriate driver |
| | 27 | that tests the barrier. Try to develop the most universal (challenging) driver |
| | 28 | you can. Can you make one that guarantees the barrier is correct? |
