90c69d7cd72786efd9ce207a24c975668d834b02
[charm.git] / doc / charm++ / intro.tex
1 \section{Introduction}
2
3 This manual describes \charmpp, an object oriented portable parallel
4 programming language based on \CC. Its program structure, execution
5 model, interface language constructs and runtime system calls are
6 described here\footnote{For a description of the underlying design
7 philosophy please refer to the following papers :\\
8     L. V. Kale and Sanjeev Krishnan,
9     {\em ``\charmpp : Parallel Programming with Message-Driven Objects''},
10     in ``Parallel Programming Using \CC'',
11     MIT Press, 1995. \\
12     L. V. Kale and Sanjeev Krishnan,
13     {\em ``\charmpp : A Portable Concurrent Object Oriented System
14     Based On \CC''},
15     Proceedings of the Conference on Object Oriented Programming,
16     Systems, Languages and Applications (OOPSLA), September 1993.
17 }.
18
19 \charmpp\ has continuously evolved since the OOPSLA 1993 paper.  The earlier
20 versions modified the \CC\ syntax to support \charmpp\ primitives, and
21 contained a full-fledged \charmpp\ translator that parsed the \charmpp\
22 syntactic extensions as well as the \CC\ syntax to produce a \CC\ program,
23 which was later compiled using a \CC\ compiler.  The current version does not
24 augment the \CC{} syntax, and does not use a \charmpp\ translator as in previous
25 versions. Instead, the older constructs are converted to calls into the runtime
26 library, several new constructs are added, and minimal language constructs are
27 used to describe the interfaces.
28
29 \charmpp\ is an explicitly parallel language based on \CC\ with a runtime
30 library for supporting parallel computation called the Charm kernel.  It
31 provides a clear separation between sequential and parallel objects.  The
32 execution model of \charmpp\ is message driven, thus helping one write programs
33 that are latency-tolerant.  \charmpp\ supports dynamic load balancing while
34 creating new work as well as periodically, based on object migration.  Several
35 dynamic load balancing strategies are provided.  \charmpp\ supports both
36 irregular as well as regular, data-parallel applications.  It is based on the
37 {\sc Converse} interoperable runtime system for parallel programming.
38
39 Currently the parallel platforms supported by \charmpp\ are the BlueGene/L,BlueGene/P, PSC
40 Lemieux, IBM SP, SGI Origin2000, Cray XT3/4, Cray X1, Cray T3E, a single workstation or a
41 network of workstations from Sun Microsystems (Solaris), IBM RS-6000 (AIX) SGI
42 (IRIX 5.3 or 6.4), HP (HP-UX), Intel x86 (Linux, Windows 98/2000/XP), Intel
43 IA64, Intel x86\_64, multicore x86 and x86\_64, and Apple Mac. The communication protocols and infrastructures supported
44 by \charmpp\ are UDP, TCP, Myrinet, Infiniband, Quadrics Elan, Shmem, MPI and
45 NCSA VMI.  \charmpp\ programs can run without changing the source on all these
46 platforms.  Please see the \charmpp{}/\converse{} Installation and
47 Usage \htmladdnormallink{Manual}{http://charm.cs.uiuc.edu/manuals/html/install/manual.html}
48 for details about installing, compiling and running \charmpp\ programs.
49
50 \subsection{Overview}
51
52 \charmpp\ is an object oriented parallel language. What sets \charmpp\ apart
53 from traditional programming models such as message passing and shared variable
54 programming is that the execution model of \charmpp\ is message-driven.
55 Therefore, computations in \charmpp\ are triggered based on arrival of
56 associated messages. These computations in turn can fire off more messages to
57 other (possibly remote) processors that trigger more computations on those
58 processors.
59
60 At the heart of any \charmpp\ program is a scheduler that repetitively chooses
61 a message from the available pool of messages, and executes the computations
62 associated with that message.
63
64 The programmer-visible entities in a \charmpp\ program are:
65
66 \begin{itemize}
67 \item Concurrent Objects : called {\em chares}\footnote{
68       Chare (pronounced {\bf ch\"ar}, \"a as in c{\bf a}rt) is Old 
69       English for chore.
70       }
71 \item Communication Objects : Messages
72 \item Readonly data
73 \end{itemize}
74
75 \charmpp\ starts a program by creating a single \index{chare} instance of each
76 {\em mainchare} on processor 0, and invokes constructor methods of these
77 chares.  Typically, these chares then creates a number of other \index{chare}
78 chares, possibly on other processors, which can simultaneously work to solve
79 the problem at hand.
80
81 Each \index{chare}chare contains a number of \index{entry method}{\em entry
82 methods}, which are methods that can be invoked from remote processors. The
83 \charmpp\ runtime system needs to be explicitly told about these methods, via
84 an {\em interface} in a separate file.  The syntax of this interface
85 specification file is described in the later sections.
86
87 \charmpp\ provides system calls to asynchronously create remote \index{chare}
88 chares and to asynchronously invoke entry methods on remote chares by sending
89 \index{message} messages to those chares. This asynchronous
90 \index{message}message passing is the basic interprocess communication
91 mechanism in \charmpp. However, \charmpp\ also permits wide variations on this
92 mechanism to make it easy for the programmer to write programs that adapt to
93 the dynamic runtime environment.  These possible variations include
94 prioritization (associating priorities with method invocations), conditional
95 \index{message packing}message packing and unpacking (for reducing messaging
96 overhead), \index{quiescence}quiescence detection (for detecting completion of
97 some phase of the program), and dynamic load balancing (during remote object
98 creation). In addition, several libraries are built on top of \charmpp\ that
99 can simplify otherwise arduous parallel programming tasks.
100
101 The following sections provide detailed information about various features of
102 \charmpp\ programming system.
103
104 \subsection{History}
105
106 The {\sc Charm} software was developed as a group effort of the Parallel
107 Programming Laboratory at the University of Illinois at Urbana-Champaign.
108 Researchers at the Parallel Programming Laboratory keep \charmpp\ updated for
109 the new machines, new programming paradigms, and for supporting and simplifying
110 development of emerging applications for parallel processing.  The earliest
111 prototype, Chare Kernel(1.0), was developed in the late eighties. It consisted
112 only of basic remote method invocation constructs available as a library.  The
113 second prototype, Chare Kernel(2.0), a complete re-write with major design
114 changes.  This included C language extensions to denote Chares, messages and
115 asynchronous remote method invocation.  {\sc Charm}(3.0) improved on this
116 syntax, and contained important features such as information sharing
117 abstractions, and chare groups (called Branch Office Chares).  {\sc Charm}(4.0)
118 included \charmpp\ and was released in fall 1993.  \charmpp\ in its initial
119 version consisted of syntactic changes to \CC\ and employed a special
120 translator that parsed the entire \CC\ code while translating the syntactic
121 extensions.  {\sc Charm}(4.5)  had a major change that resulted from a
122 significant shift in the research agenda of the Parallel Programming
123 Laboratory. The message-driven runtime system code of the \charmpp\ was
124 separated from the actual language implementation, resulting in an
125 interoperable parallel runtime system called {\sc
126 Converse}. The \charmpp\ runtime system was
127 retargetted on top of {\sc Converse}, and popular programming paradigms such as
128 MPI and PVM were also implemented on {\sc Converse}. This allowed
129 interoperability between these paradigms and \charmpp. This release also
130 eliminated the full-fledged \charmpp\ translator by replacing syntactic
131 extensions to \CC\ with \CC\ macros, and instead contained a small language and
132 a translator for describing the interfaces of \charmpp\ entities to the runtime
133 system.  This version of \charmpp, which, in earlier releases was known as {\em
134 Interface Translator \charmpp}, is the default version of \charmpp\ now, and
135 hence referred simply as {\bf \charmpp}.  In early 1999, the runtime system of
136 \charmpp\ was formally named the Charm Kernel, and was rewritten in \CC.
137 Several new features were added. The interface language underwent significant
138 changes, and the macros that replaced the syntactic extensions in original
139 \charmpp, were replaced by natural \CC\ constructs. Late 1999, and early
140 2000 reflected several additions to \charmpp{}, when a load balancing
141 framework and migratable objects were added to \charmpp{}.