doc: collapse intro text into one chapter
[charm.git] / doc / charm++ / intro.tex
1
2 \charmpp\ is a C++-based parallel programming system, founded on the
3 migratable-objects programming model, and supported by a novel and
4 powerful adaptive runtime system. It supports both irregular as well
5 as regular applications, and can be used to specify task-parallelism
6 as well as data parallelism in a single application. It automates
7 dynamic load balancing for task-parallel as well as data-parallel
8 applications, via separate suites of load-balancing strategies. Via
9 its message-driven execution model, it supports automatic latency
10 tolerance, modularity and parallel composition. Charm++ also supports
11 automatic checkpoint/restart, as well as fault tolerance based on
12 distributed checkpoints.
13 % {\sc Converse} interoperable runtime system for parallel
14 % programming.
15
16 Charm++ is a production-quality parallel programming system used by
17 multiple applications in science and engineering on supercomputers as
18 well as smaller clusters around the world.  Currently the parallel
19 platforms supported by \charmpp\ are the BlueGene/L, BlueGene/P,
20 BlueGene/Q, Cray XT, XE and XK series (including XK6 and XE6),
21 % XT3/4, Cray X1, Cray T3E,
22 a single workstation or a network of workstations (including x86
23 (running Linux, Windows, MacOS)), etc.  The communication protocols
24 and infrastructures supported by
25 \charmpp\ are UDP, TCP, Myrinet, Infiniband, uGNI, and PAMI. 
26 \charmpp\ programs can run without changing the source
27 on all these platforms.  Please see the \charmpp{}/\converse{}
28 Installation and Usage
29 \htmladdnormallink{Manual}{http://charm.cs.uiuc.edu/manuals/html/install/manual.html}
30 for details about installing, compiling and running
31 \charmpp\ programs.
32
33
34 \section{Programming Model}
35 The key feature of the migratable-objects programming model is {\em
36 over-decomposition}: The programmer decomposes the program into a
37 large number of work units and data units, and specifies the
38 computation in terms of creation of and interactions between these
39 units, without any direct reference to the processor on which any unit
40 resides. This empowers the runtime system to assign units to
41 processors, and to change the assignment at runtime as
42 necessary. Charm++ is the main (and early) exemplar of this
43 programming model. AMPI is another example within the Charm++ family
44 of the same model.
45
46
47 \section{Execution Model}
48
49 % A \charmpp\ program consists of a number of \charmpp\ objects
50 % distributed across the available number of processors. Thus, 
51 A basic
52 unit of parallel computation in \charmpp\ programs is a {\em
53 chare}\index{chare}. 
54 % a \charmpp\ object that can be created on any
55 % available processor and can be accessed from remote processors.
56 A \index{chare}chare is similar to a process, an actor, an ADA task,
57 etc. At its most basic level, it is just a C++ object.
58 %  with some of its methods
59 % that can be invoked from remote objects. 
60 A \charmpp computation consists of a large number of chares
61 distributed on available processors of the system, and interacting
62 with each other via asynchronous method invocations.
63 Asynchronously invoking a method on a remote object can also be
64 thought of as
65 sending a ``message'' to it. So, these method invocations are
66 sometimes referred to as messages. (besides, in the implementation,
67 the method invocations are packaged as messages anyway).
68 \index{chare}Chares can be
69 created dynamically.
70 % , and many chares may be active simultaneously.
71 % Chares send \index{message}{\em messages} to one another to invoke
72 % methods asynchronously.  
73
74 Conceptually, the system maintains a
75 ``work-pool'' consisting of seeds for new \index{chare}chares, and
76 \index{message}messages for existing chares. The Charm++ runtime system ({\em
77 Charm RTS}) may pick multiple items, non-deterministically, from this
78 pool and execute them, with the proviso that two different methods
79 cannot be simultaneously executing on the same chare object (say, on
80 different processors). Although one can define a reasonable
81 theoretical operational semantics of Charm++ in this fashion, a more
82 practical description of execution is useful to understand Charm++: On
83 each PE (``PE'' stands for a ``Processing Element''. PEs are akin to
84 cores; see section \ref{sec:machine} for a precise description), there is a
85 scheduler operating with its own private pool of messages. Each
86 instantiated chare has one PE which is where it currently resides. The
87 pool on each PE includes messages meant for Chares residing on that
88 PE, and seeds for new Chares that are tentatively meant to be
89 instantiated on that PE. The scheduler picks a message, creates a new
90 chare if the message is a seed (i.e. a constructor invocation) for a
91 new Chare, and invokes the method specified by the message. When the
92 method returns control back to the scheduler, it repeats the
93 cycle. I.e. there is no pre-emptive scheduling of other invocations.
94
95 When a chare method executes, it may create  method invocatins for other
96 chares. The Charm Runtime System (RTS, sometimes referred to as the
97 Chare Kernl in the manual) locates the PE where the targeted chare
98 resides, and delivers the invocation to the scheduler on that PE. 
99
100 Methods of a \index{chare}chare that can be remotely invoked are called
101 \index{entry method}{\em entry} methods.  Entry methods may take marshalled
102 parameters, or a pointer to a message object.  Since \index{chare}
103 chares can be created on remote processors, obviously some constructor
104 of a chare needs to be an entry method.  Ordinary entry
105 methods\footnote{``Threaded'' or ``synchronous'' methods are
106 different. But even they do not lead to pre-emption; only to
107 cooperative multi-threading} are completely non-preemptive--
108 \charmpp\ will never interrupt an executing method to start any other work,
109 and all calls made are asynchronous.
110
111 \charmpp\ provides dynamic seed-based load balancing. Thus location (processor
112 number) need not be specified while creating a
113 remote \index{chare}chare. The Charm RTS will then place the remote
114 chare on a suitable processor. Thus one can imagine chare creation
115 as generating only a seed for the new chare, which may {\em take root}
116 on some specific processor at a later time. 
117
118 % Charm RTS identifies a \index{chare}chare by a {\em ChareID}.  
119
120 % Since user code does not
121 % need to name a chares' processor, chares can potentially migrate from
122 % one processor to another.  (This behavior is used by the dynamic
123 % load-balancing framework for chare containers, such as arrays.)
124
125 Chares can be grouped into collections. The types of collections of
126 chares supported in Charm++ are: {\em chare-arrays}, \index{group}{\em
127 chare-groups}, and \index{nodegroup}{\em chare-nodegroups}, referred
128 to as {\em arrays}, {\em groups}, and {\em nodegroups} throughout this
129 manual for brevity. A Chare-array is a collection of arbitrary number
130 of migratable chares, indexed by some index type, and mapped to
131 processors according to a user-defined map group. A group (nodegroup)
132 is a collection of chares, with exactly one member element on each PE
133 (SMP node).
134
135 Charm++ does not allow global variables except readonly variables
136 (see \ref{readonly}). A chare can only access its own data directly.
137 However, each chare is accessible by a globally valid name. So, one
138 can think of Charm++ as supporting a {\em global object space}.
139
140
141
142 Every \charmpp\ program must have at least one \kw{mainchare}.  Each
143 \kw{mainchare} is created by the system on processor 0 when the \charmpp\
144 program starts up.  Execution of a \charmpp\ program begins with the
145 Charm Kernel constructing all the designated \kw{mainchare}s.  For
146 a \kw{mainchare} named X, execution starts at constructor X() or
147 X(CkArgMsg *) which are equivalent.  Typically, the
148 \kw{mainchare} constructor starts the computation by creating arrays, other
149 chares, and groups.  It can also be used to initialize shared \kw{readonly}
150 objects.
151
152 \charmpp\ program execution is terminated by the \kw{CkExit} call.  Like the
153 \kw{exit} system call, \kw{CkExit} never returns. The Charm RTS ensures
154 that no more messages are processed and no entry methods are called after a
155 \kw{CkExit}. \kw{CkExit} need not be called on all processors; it is enough
156 to call it from just one processor at the end of the computation.
157
158 \zap{
159 The only method of communication between processors in \charmpp\ is
160 asynchronous \index{entry method} entry method invocation on remote chares.
161 For this purpose, Charm RTS needs to know the types of
162 \index{chare}chares in the user program, the methods that can be invoked on
163 these chares from remote processors, the arguments these methods take as
164 input etc. Therefore, when the program starts up, these user-defined
165 entities need to be registered with Charm RTS, which assigns a unique
166 identifier to each of them. While invoking a method on a remote object,
167 these identifiers need to be specified to Charm RTS. Registration of
168 user-defined entities, and maintaining these identifiers can be cumbersome.
169 Fortunately, it is done automatically by the \charmpp\ interface translator.
170 The \charmpp\ interface translator generates definitions for {\em proxy}
171 objects. A proxy object acts as a {\em handle} to a remote chare. One
172 invokes methods on a proxy object, which in turn carries out remote method
173 invocation on the chare.}
174
175 As described so far, the execution of individual Chares is
176 ``reactive'': When method A is invoked the chare executes this code,
177 and so on. But very often, chares have specific life-cycles, and the
178 sequence of entry methods they execute can be specified in a
179 structured manner, while allowing for some localized non-determinism
180 (e.g. a pair of methods may execute in any order, but when they both
181 finish, the execution continues in a pre-determined manner, say
182 executing a 3rd entry method). To simplify expression of such control
183 structures, Charm++ provides two methods: the structured dagger
184 notation (Sec \ref{sec:sdag}), which is the main notation we recommend
185 you use.  Alternatively, you may use threaded entry methods, in
186 combination with {\em futures} and {\em sync} methods
187 (See \ref{sec:threads}). The threaded methods run in light-weight
188 user-level threads, and can block waiting for data in a variety of
189 ways. Again, only the particular thread of a particular chare is
190 blocked, while the PE continues executing other chares.
191
192 The normal entry methods, being asynchronus, are not allowed to return
193 any value, and are declared with a void return type. However, the {\em
194 sync} methods are an exception to this. They must be called from a
195 threaded method, and so are allowed to return (certain types of)
196 values.  
197
198 \section{Proxies and the charm interface file}
199 \label{proxies}
200
201 To support asynchronous method invocation and global object space, the
202 RTS needs to be able to serialize (``marshall'') the parameters, and
203 be able to generate global ``names'' for chares. For this purprpose,
204 programmers have to declare the chare classes and the signature of
205 their entry methods in a special ``\verb#.ci#'' file, called an
206 interface file. Other than the interface file, the rest of a Charm++
207 program consists of just normal C++ code. The system generates several
208 classes based on the declarations in the interface file, including
209 ``Proxy'' classes for each chare class.
210 Those familiar with various component models (such as CORBA) in the
211 distributed computing world will recognize ``proxy'' to be a dummy, standin
212 entity that refers to an actual entity.  For each chare type, a ``proxy''
213 class exists.
214 % \footnote{The proxy class is generated by the ``interface
215 % translator'' based on a description of the entry methods}  
216 The methods of
217 this ``proxy'' class correspond to the remote methods of the actual class, and
218 act as ``forwarders''. That is, when one invokes a method on a proxy to a
219 remote object, the proxy marshalls the parameters into a message, puts
220 adequate information about the target chare on the envelope of the
221 message, and forwards it to the
222 remote object. 
223 Individual chares, chare array, groups, node-groups, as well as the
224 individual elements of these collections have a such a
225 proxy. Multiple methods for obtaining such proxies are described in
226 the manual.
227 Proxies for each type of entity in \charmpp\
228 have some differences among the features they support, but the basic
229 syntax and semantics remain the same -- that of invoking methods on
230 the remote object by invoking methods on proxies.
231
232 % You can have several proxies that all refer to the same object.
233
234 \zap{
235 Historically, handles (which are basically globally unique
236 identifiers) were used to uniquely identify \charmpp\ objects.  Unlike
237 pointers, they are valid on all processors and so could be sent as
238 parameters in messages.  They are still available, but now proxies
239 also have the same feature.
240 }
241
242 (NOTE: I assume handles are not to be mentioned. Right?)
243 Handles (like CkChareID, CkArrayID, etc.) and 
244
245 \zap{
246 Proxies (like
247 CProxy\_foo) are just bytes and can be sent in messages, pup'd, and
248 parameter marshalled.  This is now true of almost all objects in
249 Charm++: the only exceptions being entire Chares (Array Elements,
250 etc.) and, paradoxically, messages themselves.
251 }
252
253 The following sections provide detailed information about various features of the
254 \charmpp\ programming system. Part I, ``Basic Usage'', is sufficient
255 for wrirting full-fledged applications. Note that only the last two
256 chapters of this part involve the notion of physical processors
257 (cores, nodes, ..), with the exception of simple query-type utilities
258 (Sec \ref{sec:basic utility fns}). We strongly suggest that all
259 application developers, beginners and experts alike, try to stick to
260 the basic language to the extent possible, and use features from the
261 advanced sections only when you are convinced they are
262 essential. (They are are useful in specific situatins; but a common
263 mistake we see when we examine programs written by beginners is to
264 jump to using more complex features that are not really needed for
265 their purpose. Hence the caution). The
266 advanced concepts in the Part II of the manual support optimizations,
267 convenience features, and more complex or sophisticated features. 
268
269
270 \footnote{For a description of the underlying design
271 philosophy please refer to the following papers :\\
272     L. V. Kale and Sanjeev Krishnan,
273     {\em ``\charmpp : Parallel Programming with Message-Driven Objects''},
274     in ``Parallel Programming Using \CC'',
275     MIT Press, 1995. \\
276     L. V. Kale and Sanjeev Krishnan,
277     {\em ``\charmpp : A Portable Concurrent Object Oriented System
278     Based On \CC''},
279     Proceedings of the Conference on Object Oriented Programming,
280     Systems, Languages and Applications (OOPSLA), September 1993.
281 }.
282