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 PSC Lemieux,
  40 IBM SP, SGI Origin2000, Cray X1, Cray T3E, Intel Paragon,
  41 a single workstation or a network of workstations from Sun
  42 Microsystems (Solaris), IBM RS-6000 (AIX) SGI (IRIX 5.3
  43 or 6.4), HP (HP-UX), Intel x86 (Linux, Windows 98/2000/XP) and Intel IA64.
  44 The communication protocols and infrastructures supported by \charmpp\
  45 are UDP, TCP, Myrinet, Quadrics Elan, Shmem, MPI and VMI.
  46 \charmpp\ programs can run without changing the source on all these platforms.
  47 Please see the \charmpp{}/\converse{} Installation and Usage Manual for
  48 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{}.