docs: Add some explanation of SDAG constructs
[charm.git] / doc / charm++ / sdag.tex
1 \section{Structured Dagger}
2 \label{sec:sdag}
3
4 \charmpp\ is based on the Message-Driven parallel programming paradigm.  The
5 message-driven programming style avoids the use of blocking receives and
6 allows overlap of computation and communication by scheduling computations
7 depending on availability of data.  This programing style enables \charmpp\
8 programs to tolerate communication latencies adaptively. Threads suffer from
9 loss of performance due to context-switching overheads and limited scalability
10 due to large and unpredictable stack memory requirements, when used in a
11 data-driven manner to coordinate a sequence of remotely triggered actions.
12
13 The need to sequence remotely triggered actions
14 arises in many situations. Let us consider an example:
15
16 %\begin{figure}[ht]
17 \begin{center}
18 \begin{alltt}
19       class compute_object : public Chare \{
20       private:
21       int         count;
22       Patch       *first, *second;
23       public:
24       compute_object(MSG *msg) \{
25       count = 2; MyChareID(\&chareid);
26       PatchManager->Get(msg->first_index, recv_first, \&thishandle,NOWAIT);
27       PatchManager->Get(msg->second_index, recv_second, \&thishandle,NOWAIT);
28       \}
29       void recv_first(PATCH_MSG *msg) \{
30        first = msg->patch;
31        filter(first);
32        if (--count == 0 ) computeInteractions(first,second);
33       \} 
34       void recv_second(PATCH_MSG *msg)\{
35        second = msg->patch;
36        filter(second);
37        if (--count == 0) computeInteractions(first,second);
38       \}
39      \}
40 \end{alltt}
41 \end{center}
42 %\caption{Compute Object in a Molecular Dynamics Application}
43 %\label{figchareexample}
44 %\end{figure}
45
46
47 Consider an algorithm for computing cutoff-based pairwise interactions
48 between atoms in a molecular dynamics application, where interaction
49 between atoms is considered only when they are within some cutoff
50 distance of each other.  This algorithm is based on a combination of
51 task and spatial decompositions of the molecular system. The bounding
52 box for the molecule is divided into a number of cubes ({\em Patches})
53 each containing some number of atoms.  Since each patch contains a
54 different number of atoms and these atoms migrate between patches as
55 simulation progresses, a dynamic load balancing scheme is used. In
56 this scheme, the task of computing the pairwise interactions between
57 atoms of all pairs of patches is divided among a number of {\em
58 Compute Objects}. These compute objects are assigned at runtime to
59 different processors. The initialization message for each compute
60 object contains the indices of the patches. The patches themselves are
61 distributed across processors. Mapping information of patches to
62 processors is maintained by a replicated object called {\em
63 PatchManager}.  Figure~\ref{figchareexample} illustrates the \charmpp\
64 implementation of the compute object. Each compute object requests
65 information about both patches assigned to it from the
66 PatchManager. PatchManager then contacts the appropriate processors
67 and delivers the patch information to the requesting compute
68 object. The compute object, after receiving information about each
69 patch, determines which atoms in a patch do not interact with atoms in
70 another patch since they are separated by more than the cut-off
71 distance. This is done in method {\tt filter}.  Filtering could be
72 done after both patches arrive. However, in order to increase
73 processor utilization, we do it immediately after any patch
74 arrives. Since the patches can arrive at the requesting compute object
75 in any order, the compute object has to buffer the received patches,
76 and maintain state information using counters or flags.  This example
77 has been chosen for simplicity in order to demonstrate the necessity
78 of counters and buffers.  In general, a parallel algorithm may have
79 more interactions leading to the use of many counters, flags, and
80 message buffers, which complicates program development significantly.
81
82 Threads are typically used to perform the abovementioned sequencing.
83 Lets us code our previous example using threads.
84
85 %\begin{figure}[ht]
86 \begin{center}
87 \begin{alltt}
88 void compute_thread(int first_index, int second_index)
89 \{
90     getPatch(first_index);
91     getPatch(second_index);
92     threadId[0] = createThread(recvFirst);
93     threadId[1] = createThread(recvSecond);
94     threadJoin(2, threadId);
95     computeInteractions(first, second);
96   \}
97   void recvFirst(void)
98   \{
99     recv(first, sizeof(Patch), ANY_PE, FIRST_TAG);
100     filter(first);
101   \}
102   void recvSecond(void)
103   \{
104     recv(second, sizeof(Patch), ANY_PE, SECOND_TAG);
105     filter(second);
106   \}
107 \end{alltt}
108 \end{center}
109 %\caption{Compute Thread in a Molecular Dynamics Application}
110 %\label{figthreadexample}
111 %\end{figure}
112
113 Contrast the compute chare-object example in figure~\ref{figchareexample} with
114 a thread-based implementation of the same scheme in
115 figure~\ref{figthreadexample}. Functions \uw{getFirst}, and \uw{getSecond} send
116 messages asynchronously to the PatchManager, requesting that the specified
117 patches be sent to them, and return immediately. Since these messages with
118 patches could arrive in any order, two threads, \uw{recvFirst} and
119 \uw{recvSecond}, are created. These threads block, waiting for messages to
120 arrive. After each message arrives, each thread performs the filtering
121 operation. The main thread waits for these two threads to complete, and then
122 computes the pairwise interactions. Though the programming complexity of
123 buffering the messages and maintaining the counters has been eliminated in this
124 implementation, considerable overhead in the form of thread creation, and
125 synchronization in the form of {\em join} has been added. Let us now code the
126 same example in \sdag. It reduces the parallel programming complexity without
127 adding any significant overhead.
128
129 %\begin{figure}[ht]
130 \begin{center}
131 \begin{alltt}
132   array[1D] compute_object \{
133     entry void recv_first(Patch *first);
134     entry void recv_second(Patch *first);
135     entry void compute_object(MSG *msg)\{
136       atomic \{
137          PatchManager->Get(msg->first_index,\dots);
138          PatchManager->Get(msg->second_index,\dots);
139       \}
140       overlap \{
141         when recv_first(Patch *first) atomic \{ filter(first); \}
142         when recv_second(Patch *second) atomic \{ filter(second); \}
143       \}
144       atomic \{ computeInteractions(first, second); \}
145     \}
146   \}
147 \end{alltt}
148 \end{center}
149 %\caption{\sdag\ Implementation of the Compute Object}
150 %\label{figsdagexample}
151 %\end{figure}
152
153 \sdag\ is a coordination language built on top of \charmpp\ that supports the
154 sequencing mentioned above, while overcoming limitations of thread-based
155 languages, and facilitating a clear expression of flow of control within the
156 object without losing the performance benefits of adaptive message-driven
157 execution.  In other words, \sdag\ is a structured notation for specifying
158 intra-process control dependences in message-driven programs. It combines the
159 efficiency of message-driven execution with the explicitness of control
160 specification. \sdag\ allows easy expression of dependences among messages and
161 computations and also among computations within the same object using
162 when-blocks and various structured constructs.  \sdag\ is adequate for
163 expressing control-dependencies that form a series-parallel control-flow graph.
164 \sdag\ has been developed on top of \charmpp\. \sdag\ allows \charmpp\ entry
165 methods (in chares, groups or arrays) to specify code (a when-block body) to be
166 executed upon occurrence of certain events.  These events (or guards of a
167 when-block) are entry methods of the object that can be invoked remotely. While
168 writing a \sdag\ program, one has to declare these entries in \charmpp\
169 interface file. The implementation of the entry methods that contain the
170 when-block is written using the \sdag\ language. Grammar of \sdag\ is given in
171 the EBNF form below.
172
173 \subsection{Usage}
174
175 You can use SDAG to implement entry methods for any chare, chare array, group,
176 or nodegroup. Any entry method implemented using SDAG must be implemented in the
177 interface (.ci) file for its class. An SDAG entry method consists of a series of
178 SDAG constructs of the following kinds:
179
180 \begin{itemize}
181     \item {\tt atomic} blocks: Atomic blocks simply contain sequential \CC code.
182         They're called atomic because the code within them executes without
183         interruption from incoming messages. Typically atomic blocks hold the
184         code that actually deals with incoming messages in a {\tt when}
185         statement, or to do local operations before a message is sent or after
186         it's received.
187     \item {\tt overlap} blocks: Overlap blocks contain a series of SDAG
188         statements within them which can occur in any order. Commonly these
189         blocks are used to hold a series of {\tt when} triggers which can be
190         received and processed in any order. Flow of control doesn't leave the
191         overlap block until all the statements within it have been processed.
192     \item {\tt when} statements: These statement, also called triggers, indicate
193         that we expect an incoming message of a particular type, and provide
194         code to handle that message when it arrives. They commonly occur inside
195         of {\tt overlap} blocks, loops, and other control flow statements.
196     \item {\tt forall} loops: These loops are used when each iteration of a loop
197         can be performed in parallel. This is in contrast to a regular {\tt for}
198         loop, in which each iteration is executed sequentially.
199     \item {\tt if}, {\tt for}, and {\tt while} statements: these statements have
200         the same meaning as the normal {\tt if}, {\tt for}, and {\tt while}
201         loops in sequential \CC programs. This allows the programmer to use
202         common control flow constructs outside the context of atomic blocks.
203 \end{itemize}
204
205 \sdag{} code can be inserted into the .ci file for any array, group, or chare's entry methods.
206
207 If you've added \sdag\ code to your class, you must link in the code by:
208 \begin{itemize}
209   \item Adding ``{\it className}\_SDAG\_CODE'' inside the class declaration
210      in the .h file.  This macro defines the entry points and support
211      code used by \sdag{}.  Forgetting this results in a compile error
212      (undefined sdag entry methods referenced from the .def file).
213   \item Adding a call to the routine ``\_\_sdag\_init();'' from every constructor,
214      including the migration constructor.  Forgetting this results in
215      using uninitalized data, and a horrible runtime crash.
216   \item Adding a call to the pup routine ``\_\_sdag\_pup(p);'' from your pup routine.
217      Forgetting this results in failure after migration.
218 \end{itemize}
219
220 For example, an array named ``Foo'' that uses sdag code might contain:
221
222 \begin{alltt}
223 class Foo : public CBase_Foo \{
224 public:
225     Foo_SDAG_CODE
226     Foo(...) \{
227        __sdag_init();
228        ...
229     \}
230     Foo(CkMigrateMessage *m) \{
231        __sdag_init();
232     \}
233     
234     void pup(PUP::er &p) \{
235        CBase_Foo::pup(p);
236        __sdag_pup(p);
237     \}
238 \};
239 \end{alltt}
240
241 For more details regarding \sdag{}, look at the example located in the 
242 {\tt examples/charm++/hello/sdag} directory in the \charmpp\ distribution.
243
244
245 \subsection{Grammar}
246
247 \subsubsection{Tokens}
248
249 \begin{alltt}
250   <ident> = Valid \CC{} identifier 
251   <int-expr> = Valid \CC{} integer expression 
252   <\CC{}-code> = Valid \CC{} code 
253 \end{alltt}
254
255 \subsubsection{Grammar in EBNF Form}
256
257 \begin{alltt}
258 <sdag> := <class-decl> <sdagentry>+ 
259
260 <class-decl> := "class" <ident> 
261
262 <sdagentry> := "sdagentry" <ident> "(" <ident> "*" <ident> ")" <body> 
263
264 <body> := <stmt> 
265         | "\{" <stmt>+ "\}" 
266
267 <stmt> := <overlap-stmt> 
268         | <when-stmt> 
269         | <atomic-stmt> 
270         | <if-stmt> 
271         | <while-stmt> 
272         | <for-stmt> 
273         | <forall-stmt> 
274
275 <overlap-stmt> := "overlap" <body> 
276
277 <atomic-stmt> := "atomic" "\{" <\CC-code> "\}" 
278
279 <if-stmt> := "if" "(" <int-expr> ")" <body> [<else-stmt>] 
280
281 <else-stmt> := "else" <body> 
282
283 <while-stmt> := "while" "(" <int-expr> ")" <body> 
284
285 <for-stmt> := "for" "(" <c++-code> ";" <int-expr> ";" <c++-code> ")" <body> 
286
287 <forall-stmt> := "forall" "[" <ident> "]" "(" <range-stride> ")" <body> 
288
289 <range-stride> := <int-expr> ":" <int-expr> "," <int-expr> 
290
291 <when-stmt> := "when" <entry-list>  <body> 
292
293 <entry-list> := <entry> 
294               | <entry> [ "," <entry-list> ] 
295
296 <entry> := <ident> [ "[" <int-expr> "]" ] "(" <ident> "*" <ident> ")" 
297   
298 \end{alltt}
299