*** empty log message ***
authorChao Huang <chuang10@uiuc.edu>
Fri, 18 May 2007 19:52:55 +0000 (19:52 +0000)
committerChao Huang <chuang10@uiuc.edu>
Fri, 18 May 2007 19:52:55 +0000 (19:52 +0000)
doc/charisma/manual.tex

index 555aaa4e872e4e08d016d64edb6b1025804e1858..bc2a737f57ce7c9f17edb58b6a597a9389bf7099 100644 (file)
@@ -24,446 +24,11 @@ A Charisma program is composed of two parts: the orchestration code in a .or
 file, and sequential user code in C/C++ form. 
 
 \subsection{Orchestration Code}
-The orchestration code in the .or file can be divided into two part. The header
-part contains information about the program, included external files, defines,
-and declaration of parallel constructs used in the code. The orchestration
-section is made up of statements that forms a global control flow of the
-parallel program. In the orchestration code, Charisma employs a macro dataflow
-approach; the statements produce and consume values, from which the control flows
-can be organized, and messages and method invocations generated. 
-
-\subsubsection{Header Section}
-
-The very first line should give the name of the Charisma program with the {\tt
-program} keyword.
-
-\begin{alltt}
-    program jacobi 
-\end{alltt}
-
-The {\tt program} keyword can be replaced with {\tt module}, which means that
-the output program is going to be a library module instead of a stand-alone
-program. Please refer to Section~\ref{sec:module} for more details.
-
-Next, the programmer can include external code files in the generated code with
-keyword {\tt include} with the filename without extension. For example, the
-following statement tells the Charisma compiler to look for header file
-``particles.h'' to be included in the generated header file ``jacobi.h'' and to
-look for C/C++ code file ``particles.[C/cc/cpp/cxx/c]'' to be included in the
-generated C++ code file ``jacobi.C''.
-
-\begin{alltt}
-    include particles;
-\end{alltt}
-
-It is useful when there are source code that must precede the generated
-parallel code, such as basic data structure declaration. 
-
-After the {\tt include} section is the {\tt define} section, where environmental
-variables can be defined for Charisma. For example, to tell Charisma to generate
-additional code to enable the load balancing module, the programmer should
-define ``ldb'' to be 1, as follows.
-
-\begin{alltt}
-    define ldb 1;
-\end{alltt}
-
-\subsubsection{Declaration Section}
-
-Next comes the declaration section, where classes, objects and parameters are
-declared. A Charisma program is composed of multiple sets of parallel objects
-which are organized by the orchestration code. Different sets of objects can be
-instantiated from different class types. Therefore, we have to specify the class
-types and object instantiation. Also we need to specify the parameters (See
-Section~\ref{sec:orchsec}) to use in the orchestration statements. 
-
-A Charisma program or module has one ``MainChare'' class, and it does not
-require explicit instantiation since it is a singleton. The statement to declare
-MainChare looks like this:
-
-\begin{alltt}
-    class JacobiMain : MainChare;
-\end{alltt}
-
-For object arrays, we first need to declare the class types inherited from 1D
-object array, 2D object array, etc, and then instantiate from the class types. 
-The dimensionality information of the object array is given in a pair of 
-brackets with each dimension size separated by a comma.
-
-\begin{alltt}
-    class JacobiWorker : ChareArray1D;
-    obj workers : JacobiWorker[N];
-
-    class Cell : ChareArray3D;
-    obj cells : Cell[M,M,M];
-\end{alltt}
-
-Note that key word ``class'' is for class type derivation, and ``obj'' is for
-parallel object or object array instantiation. The above code segment declares a
-new class type JacobiWorker which is a 1D object array, (and the programmer is
-supposed to supply sequential code for it in files ``JacobiWorker.h'' and
-``JacobiWorker.C'' (See Section~\ref{sec:sequential} for more details on
-sequential code). Object array ``workers'' is instantiated from ``JacobiWorker''
-and has 16 elements.
-
-The last part is orchestration parameter declaration. These parameters are used
-only in the orchestration code to connect input and output of orchestration
-statements, and their data type and size is declared here. More explanation of
-these parameters can be found in Section~\ref{sec:orchsec}. 
-
-\begin{alltt}
-    param lb : double[N];
-    param rb : double[N];
-\end{alltt}
-
-With this, ``lb'' and ``rb'' are declared as parameters of that can be 
-``connected'' with local variables of double array with size of 512. 
-
-\subsubsection{Orchestration Section}
-\label{sec:orchsec}
-
-In the main body of orchestration code, the programmer describes the behavior
-and interaction of the elements of the object arrays using orchestration
-statements.
-
-$\bullet$ {\bf Foreach Statement}
-
-The most common kind of parallelism is the invocation of a method
-across all elements in an object array. Charisma provides a {\em foreach}
-statement for specifying such parallelism. The keywords \code{foreach} and
-\code{end-foreach} forms an enclosure within which the parallel invocation is
-performed. The following code segment invokes the entry method \code{compute} on
-all the elements of array \code{myWorkers}. 
-
-\begin{SaveVerbatim}{foodecl}
-  foreach i in workers
-    workers[i].compute();
-  end-foreach
-\end{SaveVerbatim}
-\vspace{0.1in}
-\smallfbox{\BUseVerbatim{foodecl}}
-\vspace{0.1in}
-
-$\bullet$ {\bf Publish Statement and Produced/Consumed Parameters}
-
-In the orchestration code, an object method invocation can have input and output
-(consumed and produced) parameters. Here is an orchestration statement that
-exemplifies the input and output of this object methods
-\code{workers.produceBorders} and \code{workers.compute}. 
-
-\begin{SaveVerbatim}{foodecl}
-  foreach i in workers
-    <lb[i], rb[i]> := workers[i].produceBorders();
-    workers[i].compute(lb[i+1], rb[i-1]);
-    
-    <+error> := workers[i].reduceData();
-  end-foreach
-\end{SaveVerbatim}
-\vspace{0.1in}
-\smallfbox{\BUseVerbatim{foodecl}}
-\vspace{0.1in}
-
-Here, the entry method \code{workers[i].produceBorders} produces (called {\em
-published} in Charisma) values of \code{lb[i], rb[i]}, enclosed in a pair of
-angular brackets before the publishing sign ``\code{:=}''. In the second
-statement, function \code{workers[i].compute} consumes values of \code{lb[i+1],
-rb[i-1]}, just like normal function parameters. If a reduction operation is
-needed, the reduced parameter is marked with a ``\code{+}'' before it, like the
-\code{error} in the third statement. 
-
-A entry method can have arbitrary number of published (produced and reduced)
-values and consumed values. In addition to basic data types, each of these
-values can also be an object of arbitrary type. The values published by
-\code{A[i]} must have the index \code{i}, whereas values consumed can have the
-index \code{e(i)}, which is an index expression in the form of \code{i}$\pm c$
-where $c$ is a constant. Although we have used different symbols (\code{p} and
-\code{q}) for the input and the output variables, they are allowed to overlap. 
-
-The parameters are produced and consumed in the program order. Namely, a
-parameter produced in an early statement will be consumed by the next consuming
-statement, but will no longer be visible to any consuming statement after that.
-Special rules involving loops are discussed later with loop statement.
-
-$\bullet$ {\bf Overlap Statement}
-
-Complicated parallel programs usually have concurrent flows of control. To
-explicitly express this, Charisma provides a \code{overlap} keyword, whereby the
-programmer can fire multiple overlapping control flows. These flows may contain
-different number of steps or statements, and their execution should be
-independent of one another so that their progress can interleave with arbitrary
-order and always return correct results. 
-
-\begin{SaveVerbatim}{foodecl}
-  overlap
-  {
-    foreach i in workers1
-      <lb[i], rb[i]> := workers1[i].produceBorders();
-    end-foreach
-    foreach i in workers1
-      workers1[i].compute(lb[i+1], rb[i-1]);
-    end-foreach
-  }
-  {
-    foreach i in workers2
-      <lb[i], rb[i]> := workers2[i].compute(lb[i+1], rb[i-1]);
-    end-foreach
-  }
-  end-overlap
-\end{SaveVerbatim}
-\vspace{0.1in}
-\smallfbox{\BUseVerbatim{foodecl}}
-\vspace{0.1in}
-
-This example shows an \code{overlap} statement where two blocks in curly
-brackets are executed in parallel. Their execution join back to one at the end
-mark of \code{end-overlap}. 
-
-$\bullet$ {\bf Loop Statement}
-
-Loops are supported with \code{for} statement and \code{while} statement. Here
-are two examples.
-\begin{SaveVerbatim}{foodecl}
-  for iter := 0 to MAX_ITER
-     workers.doWork();
-  end-for
-\end{SaveVerbatim}
-\vspace{0.1in}
-\smallfbox{\BUseVerbatim{foodecl}}
-\vspace{0.1in}
-  
-\begin{SaveVerbatim}{foodecl}
-  while (maxError > epsilon)
-     workers.doWork();
-  end-while
-\end{SaveVerbatim}
-\vspace{0.1in}
-\smallfbox{\BUseVerbatim{foodecl}}
-\vspace{0.1in}
-
-The loop condition in \code{for} statement is independent from the main program;
-It simply tells the program to repeat the block for so many times. The loop
-condition in \code{while} statement is actually updated in the MainChare. In the
-above example, maxError and epsilon are both member variables of class
-MainChare, and can (should) be updated as the program executes. 
-
-Rules of connecting produced and consumed parameters concerning loops are
-natural. The first consuming statement will look for values produced by the last
-producing statement before the loop, for the first iteration. The last
-producing statement within the loop body, for the following iterations. At the
-last iteration, the last produced values will be disseminated to the code
-segment following the loop body. Within the loop body, program order holds. 
-
-\begin{SaveVerbatim}{foodecl}
-  for iter := 0 to MAX_ITER
-    foreach i in workers
-      <lb[i], rb[i]> := workers[i].compute(lb[i+1], rb[i-1]);
-    end-foreach
-  end-for
-\end{SaveVerbatim}
-\vspace{0.1in}
-\smallfbox{\BUseVerbatim{foodecl}}
-\vspace{0.1in}
-
-One special case is when one statement's produced parameter and consumed
-parameter overlaps. It must be noted that there is no dependency within the same
-\code{foreach} statement. In the above code segment, the values consumed
-\code{lb[i], rb[i]} by \code{worker[i]} will not come from  
-its neighbors in this iteration. The rule is that the consumed values always
-originate from previous \code{foreach} statements or \code{foreach} statements
-from a previous loop iteration, and the published values are visible only to
-following \code{foreach} statements or \code{foreach} statements in following
-loop iterations. 
-
-$\bullet$ {\bf Scatter and Gather Operation}
-
-A collection of values produced by one object may be split and consumed by
-multiple object array elements for a scatter operation. Conversely, a collection
-of values from different objects can be gathered to be consumed by one object.
-
-\begin{SaveVerbatim}{foodecl}
-  foreach i in A
-    <points[i,*]> := A[i].f(...);
-  end-foreach
-  foreach k,j in B
-    <...> := B[k,j].g(points[k,j]);
-  end-foreach
-\end{SaveVerbatim}
-\vspace{0.1in}
-\smallfbox{\BUseVerbatim{foodecl}}
-\vspace{0.1in}
-
-A wildcard dimension ``*'' in \code{A[i].f()}'s output \code{points} specifies
-that it will publish multiple data items. At the consuming side, each
-\code{B[k,j]} consumes only one point in the data, and therefore a scatter
-communication will be generated from \code{A} to \code{B}. For instance,
-\code{A[1]} will publish data \code{points[1,0..N-1]} to be consumed by multiple
-array objects \code{B[1,0..N-1]}.  
-
-\begin{SaveVerbatim}{foodecl}
-  foreach i,j in A
-    <points[i,j]> := A[i,j].f(...);
-  end-foreach
-  foreach k in B
-    <...> := B[k].g(points[*,k]);
-  end-foreach
-\end{SaveVerbatim}
-\vspace{0.1in}
-\smallfbox{\BUseVerbatim{foodecl}}
-\vspace{0.1in}
-
-Similar to the scatter example, if a wildcard dimension ``*'' is in the
-consumed parameter and the corresponding published parameter does not have a
-wildcard dimension, there is a gather operation generated from the publishing
-statement to the consuming statement. In the following code segment, each 
-\code{A[i,j]} publishes a data point, then data points from \code{A[0..N-1,j]} are
-combined together to for the data to be consumed by \code{B[j]}.  
-
-Many communication patterns can be expressed with combination of orchestration
-statements. For more details, please refer to PPL technical report 06-18,
-``Charisma: Orchestrating Migratable Parallel Objects''.
+\input{orchcode}
 
 \subsection{Sequential Code}
 \label{sec:sequential}
-
-\subsubsection{Sequential Files}
-The programmer supplies the sequential code for each class as necessary. The
-files should be named in the form of class name with appropriate file extension.
-The header file is not really an ANSI C header file. Instead, it is the
-sequential portion of the class's declaration. Charisma will generate the class 
-declaration from the orchestration code, and incorporate the sequential portion
-in the final header file. For example, if a molecular dynamics simulation has
-the following classes (as declared in the orchestration code):
-
-\begin{alltt}
-    class MDMain : MainChare;
-    class Cell : ChareArray3D;
-    class CellPair : ChareArray6D;
-\end{alltt}
-
-The user is supposed to prepare the following sequential files for the classes:
-MDMain.h, MDMain.C, Cell.h, Cell.C, CellPair.h and CellPair.C, unless a class
-does not need sequential declaration and/or definition code. Please refer to the
-example in the Appendix. 
-
-For each class, a member function ``void initialize(void)'' can be defined and
-the generated constructor will automatically call it. This saves the trouble of 
-explicitly call initialization code for each array object. 
-
-\subsubsection{Producing and Consuming Functions}
-The C/C++ source code is nothing different than ordinary sequential source code,
-except for the producing/consuming part. For consumed parameters, a function
-treat them just like normal parameters passed in. To handle produced parameters, 
-the sequential code needs to do two special things. First, the function should 
-have extra parameter for output parameters. The parameter type is keyword \code{outport},
-and the parameter name is the same as appeared in the orchestration code. Second,
-in the body of the function, the keyword \code{produce} is used to connect the 
-orchestration parameter and the local variables whose value will be sent out, in 
-a format of a function call, as follows.
-
-\begin{alltt}
-    produce(produced\_parameter, local\_variable[, size\_of\_array]);
-\end{alltt}
-
-When the parameter represents a data array, we need the additional
-\code{size\_of\_array} to specify the size of the data array. 
-
-The dimensionality of an orchestration parameter is divided into two parts: 
-its dimension in the orchestration code, which is implied by the dimensionality
-of the object arrays the parameter is associated, and the local dimensionality,
-which is declared in the declaration section. The orchestration dimension is not
-explicitly declared anywhere, but it is derived from the object arrays. For 
-instance, in the 1D Jacobi worker example, ``lb'' and ``rb'' has the same 
-orchestration dimensionality of workers, namely 1D of size [16]. The local
-dimensionality is used when the parameter is associated with local variables 
-in sequential code. Since ``lb'' and ``rb'' are declared to have the local
-type and dimension of ``double [512]'', the producing statement should connect
-it with a local variable of ``double [512]''.
-
-\begin{alltt}
-    void JacobiWorker::produceBorders(outport lb, outport rb)\{
-      . . .
-      produce(lb,localLB,512);
-      produce(rb,localRB,512);
-    \}
-\end{alltt}
-
-Special cases of the produced/consumed parameters involve scatter/gather
-operations. In scatter operation, since an additional dimension is implied in
-the produced parameter, we the \code{local\_variable} should have additional
-dimension equal to the dimension over which the scatter is performed. Similarly,
-the input parameter in gather operation will have an additional dimension the
-same size of the dimension of the gather operation.
-
-For reduction, one additional parameter of type char[] is added to specify the
-reduction operation. Built-in reduction operations are ``+'' (sum), ``*'' (product),
-``$<$'' (minimum), ``$>$'' (maximum) for basic data types. For instance the 
-following statements takes the sum of all local value of \code{result} and 
-for output in \code{sum}.
-
-\begin{alltt}
-    reduce(sum, result, ``+'');
-\end{alltt}
-
-If the data type is a user-defined class, then you might use the function or
-operator defined to do the reduction. For example, assume we have a class
-called ``Force'', and we have an ``add'' function (or a ``+'' operator) defined.
-
-\begin{alltt}
-    Force& Force::add(const Force& f_);
-\end{alltt}
-
-In the reduction to sum all the local forces, we can use
-
-\begin{alltt}
-    reduce(sumForces, localForce, ``add'');
-\end{alltt}
-
-\subsubsection{Miscellaneous Issues}
-In sequential code, the user can access the object's index by a keyword 
-``thisIndex''. The index of 1-D to 6-D object arrays are:
-
-\begin{alltt}
-1D: thisIndex
-2D: thisIndex.x, thisIndex.y
-3D: thisIndex.x, thisIndex.y, thisIndex.z
-4D: thisIndex.w, thisIndex.x, thisIndex.y, thisIndex.z
-5D: thisIndex.v, thisIndex.w, thisIndex.x, thisIndex.y, thisIndex.z
-6D: thisIndex.x1, thisIndex.y1, thisIndex.z1, thisIndex.x2, thisIndex.y2, thisIndex.z2
-\end{alltt}
-
-\section{Building and Running a Charisma Program}
-There are two steps to build a Charisma program: generating Charm++ program 
-from orchestration code, and building the Charm++ program. 
-
-1) Charisma compiler, currently named \code{orchc}, is used to compile the
-orchestration code (.or file) and integrate sequential code to generate a
-Charm++ program. The resultant Charm++ program usually consists of the 
-following code files: Charm++ Interface file ([modulename].ci), header file 
-([modulename].h) and C++ source code file ([modulename].C). The command 
-for this step is as follows.
-
-\begin{alltt}
-    > orchc [modulename].or
-\end{alltt}
-
-2) Charm++ compiler, charmc, is used to parse the Charm++ Interface (.ci) file,
-compile C/C++ code, and link and build the executable. The typical commands are:
-\begin{alltt}
-    > charmc [modulename].ci
-    > charmc [modulename].C -c
-    > charmc [modulename].o -o pgm -language charm++
-\end{alltt}
-
-Running the Charisma program is the same as running a Charm++ program, using
-Charm++'s job launcher \code{charmrun}. (On some platforms like CSE's Turing 
-Cluster, use the customized job launcher \code{rjq} or \code{rj}.) 
-
-\begin{alltt}
-    > charmrun pgm +p4
-\end{alltt}
-
-Please refer to Charm++'s manual and tutorial for more details of building 
-and running a Charm++ program. 
+\input{seqcode}
 
 \section{Handling Sparse Object Arrays}
 \label{sec:sparse}
@@ -515,6 +80,44 @@ void getIndex_cellpairs(CkVec<CkArrayIndex6D>& vec){
 
 %neighbors and neighborsize for dense array
 
+\section{Building and Running a Charisma Program}
+There are two steps to build a Charisma program: generating Charm++ program 
+from orchestration code, and building the Charm++ program. 
+
+1) Charisma compiler, currently named \code{orchc}, is used to compile the
+orchestration code (.or file) and integrate sequential code to generate a
+Charm++ program. The resultant Charm++ program usually consists of the 
+following code files: Charm++ Interface file ([modulename].ci), header file 
+([modulename].h) and C++ source code file ([modulename].C). The command 
+for this step is as follows.
+
+\begin{alltt}
+    > orchc [modulename].or
+\end{alltt}
+
+2) Charm++ compiler, charmc, is used to parse the Charm++ Interface (.ci) file,
+compile C/C++ code, and link and build the executable. The typical commands are:
+\begin{alltt}
+    > charmc [modulename].ci
+    > charmc [modulename].C -c
+    > charmc [modulename].o -o pgm -language charm++
+\end{alltt}
+
+Running the Charisma program is the same as running a Charm++ program, using
+Charm++'s job launcher \code{charmrun}. (On some platforms like CSE's Turing 
+Cluster, use the customized job launcher \code{rjq} or \code{rj}.) 
+
+\begin{alltt}
+    > charmrun pgm +p4
+\end{alltt}
+
+Please refer to Charm++'s manual and tutorial for more details of building 
+and running a Charm++ program. 
+
+\section{Using Load Balancing Module}
+\label{sec:ldb}
+\input{ldb}
+
 \section{Support for Library Module}
 \label{sec:module}
 
@@ -528,86 +131,5 @@ details will be reported in this manual when available.
 
 \appendix
 \label{sec:appendix}
-
-\section{Example: Jacobi 1D}
-Following is the content of the orchestration file jacobi.or. 
-
-\begin{SaveVerbatim}{foodecl}
-program jacobi
-
-class  JacobiMain : MainChare;
-class  JacobiWorker : ChareArray1D;
-obj  workers : JacobiWorker[M];
-param  lb : double[N];
-param  rb : double[N];
-
-begin
-    for iter := 1 to MAX_ITER
-       foreach i in workers
-           <lb[i], rb[i]> := workers[i].produceBorders();
-           workers[i].compute(lb[i+1], rb[i-1]);
-       end-foreach
-    end-for
-end
-\end{SaveVerbatim}
-\vspace{0.1in}
-\smallfbox{\BUseVerbatim{foodecl}}
-\vspace{0.1in}
-
-The class {\tt JacobiMain} does not need any sequential code, so the only
-sequential code are in JacobiWorker.h and JacobiWorker.C. Note that
-JacobiWorker.h contains only the sequential portion of JacobiWorker's
-declaration. 
-
-\begin{SaveVerbatim}{foodecl}
-#define N 512
-#define M 16
-
-int currentArray;      
-double localData[2][M][N]; 
-double localLB[N];
-double localRB[N];
-int myLeft,myRight,myUpper,myLower;
-
-void initialize();
-void compute(double lghost[], double rghost[]);
-void produceBorders(outport lb,outport rb);
-double abs(double d);
-\end{SaveVerbatim}
-\vspace{0.1in}
-\smallfbox{\BUseVerbatim{foodecl}}
-\vspace{0.1in}
-
-Similarly, the sequential C code will be integrated into the generated C file.
-Below is part of the sequential C code taken from JacobiWorker.C to show how
-consumed parameters ({\tt rghost} and {\tt lghost} in {\tt
-JacobiWorker::compute}) and produced parameters ({\tt lb} and {\tt rb} in {\tt
-JacobiWorker::produceBorders}) are handled.
-
-\begin{SaveVerbatim}{foodecl}
-void JacobiWorker::compute(double rghost[], double lghost[]){
-    /* local computation for updating elements*/
-}
-
-void JacobiWorker::produceBorders(outport lb, outport rb){
-    produce(lb,localData[currentArray][myLeft],myLower-myUpper+1);
-    produce(rb,localData[currentArray][myRight],myLower-myUpper+1);
-}
-\end{SaveVerbatim}
-\vspace{0.1in}
-\smallfbox{\BUseVerbatim{foodecl}}
-\vspace{0.1in}
-
-The user compile these input files with the following command:
-
-\begin{alltt}
-> orchc jacobi.or
-\end{alltt}
-
-The compiler generates the parallel code for sending out messages, organizing
-flow of control, and then it looks for sequential code files for the classes
-declared, namely {\tt JacobiMain} and {\tt JacobiWorker}, and integrates them
-into the final output: {\tt jacobi.h}, {\tt jacobi.C} and {\tt jacobi.ci}, which
-is a Charm++ program and can be built the way a Charm++ program is built.
-
+\input{example}
 \end{document}