4c0126971818c191e1eb8f3c40acaeff0c92250d
[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. These statements, also called triggers,
155 indicate that we expect an incoming message of a particular type, and provide
156 code to handle that message when it arrives.
157 Entry methods defined by a {\tt when} are
158 not executed immediately when a message tergeting them is delivered, but
159 instead are held until control flow in the chare reaches a corresponding {\tt
160   when} clause. Conversely, when control flow reaches a {\tt when} clause, the
161 generated code checks whether a corresponding message has arrived: if one has
162 arrived, it is processed; otherwise, control is returned to the
163 \charmpp\ scheduler. 
164
165 The use of {\tt when} substantially simplifies the example from above:
166 \begin{center}
167 \begin{alltt}
168 // in .ci file
169 chare ComputeObject \{
170   entry void ComputeObject();
171   entry void startStep() \{
172     when firstInput(Input first)
173       when secondInput(Input second)
174         atomic \{
175           computeInteractions(first, second);
176         \}
177   \};
178   entry void firstInput(Input i);
179   entry void secondInput(Input j);
180 \};
181
182 // in C++ file
183 class ComputeObject : public CBase_ComputeObject \{
184   ComputeObject_SDAG_Code
185
186 public:
187   ComputeObject() \{
188     __sdag_init();
189     startStep();
190   \}
191
192   void computeInteractions(Input a, Input b) \{
193     // do computations using a and b
194     . . .
195     // send off results
196     . . .
197     // reset for next step
198     startStep();
199   \}
200 \};
201 \end{alltt}
202 \end{center}
203 Like an {\tt if} or {\tt while} in C code, each {\tt when} clause has a body
204 made up of the statement or block following it. The variables declared as
205 arguments to the entry method triggering the when are available in the scope of
206 the body. By using the sequenced execution of SDAG code and the availability of
207 parameters to when-defined entry methods in their bodies, the counter {\tt
208   expectedMessageCount} and the intermediate copies of the received input are
209 eliminated. Note that the entry methods {\tt firstInput} and {\tt secondInput}
210 are still declared in the {\tt .ci} file, but their definition is in the SDAG
211 code. The interface translator generates code to handle buffering and
212 triggering them appropriately.
213
214 For simplicity, {\tt when} constructs can also specify multiple expected entry
215 methods that all feed into a single body, by separating their prototypes with
216 commas:
217 \begin{center}
218 \begin{alltt}
219 entry void startStep() \{
220   when firstInput(Input first),
221        secondInput(Input second)
222     atomic \{
223       computeInteractions(first, second);
224     \}
225 \};
226 \end{alltt}
227 \end{center}
228
229 SDAG supports the {\tt for} and {\tt while} loop constructs mostly as if they
230 appeared in plain C or C++ code. In the running example, {\tt
231   computeInteractions()} calls {\tt startStep()} when it is finished to start
232 the next step. Instead of this arrangement, the loop structure can be made
233 explicit:
234 \begin{center}
235 \begin{alltt}
236 // in .ci file
237 chare ComputeObject \{
238   entry void ComputeObject();
239   entry void runForever() \{
240     while(true) \{
241       when firstInput(Input first),
242            secondInput(Input second) atomic \{
243           computeInteractions(first, second);
244       \}
245     \}
246   \};
247   entry void firstInput(Input i);
248   entry void secondInput(Input j);
249 \};
250
251 // in C++ file
252 class ComputeObject : public CBase_ComputeObject \{
253   ComputeObject_SDAG_Code
254
255 public:
256   ComputeObject() \{
257     __sdag_init();
258     runForever();
259   \}
260
261   void computeInteractions(Input a, Input b) \{
262     // do computations using a and b
263     . . .
264     // send off results
265     . . .
266   \}
267 \};
268 \end{alltt}
269 \end{center}
270 If this code should instead run for a fixed number of iterations, we can
271 instead use a for loop:
272 \begin{center}
273 \begin{alltt}
274 // in .ci file
275 chare ComputeObject \{
276   entry void ComputeObject();
277   entry void runForever() \{
278     for(iter = 0; iter < n; ++iter) \{
279       when firstInput(Input first),
280            secondInput(Input second) atomic \{
281         computeInteractions(first, second);
282       \}
283     \}
284   \};
285   entry void firstInput(Input i);
286   entry void secondInput(Input j);
287 \};
288
289 // in C++ file
290 class ComputeObject : public CBase_ComputeObject \{
291   ComputeObject_SDAG_Code
292   int n, iter;
293
294 public:
295   ComputeObject() \{
296     __sdag_init();
297     n = 10;
298     runForever();
299   \}
300
301   void computeInteractions(Input a, Input b) \{
302     // do computations using a and b
303     . . .
304     // send off results
305     . . .
306   \}
307 \};
308 \end{alltt}
309 \end{center}
310 Note that {\tt int iter;} is declared in the chare's class definition and not
311 in the {\tt .ci} file. This is necessary because the \charmpp\ interface
312 translator does not fully parse the declarations in the {\tt for} loop header,
313 because of the inherent complexities of C++.
314
315 SDAG also supports conditional execution of statements and blocks with {\tt if}
316 statements. The syntax of SDAG {\tt if} statements matches that of C and
317 C++. However, if one encounters a parsing error on correct-looking code in a
318 loop or conditional statement, try assigning the condition expression to a
319 boolean variable in an atomic preceding the statement and then testing that
320 boolean's value. This can be necessary because of the complexity of parsing C++
321 code.
322
323 In cases where multiple tasks must be processed before execution continues, but
324 with no dependencies or interactions among them, SDAG provides the {\tt
325   overlap} construct. Overlap blocks contain a series of SDAG statements within
326 them which can occur in any order. Commonly these blocks are used to hold a
327 series of {\tt when} triggers which can be received and processed in any
328 order. Flow of control doesn't leave the overlap block until all the statements
329 within it have been processed.
330
331 In the running example, suppose each input needs to be preprocessed independently
332 before the call to {\tt computerInteractions}. Since we don't care which order
333 they get processed in, and want it to happen as soon as possible, we can apply
334 {\tt overlap}:
335 \begin{center}
336 \begin{alltt}
337 // in .ci file
338 chare ComputeObject \{
339   entry void ComputeObject();
340   entry void startStep() \{
341     overlap \{
342       when firstInput(Input i)
343         atomic \{ first = preprocess(i); \}
344       when secondInput(Input j)
345         atomic \{ second = preprocess(j); \}
346      \}
347      atomic \{
348        computeInteractions(first, second);
349      \}
350   \};
351   entry void firstInput(Input i);
352   entry void secondInput(Input j);
353 \};
354
355 // in C++ file
356 class ComputeObject : public CBase_ComputeObject \{
357   ComputeObject_SDAG_Code
358
359 public:
360   ComputeObject() \{
361     __sdag_init();
362     startStep();
363   \}
364
365   void computeInteractions(Input a, Input b) \{
366     // do computations using a and b
367     . . .
368     // send off results
369     . . .
370     // reset for next step
371     startStep();
372   \}
373 \};
374 \end{alltt}
375 \end{center}
376
377
378
379 Threads are typically used to perform the abovementioned sequencing.
380 Lets us code our previous example using threads.
381
382 %\begin{figure}[ht]
383 \begin{center}
384 \begin{alltt}
385 void compute_thread(int first_index, int second_index)
386 \{
387     getPatch(first_index);
388     getPatch(second_index);
389     threadId[0] = createThread(recvFirst);
390     threadId[1] = createThread(recvSecond);
391     threadJoin(2, threadId);
392     computeInteractions(first, second);
393   \}
394   void recvFirst(void)
395   \{
396     recv(first, sizeof(Patch), ANY_PE, FIRST_TAG);
397     filter(first);
398   \}
399   void recvSecond(void)
400   \{
401     recv(second, sizeof(Patch), ANY_PE, SECOND_TAG);
402     filter(second);
403   \}
404 \end{alltt}
405 \end{center}
406 %\caption{Compute Thread in a Molecular Dynamics Application}
407 %\label{figthreadexample}
408 %\end{figure}
409
410 Contrast the compute chare-object example in figure~\ref{figchareexample} with
411 a thread-based implementation of the same scheme in
412 figure~\ref{figthreadexample}. Functions \uw{getFirst}, and \uw{getSecond} send
413 messages asynchronously to the PatchManager, requesting that the specified
414 patches be sent to them, and return immediately. Since these messages with
415 patches could arrive in any order, two threads, \uw{recvFirst} and
416 \uw{recvSecond}, are created. These threads block, waiting for messages to
417 arrive. After each message arrives, each thread performs the filtering
418 operation. The main thread waits for these two threads to complete, and then
419 computes the pairwise interactions. Though the programming complexity of
420 buffering the messages and maintaining the counters has been eliminated in this
421 implementation, considerable overhead in the form of thread creation, and
422 synchronization in the form of {\em join} has been added. Let us now code the
423 same example in \sdag. It reduces the parallel programming complexity without
424 adding any significant overhead.
425
426 %\begin{figure}[ht]
427 \begin{center}
428 \begin{alltt}
429   array[1D] compute_object \{
430     entry void recv_first(Patch *first);
431     entry void recv_second(Patch *first);
432     entry void compute_object(MSG *msg)\{
433       atomic \{
434          PatchManager->Get(msg->first_index,\dots);
435          PatchManager->Get(msg->second_index,\dots);
436       \}
437       overlap \{
438         when recv_first(Patch *first) atomic \{ filter(first); \}
439         when recv_second(Patch *second) atomic \{ filter(second); \}
440       \}
441       atomic \{ computeInteractions(first, second); \}
442     \}
443   \}
444 \end{alltt}
445 \end{center}
446 %\caption{\sdag\ Implementation of the Compute Object}
447 %\label{figsdagexample}
448 %\end{figure}
449
450 \sdag\ is a coordination language built on top of \charmpp\ that supports the
451 sequencing mentioned above, while overcoming limitations of thread-based
452 languages, and facilitating a clear expression of flow of control within the
453 object without losing the performance benefits of adaptive message-driven
454 execution.  In other words, \sdag\ is a structured notation for specifying
455 intra-process control dependences in message-driven programs. It combines the
456 efficiency of message-driven execution with the explicitness of control
457 specification. \sdag\ allows easy expression of dependences among messages and
458 computations and also among computations within the same object using
459 when-blocks and various structured constructs.  \sdag\ is adequate for
460 expressing control-dependencies that form a series-parallel control-flow graph.
461 \sdag\ has been developed on top of \charmpp\. \sdag\ allows \charmpp\ entry
462 methods (in chares, groups or arrays) to specify code (a when-block body) to be
463 executed upon occurrence of certain events.  These events (or guards of a
464 when-block) are entry methods of the object that can be invoked remotely. While
465 writing a \sdag\ program, one has to declare these entries in \charmpp\
466 interface file. The implementation of the entry methods that contain the
467 when-block is written using the \sdag\ language. Grammar of \sdag\ is given in
468 the EBNF form below.
469
470 \subsubsection{Usage}
471
472 You can use SDAG to implement entry methods for any chare, chare array, group,
473 or nodegroup. Any entry method implemented using SDAG must be implemented in the
474 interface (.ci) file for its class. An SDAG entry method consists of a series of
475 SDAG constructs of the following kinds:
476
477 \begin{itemize}
478     \item {\tt forall} loops: These loops are used when each iteration of a loop
479         can be performed in parallel. This is in contrast to a regular {\tt for}
480         loop, in which each iteration is executed sequentially.
481     \item {\tt if}, {\tt for}, and {\tt while} statements: these statements have
482         the same meaning as the normal {\tt if}, {\tt for}, and {\tt while}
483         loops in sequential \CC programs. This allows the programmer to use
484         common control flow constructs outside the context of atomic blocks.
485 \end{itemize}
486
487 \sdag{} code can be inserted into the .ci file for any array, group, or chare's entry methods.
488
489 If you've added \sdag\ code to your class, you must link in the code by:
490 \begin{itemize}
491   \item Adding ``{\it className}\_SDAG\_CODE'' inside the class declaration
492      in the .h file.  This macro defines the entry points and support
493      code used by \sdag{}.  Forgetting this results in a compile error
494      (undefined sdag entry methods referenced from the .def file).
495   \item Adding a call to the routine ``\_\_sdag\_init();'' from every constructor,
496      including the migration constructor.  Forgetting this results in
497      using uninitalized data, and a horrible runtime crash.
498   \item Adding a call to the pup routine ``\_\_sdag\_pup(p);'' from your pup routine.
499      Forgetting this results in failure after migration.
500 \end{itemize}
501
502 For example, an array named ``Foo'' that uses sdag code might contain:
503
504 \begin{alltt}
505 class Foo : public CBase_Foo \{
506 public:
507     Foo_SDAG_CODE
508     Foo(...) \{
509        __sdag_init();
510        ...
511     \}
512     Foo(CkMigrateMessage *m) \{
513        __sdag_init();
514     \}
515     
516     void pup(PUP::er &p) \{
517        CBase_Foo::pup(p);
518        __sdag_pup(p);
519     \}
520 \};
521 \end{alltt}
522
523 For more details regarding \sdag{}, look at the example located in the 
524 {\tt examples/charm++/hello/sdag} directory in the \charmpp\ distribution.
525
526
527 \subsubsection{Grammar}
528
529 \paragraph{Tokens}
530
531 \begin{alltt}
532   <ident> = Valid \CC{} identifier 
533   <int-expr> = Valid \CC{} integer expression 
534   <\CC{}-code> = Valid \CC{} code 
535 \end{alltt}
536
537 \paragraph{Grammar in EBNF Form}
538
539 \begin{alltt}
540 <sdag> := <class-decl> <sdagentry>+ 
541
542 <class-decl> := "class" <ident> 
543
544 <sdagentry> := "sdagentry" <ident> "(" <ident> "*" <ident> ")" <body> 
545
546 <body> := <stmt> 
547         | "\{" <stmt>+ "\}" 
548
549 <stmt> := <overlap-stmt> 
550         | <when-stmt> 
551         | <atomic-stmt> 
552         | <if-stmt> 
553         | <while-stmt> 
554         | <for-stmt> 
555         | <forall-stmt> 
556
557 <overlap-stmt> := "overlap" <body> 
558
559 <atomic-stmt> := "atomic" "\{" <\CC-code> "\}" 
560
561 <if-stmt> := "if" "(" <int-expr> ")" <body> [<else-stmt>] 
562
563 <else-stmt> := "else" <body> 
564
565 <while-stmt> := "while" "(" <int-expr> ")" <body> 
566
567 <for-stmt> := "for" "(" <c++-code> ";" <int-expr> ";" <c++-code> ")" <body> 
568
569 <forall-stmt> := "forall" "[" <ident> "]" "(" <range-stride> ")" <body> 
570
571 <range-stride> := <int-expr> ":" <int-expr> "," <int-expr> 
572
573 <when-stmt> := "when" <entry-list>  <body> 
574
575 <entry-list> := <entry> 
576               | <entry> [ "," <entry-list> ] 
577
578 <entry> := <ident> [ "[" <int-expr> "]" ] "(" <ident> "*" <ident> ")" 
579   
580 \end{alltt}
581