[SOLVED] IT CS 563 Concurrent Programming

CS 563 Concurrent Programming
Lecture 13: Barriers

Barrier Synchronization

Copyright By Assignmentchef assignmentchef

A BARRIER is a point that all processes must reach before any proceed
very common in iterative parallelism Example:
co inside while style of parallelism while () {
co oc # oc is
# essentially a barrier

Counter Barrier for n processes
int count = 0;
Barrier:< count++ > # record arrival
< await (count==n); > # wait for
increment use FA or critical section delay loop use spin loop
Implementation:
# everyone to arrive

Reuse problem How do we reset count? Contention single shared counter

Solving the reuse problem
Try counting up then counting down (called reverse sense)
odd barriers: < count++ >
< await(count==n) >
even barriers:< count– >
< await(count==0) >

Solving the reuse problem
Use TWO counters AND reverse their senses
up1, up2, down1, down2, repeat
Why does this work?

Coordinator Barrier
Idea: distribute the single counter above (a time/space tradeoff) Shared variables:
int arrive[1:n] = ([n] 0);
continue[1:n] = ([n] 0);

Coordinator Barrier
The basic signaling scheme is then implemented as follows:
int arrive[1:n] = ([n] 0), continue[1:n] = ([n] 0);
Worker[i]:
process Worker[i = 1 to n] { while (true) {
code to implement task i; arrive[i] = 1;
await (continue[i] == 1);
Coordinator:
process Coordinator { while (true) {
for [i = 1 to n] {
await (arrive[i] == 1);
for [i = 1 to n] continue[i] = 1; }

Coordinator Barrier
What about the reset problem?
solve by clearing flags at the points above
be sure to follow the Flag Synchronization Principles:
Process waiting for a flag to be set should clear the flag A flag should not be set until it is known that it is clear

Coordinator Barrier
int arrive[1:n] = ([n] 0), continue[1:n] = ([n] 0);
Worker[i]:
process Worker[i = 1 to n] { while (true) {
code to implement task i; arrive[i] = 1;
await (continue[i] == 1); continue[i] = 0;
Coordinator:
process Coordinator { while (true) {
for [i = 1 to n] {
await (arrive[i] == 1);
arrive[i] = 0;
for [i = 1 to n] continue[i] = 1;

Coordinator Barrier
process Worker[i = 1 to n] { while (true) {
code to implement task i; arrive[i] = 1;
await (continue[i] == 1); continue[i] = 0;
process Coordinator { while (true) {
for [i = 1 to n] {
await (arrive[i] == 1);
arrive[i] = 0;
for [i = 1 to n] continue[i] = 1; }
Why 2n flags?
Can we make it work with n flags
What about contention?
What about total time in best case (all workers arrive at once)

Combining Tree Barriers

All processes must arrive before any leave
Flags: one per edge in the signaling graph
Different types of barriers so far:
Counter symmetric, but reset problem and O(n) Coordinator simple, but asymmetric and O(n)
Tree O(log n), but asymmetric and harder to program

Two Process Barrier
Basic building block for two processes:
Worker1<–>Worker2 # signal each other
shared vars:
Worker[i]:
Worker[j]:
int arrive[n] = ([n] 0);
arrive[i] = 1;
< await(arrive[j]==1); >
arrive[j] = 1;
< await([arrive[i]==1); >
What about reset?

Two Process Barrier
Worker[i]:
Worker[j]:
arrive[i] = 1;
< await(arrive[j]==1); >
arrive[j] = 0;
arrive[j] = 1;
< await([arrive[i]==1); >
arrive[i] = 0;

Symmetric Barriers
What about reuse?
Worker[i]:
Worker[j]:

arrive[i] = 1;
< await(arrive[j]==1); >
arrive[j] = 0;

arrive[j] = 1;
< await([arrive[i]==1); >
arrive[i] = 0;

Butterfly Barrier
log2n stages of 2 process barriers
idea is to replicate work: each worker barriers with log2n others

Butterfly Barrier
Use multiple flags (arrays)
Or better yet, use stage counters:
# barrier code for worker process I
for [s = 1 to num_stages] {
arrive[i] = arrive[i] + 1;
#determine neighbour j for stage s while (arrive[j] < arrive[i]) skip; Butterfly BarrierAny disadvantages? Dissemination BarrierA different way to connect the processesSimpler to program and works for any value of n CS: assignmentchef QQ: 1823890830 Email: [email protected]