Fork-Join Quit

[Back]

Fork, Join, Quit: A simple means to create multiple threads of control. This fork command (statement) is not the familiar Unix system call that creates a complete process: it creates a thread within the current process’ context. There are a number of variants, but we’ll look at the one below:

FORK( <label>);
This creates a thread that begins execution at label.
JOIN(int count);
This is an atomic function:
count = count - 1;
if (count .NE. 0) then QUIT();
QUIT(void);
Terminate the current thread.

For example, the sequential (or linear) code on the left, below, executes statement by statement, top to bottom. However, looking carefully, we can observe a number of things about when each statement can exceute. The computation of:

  1. a, r, and s  can occur in parallel (i.e., at the same time);
  2. b must wait for r and s to complete;
  3. c must wait on a and b;
  4. w must wait on the completion  of the other statements simply because its purpose to count loop iterations.  
w = 100;
while ( w>0) {
y = read();
a = y * y;
r = y + 20;
s = y – 10;
b = r * s;
c = a - b;
w = w –1;
}

Precedence graph  

A precedence graph showing fine-grain parallelism.
w=100;
while ( w>0) {
Y = read();
count = count = 2;
FORK(L1);
FORK(L2);
A = y * y;
goto L4;
L1: r = y + 20;
Goto L3;
L2: s = y - 1;
L3: JOIN(count1);
B = r * s;
L4: JOIN(count2);
C = a - b;
w = C+ 1;
}

Practice

Rewrite the code below so that is uses fork-join quit for the maximum amount of fine grain parallelism. (while we have not formally defined max parallelism, intuitively it means to get as much code as possible executing in parallel in such a way as to produce correct results).
while (true) {
a=read();
b=read();
c=read();
d = a * b;
z = 2 * a;
r = c * c;
q = d + z;
p = q + r;
}

 

References:
Conway, "Multiprocessing System Design," Proceedings of the AFIPS fall computer conference, 1963, pp 139-146.
 
Dennis and Van Horne, "Programming Semantics for Multiprogramming Computations," Comm. of the ACM,  March 1966, pg 143-155.