2 CHARM++

CHARM++ is an object-oriented parallel programming library for C++. It differs from traditional message passing programming libraries (such as MPI) in that CHARM++ is ``message-driven''. Message-driven parallel programs do not block the processor waiting for a message to be received. Instead, each message carries with itself a computation that the processor performs on arrival of that message. The underlying runtime system of CHARM++ is called CONVERSE, which implements a ``scheduler'' that chooses which message to schedule next (message-scheduling in CHARM++ involves locating the object for which the message is intended, and executing the computation specified in the incoming message on that object). A parallel object in CHARM++ is a C++ object on which a certain computations can be asked to performe from remote processors.

CHARM++ programs exhibit latency tolerance since the scheduler always picks up the next available message rather than waiting for a particular messageto arrive. They also tend to be modular, because of their object-based nature. Most importantly, CHARM++ programs can be dynamically load balanced, because the messages are directed at objects and not at processors; thus allowing the runtime system to migrate the objects from heavily loaded processors to lightly loaded processors. It is this feature of CHARM++ that we utilize for AMPI.

Since many CSE applications are originally written using MPI, one would have to do a complete rewrite if they were to be converted to CHARM++ to take advantage of dynamic load balancing. This is indeed impractical. However, CONVERSE - the runtime system of CHARM++ - came to our rescue here, since it supports interoperability between different parallel programming paradigms such as parallel objects and threads. Using this feature, we developed AMPI, an implementation of a significant subset of MPI-1.1 standard over CHARM++. AMPI is described in the next section.