Introduction to Charm++ Concepts

What is Charm++?

Charm++ is an object-oriented asynchronous message passing parallel programming paradigm. What does all that mean?

Let's start with "programming paradigm." By programming paradigm, we mean Charm++ is a way of writing a program (a programming model). Charm++ is not a programming language in and of itself. Instead, Charm++ uses the C++ programming language as it's base language. Charm++ adds additional functionality and structure on top of C++ that allows the programmer to solve the problem at hand.

By "parallel", we mean that Charm++ is used to write parallel applications. Generally speaking, parallel applications are applications where multiple threads of execution are executing simultaneously. This can be several threads time sharing a single processing element; or, several threads time sharing many processing elements. Each thread of execution is a sequence of sequential code (that is, code that executes in program order from start to finish without communicating with another thread of execution). In terms of Charm++, the term parallel simply means that several things may be occurring at any given moment (one or more chunks of code being executed, messages being passed between chares, and so on).

"Object-oriented" basically means the same thing that it means in the C++ programming language. The program is broken down into a logical collection of objects that interact with each other. This same concept is true for Charm++. In Charm++, however, there are special objects called chares. Chares will be discussed in more detail later. For now, each chare object may contain some state (i.e. data), send and receive messages, and will perform some task in response to receiving a message (that is, execute a special member function called an entry method).

By "asynchronous message passing", we mean that the chare objects communicate with each other by sending messages to one another. The asynchronous keyword means that the messages are sent in a manner that is asynchronous to the execution of code associated with the chare objects. That is to say, if code operating on a chare object decides to send a message to another chare object, the sending of the message occurs in an asynchronous manner to the code execution (the code directly after the send immediately continues execution while the message travels towards the target chare). The opposite is also true; a chare object can receive a message from another chare object at any time regardless of what the receiving chare is doing at that particular moment. How messages are passed, what code is executed, and so on will be discussed later in the tutorial. It is worth noting that the passing of messages is also referred to as method invocation or remote method invocation since, from the perspective of the sending chare object, the code simply looks like the calling code is invoking a member function of the target chare.

What is a Charm++ Program?

At a high-level, from the programmer's perspective, a Charm++ program is simply a collection of chare objects. Each chare object has some state associated with it. The chare objects communicate by sending messages to one another. When a particular chare object receives a message, it will execute an entry method to processes the message. This

Figure 1: User's View of a Charm++ Application

entry method may perform one or more operations/calculations, it may send more messages to other chare objects, it may buffer the contents of the message for later processing, or it may do nothing at all. This is how forward progression is made in the overall application. One chare sends a message to another chare, the receiving chare does some computation and then sends out more messages to other chares, and so on, and so on. Execution begins with a special chare called the main chare (similar to how execution of a C++ program begins with the execution of a special function called main).

It is worth pointing out that the description of a Charm++ application does not involve the number of processing elements (i.e. one thread per processing element), what type of processing elements are involved, how many chares there are per processing element, or even how data is transfered between processing elements. Charm++ applications are simply written in terms of the chare objects. The programmer does not have to worry about the number of processing elements that will be available when the program is executed or what type of interconnect (network) will be used to connect the processing elements together. All of these details are left to an intelligent runtime system called the Charm++ Runtime System. The Charm++ Runtime System takes care of mapping each of the chares to the physical processing elements, routing messages over the interconnect, and so on.

Chare Objects

Each of the chare objects in the Charm++ application can be thought of as independent entities. Each chare object has it's own state (that is, data local to it). Chare objects in the application cannot directly access the state of another chare objects, however, any chare object can directly communicate with any other chare object. The overall set of chare objects in the application is commonly referred to as the global object space. Any chare object in the global object space can request information on another chare object's state by sending the chare object a message requesting the information.

For the purposes of this tutorial, we will use two terms: chare class and chare object. These terms have the same basic meaning as their C++ equivalents, class and object, respectively. A chare class defines a type of chare object (the blueprints of a chare object). A chare object is a specific instance of a chare class. Another term that will be used in this tutorial is chare array. A chare array is simply an array of chare objects (just like an integer array is an array of integers in C++). See the section on Chare Collections below.

There is one special chare object in a Charm++ application, the main chare object. The main chare object acts as the entry point of the Charm++ application in a similar manner to the main function in a C++ application (see Entry Methods below).

Messages

The chare objects communicate with each other by sending messages to one another. In Charm++, this process is also referred to as remote method invocation since the sending chare object simply calls one of the receiving chare object's entry methods (more on entry methods later). From the programmer's perspective, the code basically looks like it is calling a member function on the target chare object.

Entry Methods

Entry methods are special member functions of the chare class. The difference between a normal C++ member function and a Charm++ entry methods is that Charm++ entry methods act as the reception points for messages (or, in other words, they are the member functions that can be remotely invoked by other chare objects). When one chare object does a remote method invocation on another chare object, the data being sent is packed into a message and passed to the receiving chare object. Once the receiving chare object receives the message, the entry method that was specified by the sending chare object is invoked (executed) and the data in the message is passed to that entry method.

Each of the chare classes also has constructor entry methods (basically the same thing as a constructor in C++). When a chare object is created, this constructor entry method is automatically invoked by the Charm++ Runtime System to create the chare object (once again, similar to what is done for an object in C++). The execution of a Charm++ application begins with the execution of the main chare object's constructor.

There are two aspects of entry methods that make them different from standard C++ member functions. First, entry methods do not have return values (i.e. they return void). Second, from the perspective of the calling chare object, the entry method returns immediately and the code of the calling chare object continues to execute. This does not mean that the target entry method has executed, only that a message has been sent to the chare object which will cause the target entry method to execute at some time in the future. Both of these aspects of entry methods are directly related to the message passing nature of Charm++. Invoking an entry method on a chare object does not cause the entry method to execute immediately nor is any value produced immediately. Instead a message is sent to the target chare and the entry method will be executed at some point in the future.

Proxies

Figure 2: Proxies and the Global Object Space

Because the actual chare objects in the global object space in a Charm++ program are spread out across the various processing elements, it is not always possible for two chare objects to directly communicate with each other. Instead, for one chare object to invoke an entry method on another chare object, the sending chare object must first have a reference called a proxy to the target chare object. The proxy objects hide the details of the actual communication from the programmer. Entry methods are called on the proxy object as if the chare object itself were local to the current physical processor. The Charm++ Runtime System takes care of locating the actual chare object in the global object space on behalf of the chare object. See Figure 2.

Chare Collections

In actual Charm++ applications, it is more common to see collections of chare objects rather than individual chare objects. The collection of chare objects is spread out across the processors and all members are commonly performing a similar operation on different pieces of data. There are several types of chare collections.

Each collection within a program is represented by a unique handle. This handle is visible to all processors (can be transfered between processors) and can be used to access the members of the collection.

Chare Arrays

As was previously mentioned, a chare array is simply an array of chare objects. The array can indexed using a simple integer index similar to how C++ arrays are indexed (int arrays, for example). Chare arrays can be single or multidimensional (indexing schemes for 1D through 6D are provided). Chare arrays can also be indexed using more complex schemes such as a bit vector or even use user defined objects to index into the array.

Initially, the chare array elements are spread out according to a mapping scheme (with round-robin being the default). However, because the chare array elements are migratable chare objects, they can be moved between the processors on an individual basis. The Charm++ Runtime System will migrate the chare array elements between the processors based on runtime data that it gathers in an effort to balance the processing load on all of the processors. The programmer does not have to concern themselves with where each of the individual chare array elements are. Even if a chare array element is moved from one processor to another, the programmer still refers to it as the same array element (e.g. myChareArray[i] for the ith element in the myChareArray chare array). The Charm++ Runtime System takes care of making sure the message are redirected to the appropriate processor.

Chare Groups

A chare group is a collection where each of the physical processors available to the application has one, and only one, representative (chare object) located on it.

Chare NodeGroups

A chare nodegroup is similar to a chare group. The difference is that there is only a single representative per node, instead of per processor.