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