Docs: refer to illinois.edu, not uiuc.edu
[charm.git] / doc / charm++ / overview.tex
1 \zap{
2 \subsection{Basic Constructs and Program Structure}
3
4 \charmpp\ is an object-based parallel programming paradigm.
5 %What sets \charmpp\ apart
6 %from traditional programming models such as message passing and shared variable
7 %programming is that the execution model of \charmpp\ is message-driven.
8 Computations in \charmpp\ are triggered based on arrival of
9 associated messages. These computations in turn can fire off more messages to
10 other (possibly remote) processors that trigger more computations on those
11 processors.
12
13 At the heart of any \charmpp\ program is a scheduler that repetitively chooses
14 a message from the available pool of messages, and executes the computations
15 associated with that message.
16
17 The programmer-visible entities in a \charmpp\ program are:
18
19 \begin{itemize}
20 \item Concurrent Objects : called {\em chares}\footnote{
21       Chare (pronounced {\bf ch\"ar}, \"a as in c{\bf a}rt) is Old 
22       English for chore.
23       }
24 \item Communication Objects : Messages
25 \item Readonly data
26 \end{itemize}
27
28 \charmpp\ starts a program by creating a single \index{chare} instance of each
29 {\em mainchare} on processor 0, and invokes constructor methods of these
30 chares.  Typically, these chares then creates a number of other \index{chare}
31 chares, possibly on other processors, which can simultaneously work to solve
32 the problem at hand.
33
34 Each \index{chare}chare contains a number of \index{entry method}{\em entry
35 methods}, which are methods that can be invoked from remote processors. The
36 \charmpp\ runtime system needs to be explicitly told about these methods, via
37 an {\em interface} in a separate file.  The syntax of this interface
38 specification file is described in the later sections.
39
40 \charmpp\ provides system calls to asynchronously create remote \index{chare}
41 chares and to asynchronously invoke entry methods on remote chares by sending
42 \index{message} messages to those chares. This asynchronous
43 \index{message}message passing is the basic interprocess communication
44 mechanism in \charmpp. However, \charmpp\ also permits wide variations on this
45 mechanism to make it easy for the programmer to write programs that adapt to
46 the dynamic runtime environment.  These possible variations include
47 prioritization (associating priorities with method invocations), conditional
48 \index{message packing}message packing and unpacking (for reducing messaging
49 overhead), \index{quiescence}quiescence detection (for detecting completion of
50 some phase of the program), and dynamic load balancing (during remote object
51 creation). In addition, several libraries are built on top of \charmpp\ that
52 can simplify otherwise arduous parallel programming tasks.
53
54 We think that \charmpp\ is easy to use if you are familiar with object-based
55 programming. (But of course that is our opinion, if your opinion differs,
56 you are encouraged to let us know the reasons, and features that you would
57 like to see in \charmpp.) Object-based programming is built around the
58 concept of ``encapsulation'' of data. As implemented in \CC, data
59 encapsulation is achieved by grouping together data and methods (also known
60 as functions, subroutines, or procedures) inside of an object.
61
62 A class is a blueprint for an object.  The encapsulated data is said to be
63 ``private'' to the object, and only the methods of that class can manipulate
64 that data. A method that has the same name as the class is a ``blessed''
65 method, called a ``Constructor'' for that class.  A constructor method is
66 typically responsible for initializing the encapsulated data of an object.
67 Each method, including the constructor can optionally be supplied data in
68 the form of parameters (or arguments). In \CC, one can create objects with
69 the {\tt new} operator that returns a pointer to the object. This pointer
70 can be used to refer to the object, and call methods on that object.
71
72 \charmpp{} is built on top of \CC, and also based on ``encapsulation''.
73 Similar to \CC, \charmpp\ entities can contain private data, and public
74 methods. The major difference is that these methods can be invoked from
75 remote processors asynchronously.  Asynchronous method invocation means that
76 the caller does not wait for the method to be actually executed and does not
77 wait for the method's return value. Therefore, \charmpp\ methods (called
78 entry methods) do not have a return value\footnote{Asynchronous remote
79 method invocation is the core of \charmpp. However, to simplify programming,
80 \charmpp\ makes use of the interoperable nature of its runtime system, and
81 combines seamlessly with user-level threads to also support synchronous
82 method execution, albeit with a slight overhead of thread creation and
83 scheduling.}. Since the actual \charmpp\ object on which the method is being
84 invoked may be on a remote processor\footnote{With its own, different address
85 space}, the \CC\ way of referring to an object, via a pointer, is not valid
86 in \charmpp.  Instead, we refer to a remote chare via a ``proxy'',
87 as explained below.
88
89
90 \subsection{Entities in \charmpp\ programs}
91
92 This section describes various entities in a typical \charmpp\ program.
93
94 \subsubsection{Sequential Objects}
95
96 A \charmpp\ program typically consists mostly of ordinary sequential \CC
97 code and objects. Such entities are only accessible locally, are not known
98 to the \charmpp\ runtime system, and thus need not be mentioned in the
99 module interface files. 
100
101 \charmpp\ does not affect the syntax or semantics of such \CC\ entities,
102 except that changes to global variables (or static data members of a class)
103 on one node will not be visible on other nodes.  Global data changes
104 must be explicitly sent between processors.  For processor- and
105 thread-private storage, refer to the ``Global Variables'' section
106 of the Converse manual.
107
108
109 \subsubsection{Messages}
110
111 Messages supply data arguments to the asynchronous remote method invocation.
112 These objects are treated differently from other objects in \charmpp\ by the
113 runtime system, and therefore they must be specified in the interface file
114 of the module.  With parameter marshalling, the system creates and handles
115 the message completely internally. Other messages are instances of \CC\
116 classes that are subclassed from a special class that is generated by the
117 \charmpp\ interface translator.  Another variation of communication objects
118 is conditionally packed and unpacked. This variation should be used when one
119 wants to send messages that contain pointers to the data rather than the
120 actual data to other processors. This type of communication objects contains
121 two static methods: \kw{pack}, and \kw{unpack}. The third variation of
122 communication objects is called {\em varsize} messages. Varsize messages is
123 an effective optimization on conditionally packed messages, and can be
124 declared with special syntax in the interface file.
125
126 \subsubsection{Chares}
127
128 Chares are the most important entities in a \charmpp\ program. These concurrent
129 objects are different from sequential \CC\ objects in many ways. Syntactically,
130 Chares are instances of \CC\  classes that are derived from a system-provided
131 class called \kw{Chare}. Also, in addition to the usual \CC\ private and public
132 data and method members, they contain some public methods called {\em entry
133 methods}. These entry methods do not return anything (they are {\tt void}
134 methods), and take at most one argument, which is a pointer to a message.
135 Chares are {\em accessed} using a proxy (an object of a specialized class
136 generated by the \charmpp\ interface translator) or using a handle (a \kw{
137 CkChareID} structure defined in \charmpp), rather than a pointer as in \CC.
138 Semantically, they are different from \CC\ objects because they can be created
139 asynchronously from remote processors, and their entry methods also could be
140 invoked asynchronously from the remote processors. Since the constructor method
141 is invoked from remote processor (while creating a chare), every chare should
142 have its constructors as entry methods (with at most one message pointer
143 parameter). These chares and their entry methods have to be specified in the
144 interface file.
145
146 \subsubsection{Chare Arrays}
147
148 Chare arrays are collections of chares. However, unlike chare groups or
149 nodegroups, arrays are not constrained by characteristics of the underlying
150 parallel machine such as number of processors or nodes. Thus, chare arrays
151 can have any number of {\em elements}. The array elements themselves are
152 chares, and methods can be invoked on individual array elements as usual.  
153 Each element of an array has a globally unique index, and messages are
154 addressed to that index.
155
156 Unlike other entities in \charmpp\, the dynamic load balancing framework (LB
157 Framework) treats array elements as objects that can be migrated across
158 processors. Thus, the runtime system keeps track of computational load
159 across the system, and also the time spent in execution of entry methods on
160 array elements, and then employs one of several strategies to redistribute
161 array elements across the available processors.
162
163 \subsubsection{Chare Groups}
164
165 Chare Groups\footnote{ These were called Branch Office Chares (BOC) in earlier
166 versions of Charm.} are a special type of concurrent objects.  Each chare group
167 is a collection of chares, with one representative (group member) on each
168 processor. All the members of a chare group share a globally unique name
169 (handle, defined by Charm RTS to be of type \kw{CkGroupID}). An entire chare
170 group could be addressed using this global handle, and an individual member of
171 a chare group can be addressed using the global handle, and a processor number.
172 Chare groups are instances of \CC\ classes subclassed from a system-provided
173 class called \kw{Group}. The Charm RTS has to be notified that these chares
174 are semantically different, and therefore chare groups have a different
175 declaration in the interface specification file.
176
177 \subsubsection{Chare Nodegroups}
178
179 Chare nodegroups are very similar to chare groups except that instead of having
180 one group member on each processor, the nodegroup has one member on each shared
181 memory multiprocessor node. Note that \charmpp\ (and its underlying runtime
182 system Converse) distinguish between processors and nodes. A node consists of
183 one or more processors that share an address space. The last few years have
184 seen emergence of fast SMP systems of small (2-4 processors) to large (32-64
185 processors) number of processors per node. A network of such SMP nodes is the
186 most general model of parallel computers, making pure distributed and pure
187 shared memory systems mere special cases. \charmpp\ is built on top of this
188 machine abstraction, and Chare nodegroups embody this abstraction in a higher
189 level language construct. Semantically, methods invoked on a nodegroup member
190 could be executed on any processor within that node. This fact can be utilized
191 for supporting load balance across processors within a node. However, this also
192 means that different processors within a node could be executing methods of the
193 same nodegroup member simultaneously, thus leading to common problems
194 associated with shared address space programming. However, \charmpp\ eases such
195 problems by allowing the programmer to specify an entry method of a nodegroup
196 to be {\em exclusive}, thus guaranteeing that no other {\em exclusive} method
197 of that nodegroup member can execute simultaneously within the node.
198
199 \subsubsection{Entry Methods}
200 In \charmpp, \index{chare}chares, \index{group}groups and \index{nodegroup}
201 nodegroups communicate using remote method invocation.  These ``remote entry'' methods may either take marshalled parameters, described in the next section; or special objects called messages.
202
203 \charm programs are open to the full gamut of program design techniques that are possible in
204 \CC. One may view the role of the programming model as providing a platform for
205 addressing and interacting with remote objects.
206 However, \charmpp does not provide a full global address space. Each process in
207 the parallel execution has its own address space and \charmpp does not
208 implicitly share or synchronize global or static variables.
209
210 }