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