697ec30ccba3f6fae6f6ae92f1b42b6b6fc2b703
[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 \sdag{} code can be inserted into the .ci file for any array, group, or chare's entry methods.
176
177 If you've added \sdag\ code to your class, you must link in the code by:
178 \begin{itemize}
179   \item Adding ``{\it className}\_SDAG\_CODE'' inside the class declaration
180      in the .h file.  This macro defines the entry points and support
181      code used by \sdag{}.  Forgetting this results in a compile error
182      (undefined sdag entry methods referenced from the .def file).
183   \item Adding a call to the routine ``\_\_sdag\_init();'' from every constructor,
184      including the migration constructor.  Forgetting this results in
185      using uninitalized data, and a horrible runtime crash.
186   \item Adding a call to the pup routine ``\_\_sdag\_pup(p);'' from your pup routine.
187      Forgetting this results in failure after migration.
188 \end{itemize}
189
190 For example, an array named ``Foo'' that uses sdag code might contain:
191
192 \begin{alltt}
193 class Foo : public CBase_Foo \{
194 public:
195     Foo_SDAG_CODE
196     Foo(...) \{
197        __sdag_init();
198        ...
199     \}
200     Foo(CkMigrateMessage *m) \{
201        __sdag_init();
202     \}
203     
204     void pup(PUP::er &p) \{
205        __sdag_pup(p);
206     \}
207 \};
208 \end{alltt}
209
210 For more details regarding \sdag{}, look at the example located in the 
211 {\tt examples/charm++/hello/sdag} directory in the \charmpp\ distribution.
212
213
214 \subsection{Grammar}
215
216 \subsubsection{Tokens}
217
218 \begin{alltt}
219   <ident> = Valid \CC{} identifier 
220   <int-expr> = Valid \CC{} integer expression 
221   <\CC{}-code> = Valid \CC{} code 
222 \end{alltt}
223
224 \subsubsection{Grammar in EBNF Form}
225
226 \begin{alltt}
227 <sdag> := <class-decl> <sdagentry>+ 
228
229 <class-decl> := "class" <ident> 
230
231 <sdagentry> := "sdagentry" <ident> "(" <ident> "*" <ident> ")" <body> 
232
233 <body> := <stmt> 
234         | "\{" <stmt>+ "\}" 
235
236 <stmt> := <overlap-stmt> 
237         | <when-stmt> 
238         | <atomic-stmt> 
239         | <if-stmt> 
240         | <while-stmt> 
241         | <for-stmt> 
242         | <forall-stmt> 
243
244 <overlap-stmt> := "overlap" <body> 
245
246 <atomic-stmt> := "atomic" "\{" <\CC-code> "\}" 
247
248 <if-stmt> := "if" "(" <int-expr> ")" <body> [<else-stmt>] 
249
250 <else-stmt> := "else" <body> 
251
252 <while-stmt> := "while" "(" <int-expr> ")" <body> 
253
254 <for-stmt> := "for" "(" <c++-code> ";" <int-expr> ";" <c++-code> ")" <body> 
255
256 <forall-stmt> := "forall" "[" <ident> "]" "(" <range-stride> ")" <body> 
257
258 <range-stride> := <int-expr> ":" <int-expr> "," <int-expr> 
259
260 <when-stmt> := "when" <entry-list>  <body> 
261
262 <entry-list> := <entry> 
263               | <entry> [ "," <entry-list> ] 
264
265 <entry> := <ident> [ "[" <int-expr> "]" ] "(" <ident> "*" <ident> ")" 
266   
267 \end{alltt}
268