A node in a precedence graph could be a software task, as recognised by the operating system, or could be statements within a program that can be executed concurrently with respect to each other [see example below], or could describe some activity taking place during the execution of a single machine instruction. People refer to the different "sizes" of these concurrent activities, as the CONCURRENCY GRAIN of the representation. It goes from COARSE (the concurrency of operating systems task), to fine (the concurrency of single instructions, or of groups of instructions, as done for example in superscalar processors), to very fine (concurrency in the hardware during the execution of the single instruction).
a := x + y; /* Statement s1 */ b := z + 1; /* Statement s2 */ c := a - b; /* Statement s3 */ w := c + 1; /* Statement s4 */ d := a + e; /* Statement s5 */ w := w * d; /* Statement s6 */We can use the Bernstein conditions to derive a precedence graph from this sequential program. The nodes in this graph are the statements s1, s2, s3, s4, s5, s6. This precedence graph could be executed using two processors. One processor could execute in order s1, s5, s6 and the other s2, s3, s4. Of course they should synchronize so that s3 executes after s1 and s6 after s4.This precedence graph is MAXIMALLY PARALLEL for the given program. That is, the only dependencies that appear in the graph are those required by the logic of the program.
Given a precedence graph, how many processors should be used to execute it?Notice the precedence graphs are acyclic, that is, they do not have loops. Thus they cannot represent cyclic computations. Since many of the computations in operating systems are cyclical, this is a strong restriction. There are two ways out. One, represent each cycle with an acyclic graph; you will lose possible concurrency across two successive cycles, but you will be able to deal fully with concurrency within a single cycle. Two, give up on precedence graphs and use instead Petri Nets (unfortunately Petri Nets are beyond the scope of our course).
We now we examine how we can represent concurrency and precedence graphs using textual representations. We introduce some of the constructs suggested for the specification of concurrency.
When the statement:
When the statement:
Here are some example where we translate
Precedence Graphs into programs using the Fork and Join constructs.
Note that Fork and Join are Complete for Precedence Graphs in the sense that any Precedence Graph can be expresed using Fork and Join and this is done without loss of concurrency [remember that any precedence graph could be executed as a sequential program, but at a loss in concurrency.]
Here is the construct, where S1, S2, .. Sn are statements:
When CoBegin is executed, S1, S2, .. Sn are executed concurrently each in a separate thread. When all these statements are terminated, only then the CoEnd is executed and the construct is terminated.
Here are examples of Precedence Graphs represented using CoBegin CoEnd. Notice that Cobegin Coend is not complete. That is there are Precedence Graphs that can be represented using CoBegin CoEnd only at the cost of some loss in concurrency.