Docs: refer to illinois.edu, not uiuc.edu
[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 \examplereffile{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 \examplereffile{matmul/matmul.ci}
415
416 \section{Usage Notes}
417
418 If you've added \sdag\ code to your class, you must link in the code by:
419 \begin{itemize}
420   \item Adding ``{\it className}\_SDAG\_CODE'' inside the class declaration
421      in the .h file.  This macro defines the entry points and support
422      code used by \sdag{}.  Forgetting this results in a compile error
423      (undefined sdag entry methods referenced from the .def.h file).
424   \item Adding a call to the routine ``\_\_sdag\_init();'' from every constructor,
425      including the migration constructor.  Forgetting this results in
426      using uninitalized data, and a horrible runtime crash.
427   \item Adding a call to the pup routine ``\_\_sdag\_pup(p);'' from your pup routine.
428      Forgetting this results in failure after migration.
429 \end{itemize}
430 For example, an array named ``Foo'' that uses sdag code might contain:
431 \begin{center}
432 \begin{alltt}
433 class Foo : public CBase_Foo \{
434 public:
435     Foo_SDAG_CODE
436     Foo(...) \{
437        __sdag_init();
438        ...
439     \}
440     Foo(CkMigrateMessage *m) \{
441        __sdag_init();
442     \}
443     
444     void pup(PUP::er &p) \{
445        CBase_Foo::pup(p);
446        __sdag_pup(p);
447     \}
448     . . .
449 \};
450 \end{alltt}
451 \end{center}
452
453 \zap{
454 \section{Relationship to Threads}
455
456 Threads are typically used to perform the abovementioned sequencing.
457 Lets us code our previous example using threads.
458
459 %\begin{figure}[ht]
460 \begin{center}
461 \begin{alltt}
462 void compute_thread(int first_index, int second_index)
463 \{
464     getPatch(first_index);
465     getPatch(second_index);
466     threadId[0] = createThread(recvFirst);
467     threadId[1] = createThread(recvSecond);
468     threadJoin(2, threadId);
469     computeInteractions(first, second);
470   \}
471   void recvFirst(void)
472   \{
473     recv(first, sizeof(Patch), ANY_PE, FIRST_TAG);
474     filter(first);
475   \}
476   void recvSecond(void)
477   \{
478     recv(second, sizeof(Patch), ANY_PE, SECOND_TAG);
479     filter(second);
480   \}
481 \end{alltt}
482 \end{center}
483 %\caption{Compute Thread in a Molecular Dynamics Application}
484 %\label{figthreadexample}
485 %\end{figure}
486
487 Contrast the compute chare-object example in figure~\ref{figchareexample} with
488 a thread-based implementation of the same scheme in
489 figure~\ref{figthreadexample}. Functions \uw{getFirst}, and \uw{getSecond} send
490 messages asynchronously to the PatchManager, requesting that the specified
491 patches be sent to them, and return immediately. Since these messages with
492 patches could arrive in any order, two threads, \uw{recvFirst} and
493 \uw{recvSecond}, are created. These threads block, waiting for messages to
494 arrive. After each message arrives, each thread performs the filtering
495 operation. The main thread waits for these two threads to complete, and then
496 computes the pairwise interactions. Though the programming complexity of
497 buffering the messages and maintaining the counters has been eliminated in this
498 implementation, considerable overhead in the form of thread creation, and
499 synchronization in the form of {\em join} has been added. Let us now code the
500 same example in \sdag. It reduces the parallel programming complexity without
501 adding any significant overhead.
502
503 %\begin{figure}[ht]
504 \begin{center}
505 \begin{alltt}
506   array[1D] compute_object \{
507     entry void recv_first(Patch *first);
508     entry void recv_second(Patch *first);
509     entry void compute_object(MSG *msg)\{
510       atomic \{
511          PatchManager->Get(msg->first_index,\dots);
512          PatchManager->Get(msg->second_index,\dots);
513       \}
514       overlap \{
515         when recv_first(Patch *first) atomic \{ filter(first); \}
516         when recv_second(Patch *second) atomic \{ filter(second); \}
517       \}
518       atomic \{ computeInteractions(first, second); \}
519     \}
520   \}
521 \end{alltt}
522 \end{center}
523 %\caption{\sdag\ Implementation of the Compute Object}
524 %\label{figsdagexample}
525 %\end{figure}
526 }
527
528
529 \zap{
530 \section{Grammar}
531
532 \paragraph{Tokens}
533
534 \begin{alltt}
535   <ident> = Valid \CC{} identifier 
536   <int-expr> = Valid \CC{} integer expression 
537   <\CC{}-code> = Valid \CC{} code 
538 \end{alltt}
539
540 \paragraph{Grammar in EBNF Form}
541
542 \begin{alltt}
543 <sdag> := <class-decl> <sdagentry>+ 
544
545 <class-decl> := "class" <ident> 
546
547 <sdagentry> := "sdagentry" <ident> "(" <ident> "*" <ident> ")" <body> 
548
549 <body> := <stmt> 
550         | "\{" <stmt>+ "\}" 
551
552 <stmt> := <overlap-stmt> 
553         | <when-stmt> 
554         | <atomic-stmt> 
555         | <if-stmt> 
556         | <while-stmt> 
557         | <for-stmt> 
558         | <forall-stmt> 
559
560 <overlap-stmt> := "overlap" <body> 
561
562 <atomic-stmt> := "atomic" "\{" <\CC-code> "\}" 
563
564 <if-stmt> := "if" "(" <int-expr> ")" <body> [<else-stmt>] 
565
566 <else-stmt> := "else" <body> 
567
568 <while-stmt> := "while" "(" <int-expr> ")" <body> 
569
570 <for-stmt> := "for" "(" <c++-code> ";" <int-expr> ";" <c++-code> ")" <body> 
571
572 <forall-stmt> := "forall" "[" <ident> "]" "(" <range-stride> ")" <body> 
573
574 <range-stride> := <int-expr> ":" <int-expr> "," <int-expr> 
575
576 <when-stmt> := "when" <entry-list>  <body> 
577
578 <entry-list> := <entry> 
579               | <entry> [ "," <entry-list> ] 
580
581 <entry> := <ident> [ "[" <int-expr> "]" ] "(" <ident> "*" <ident> ")" 
582   
583 \end{alltt}
584 }
585
586 \zap{
587 \sdag\ is a coordination language built on top of \charmpp\ that supports the
588 sequencing mentioned above, while overcoming limitations of thread-based
589 languages, and facilitating a clear expression of flow of control within the
590 object without losing the performance benefits of adaptive message-driven
591 execution.  In other words, \sdag\ is a structured notation for specifying
592 intra-process control dependences in message-driven programs. It combines the
593 efficiency of message-driven execution with the explicitness of control
594 specification. \sdag\ allows easy expression of dependences among messages and
595 computations and also among computations within the same object using
596 when-blocks and various structured constructs.  \sdag\ is adequate for
597 expressing control-dependencies that form a series-parallel control-flow graph.
598 \sdag\ has been developed on top of \charmpp\. \sdag\ allows \charmpp\ entry
599 methods (in chares, groups or arrays) to specify code (a when-block body) to be
600 executed upon occurrence of certain events.  These events (or guards of a
601 when-block) are entry methods of the object that can be invoked remotely. While
602 writing a \sdag\ program, one has to declare these entries in \charmpp\
603 interface file. The implementation of the entry methods that contain the
604 when-block is written using the \sdag\ language. Grammar of \sdag\ is given in
605 the EBNF form below.
606
607 \subsubsection{Usage}
608
609 You can use SDAG to implement entry methods for any chare, chare array, group,
610 or nodegroup. Any entry method implemented using SDAG must be implemented in the
611 interface (.ci) file for its class. An SDAG entry method consists of a series of
612 SDAG constructs of the following kinds:
613
614 \begin{itemize}
615     \item {\tt forall} loops: 
616     \item {\tt if}, {\tt for}, and {\tt while} statements: these statements have
617         the same meaning as the normal {\tt if}, {\tt for}, and {\tt while}
618         loops in sequential \CC programs. This allows the programmer to use
619         common control flow constructs outside the context of atomic blocks.
620 \end{itemize}
621
622 \sdag{} code can be inserted into the .ci file for any array, group, or chare's entry methods.
623
624 For more details regarding \sdag{}, look at \examplerefdir{hello/sdag}
625 }
626