4c6103737846637d90f8616d44e904928c8e4813
[charm.git] / doc / charm++ / intro.tex
1 \section{Programming and Execution Model}
2
3 \charmpp\ is an explicitly parallel language based on \CC\ with a runtime
4 library for supporting parallel computation called the Charm Runtime System.  It
5 provides a clear separation between sequential and parallel objects.  The
6 execution model of \charmpp\ is message driven, thus helping one write programs
7 that are latency-tolerant.  \charmpp\ supports dynamic load balancing while
8 creating new work as well as periodically, based on object migration.  Several
9 dynamic load balancing strategies are provided.  \charmpp\ supports both
10 irregular as well as regular, data-parallel applications.  It is built on top of the
11 {\sc Converse} interoperable runtime system for parallel programming.
12
13 Currently the parallel platforms supported by \charmpp\ are the
14 BlueGene/L,BlueGene/P, BlueGene/Q, Cray XT, XE and XK series
15 (including XK6 and XE6), 
16 % XT3/4, Cray X1, Cray T3E,
17 a single workstation or a network of
18 workstations (including x86 (running Linux, Windows, MacOS)), etc.
19 The communication protocols and infrastructures supported by
20 \charmpp\ are UDP, TCP, Myrinet, Infiniband, uGNI, and PAMI. 
21 \charmpp\ programs can run without changing the source
22 on all these platforms.  Please see the \charmpp{}/\converse{}
23 Installation and Usage
24 \htmladdnormallink{Manual}{http://charm.cs.uiuc.edu/manuals/html/install/manual.html}
25 for details about installing, compiling and running
26 \charmpp\ programs.
27
28 \subsection{\charmpp\ Execution Model}
29
30 A \charmpp\ program consists of a number of \charmpp\ objects distributed
31 across the available number of processors. Thus, the basic unit of parallel
32 computation in \charmpp\ programs is the {\em chare}\index{chare}, a \charmpp\
33 object that can be created on any available processor and can be accessed from
34 remote processors.  A \index{chare}chare is similar to a process, an actor, an
35 ADA task, etc.  \index{chare}Chares are created dynamically, and many chares
36 may be active simultaneously.  Chares send \index{message}{\em messages} to one
37 another to invoke methods asynchronously.  Conceptually, the system maintains a
38 ``work-pool'' consisting of seeds for new \index{chare}chares, and
39 \index{message}messages for existing chares. The Charm++ runtime system ({\em
40 Charm RTS}) may pick multiple items, non-deterministically, from this pool
41 and execute them.  
42
43 Methods of a \index{chare}chare that can be remotely invoked are called
44 \index{entry method}{\em entry} methods.  Entry methods may take marshalled
45 parameters, or a pointer to a message object.  Since \index{chare}chares can
46 be created on remote processors, obviously some constructor of a chare needs
47 to be an entry method.  Ordinary entry methods\footnote{``Threaded'' or
48 ``synchronous'' methods are different.} are completely non-preemptive--
49 \charmpp\ will never interrupt an executing method to start any other work,
50 and all calls made are asynchronous.
51
52 \charmpp\ provides dynamic seed-based load balancing. Thus location (processor
53 number) need not be specified while creating a remote \index{chare}chare. The
54 Charm RTS will then place the remote chare on a least loaded processor. Thus
55 one can imagine chare creation as generating only a seed for the new chare,
56 which may {\em take root} on the most {\em fertile} processor. Charm RTS
57 identifies a \index{chare}chare by a {\em ChareID}.  Since user code does not
58 need to name a chares' processor, chares can potentially migrate from one
59 processor to another.  (This behavior is used by the dynamic load-balancing
60 framework for chare containers, such as arrays.)
61
62 Other \charmpp\ objects are collections of chares. They are: {\em
63 chare-arrays}, \index{group}{\em chare-groups}, and \index{nodegroup}{\em
64 chare-nodegroups}, referred to as {\em arrays}, {\em groups}, and {\em
65 nodegroups} throughout this manual. An array is a collection of arbitrary
66 number of migratable chares, indexed by some index type, and mapped to
67 processors according to a user-defined map group. A group (nodegroup) is a
68 collection of chares, one per processor (SMP node), that is addressed using
69 a unique system-wide name.
70
71 Every \charmpp\ program must have at least one \kw{mainchare}.  Each
72 \kw{mainchare} is created by the system on processor 0 when the \charmpp\
73 program starts up.  Execution of a \charmpp\ program begins with the Charm
74 Kernel constructing all the designated \kw{mainchare}s.  For a \kw{mainchare} named X, execution starts at constructor X() or X(CkArgMsg *) which are equivalent.
75 Typically, the
76 \kw{mainchare} constructor starts the computation by creating arrays, other
77 chares, and groups.  It can also be used to initialize shared \kw{readonly}
78 objects.
79
80 The only method of communication between processors in \charmpp\ is
81 asynchronous \index{entry method} entry method invocation on remote chares.
82 For this purpose, Charm RTS needs to know the types of
83 \index{chare}chares in the user program, the methods that can be invoked on
84 these chares from remote processors, the arguments these methods take as
85 input etc. Therefore, when the program starts up, these user-defined
86 entities need to be registered with Charm RTS, which assigns a unique
87 identifier to each of them. While invoking a method on a remote object,
88 these identifiers need to be specified to Charm RTS. Registration of
89 user-defined entities, and maintaining these identifiers can be cumbersome.
90 Fortunately, it is done automatically by the \charmpp\ interface translator.
91 The \charmpp\ interface translator generates definitions for {\em proxy}
92 objects. A proxy object acts as a {\em handle} to a remote chare. One
93 invokes methods on a proxy object, which in turn carries out remote method
94 invocation on the chare.
95
96 In addition, the \charmpp\ interface translator provides ways to enhance the
97 basic functionality of Charm RTS using user-level threads and futures. These
98 allow entry methods to be executed in separate user-level threads.  These
99 \index{threaded} {\em threaded} entry methods may block waiting for data by
100 making {\em synchronous} calls to remote object methods that return results in
101 messages.
102
103 \charmpp\ program execution is terminated by the \kw{CkExit} call.  Like the
104 \kw{exit} system call, \kw{CkExit} never returns. The Charm RTS ensures
105 that no more messages are processed and no entry methods are called after a
106 \kw{CkExit}. \kw{CkExit} need not be called on all processors; it is enough
107 to call it from just one processor at the end of the computation.
108
109 The following sections provide detailed information about various features of the
110 \charmpp\ programming system.\footnote{For a description of the underlying design
111 philosophy please refer to the following papers :\\
112     L. V. Kale and Sanjeev Krishnan,
113     {\em ``\charmpp : Parallel Programming with Message-Driven Objects''},
114     in ``Parallel Programming Using \CC'',
115     MIT Press, 1995. \\
116     L. V. Kale and Sanjeev Krishnan,
117     {\em ``\charmpp : A Portable Concurrent Object Oriented System
118     Based On \CC''},
119     Proceedings of the Conference on Object Oriented Programming,
120     Systems, Languages and Applications (OOPSLA), September 1993.
121 }.
122