\section{\charmpp{} Overview}

We think that \charmpp\ is easy to use if you are familiar with object-based
programming. (But of course that is our opinion, if your opinion differs, you
are encouraged to let us know the reasons, and features that you would like to
see in \charmpp.) Object-based programming is built around the concept of
``encapsulation'' of data. As implemented in \CC, data encapsulation is
achieved by grouping together data and methods (or functions, or subroutines,
or procedures, or other such entities) inside of an object. A class is a
blueprint for an object.  The encapsulated data is said to be ``private'' to
the object, and only the methods of that class can manipulate that data. A
method that has the same name as the class is a ``blessed'' method, called a
``Constructor'' for that class.  Constructor method is typically responsible
for initializing the encapsulated data of an object. Each method, including the
constructor can optionally be supplied data in the form of parameters (or
arguments). In \CC, one can create objects with the {\tt new} operator that
returns a pointer to the object. This pointer can be used to refer to the
object, and call methods on that object.

\charmpp{} is built on top of \CC, and also based on ``encapsulation''. Similar
to \CC, \charmpp\ entities can contain private data, and public methods. The
major difference is that these methods can be invoked from remote processors
asynchronously.  Asynchronous method invocation implies that the caller does
not wait for the method to be actually executed and does not wait for the
method's return value. Therefore, \charmpp\ methods (called entry methods) do
not have a return value\footnote{Asynchronous remote method invocation is the
core of \charmpp. However, to simplify programming, \charmpp\ makes use of the
interoperable nature of its runtime system, and combines seemlessly with
user-level threads to also support synchronous method execution, albeit with a
slight overhead of thread creation and scheduling.}. Since the actual \charmpp\
object on which the method is being invoked is possibly on a remote processor,
in possibly different address space, the \CC\ way of referring to an object,
such as a pointer, is not valid in \charmpp.  Instead, there are two ways of
referring to a remote object in \charmpp. First, every remote object has a
unique {\em handle} called \kw{ChareID}. This is a C struct that uniquely
defines the location of the object on the parallel machine. Note that, whatever
the type of object (its class), it has the same kind of such handle. The
second, and preferred way of referring to a remote object is its ``proxy''.

Those familiar with various component models in the distributed computing world
will recognize ``proxy'' to be a dummy entity that refers to the actual
entity. It is exactly that way in \charmpp\ too. For each object type (each
class), its ``proxy'' class exists (actually it is generated by the ``interface
translator''), which contains an actual reference to the class (such as a \kw{
ChareID}). Furthermore, the methods of this ``proxy'' class correspond to the
methods of actual class, and act as ``forwarders''. That is, when one invokes a
method on a proxy to a remote object, the proxy forwards this method invocation
to the actual remote object. Creation of a proxy results in creation of a new
remote object. All entities that are created and manipulated remotely in
\charmpp\ have such proxies. Proxies for each type of entity in \charmpp\ have
some differences among the features they support, but the basic syntax and
semantics almost always remains the same, and that is of invoking methods on
the remote object by invoking methods on proxies.

\subsection{\charmpp\ Execution Model}

A \charmpp\ program consists of a number of \charmpp\ objects distributed
across the available number of processors. Thus, the basic unit of parallel
computation in \charmpp\ programs is the {\em chare}\index{chare}, a \charmpp\
object that can be created on any available processor and can be accessed from
remote processors.  A \index{chare}chare is similar to a process, an actor, an
ADA task, etc.  \index{chare}Chares are created dynamically, and many chares
may be active simultaneously.  Chares send \index{message}{\em messages} to one
another to invoke methods asynchronously.  Conceptually, the system maintains a
``work-pool'' consisting of seeds for new \index{chare}chares, and
\index{message}messages for existing chares. The runtime system (called {\em
Charm Kernel}) may pick multiple items, non-deterministically, from this pool
and execute them.  It will not process two messages for the same
\index{chare}chare concurrently, but otherwise it is free to schedule them in
any way.

Methods of a \index{chare}chare that can be remotely invoked are called
\index{entry method}{\em entry} methods.  Entry methods may take a pointer to a
message object, or no parameters.  Since \index{chare}chares can be created on
remote processors, obviously some constructor of a chare needs to be an entry
method.

\charmpp\ provides dynamic seed-based load balancing. Thus location (processor
number) need not be specified while creating a remote \index{chare}chare. The
Charm Kernel will then place the remote chare on a least loaded processor. Thus
one can imagine chare creation as generating only a seed for the new chare,
which may {\em take root} on the most {\em fertile} processor. Charm Kernel
identifies a \index{chare}chare by a {\em ChareID}.  Since user code does not
need to name a chares' processor, chares can potentially migrate from one
processor to another.  (This behaviour is used by the dynamic load-balancing
framework for chare containers, such as arrays.)

Other \charmpp\ objects are collections of chares. They are: \index{group}{\em
chare-groups}, \index{nodegroup}{\em chare-nodegroups}, and \index{array}{\em
chare-arrays}, referred to as {\em groups}, {\em nodegroups}, and {\em arrays}
throughout this manual. A group (nodegroup) is a collection of chares, one per
processor (SMP node), that is addressed using a unique system-wide name. An
array is a collection of arbitrary number of migratable chares, mapped to
processors according to a user-defined map group.

Every \charmpp\ program must have at least one \kw{mainchare}.  There can be
only one instance of this, which is created on processor 0 when the \charmpp\
program starts up.  Execution of a \charmpp\ program begins with Charm Kernel
constructing all the designated \kw{mainchare}s.  Typically, the \kw{mainchare}
constructor starts the computation by creating other chares and chare
\index{group} groups.  It can also be used to initialize shared \kw{readonly}
objects.

The only method of communication between processors in \charmpp\ is
asynchronous \index{entry method} entry method invocation on remote chares. For
this purpose, Charm Kernel needs to know about the types of \index{chare}chares
in the user program, the methods that can be invoked on these chares from
remote processors, the arguments these methods take as input etc. Therefore,
when the program starts up, these user-defined entities need to be registered
with Charm Kernel, which assigns a unique identifier to each of them. While
invoking a method on a remote object, these identifiers need to be specified to
Charm Kernel. Registration of user-defind entities, and maintaining these
identifiers can be cumbersome. Fortunately, it can be done by the \charmpp\
interface translator. The \charmpp\ interface translator generates definitions
for {\em proxy} objects. A proxy object acts as a {\em handle} to a remote
chare. One invokes methods on a proxy object, which in turn carries out remote
method invocation on the chare.

In addition, the \charmpp\ interface translator provides ways to enhance the
basic functionality of Charm Kernel using user-level threads and futures. These
allow entry methods to be executed in separate user-level threads.  These
\index{threaded} {\em threaded} entry methods may block waiting for data by
making {\em synchronous} calls to remote object methods that return results in
messages.

\charmpp\ program execution is terminated by the \kw{CkExit} call. This call is
not the same as in Unix: it merely informs the Charm Kernel that all
computations on all processors must be terminated, and then returns to the user
program: the programmer should make sure that no work is done by the method
after \kw{CkExit} is called.  Charm Kernel ensures that no messages are
processed and no entry methods are called after the currently executing entry
method completes. \kw{CkExit} need not be called on all processors; it is
enough to call it from just one processor at the end of the computation.

\subsection{Entities in \charmpp\ programs}

This section describes various entities in a typical \charmpp\ program.

\subsubsection{Sequential Objects}

A \charmpp\ program typically contains a number of sequential objects. These
objects are similar to the objects in \CC, except that they {\em should not
have any static data members}\footnote{ This restriction makes \charmpp\
programs portable across distributed and shared memory architectures, as well
as clusters of shared memory multiprocessors. If one feels that these
restrictions are too severe, one is encouraged to look at the portability
macros of Converse, that make it possible to write portable programs in
presence of global or static variables.}. These objects are created
synchronously on the local processor (using a {\tt new} operator in \CC), and
their methods could be synchronously invoked only from the local processor.
These objects are not known to the \charmpp\ runtime system, and thus they need
not be mentioned in the module interface files.

\subsubsection{Messages}

Messages supply data arguments to the asynchronous remote method invocation.
These objects are treated differently from other objects in \charmpp\ by the
runtime system, and therefore they should be specified in the interface file of
the module.  Messages are instances of \CC\ classes that are subclassed from a
special class that is generated by the \charmpp\ interface translator.  Another
variation of communication objects is conditionally packed and unpacked. This
variation should be used when one wants to send messages that contain pointers
to the data rather than the actual data to other processors. This type of
communication objects contains two methods: \kw{pack}, and \kw{unpack}.  These
messages are specified differently in the interface file for the module.  The
third variation of communication objects is called {\em varsize} messages.
Varsize messages is an effective optimization on conditionally packed messages,
and have to be made known to the \charmpp\ runtime using a special keyword in
the interface file.

\subsubsection{Chares}

Chares are the most important entities in a \charmpp\ program. These concurrent
objects are different from sequential \CC\ objects in many ways. Syntactically,
Chares are instances of \CC\  classes that are derived from a system-provided
class called \kw{Chare}. Also, in addition to the usual \CC\ private and public
data and method members, they contain some public methods called {\em entry
methods}. These entry methods do not return anything (they are {\tt void}
methods), and take at most one argument, which is a pointer to a message.
Chares are {\em accessed} using a proxy (an object of a specialized class
generated by the \charmpp\ interface translator) or using a handle (a \kw{
CkChareID} structure defined in \charmpp), rather than a pointer as in \CC.
Semantically, they are different from \CC\ objects because they can be created
asynchronously from remote processors, and their entry methods also could be
invoked asynchronously from the remote processors. Since the constructor method
is invoked from remote processor (while creating a chare), every chare should
have its constuctors as entry methods (with at most one message pointer
parameter). These chares and their entry methods have to be specified in the
interface file.

\subsubsection{Chare Groups}

Chare Groups\footnote{ These were called Branch Office Chares (BOC) in earlier
version of Charm.} are a special type of concurrent objects.  Each chare group
is a collection of chares, with one representative (group member) on each
processor. All the members of a chare group share a globally unique name
(handle, defined by Charm kernel to be of type \kw{CkGroupID}). An entire chare
group could be addressed using this global handle, and an individual member of
a chare group can be addressed using the global handle, and a processor number.
Chare groups are instances of \CC\ classes subclassed from a system-provided
class called \kw{Group}. The Charm kernel has to be notified that these chares
are semantically different, and therefore chare groups have a different
declaration in the interface specification file.

\subsubsection{Chare Nodegroups}

Chare nodegroups are very similar to chare groups except that instead of having
one groupmember on each processor, the nodegroup has one member on each shared
memory multiprocessor node. Note that \charmpp\ (and its underlying runtime
system Converse) distinguish between processors and nodes. A node consists of
one or more processors that share an address space. The last few years have
seen emergence of fast SMP systems of small (2-4 processors) to large (32-64
processors) number of processors per node. A network of such SMP nodes is the
most general model of parallel computers, making pure distributed and pure
shared memory systems mere special cases. \charmpp\ is built on top of this
machine abstraction, and Chare nodegroups embody this abstraction in a higher
level language construct. Sematically, methods invoked on a nodegroup member
could be executed on any processor within that node. This fact can be utilized
for supporting load balance across processors within a node. However, this also
means that different processors within a node could be executing methods of the
same nodegroup member simultaneously, thus leading to common problems
associated with shared address space programming. However, \charmpp\ eases such
problems by allowing the programmer to specify an entry method of a nodegroup
to be {\em exclusive}, thus guaranteeing that no other {\em exclusive} method
of that nodegroup member can execute simultaneously within the node.

\subsubsection{Chare Arrays}

Chare arrays are collections of chares. However unlike chare groups or
nodegroups, arrays are not constrained by characteristics of the underlying
parallel machine such as number of processors or nodes. Thus, chare arrays can
have any number of {\em elements}. The array elements themselves are chares,
and methods can be invoked on individual array elements as usual. However, what
distinguishes chare arrays from the other entities in \charmpp\ is that the
dynamic load balancing framework in \charmpp\ (LB Framework) treats them as
objects that can be migrated across processors. Thus, the runtime system keeps
track of computational load across the system, and also the time spent in
execution of entry methods on array elements, and then employs some smart
strategies to redistribute array elements across the available processors.
Chare arrays is a recent addition to \charmpp\ in response to various dynamic
and irregular applications of parallel computing. Currently, chare arrays are
implemented as a library on top of the Charm kernel. However, the \charmpp\
interface translator recognizes them and has special syntax for describing
them.

