SDAG docs: rewrite initial text and example
[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.
75
76 Threads are typically used to perform the abovementioned sequencing.
77 Lets us code our previous example using threads.
78
79 %\begin{figure}[ht]
80 \begin{center}
81 \begin{alltt}
82 void compute_thread(int first_index, int second_index)
83 \{
84     getPatch(first_index);
85     getPatch(second_index);
86     threadId[0] = createThread(recvFirst);
87     threadId[1] = createThread(recvSecond);
88     threadJoin(2, threadId);
89     computeInteractions(first, second);
90   \}
91   void recvFirst(void)
92   \{
93     recv(first, sizeof(Patch), ANY_PE, FIRST_TAG);
94     filter(first);
95   \}
96   void recvSecond(void)
97   \{
98     recv(second, sizeof(Patch), ANY_PE, SECOND_TAG);
99     filter(second);
100   \}
101 \end{alltt}
102 \end{center}
103 %\caption{Compute Thread in a Molecular Dynamics Application}
104 %\label{figthreadexample}
105 %\end{figure}
106
107 Contrast the compute chare-object example in figure~\ref{figchareexample} with
108 a thread-based implementation of the same scheme in
109 figure~\ref{figthreadexample}. Functions \uw{getFirst}, and \uw{getSecond} send
110 messages asynchronously to the PatchManager, requesting that the specified
111 patches be sent to them, and return immediately. Since these messages with
112 patches could arrive in any order, two threads, \uw{recvFirst} and
113 \uw{recvSecond}, are created. These threads block, waiting for messages to
114 arrive. After each message arrives, each thread performs the filtering
115 operation. The main thread waits for these two threads to complete, and then
116 computes the pairwise interactions. Though the programming complexity of
117 buffering the messages and maintaining the counters has been eliminated in this
118 implementation, considerable overhead in the form of thread creation, and
119 synchronization in the form of {\em join} has been added. Let us now code the
120 same example in \sdag. It reduces the parallel programming complexity without
121 adding any significant overhead.
122
123 %\begin{figure}[ht]
124 \begin{center}
125 \begin{alltt}
126   array[1D] compute_object \{
127     entry void recv_first(Patch *first);
128     entry void recv_second(Patch *first);
129     entry void compute_object(MSG *msg)\{
130       atomic \{
131          PatchManager->Get(msg->first_index,\dots);
132          PatchManager->Get(msg->second_index,\dots);
133       \}
134       overlap \{
135         when recv_first(Patch *first) atomic \{ filter(first); \}
136         when recv_second(Patch *second) atomic \{ filter(second); \}
137       \}
138       atomic \{ computeInteractions(first, second); \}
139     \}
140   \}
141 \end{alltt}
142 \end{center}
143 %\caption{\sdag\ Implementation of the Compute Object}
144 %\label{figsdagexample}
145 %\end{figure}
146
147 \sdag\ is a coordination language built on top of \charmpp\ that supports the
148 sequencing mentioned above, while overcoming limitations of thread-based
149 languages, and facilitating a clear expression of flow of control within the
150 object without losing the performance benefits of adaptive message-driven
151 execution.  In other words, \sdag\ is a structured notation for specifying
152 intra-process control dependences in message-driven programs. It combines the
153 efficiency of message-driven execution with the explicitness of control
154 specification. \sdag\ allows easy expression of dependences among messages and
155 computations and also among computations within the same object using
156 when-blocks and various structured constructs.  \sdag\ is adequate for
157 expressing control-dependencies that form a series-parallel control-flow graph.
158 \sdag\ has been developed on top of \charmpp\. \sdag\ allows \charmpp\ entry
159 methods (in chares, groups or arrays) to specify code (a when-block body) to be
160 executed upon occurrence of certain events.  These events (or guards of a
161 when-block) are entry methods of the object that can be invoked remotely. While
162 writing a \sdag\ program, one has to declare these entries in \charmpp\
163 interface file. The implementation of the entry methods that contain the
164 when-block is written using the \sdag\ language. Grammar of \sdag\ is given in
165 the EBNF form below.
166
167 \subsubsection{Usage}
168
169 You can use SDAG to implement entry methods for any chare, chare array, group,
170 or nodegroup. Any entry method implemented using SDAG must be implemented in the
171 interface (.ci) file for its class. An SDAG entry method consists of a series of
172 SDAG constructs of the following kinds:
173
174 \begin{itemize}
175     \item {\tt atomic} blocks: Atomic blocks simply contain sequential \CC code.
176         They're called atomic because the code within them executes without
177         interruption from incoming messages. Typically atomic blocks hold the
178         code that actually deals with incoming messages in a {\tt when}
179         statement, or to do local operations before a message is sent or after
180         it's received.
181     \item {\tt overlap} blocks: Overlap blocks contain a series of SDAG
182         statements within them which can occur in any order. Commonly these
183         blocks are used to hold a series of {\tt when} triggers which can be
184         received and processed in any order. Flow of control doesn't leave the
185         overlap block until all the statements within it have been processed.
186     \item {\tt when} statements: These statement, also called triggers, indicate
187         that we expect an incoming message of a particular type, and provide
188         code to handle that message when it arrives. They commonly occur inside
189         of {\tt overlap} blocks, loops, and other control flow statements.
190     \item {\tt forall} loops: These loops are used when each iteration of a loop
191         can be performed in parallel. This is in contrast to a regular {\tt for}
192         loop, in which each iteration is executed sequentially.
193     \item {\tt if}, {\tt for}, and {\tt while} statements: these statements have
194         the same meaning as the normal {\tt if}, {\tt for}, and {\tt while}
195         loops in sequential \CC programs. This allows the programmer to use
196         common control flow constructs outside the context of atomic blocks.
197 \end{itemize}
198
199 \sdag{} code can be inserted into the .ci file for any array, group, or chare's entry methods.
200
201 If you've added \sdag\ code to your class, you must link in the code by:
202 \begin{itemize}
203   \item Adding ``{\it className}\_SDAG\_CODE'' inside the class declaration
204      in the .h file.  This macro defines the entry points and support
205      code used by \sdag{}.  Forgetting this results in a compile error
206      (undefined sdag entry methods referenced from the .def file).
207   \item Adding a call to the routine ``\_\_sdag\_init();'' from every constructor,
208      including the migration constructor.  Forgetting this results in
209      using uninitalized data, and a horrible runtime crash.
210   \item Adding a call to the pup routine ``\_\_sdag\_pup(p);'' from your pup routine.
211      Forgetting this results in failure after migration.
212 \end{itemize}
213
214 For example, an array named ``Foo'' that uses sdag code might contain:
215
216 \begin{alltt}
217 class Foo : public CBase_Foo \{
218 public:
219     Foo_SDAG_CODE
220     Foo(...) \{
221        __sdag_init();
222        ...
223     \}
224     Foo(CkMigrateMessage *m) \{
225        __sdag_init();
226     \}
227     
228     void pup(PUP::er &p) \{
229        CBase_Foo::pup(p);
230        __sdag_pup(p);
231     \}
232 \};
233 \end{alltt}
234
235 For more details regarding \sdag{}, look at the example located in the 
236 {\tt examples/charm++/hello/sdag} directory in the \charmpp\ distribution.
237
238
239 \subsubsection{Grammar}
240
241 \paragraph{Tokens}
242
243 \begin{alltt}
244   <ident> = Valid \CC{} identifier 
245   <int-expr> = Valid \CC{} integer expression 
246   <\CC{}-code> = Valid \CC{} code 
247 \end{alltt}
248
249 \paragraph{Grammar in EBNF Form}
250
251 \begin{alltt}
252 <sdag> := <class-decl> <sdagentry>+ 
253
254 <class-decl> := "class" <ident> 
255
256 <sdagentry> := "sdagentry" <ident> "(" <ident> "*" <ident> ")" <body> 
257
258 <body> := <stmt> 
259         | "\{" <stmt>+ "\}" 
260
261 <stmt> := <overlap-stmt> 
262         | <when-stmt> 
263         | <atomic-stmt> 
264         | <if-stmt> 
265         | <while-stmt> 
266         | <for-stmt> 
267         | <forall-stmt> 
268
269 <overlap-stmt> := "overlap" <body> 
270
271 <atomic-stmt> := "atomic" "\{" <\CC-code> "\}" 
272
273 <if-stmt> := "if" "(" <int-expr> ")" <body> [<else-stmt>] 
274
275 <else-stmt> := "else" <body> 
276
277 <while-stmt> := "while" "(" <int-expr> ")" <body> 
278
279 <for-stmt> := "for" "(" <c++-code> ";" <int-expr> ";" <c++-code> ")" <body> 
280
281 <forall-stmt> := "forall" "[" <ident> "]" "(" <range-stride> ")" <body> 
282
283 <range-stride> := <int-expr> ":" <int-expr> "," <int-expr> 
284
285 <when-stmt> := "when" <entry-list>  <body> 
286
287 <entry-list> := <entry> 
288               | <entry> [ "," <entry-list> ] 
289
290 <entry> := <ident> [ "[" <int-expr> "]" ] "(" <ident> "*" <ident> ")" 
291   
292 \end{alltt}
293