Inadequacy of Structured Dagger

Structured Dagger is adequate to express the series-parallel control flow graphs that occur in most parallel objects in real-world applications. However, in some cases, the control-flow graphs of objects do not conform to this restriction. Figure 4.12 shows one such control flow graph. The annotated circles represent code-blocks to be executed. The arrows show dependencies between code-blocks. Note that only the dependencies within an object containing these code-blocks are shown. Each of these code-blocks may have additional external dependencies such as message arrival from remote processors. If one tries to code this graph as a Structured Dagger program, this introduces spurious dependencies and can slow the program down. Figure 4.13 shows two possible implementations in Structured Dagger. In implementation 4.13(a), $C_4$ has to wait for $C_3$ to finish execution and in implementation 4.13(b), $C_3$ unnecessarily waits for $C_2$ to finish execution. In order to express such control flow graphs correctly, a lower-level mechanism is needed. Dagger [28], a notation that makes use of unstructured constructs such as when-blocks and condition-variables can be used to express such control-flow graphs.

Figure 4.12: A Non-Series-Parallel Control-Flow Graph

{NonSpgOne}
  seq {
     C0; 
     overlap { 
       seq { C1; C3; } 
       C2; 
     } 
     C4; 
     C5; 
  }

{NonSpgTwo}
  seq {
     C0; 
     overlap { 
       C1; 
       C2; 
     } 
     overlap { 
       C3; 
       seq { C4; C5; } 
     } 
  }

Figure 4.13: Possible Structured Dagger implementations for the Non-Series-Parallel Graph (Fig. 4.12)