Add a flag to provide timer for the case of no objs in Meta-Balancer
[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     startStep();
114   \}
115   void startStep() \{
116     expectedMessageCount = 2;
117   \}
118
119   void computeInteractions(Input a, Input b) \{
120     // do computations using a and b
121     . . .
122     // send off results
123     . . .
124     // reset for next step
125     startStep();
126   \}
127 \};
128 \end{alltt}
129 \end{center}
130 Note that chare classes containing SDAG code must include a few additional declarations
131 in addition to inheriting from their {\tt CBase\_Foo} class, by incorporating the
132 {\tt Foo\_SDAG\_CODE} generated-code macro in the class.
133
134 Atomic blocks can also specify a textual `label' that will appear in traces, as
135 follows:
136 \begin{center}
137 \begin{alltt}
138   entry void firstInput(Input i) \{
139     atomic "process first" \{
140       first = i;
141       if (--expectedMessageCount == 0)
142         computeInteractions(first, second);
143     \}
144   \};
145 \end{alltt}
146 \end{center}
147
148 In order to control the sequence in which entry methods are processed, SDAG
149 provides the {\tt when} construct. These statements, also called triggers,
150 indicate that we expect an incoming message of a particular type, and provide
151 code to handle that message when it arrives. From the perspective of a chare
152 object reaching a {\tt when} statement, it is effectively a `blocking
153 receive.'
154
155 Entry methods defined by a {\tt when} are
156 not executed immediately when a message targeting them is delivered, but
157 instead are held until control flow in the chare reaches a corresponding {\tt
158   when} clause. Conversely, when control flow reaches a {\tt when} clause, the
159 generated code checks whether a corresponding message has arrived: if one has
160 arrived, it is processed; otherwise, control is returned to the
161 \charmpp\ scheduler. 
162
163 The use of {\tt when} substantially simplifies the example from above:
164 \begin{center}
165 \begin{alltt}
166 // in .ci file
167 chare ComputeObject \{
168   entry void ComputeObject();
169   entry void startStep() \{
170     when firstInput(Input first)
171       when secondInput(Input second)
172         atomic \{
173           computeInteractions(first, second);
174         \}
175   \};
176   entry void firstInput(Input i);
177   entry void secondInput(Input j);
178 \};
179
180 // in C++ file
181 class ComputeObject : public CBase_ComputeObject \{
182   ComputeObject_SDAG_Code
183
184 public:
185   ComputeObject() \{
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 A single entry method is allowed to appear in more than one {\tt when} statement.
227 If only one of those {\tt when} statements has been triggered when the runtime
228 delivers a message to that entry method, that {\tt when} statement is guaranteed
229 to process it. If there is no trigger waiting for that entry method, then the
230 next corresponding {\tt when} to be reached will receive that message. If there is
231 more than one {\tt when} waiting on that method, which one will receive it is not
232 specified, and should not be relied upon. For an example of multiple {\tt when}
233 statements handling the same entry method without reaching the unspecified case,
234 see the CharmLU benchmark.
235
236 To more finely control the correspondence between incoming messages and {\tt when}
237 clauses associated with the target entry method, SDAG supports \emph{matching} on
238 reference numbers. Matching is typically used to denote an iteration of a program
239 that executes asynchronously (without any sort of barrier or other synchronization
240 between steps) or a particular piece of the problem being solved.
241 Matching is requested by placing an expression denoting the desired reference
242 number in square brackets between the entry method name and its parameter list.
243 That expression will be compared for equality with the entry method's first
244 argument, or with the reference number field of an explicit message
245 (\S~\ref{messages}). Matching is used in the loop example below, and in
246 \examplereffile{jacobi2d-sdag/jacobi2d.ci}. Multiple {\tt when} triggers for
247 an entry method with different matching reference numbers will not conflict - each
248 will receive only corresponding messages.
249
250 SDAG supports the {\tt for} and {\tt while} loop constructs mostly as if they
251 appeared in plain C or C++ code. In the running example, {\tt
252   computeInteractions()} calls {\tt startStep()} when it is finished to start
253 the next step. Instead of this arrangement, the loop structure can be made
254 explicit:
255 \begin{center}
256 \begin{alltt}
257 // in .ci file
258 chare ComputeObject \{
259   entry void ComputeObject();
260   entry void runForever() \{
261     while(true) \{
262       when firstInput(Input first),
263            secondInput(Input second) atomic \{
264           computeInteractions(first, second);
265       \}
266     \}
267   \};
268   entry void firstInput(Input i);
269   entry void secondInput(Input j);
270 \};
271
272 // in C++ file
273 class ComputeObject : public CBase_ComputeObject \{
274   ComputeObject_SDAG_Code
275
276 public:
277   ComputeObject() \{
278     runForever();
279   \}
280
281   void computeInteractions(Input a, Input b) \{
282     // do computations using a and b
283     . . .
284     // send off results
285     . . .
286   \}
287 \};
288 \end{alltt}
289 \end{center}
290 If this code should instead run for a fixed number of iterations, we can
291 instead use a for loop:
292 \begin{center}
293 \begin{alltt}
294 // in .ci file
295 chare ComputeObject \{
296   entry void ComputeObject();
297   entry void runForever() \{
298     for(iter = 0; iter < n; ++iter) \{
299       // Match to only accept inputs for the current iteration
300       when firstInput[iter](int a, Input first),
301            secondInput[iter](int b, Input second) atomic \{
302         computeInteractions(first, second);
303       \}
304     \}
305   \};
306   entry void firstInput(int a, Input i);
307   entry void secondInput(int b, Input j);
308 \};
309
310 // in C++ file
311 class ComputeObject : public CBase_ComputeObject \{
312   ComputeObject_SDAG_Code
313   int n, iter;
314
315 public:
316   ComputeObject() \{
317     n = 10;
318     runForever();
319   \}
320
321   void computeInteractions(Input a, Input b) \{
322     // do computations using a and b
323     . . .
324     // send off results
325     . . .
326   \}
327 \};
328 \end{alltt}
329 \end{center}
330 Note that {\tt int iter;} is declared in the chare's class definition and not
331 in the {\tt .ci} file. This is necessary because the \charmpp\ interface
332 translator does not fully parse the declarations in the {\tt for} loop header,
333 because of the inherent complexities of C++.
334
335 SDAG also supports conditional execution of statements and blocks with {\tt if}
336 statements. The syntax of SDAG {\tt if} statements matches that of C and
337 C++. However, if one encounters a syntax error on correct-looking code in a
338 loop or conditional statement, try assigning the condition expression to a
339 boolean variable in an atomic preceding the statement and then testing that
340 boolean's value. This can be necessary because of the complexity of parsing C++
341 code.
342
343 In cases where multiple tasks must be processed before execution continues, but
344 with no dependencies or interactions among them, SDAG provides the {\tt
345   overlap} construct. Overlap blocks contain a series of SDAG statements within
346 them which can occur in any order. Commonly these blocks are used to hold a
347 series of {\tt when} triggers which can be received and processed in any
348 order. Flow of control doesn't leave the overlap block until all the statements
349 within it have been processed.
350
351 In the running example, suppose each input needs to be preprocessed independently
352 before the call to {\tt computeInteractions}. Since we don't care which order
353 they get processed in, and want it to happen as soon as possible, we can apply
354 {\tt overlap}:
355 \begin{center}
356 \begin{alltt}
357 // in .ci file
358 chare ComputeObject \{
359   entry void ComputeObject();
360   entry void startStep() \{
361     overlap \{
362       when firstInput(Input i)
363         atomic \{ first = preprocess(i); \}
364       when secondInput(Input j)
365         atomic \{ second = preprocess(j); \}
366      \}
367      atomic \{
368        computeInteractions(first, second);
369      \}
370   \};
371   entry void firstInput(Input i);
372   entry void secondInput(Input j);
373 \};
374
375 // in C++ file
376 class ComputeObject : public CBase_ComputeObject \{
377   ComputeObject_SDAG_Code
378
379 public:
380   ComputeObject() \{
381     startStep();
382   \}
383
384   void computeInteractions(Input a, Input b) \{
385     // do computations using a and b
386     . . .
387     // send off results
388     . . .
389     // reset for next step
390     startStep();
391   \}
392 \};
393 \end{alltt}
394 \end{center}
395
396 The final construct offered by SDAG is the {\tt forall} loop. These loops are
397 used when the iterations of a loop can be performed independently and in any
398 order. This is in contrast to a regular {\tt for} loop, in which each iteration
399 is executed sequentially. The {\tt forall} loop can be seen as an overlap with
400 an indexed set of otherwise identical statements in the body. Its syntax is 
401 \begin{center}
402 \begin{alltt}
403 forall [IDENT] (MIN:MAX,STRIDE) BODY
404 \end{alltt}
405 \end{center}
406 The range from MIN to MAX is inclusive. Its use is demonstrated through
407 distributed parallel matrix-matrix multiply shown in
408 \examplereffile{matmul/matmul.ci}
409
410 \section{Usage Notes}
411
412 If you've added \sdag\ code to your class, you must link in the code by:
413 \begin{itemize}
414   \item Adding ``{\it className}\_SDAG\_CODE'' inside the class declaration
415      in the .h file.  This macro defines the entry points and support
416      code used by \sdag{}.  Forgetting this results in a compile error
417      (undefined sdag entry methods referenced from the .def.h file).
418   \item Adding a call to the pup routine ``\_\_sdag\_pup(p);'' from your pup routine.
419      Forgetting this results in failure after migration.
420 \end{itemize}
421 For example, an array named ``Foo'' that uses sdag code might contain:
422 \begin{center}
423 \begin{alltt}
424 class Foo : public CBase_Foo \{
425 public:
426     Foo_SDAG_CODE
427     Foo(...) \{
428        ...
429     \}
430     Foo(CkMigrateMessage *m) \{ \}
431     
432     void pup(PUP::er &p) \{
433        CBase_Foo::pup(p);
434        __sdag_pup(p);
435     \}
436     . . .
437 \};
438 \end{alltt}
439 \end{center}
440
441 \zap{
442 \section{Relationship to Threads}
443
444 Threads are typically used to perform the abovementioned sequencing.
445 Lets us code our previous example using threads.
446
447 %\begin{figure}[ht]
448 \begin{center}
449 \begin{alltt}
450 void compute_thread(int first_index, int second_index)
451 \{
452     getPatch(first_index);
453     getPatch(second_index);
454     threadId[0] = createThread(recvFirst);
455     threadId[1] = createThread(recvSecond);
456     threadJoin(2, threadId);
457     computeInteractions(first, second);
458   \}
459   void recvFirst(void)
460   \{
461     recv(first, sizeof(Patch), ANY_PE, FIRST_TAG);
462     filter(first);
463   \}
464   void recvSecond(void)
465   \{
466     recv(second, sizeof(Patch), ANY_PE, SECOND_TAG);
467     filter(second);
468   \}
469 \end{alltt}
470 \end{center}
471 %\caption{Compute Thread in a Molecular Dynamics Application}
472 %\label{figthreadexample}
473 %\end{figure}
474
475 Contrast the compute chare-object example in figure~\ref{figchareexample} with
476 a thread-based implementation of the same scheme in
477 figure~\ref{figthreadexample}. Functions \uw{getFirst}, and \uw{getSecond} send
478 messages asynchronously to the PatchManager, requesting that the specified
479 patches be sent to them, and return immediately. Since these messages with
480 patches could arrive in any order, two threads, \uw{recvFirst} and
481 \uw{recvSecond}, are created. These threads block, waiting for messages to
482 arrive. After each message arrives, each thread performs the filtering
483 operation. The main thread waits for these two threads to complete, and then
484 computes the pairwise interactions. Though the programming complexity of
485 buffering the messages and maintaining the counters has been eliminated in this
486 implementation, considerable overhead in the form of thread creation, and
487 synchronization in the form of {\em join} has been added. Let us now code the
488 same example in \sdag. It reduces the parallel programming complexity without
489 adding any significant overhead.
490
491 %\begin{figure}[ht]
492 \begin{center}
493 \begin{alltt}
494   array[1D] compute_object \{
495     entry void recv_first(Patch *first);
496     entry void recv_second(Patch *first);
497     entry void compute_object(MSG *msg)\{
498       atomic \{
499          PatchManager->Get(msg->first_index,\dots);
500          PatchManager->Get(msg->second_index,\dots);
501       \}
502       overlap \{
503         when recv_first(Patch *first) atomic \{ filter(first); \}
504         when recv_second(Patch *second) atomic \{ filter(second); \}
505       \}
506       atomic \{ computeInteractions(first, second); \}
507     \}
508   \}
509 \end{alltt}
510 \end{center}
511 %\caption{\sdag\ Implementation of the Compute Object}
512 %\label{figsdagexample}
513 %\end{figure}
514 }
515
516
517 \zap{
518 \section{Grammar}
519
520 \paragraph{Tokens}
521
522 \begin{alltt}
523   <ident> = Valid \CC{} identifier 
524   <int-expr> = Valid \CC{} integer expression 
525   <\CC{}-code> = Valid \CC{} code 
526 \end{alltt}
527
528 \paragraph{Grammar in EBNF Form}
529
530 \begin{alltt}
531 <sdag> := <class-decl> <sdagentry>+ 
532
533 <class-decl> := "class" <ident> 
534
535 <sdagentry> := "sdagentry" <ident> "(" <ident> "*" <ident> ")" <body> 
536
537 <body> := <stmt> 
538         | "\{" <stmt>+ "\}" 
539
540 <stmt> := <overlap-stmt> 
541         | <when-stmt> 
542         | <atomic-stmt> 
543         | <if-stmt> 
544         | <while-stmt> 
545         | <for-stmt> 
546         | <forall-stmt> 
547
548 <overlap-stmt> := "overlap" <body> 
549
550 <atomic-stmt> := "atomic" "\{" <\CC-code> "\}" 
551
552 <if-stmt> := "if" "(" <int-expr> ")" <body> [<else-stmt>] 
553
554 <else-stmt> := "else" <body> 
555
556 <while-stmt> := "while" "(" <int-expr> ")" <body> 
557
558 <for-stmt> := "for" "(" <c++-code> ";" <int-expr> ";" <c++-code> ")" <body> 
559
560 <forall-stmt> := "forall" "[" <ident> "]" "(" <range-stride> ")" <body> 
561
562 <range-stride> := <int-expr> ":" <int-expr> "," <int-expr> 
563
564 <when-stmt> := "when" <entry-list>  <body> 
565
566 <entry-list> := <entry> 
567               | <entry> [ "," <entry-list> ] 
568
569 <entry> := <ident> [ "[" <int-expr> "]" ] "(" <ident> "*" <ident> ")" 
570   
571 \end{alltt}
572 }
573
574 \zap{
575 \sdag\ is a coordination language built on top of \charmpp\ that supports the
576 sequencing mentioned above, while overcoming limitations of thread-based
577 languages, and facilitating a clear expression of flow of control within the
578 object without losing the performance benefits of adaptive message-driven
579 execution.  In other words, \sdag\ is a structured notation for specifying
580 intra-process control dependences in message-driven programs. It combines the
581 efficiency of message-driven execution with the explicitness of control
582 specification. \sdag\ allows easy expression of dependences among messages and
583 computations and also among computations within the same object using
584 when-blocks and various structured constructs.  \sdag\ is adequate for
585 expressing control-dependencies that form a series-parallel control-flow graph.
586 \sdag\ has been developed on top of \charmpp\. \sdag\ allows \charmpp\ entry
587 methods (in chares, groups or arrays) to specify code (a when-block body) to be
588 executed upon occurrence of certain events.  These events (or guards of a
589 when-block) are entry methods of the object that can be invoked remotely. While
590 writing a \sdag\ program, one has to declare these entries in \charmpp\
591 interface file. The implementation of the entry methods that contain the
592 when-block is written using the \sdag\ language. Grammar of \sdag\ is given in
593 the EBNF form below.
594
595 \subsubsection{Usage}
596
597 You can use SDAG to implement entry methods for any chare, chare array, group,
598 or nodegroup. Any entry method implemented using SDAG must be implemented in the
599 interface (.ci) file for its class. An SDAG entry method consists of a series of
600 SDAG constructs of the following kinds:
601
602 \begin{itemize}
603     \item {\tt forall} loops: 
604     \item {\tt if}, {\tt for}, and {\tt while} statements: these statements have
605         the same meaning as the normal {\tt if}, {\tt for}, and {\tt while}
606         loops in sequential \CC programs. This allows the programmer to use
607         common control flow constructs outside the context of atomic blocks.
608 \end{itemize}
609
610 \sdag{} code can be inserted into the .ci file for any array, group, or chare's entry methods.
611
612 For more details regarding \sdag{}, look at \examplerefdir{hello/sdag}
613 }
614