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