2ecbdd554220425fac616f510bd233aa4915dfbd
[charm.git] / doc / charm++ / sdag.tex
1 \subsection{Structured Control Flow: Structured Dagger}
2 \label{sec:sdag}
3
4 \charmpp\ is based on the message-driven parallel programming paradigm. In
5 contrast to many other approaches, \charmpp\ programmers encode entry points to
6 their parallel objects, but do not explicitly wait (i.e. block) on the runtime
7 to indicate completion of posted `receive' requests. Thus, a \charmpp\ object's
8 overall flow of control can end up fragmented across a number of separate
9 methods, obscuring the sequence in which code is expected to
10 execute. Furthermore, there are often constraints on when different pieces of
11 code should execute relative to one another, related to data and
12 synchronization dependencies.
13
14 Consider one way of expressing these constraints using flags, buffers, and
15 counters, as in the following example:
16 %
17 %\begin{figure}[ht]
18 \begin{center}
19 \begin{alltt}
20 // in .ci file
21 chare ComputeObject \{
22   entry void ComputeObject();
23   entry void startStep();
24   entry void firstInput(Input i);
25   entry void secondInput(Input j);
26 \};
27
28 // in C++ file
29 class ComputeObject : public CBase_ComputeObject \{
30   int   expectedMessageCount;
31   Input first, second;
32
33 public:
34   ComputeObject() \{
35     startStep();
36   \}
37   void startStep() \{
38     expectedMessageCount = 2;
39   \}
40
41   void firstInput(Input i) \{
42     first = i;
43     if (--expectedMessageCount == 0)
44       computeInteractions(first, second);
45     \}
46   void recv_second(Input j) \{
47     second = j;
48     if (--expectedMessageCount == 0)
49       computeInteractions(first, second);
50   \}
51
52   void computeInteractions(Input a, Input b) \{
53     // do computations using a and b
54     . . .
55     // send off results
56     . . .
57     // reset for next step
58     startStep();
59   \}
60 \};
61 \end{alltt}
62 \end{center}
63 %\caption{Compute Object in a Molecular Dynamics Application}
64 %\label{figchareexample}
65 %\end{figure}
66 In each step, this object expects pairs of messages, and waits to process the
67 incoming data until it has both of them. This sequencing is encoded across 4
68 different functions, which in real code could be much larger and more numerous,
69 resulting in a spaghetti-code mess.
70
71 Instead, it would be preferable to express this flow of control using
72 structured constructs, such as loops. \charmpp\ provides such constructs for
73 structured control flow across an object's entry methods in a notation called
74 Structured Dagger. The basic constructs of Structured Dagger (SDAG) provide for
75 \emph{program-order execution} of the entry methods and code blocks that they
76 define. These definitions appear in the {\tt .ci} file definition of the
77 enclosing chare class as a `body' of an entry method following its signature.
78
79 The most basic construct in SDAG is the {\tt atomic} block. Atomic blocks
80 contain sequential \CC code.  They're called atomic because the code within
81 them executes without returning control to the \charmpp\ runtime scheduler, and
82 thus avoiding interruption from incoming messages. Typically atomic blocks hold
83 the code that actually deals with incoming messages in a {\tt when} statement,
84 or to do local operations before a message is sent or after it's received. The
85 earlier example can be adapted to use atomic blocks as follows:
86 \begin{center}
87 \begin{alltt}
88 // in .ci file
89 chare ComputeObject \{
90   entry void ComputeObject();
91   entry void startStep();
92   entry void firstInput(Input i) \{
93     atomic \{
94       first = i;
95       if (--expectedMessageCount == 0)
96         computeInteractions(first, second);
97     \}
98   \};
99   entry void secondInput(Input j) \{
100     atomic \{
101       second = j;
102       if (--expectedMessageCount == 0)
103         computeInteractions(first, second);
104     \}
105   \};
106 \};
107
108 // in C++ file
109 class ComputeObject : public CBase\_ComputeObject \{
110   ComputeObject\_SDAG\_Code
111   int   expectedMessageCount;
112   Input first, second;
113
114 public:
115   ComputeObject() \{
116     __sdag_init();
117     startStep();
118   \}
119   void startStep() \{
120     expectedMessageCount = 2;
121   \}
122
123   void computeInteractions(Input a, Input b) \{
124     // do computations using a and b
125     . . .
126     // send off results
127     . . .
128     // reset for next step
129     startStep();
130   \}
131 \};
132 \end{alltt}
133 \end{center}
134 Note that chare classes containing SDAG code must make a few additional calls
135 in addition to inheriting from their {\tt CBase\_Foo} class: incorporate the
136 {\tt Foo\_SDAG\_CODE} generated-code macro in the class, and call {\tt
137   \_\_sdag\_init()} in the class's constructor(s).
138
139 Atomic blocks can also specify a textual `label' that will appear in traces, as
140 follows:
141 \begin{center}
142 \begin{alltt}
143   entry void firstInput(Input i) \{
144     atomic "process first" \{
145       first = i;
146       if (--expectedMessageCount == 0)
147         computeInteractions(first, second);
148     \}
149   \};
150 \end{alltt}
151 \end{center}
152
153 In order to control the sequence in which entry methods are processed, SDAG
154 provides the {\tt when} construct. Entry methods defined by a {\tt when} are
155 not executed immediately when a message tergeting them is delivered, but
156 instead are held until control flow in the chare reaches a corresponding {\tt
157   when} clause. Conversely, when control flow reaches a {\tt when} clause, the
158 generated code checks whether a corresponding message has arrived: if one has
159 arrived, it is processed; otherwise, control is returned to the
160 \charmpp\ scheduler. 
161
162 The use of {\tt when} substantially simplifies the example from above:
163 \begin{center}
164 \begin{alltt}
165 // in .ci file
166 chare ComputeObject \{
167   entry void ComputeObject();
168   entry void startStep() \{
169     when firstInput(Input first)
170       when secondInput(Input second)
171         atomic \{
172           computeInteractions(first, second);
173         \}
174   \};
175   entry void firstInput(Input i);
176   entry void secondInput(Input j);
177 \};
178
179 // in C++ file
180 class ComputeObject : public CBase_ComputeObject \{
181   ComputeObject_SDAG_Code
182
183 public:
184   ComputeObject() \{
185     __sdag_init();
186     startStep();
187   \}
188
189   void computeInteractions(Input a, Input b) \{
190     // do computations using a and b
191     . . .
192     // send off results
193     . . .
194     // reset for next step
195     startStep();
196   \}
197 \};
198 \end{alltt}
199 \end{center}
200 Like an {\tt if} or {\tt while} in C code, each {\tt when} clause has a body
201 made up of the statement or block following it. The variables declared as
202 arguments to the entry method triggering the when are available in the scope of
203 the body. By using the sequenced execution of SDAG code and the availability of
204 parameters to when-defined entry methods in their bodies, the counter {\tt
205   expectedMessageCount} and the intermediate copies of the received input are
206 eliminated. Note that the entry methods {\tt firstInput} and {\tt secondInput}
207 are still declared in the {\tt .ci} file, but their definition is in the SDAG
208 code. The interface translator generates code to handle buffering and
209 triggering them appropriately.
210
211 For simplicity, {\tt when} constructs can also specify multiple expected entry
212 methods that all feed into a single body, by separating their prototypes with
213 commas:
214 \begin{center}
215 \begin{alltt}
216 entry void startStep() \{
217   when firstInput(Input first),
218        secondInput(Input second)
219     atomic \{
220       computeInteractions(first, second);
221     \}
222 \};
223 \end{alltt}
224 \end{center}
225
226 SDAG supports the {\tt for} and {\tt while} loop constructs mostly as if they
227 appeared in plain C or C++ code. In the running example, {\tt
228   computeInteractions()} calls {\tt startStep()} when it is finished to start
229 the next step. Instead of this arrangement, the loop structure can be made
230 explicit:
231 \begin{center}
232 \begin{alltt}
233 // in .ci file
234 chare ComputeObject \{
235   entry void ComputeObject();
236   entry void runForever() \{
237     while(true) \{
238       when firstInput(Input first),
239            secondInput(Input second) atomic \{
240           computeInteractions(first, second);
241       \}
242     \}
243   \};
244   entry void firstInput(Input i);
245   entry void secondInput(Input j);
246 \};
247
248 // in C++ file
249 class ComputeObject : public CBase_ComputeObject \{
250   ComputeObject_SDAG_Code
251
252 public:
253   ComputeObject() \{
254     __sdag_init();
255     runForever();
256   \}
257
258   void computeInteractions(Input a, Input b) \{
259     // do computations using a and b
260     . . .
261     // send off results
262     . . .
263   \}
264 \};
265 \end{alltt}
266 \end{center}
267 If this code should instead run for a fixed number of iterations, we can
268 instead use a for loop:
269 \begin{center}
270 \begin{alltt}
271 // in .ci file
272 chare ComputeObject \{
273   entry void ComputeObject();
274   entry void runForever() \{
275     for(iter = 0; iter < n; ++iter) \{
276       when firstInput(Input first),
277            secondInput(Input second) atomic \{
278         computeInteractions(first, second);
279       \}
280     \}
281   \};
282   entry void firstInput(Input i);
283   entry void secondInput(Input j);
284 \};
285
286 // in C++ file
287 class ComputeObject : public CBase_ComputeObject \{
288   ComputeObject_SDAG_Code
289   int n, iter;
290
291 public:
292   ComputeObject() \{
293     __sdag_init();
294     n = 10;
295     runForever();
296   \}
297
298   void computeInteractions(Input a, Input b) \{
299     // do computations using a and b
300     . . .
301     // send off results
302     . . .
303   \}
304 \};
305 \end{alltt}
306 \end{center}
307 Note that {\tt int iter;} is declared in the chare's class definition and not
308 in the {\tt .ci} file. This is necessary because the \charmpp\ interface
309 translator does not fully parse the declarations in the {\tt for} loop header,
310 because of the inherent complexities of C++.
311
312 SDAG also supports conditional execution of statements and blocks with {\tt if}
313 statements. The syntax of SDAG {\tt if} statements matches that of C and
314 C++. However, if one encounters a parsing error on correct-looking code in a
315 loop or conditional statement, try assigning the condition expression to a
316 boolean variable in an atomic preceding the statement and then testing that
317 boolean's value. This can be necessary because of the complexity of parsing C++
318 code.
319
320 In cases where multiple tasks must be processed before execution continues, but
321 with no dependencies or interactions among them, SDAG provides the {\tt
322   overlap} construct. Overlap blocks contain a series of SDAG statements within
323 them which can occur in any order. Commonly these blocks are used to hold a
324 series of {\tt when} triggers which can be received and processed in any
325 order. Flow of control doesn't leave the overlap block until all the statements
326 within it have been processed.
327
328 In the running example, suppose each input needs to be preprocessed independently
329 before the call to {\tt computerInteractions}. Since we don't care which order
330 they get processed in, and want it to happen as soon as possible, we can apply
331 {\tt overlap}:
332 \begin{center}
333 \begin{alltt}
334 // in .ci file
335 chare ComputeObject \{
336   entry void ComputeObject();
337   entry void startStep() \{
338     overlap \{
339       when firstInput(Input i)
340         atomic \{ first = preprocess(i); \}
341       when secondInput(Input j)
342         atomic \{ second = preprocess(j); \}
343      \}
344      atomic \{
345        computeInteractions(first, second);
346      \}
347   \};
348   entry void firstInput(Input i);
349   entry void secondInput(Input j);
350 \};
351
352 // in C++ file
353 class ComputeObject : public CBase_ComputeObject \{
354   ComputeObject_SDAG_Code
355
356 public:
357   ComputeObject() \{
358     __sdag_init();
359     startStep();
360   \}
361
362   void computeInteractions(Input a, Input b) \{
363     // do computations using a and b
364     . . .
365     // send off results
366     . . .
367     // reset for next step
368     startStep();
369   \}
370 \};
371 \end{alltt}
372 \end{center}
373
374
375
376 Threads are typically used to perform the abovementioned sequencing.
377 Lets us code our previous example using threads.
378
379 %\begin{figure}[ht]
380 \begin{center}
381 \begin{alltt}
382 void compute_thread(int first_index, int second_index)
383 \{
384     getPatch(first_index);
385     getPatch(second_index);
386     threadId[0] = createThread(recvFirst);
387     threadId[1] = createThread(recvSecond);
388     threadJoin(2, threadId);
389     computeInteractions(first, second);
390   \}
391   void recvFirst(void)
392   \{
393     recv(first, sizeof(Patch), ANY_PE, FIRST_TAG);
394     filter(first);
395   \}
396   void recvSecond(void)
397   \{
398     recv(second, sizeof(Patch), ANY_PE, SECOND_TAG);
399     filter(second);
400   \}
401 \end{alltt}
402 \end{center}
403 %\caption{Compute Thread in a Molecular Dynamics Application}
404 %\label{figthreadexample}
405 %\end{figure}
406
407 Contrast the compute chare-object example in figure~\ref{figchareexample} with
408 a thread-based implementation of the same scheme in
409 figure~\ref{figthreadexample}. Functions \uw{getFirst}, and \uw{getSecond} send
410 messages asynchronously to the PatchManager, requesting that the specified
411 patches be sent to them, and return immediately. Since these messages with
412 patches could arrive in any order, two threads, \uw{recvFirst} and
413 \uw{recvSecond}, are created. These threads block, waiting for messages to
414 arrive. After each message arrives, each thread performs the filtering
415 operation. The main thread waits for these two threads to complete, and then
416 computes the pairwise interactions. Though the programming complexity of
417 buffering the messages and maintaining the counters has been eliminated in this
418 implementation, considerable overhead in the form of thread creation, and
419 synchronization in the form of {\em join} has been added. Let us now code the
420 same example in \sdag. It reduces the parallel programming complexity without
421 adding any significant overhead.
422
423 %\begin{figure}[ht]
424 \begin{center}
425 \begin{alltt}
426   array[1D] compute_object \{
427     entry void recv_first(Patch *first);
428     entry void recv_second(Patch *first);
429     entry void compute_object(MSG *msg)\{
430       atomic \{
431          PatchManager->Get(msg->first_index,\dots);
432          PatchManager->Get(msg->second_index,\dots);
433       \}
434       overlap \{
435         when recv_first(Patch *first) atomic \{ filter(first); \}
436         when recv_second(Patch *second) atomic \{ filter(second); \}
437       \}
438       atomic \{ computeInteractions(first, second); \}
439     \}
440   \}
441 \end{alltt}
442 \end{center}
443 %\caption{\sdag\ Implementation of the Compute Object}
444 %\label{figsdagexample}
445 %\end{figure}
446
447 \sdag\ is a coordination language built on top of \charmpp\ that supports the
448 sequencing mentioned above, while overcoming limitations of thread-based
449 languages, and facilitating a clear expression of flow of control within the
450 object without losing the performance benefits of adaptive message-driven
451 execution.  In other words, \sdag\ is a structured notation for specifying
452 intra-process control dependences in message-driven programs. It combines the
453 efficiency of message-driven execution with the explicitness of control
454 specification. \sdag\ allows easy expression of dependences among messages and
455 computations and also among computations within the same object using
456 when-blocks and various structured constructs.  \sdag\ is adequate for
457 expressing control-dependencies that form a series-parallel control-flow graph.
458 \sdag\ has been developed on top of \charmpp\. \sdag\ allows \charmpp\ entry
459 methods (in chares, groups or arrays) to specify code (a when-block body) to be
460 executed upon occurrence of certain events.  These events (or guards of a
461 when-block) are entry methods of the object that can be invoked remotely. While
462 writing a \sdag\ program, one has to declare these entries in \charmpp\
463 interface file. The implementation of the entry methods that contain the
464 when-block is written using the \sdag\ language. Grammar of \sdag\ is given in
465 the EBNF form below.
466
467 \subsubsection{Usage}
468
469 You can use SDAG to implement entry methods for any chare, chare array, group,
470 or nodegroup. Any entry method implemented using SDAG must be implemented in the
471 interface (.ci) file for its class. An SDAG entry method consists of a series of
472 SDAG constructs of the following kinds:
473
474 \begin{itemize}
475     \item {\tt when} statements: These statement, also called triggers, indicate
476         that we expect an incoming message of a particular type, and provide
477         code to handle that message when it arrives. They commonly occur inside
478         of {\tt overlap} blocks, loops, and other control flow statements.
479     \item {\tt forall} loops: These loops are used when each iteration of a loop
480         can be performed in parallel. This is in contrast to a regular {\tt for}
481         loop, in which each iteration is executed sequentially.
482     \item {\tt if}, {\tt for}, and {\tt while} statements: these statements have
483         the same meaning as the normal {\tt if}, {\tt for}, and {\tt while}
484         loops in sequential \CC programs. This allows the programmer to use
485         common control flow constructs outside the context of atomic blocks.
486 \end{itemize}
487
488 \sdag{} code can be inserted into the .ci file for any array, group, or chare's entry methods.
489
490 If you've added \sdag\ code to your class, you must link in the code by:
491 \begin{itemize}
492   \item Adding ``{\it className}\_SDAG\_CODE'' inside the class declaration
493      in the .h file.  This macro defines the entry points and support
494      code used by \sdag{}.  Forgetting this results in a compile error
495      (undefined sdag entry methods referenced from the .def file).
496   \item Adding a call to the routine ``\_\_sdag\_init();'' from every constructor,
497      including the migration constructor.  Forgetting this results in
498      using uninitalized data, and a horrible runtime crash.
499   \item Adding a call to the pup routine ``\_\_sdag\_pup(p);'' from your pup routine.
500      Forgetting this results in failure after migration.
501 \end{itemize}
502
503 For example, an array named ``Foo'' that uses sdag code might contain:
504
505 \begin{alltt}
506 class Foo : public CBase_Foo \{
507 public:
508     Foo_SDAG_CODE
509     Foo(...) \{
510        __sdag_init();
511        ...
512     \}
513     Foo(CkMigrateMessage *m) \{
514        __sdag_init();
515     \}
516     
517     void pup(PUP::er &p) \{
518        CBase_Foo::pup(p);
519        __sdag_pup(p);
520     \}
521 \};
522 \end{alltt}
523
524 For more details regarding \sdag{}, look at the example located in the 
525 {\tt examples/charm++/hello/sdag} directory in the \charmpp\ distribution.
526
527
528 \subsubsection{Grammar}
529
530 \paragraph{Tokens}
531
532 \begin{alltt}
533   <ident> = Valid \CC{} identifier 
534   <int-expr> = Valid \CC{} integer expression 
535   <\CC{}-code> = Valid \CC{} code 
536 \end{alltt}
537
538 \paragraph{Grammar in EBNF Form}
539
540 \begin{alltt}
541 <sdag> := <class-decl> <sdagentry>+ 
542
543 <class-decl> := "class" <ident> 
544
545 <sdagentry> := "sdagentry" <ident> "(" <ident> "*" <ident> ")" <body> 
546
547 <body> := <stmt> 
548         | "\{" <stmt>+ "\}" 
549
550 <stmt> := <overlap-stmt> 
551         | <when-stmt> 
552         | <atomic-stmt> 
553         | <if-stmt> 
554         | <while-stmt> 
555         | <for-stmt> 
556         | <forall-stmt> 
557
558 <overlap-stmt> := "overlap" <body> 
559
560 <atomic-stmt> := "atomic" "\{" <\CC-code> "\}" 
561
562 <if-stmt> := "if" "(" <int-expr> ")" <body> [<else-stmt>] 
563
564 <else-stmt> := "else" <body> 
565
566 <while-stmt> := "while" "(" <int-expr> ")" <body> 
567
568 <for-stmt> := "for" "(" <c++-code> ";" <int-expr> ";" <c++-code> ")" <body> 
569
570 <forall-stmt> := "forall" "[" <ident> "]" "(" <range-stride> ")" <body> 
571
572 <range-stride> := <int-expr> ":" <int-expr> "," <int-expr> 
573
574 <when-stmt> := "when" <entry-list>  <body> 
575
576 <entry-list> := <entry> 
577               | <entry> [ "," <entry-list> ] 
578
579 <entry> := <ident> [ "[" <int-expr> "]" ] "(" <ident> "*" <ident> ")" 
580   
581 \end{alltt}
582