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 }