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