bug fix: handle failure detected during checkpoint
[charm.git] / doc / charisma / orchcode.tex
1
2 The orchestration code in the .or file can be divided into two part. The header
3 part contains information about the program, included external files, defines,
4 and declaration of parallel constructs used in the code. The orchestration
5 section is made up of statements that forms a global control flow of the
6 parallel program. In the orchestration code, Charisma employs a macro dataflow
7 approach; the statements produce and consume values, from which the control flows
8 can be organized, and messages and method invocations generated. 
9
10 \subsubsection{Header Section}
11
12 The very first line should give the name of the Charisma program with the {\tt
13 program} keyword.
14
15 \begin{SaveVerbatim}{foodecl}
16     program jacobi 
17 \end{SaveVerbatim}
18 \smallfbox{\BUseVerbatim{foodecl}}
19
20 The {\tt program} keyword can be replaced with {\tt module}, which means that
21 the output program is going to be a library module instead of a stand-alone
22 program. Please refer to Section~\ref{sec:module} for more details.
23
24 Next, the programmer can include external code files in the generated code with
25 keyword {\tt include} with the filename without extension. For example, the
26 following statement tells the Charisma compiler to look for header file
27 ``particles.h'' to be included in the generated header file ``jacobi.h'' and to
28 look for C/C++ code file ``particles.[C|cc|cpp|cxx|c]'' to be included in the
29 generated C++ code file ``jacobi.C''.
30
31 \begin{SaveVerbatim}{foodecl}
32     include particles;
33 \end{SaveVerbatim}
34 \smallfbox{\BUseVerbatim{foodecl}}
35
36 It is useful when there are source code that must precede the generated
37 parallel code, such as basic data structure declaration. 
38
39 After the {\tt include} section is the {\tt define} section, where environmental
40 variables can be defined for Charisma. For example, to tell Charisma to generate
41 additional code to enable the load balancing module, the programmer needs to 
42 define ``ldb'' in the orchestration code. Please refer to Section~\ref{sec:ldb}
43 for details.
44
45 \subsubsection{Declaration Section}
46
47 Next comes the declaration section, where classes, objects and parameters are
48 declared. A Charisma program is composed of multiple sets of parallel objects
49 which are organized by the orchestration code. Different sets of objects can be
50 instantiated from different class types. Therefore, we have to specify the class
51 types and object instantiation. Also we need to specify the parameters (See
52 Section~\ref{sec:orchsec}) to use in the orchestration statements. 
53
54 A Charisma program or module has one ``MainChare'' class, and it does not
55 require explicit instantiation since it is a singleton. The statement to declare
56 MainChare looks like this:
57
58 \begin{SaveVerbatim}{foodecl}
59     class JacobiMain : MainChare;
60 \end{SaveVerbatim}
61 \smallfbox{\BUseVerbatim{foodecl}}
62
63 For object arrays, we first need to declare the class types inherited from 1D
64 object array, 2D object array, etc, and then instantiate from the class types. 
65 The dimensionality information of the object array is given in a pair of 
66 brackets with each dimension size separated by a comma.
67
68 \begin{SaveVerbatim}{foodecl}
69     class JacobiWorker : ChareArray1D;
70     obj workers : JacobiWorker[N];
71
72     class Cell : ChareArray3D;
73     obj cells : Cell[M,M,M];
74 \end{SaveVerbatim}
75 \smallfbox{\BUseVerbatim{foodecl}}
76
77 Note that key word ``class'' is for class type derivation, and ``obj'' is for
78 parallel object or object array instantiation. The above code segment declares a
79 new class type JacobiWorker which is a 1D object array, (and the programmer is
80 supposed to supply sequential code for it in files ``JacobiWorker.h'' and
81 ``JacobiWorker.C'' (See Section~\ref{sec:sequential} for more details on
82 sequential code). Object array ``workers'' is instantiated from ``JacobiWorker''
83 and has 16 elements.
84
85 The last part is orchestration parameter declaration. These parameters are used
86 only in the orchestration code to connect input and output of orchestration
87 statements, and their data type and size is declared here. More explanation of
88 these parameters can be found in Section~\ref{sec:orchsec}. 
89
90 \begin{SaveVerbatim}{foodecl}
91     param lb : double[N];
92     param rb : double[N];
93 \end{SaveVerbatim}
94 \smallfbox{\BUseVerbatim{foodecl}}
95
96 With this, ``lb'' and ``rb'' are declared as parameters of that can be 
97 ``connected'' with local variables of double array with size of 512. 
98
99 \subsubsection{Orchestration Section}
100 \label{sec:orchsec}
101
102 In the main body of orchestration code, the programmer describes the behavior
103 and interaction of the elements of the object arrays using orchestration
104 statements.
105
106 $\bullet$ {\bf Foreach Statement}
107
108 The most common kind of parallelism is the invocation of a method
109 across all elements in an object array. Charisma provides a {\em foreach}
110 statement for specifying such parallelism. The keywords \code{foreach} and
111 \code{end-foreach} forms an enclosure within which the parallel invocation is
112 performed. The following code segment invokes the entry method \code{compute} on
113 all the elements of array \code{myWorkers}. 
114
115 \begin{SaveVerbatim}{foodecl}
116   foreach i in workers
117     workers[i].compute();
118   end-foreach
119 \end{SaveVerbatim}
120 \smallfbox{\BUseVerbatim{foodecl}}
121
122 $\bullet$ {\bf Publish Statement and Produced/Consumed Parameters}
123
124 In the orchestration code, an object method invocation can have input and output
125 (consumed and produced) parameters. Here is an orchestration statement that
126 exemplifies the input and output of this object methods
127 \code{workers.produceBorders} and \code{workers.compute}. 
128
129 \begin{SaveVerbatim}{foodecl}
130   foreach i in workers
131     (lb[i], rb[i]) <- workers[i].produceBorders();
132     workers[i].compute(lb[i+1], rb[i-1]);
133     
134     (+error) <- workers[i].reduceData();
135   end-foreach
136 \end{SaveVerbatim}
137 \smallfbox{\BUseVerbatim{foodecl}}
138
139 Here, the entry method \code{workers[i].produceBorders} produces (called {\em
140 published} in Charisma) values of \code{lb[i], rb[i]}, enclosed in a pair of
141 parentheses before the publishing sign ``\code{<-}''. In the second
142 statement, function \code{workers[i].compute} consumes values of \code{lb[i+1],
143 rb[i-1]}, just like normal function parameters. If a reduction operation is
144 needed, the reduced parameter is marked with a ``\code{+}'' before it, like the
145 \code{error} in the third statement. 
146
147 A entry method can have arbitrary number of published (produced and reduced)
148 values and consumed values. In addition to basic data types, each of these
149 values can also be an object of arbitrary type. The values published by
150 \code{A[i]} must have the index \code{i}, whereas values consumed can have the
151 index \code{e(i)}, which is an index expression in the form of \code{i}$\pm c$
152 where $c$ is a constant. Although we have used different symbols (\code{p} and
153 \code{q}) for the input and the output variables, they are allowed to overlap. 
154
155 The parameters are produced and consumed in the program order. Namely, a
156 parameter produced in an early statement will be consumed by the next consuming
157 statement, but will no longer be visible to any consuming statement after a 
158 subsequent statement producing the same parameter in program order.
159 Special rules involving loops are discussed later with loop statement.
160
161 $\bullet$ {\bf Overlap Statement}
162
163 Complicated parallel programs usually have concurrent flows of control. To
164 explicitly express this, Charisma provides a \code{overlap} keyword, whereby the
165 programmer can fire multiple overlapping control flows. These flows may contain
166 different number of steps or statements, and their execution should be
167 independent of one another so that their progress can interleave with arbitrary
168 order and always return correct results. 
169
170 \begin{SaveVerbatim}{foodecl}
171   overlap
172   {
173     foreach i in workers1
174       (lb[i], rb[i]) <- workers1[i].produceBorders();
175     end-foreach
176     foreach i in workers1
177       workers1[i].compute(lb[i+1], rb[i-1]);
178     end-foreach
179   }
180   {
181     foreach i in workers2
182       (lb[i], rb[i]) <- workers2[i].compute(lb[i+1], rb[i-1]);
183     end-foreach
184   }
185   end-overlap
186 \end{SaveVerbatim}
187 \smallfbox{\BUseVerbatim{foodecl}}
188
189 This example shows an \code{overlap} statement where two blocks in curly
190 brackets are executed in parallel. Their execution join back to one at the end
191 mark of \code{end-overlap}. 
192
193 $\bullet$ {\bf Loop Statement}
194
195 Loops are supported with \code{for} statement and \code{while} statement. Here
196 are two examples.
197 \begin{SaveVerbatim}{foodecl}
198   for iter = 0 to MAX_ITER
199      workers.doWork();
200   end-for
201 \end{SaveVerbatim}
202 \smallfbox{\BUseVerbatim{foodecl}}
203   
204 \begin{SaveVerbatim}{foodecl}
205   while (err > epsilon)
206      (+err) <- workers.doWork();
207      MainChare.updateError(err);
208   end-while
209 \end{SaveVerbatim}
210 \smallfbox{\BUseVerbatim{foodecl}}
211
212 The loop condition in \code{for} statement is independent from the main program;
213 It simply tells the program to repeat the block for so many times. The loop
214 condition in \code{while} statement is actually updated in the MainChare. In the
215 above example, \code{err} and \code{epsilon} are both member variables of class
216 \code{MainChare}, and can be updated as the example shows. The programmer can
217 active the ``autoScalar'' feature by including a ``\code{define autoScalar;}''
218 statement in the orchestration code. When autoScalar is enabled,  Charisma will
219 find all the scalars in the \code{.or} file, and create a local copy in the
220 \code{MainChare}. Then every time the scalar is published by a statement, an
221 update statement will automatically be inserted after that statement. The only
222 thing that the programmer needs to do is to initialize the local scalar with
223 a proper value. 
224
225 Rules of connecting produced and consumed parameters concerning loops are
226 natural. The first consuming statement will look for values produced by the last
227 producing statement before the loop, for the first iteration. The last
228 producing statement within the loop body, for the following iterations. At the
229 last iteration, the last produced values will be disseminated to the code
230 segment following the loop body. Within the loop body, program order holds. 
231
232 \begin{SaveVerbatim}{foodecl}
233   for iter = 1 to MAX_ITER
234     foreach i in workers
235       (lb[i], rb[i]) <- workers[i].compute(lb[i+1], rb[i-1]);
236     end-foreach
237   end-for
238 \end{SaveVerbatim}
239 \smallfbox{\BUseVerbatim{foodecl}}
240
241 One special case is when one statement's produced parameter and consumed
242 parameter overlaps. It must be noted that there is no dependency within the same
243 \code{foreach} statement. In the above code segment, the values consumed
244 \code{lb[i], rb[i]} by \code{worker[i]} will not come from  
245 its neighbors in this iteration. The rule is that the consumed values always
246 originate from previous \code{foreach} statements or \code{foreach} statements
247 from a previous loop iteration, and the published values are visible only to
248 following \code{foreach} statements or \code{foreach} statements in following
249 loop iterations. 
250
251 $\bullet$ {\bf Scatter and Gather Operation}
252
253 A collection of values produced by one object may be split and consumed by
254 multiple object array elements for a scatter operation. Conversely, a collection
255 of values from different objects can be gathered to be consumed by one object.
256
257 \begin{SaveVerbatim}{foodecl}
258   foreach i in A
259     (points[i,*]) <- A[i].f(...);
260   end-foreach
261   foreach k,j in B
262     (...) <- B[k,j].g(points[k,j]);
263   end-foreach
264 \end{SaveVerbatim}
265 \smallfbox{\BUseVerbatim{foodecl}}
266
267 A wildcard dimension ``*'' in \code{A[i].f()}'s output \code{points} specifies
268 that it will publish multiple data items. At the consuming side, each
269 \code{B[k,j]} consumes only one point in the data, and therefore a scatter
270 communication will be generated from \code{A} to \code{B}. For instance,
271 \code{A[1]} will publish data \code{points[1,0..N-1]} to be consumed by multiple
272 array objects \code{B[1,0..N-1]}.  
273
274 \begin{SaveVerbatim}{foodecl}
275   foreach i,j in A
276     (points[i,j]) <- A[i,j].f(...);
277   end-foreach
278   foreach k in B
279     (...) <- B[k].g(points[*,k]);
280   end-foreach
281 \end{SaveVerbatim}
282 \smallfbox{\BUseVerbatim{foodecl}}
283
284
285 Similar to the scatter example, if a wildcard dimension ``*'' is in the
286 consumed parameter and the corresponding published parameter does not have a
287 wildcard dimension, there is a gather operation generated from the publishing
288 statement to the consuming statement. In the following code segment, each 
289 \code{A[i,j]} publishes a data point, then data points from \code{A[0..N-1,j]} are
290 combined together to for the data to be consumed by \code{B[j]}.  
291
292 Many communication patterns can be expressed with combination of orchestration
293 statements. For more details, please refer to PPL technical report 06-18,
294 ``Charisma: Orchestrating Migratable Parallel Objects''.
295
296 Last but not least, all the orchestration statements in the \code{.or} file
297 together form the dependency graph. According to this dependency graph, the
298 messages are created and the parallel program progresses. Therefore, the user is
299 advised to put only parallel constructs that are driven by the data dependency
300 into the orchestration code. Other elements such as local dependency should be
301 coded in the sequential code. 
302