Subsections


5 . Structured Control Flow: Structured Dagger

Charm++ is based on the message-driven parallel programming paradigm. In contrast to many other approaches, Charm++ programmers encode entry points to their parallel objects, but do not explicitly wait (i.e. block) on the runtime to indicate completion of posted `receive' requests. Thus, a Charm++ object's overall flow of control can end up fragmented across a number of separate methods, obscuring the sequence in which code is expected to execute. Furthermore, there are often constraints on when different pieces of code should execute relative to one another, related to data and synchronization dependencies. Consider one way of expressing these constraints using flags, buffers, and counters, as in the following example:

 // in .ci file

chare ComputeObject {
  entry void ComputeObject();
  entry void startStep();
  entry void firstInput(Input i);
  entry void secondInput(Input j);
};

// in C++ file

class ComputeObject : public CBase_ComputeObject {
  int   expectedMessageCount;
  Input first, second;


public:
  ComputeObject() {
    startStep();
  }
  void startStep() {
    expectedMessageCount = 2;
  }

  void firstInput(Input i) {
    first = i;
    if (--expectedMessageCount == 0)
      computeInteractions(first, second);
    }
  void recv_second(Input j) {
    second = j;
    if (--expectedMessageCount == 0)
      computeInteractions(first, second);
  }

  void computeInteractions(Input a, Input b) {
    // do computations using a and b
    . . .
    // send off results
    . . .
    // reset for next step
    startStep();
  }
};

In each step, this object expects pairs of messages, and waits to process the incoming data until it has both of them. This sequencing is encoded across 4 different functions, which in real code could be much larger and more numerous, resulting in a spaghetti-code mess. Instead, it would be preferable to express this flow of control using structured constructs, such as loops. Charm++ provides such constructs for structured control flow across an object's entry methods in a notation called Structured Dagger. The basic constructs of Structured Dagger (SDAG) provide for program-order execution of the entry methods and code blocks that they define. These definitions appear in the .ci file definition of the enclosing chare class as a `body' of an entry method following its signature. The most basic construct in SDAG is the serial (aka the atomic ) block. Serial blocks contain sequential C++ code. They're also called atomic because the code within them executes without returning control to the Charm++ runtime scheduler, and thus avoiding interruption from incoming messages. The keywords atomic and serial are synonymous, and you can find example programs that use atomic. However, we recommend the use of serial and are considering the deprecation of the atomic keyword. Typically serial blocks hold the code that actually deals with incoming messages in a when statement, or to do local operations before a message is sent or after it's received. The earlier example can be adapted to use serial blocks as follows:

 // in .ci file

chare ComputeObject {
  entry void ComputeObject();
  entry void startStep();
  entry void firstInput(Input i) {
    serial {
      first = i;
      if (--expectedMessageCount == 0)
        computeInteractions(first, second);
    }
  };
  entry void secondInput(Input j) {
    serial {
      second = j;
      if (--expectedMessageCount == 0)
        computeInteractions(first, second);
    }
  };
};

// in C++ file

class ComputeObject : public CBase_ComputeObject {
  ComputeObject_SDAG_CODE
  int   expectedMessageCount;
  Input first, second;


public:
  ComputeObject() {
    startStep();
  }
  void startStep() {
    expectedMessageCount = 2;
  }

  void computeInteractions(Input a, Input b) {
    // do computations using a and b
    . . .
    // send off results
    . . .
    // reset for next step
    startStep();
  }
};

Note that chare classes containing SDAG code must include a few additional declarations in addition to inheriting from their CBase_Foo class, by incorporating the Foo_SDAG_CODE generated-code macro in the class. Serial blocks can also specify a textual `label' that will appear in traces, as follows:

   entry void firstInput(Input i) {
    serial "process first" {
      first = i;
      if (--expectedMessageCount == 0)
        computeInteractions(first, second);
    }
  };

In order to control the sequence in which entry methods are processed, SDAG provides the when construct. These statements, also called triggers, indicate that we expect an incoming message of a particular type, and provide code to handle that message when it arrives. From the perspective of a chare object reaching a when statement, it is effectively a `blocking receive.' Entry methods defined by a when are not executed immediately when a message targeting them is delivered, but instead are held until control flow in the chare reaches a corresponding when clause. Conversely, when control flow reaches a when clause, the generated code checks whether a corresponding message has arrived: if one has arrived, it is processed; otherwise, control is returned to the Charm++ scheduler. The use of when substantially simplifies the example from above:

 // in .ci file

chare ComputeObject {
  entry void ComputeObject();
  entry void startStep() {
    when firstInput(Input first)
      when secondInput(Input second)
        serial {
          computeInteractions(first, second);
        }
  };
  entry void firstInput(Input i);
  entry void secondInput(Input j);
};

// in C++ file

class ComputeObject : public CBase_ComputeObject {
  ComputeObject_SDAG_CODE


public:
  ComputeObject() {
    startStep();
  }

  void computeInteractions(Input a, Input b) {
    // do computations using a and b
    . . .
    // send off results
    . . .
    // reset for next step
    startStep();
  }
};

Like an if or while in C code, each when clause has a body made up of the statement or block following it. The variables declared as arguments to the entry method triggering the when are available in the scope of the body. By using the sequenced execution of SDAG code and the availability of parameters to when-defined entry methods in their bodies, the counter expectedMessageCount and the intermediate copies of the received input are eliminated. Note that the entry methods firstInput and secondInput are still declared in the .ci file, but their definition is in the SDAG code. The interface translator generates code to handle buffering and triggering them appropriately. For simplicity, when constructs can also specify multiple expected entry methods that all feed into a single body, by separating their prototypes with commas:

 entry void startStep() {
  when firstInput(Input first),
       secondInput(Input second)
    serial {
      computeInteractions(first, second);
    }
};

A single entry method is allowed to appear in more than one when statement. If only one of those when statements has been triggered when the runtime delivers a message to that entry method, that when statement is guaranteed to process it. If there is no trigger waiting for that entry method, then the next corresponding when to be reached will receive that message. If there is more than one when waiting on that method, which one will receive it is not specified, and should not be relied upon. For an example of multiple when statements handling the same entry method without reaching the unspecified case, see the CharmLU benchmark.

To more finely control the correspondence between incoming messages and when clauses associated with the target entry method, SDAG supports matching on reference numbers. Matching is typically used to denote an iteration of a program that executes asynchronously (without any sort of barrier or other synchronization between steps) or a particular piece of the problem being solved. Matching is requested by placing an expression denoting the desired reference number in square brackets between the entry method name and its parameter list. For parameter marshalled entry methods, the reference number expression will be compared for equality with the entry method's first argument. For entry methods that accept an explicit message (§  10.1 ), the reference number on the message can be set by calling the function CkSetRefNum(void *msg, CMK_REFNUM_TYPE ref) . Matching is used in the loop example below, and in examples/charm++/jacobi2d-sdag/jacobi2d.ci . Multiple when triggers for an entry method with different matching reference numbers will not conflict - each will receive only corresponding messages.

SDAG supports the for and while loop constructs mostly as if they appeared in plain C or C++ code. In the running example, computeInteractions() calls startStep() when it is finished to start the next step. Instead of this arrangement, the loop structure can be made explicit:


 // in .ci file

chare ComputeObject {
  entry void ComputeObject();
  entry void runForever() {
    while(true) {
      when firstInput(Input first),
           secondInput(Input second) serial {
          computeInteractions(first, second);
      }
    }
  };
  entry void firstInput(Input i);
  entry void secondInput(Input j);
};

// in C++ file

class ComputeObject : public CBase_ComputeObject {
  ComputeObject_SDAG_CODE


public:
  ComputeObject() {
    runForever();
  }

  void computeInteractions(Input a, Input b) {
    // do computations using a and b
    . . .
    // send off results
    . . .
  }
};

If this code should instead run for a fixed number of iterations, we can instead use a for loop:


 // in .ci file

chare ComputeObject {
  entry void ComputeObject();
  entry void runForever() {
    for(iter = 0; iter < n; ++iter) {
      // Match to only accept inputs for the current iteration
      when firstInput[iter](int a, Input first),
           secondInput[iter](int b, Input second) serial {
        computeInteractions(first, second);
      }
    }
  };
  entry void firstInput(int a, Input i);
  entry void secondInput(int b, Input j);
};

// in C++ file

class ComputeObject : public CBase_ComputeObject {
  ComputeObject_SDAG_CODE
  int n, iter;


public:
  ComputeObject() {
    n = 10;
    runForever();
  }

  void computeInteractions(Input a, Input b) {
    // do computations using a and b
    . . .
    // send off results
    . . .
  }
};

Note that int iter; is declared in the chare's class definition and not in the .ci file. This is necessary because the Charm++ interface translator does not fully parse the declarations in the for loop header, because of the inherent complexities of C++.

SDAG also supports conditional execution of statements and blocks with if statements. The syntax of SDAG if statements matches that of C and C++. However, if one encounters a syntax error on correct-looking code in a loop or conditional statement, try assigning the condition expression to a boolean variable in a serial block preceding the statement and then testing that boolean's value. This can be necessary because of the complexity of parsing C++ code.

In cases where multiple tasks must be processed before execution continues, but with no dependencies or interactions among them, SDAG provides the overlap construct. Overlap blocks contain a series of SDAG statements within them which can occur in any order. Commonly these blocks are used to hold a series of when triggers which can be received and processed in any order. Flow of control doesn't leave the overlap block until all the statements within it have been processed.

In the running example, suppose each input needs to be preprocessed independently before the call to computeInteractions . Since we don't care which order they get processed in, and want it to happen as soon as possible, we can apply overlap :


 // in .ci file

chare ComputeObject {
  entry void ComputeObject();
  entry void startStep() {
    overlap {
      when firstInput(Input i)
        serial { first = preprocess(i); }
      when secondInput(Input j)
        serial { second = preprocess(j); }
     }
     serial {
       computeInteractions(first, second);
     }
  };
  entry void firstInput(Input i);
  entry void secondInput(Input j);
};

// in C++ file

class ComputeObject : public CBase_ComputeObject {
  ComputeObject_SDAG_CODE


public:
  ComputeObject() {
    startStep();
  }

  void computeInteractions(Input a, Input b) {
    // do computations using a and b
    . . .
    // send off results
    . . .
    // reset for next step
    startStep();
  }
};

Another construct offered by SDAG is the forall loop. These loops are used when the iterations of a loop can be performed independently and in any order. This is in contrast to a regular for loop, in which each iteration is executed sequentially. The loop iterations are executed entirely on the calling PE, so they do not run in parallel. However, they are executed concurrently, in that execution of different iterations can interleave at when statements, like any other SDAG code. SDAG statements following the forall loop will not execute until all iterations have completed. The forall loop can be seen as an overlap with an indexed set of otherwise identical statements in the body.

The syntax of forall is


 forall [IDENT] (MIN:MAX,STRIDE) BODY

The range from MIN to MAX is inclusive. In each iteration instance of BODY , the IDENT variable will take on one of the values in the specified range. The IDENT variable must be declared in the application C++ code as a member of the enclosing chare class.

Use of forall is demonstrated through distributed parallel matrix-matrix multiply shown in examples/charm++/matmul/matmul.ci

5 . 0 . 1 The case Statement

The case statement in SDAG expresses a disjunction over a set of when clauses. In other words, if it is known that one dependency out of a set will be satisfied, but which one is not known, this statement allows the set to be specified and will execute the corresponding block based on which dependency ends up being fulfilled.

The following is a basic example of the case statement. Note that the trigger b(), d() will only be fulfilled if both b() and d() arrive. If only one arrives, then it will partially match, and the runtime will not ``commit'' to this branch until the second arrives. If another dependency fully matches, the partial match will be ignored and can be used to trigger another when later in the execution.

case {
  when a() { }
  when b(), d() { }
  when c() { }
}

A full example of the case statement can be found tests/charm++/sdag/case/caseTest.ci .

5 . 1 Usage Notes

If you've added Structured Dagger code to your class, you must link in the code by adding `` className _SDAG_CODE'' inside the class declaration in the .h file. This macro defines the entry points and support code used by Structured Dagger . Forgetting this results in a compile error (undefined SDAG entry methods referenced from the .def.h file).

For example, an array named ``Foo'' that uses sdag code might contain:


 class Foo : public CBase_Foo {

public:
    Foo_SDAG_CODE
    Foo(...) {
       ...
    }
    Foo(CkMigrateMessage *m) { }
    
    void pup(PUP::er &p) {
       ...
    }
    . . .
};