3.4 Messages

A message encapsulates all the parameters sent to an entry method. Since the parameters are already encapsulated, sending messages is often more efficient than parameter marshalling. In addition, messages are easier to queue and store on the receive side.

The largest difference between parameter marshalling and messages is that entry methods keep the messages passed to them. Thus each entry method must be passed a new message. On the receiving side, the entry method must either store the passed message or explicitly delete it, or else the message will never be destroyed, wasting memory.

Several kinds of message are available. Regular CHARM++ messages are objects of fixed size. One can have messages that contain pointers or variable length arrays (arrays with sizes specified at runtime) and still have these pointers to be valid when messages are sent across processors, with some additional coding. Also available is a mechanism for assigning priorities to messages that applies all kinds of messages. A detailed discussion of priorities appears later in this section.

Like all other entities involved in asynchronous method invocation, messages need to be declared in the .ci file. In the .ci file (the interface file), a message is declared as:

 message MessageType;

A message that contains variable length arrays is declared as:

 message MessageType {
   type1 var_name1[];
   type2 var_name2[];
   type3 var_name3[];
};

If the name of the message class is MessageType, the class must inherit publicly from a class whose name is CMessage_MessageType. This class is generated by the charm translator. Then message definition has the form:

 class MessageType : public CMessage_MessageType {
    // List of data and function members as in  C++
 };

3.4.1 Message Creation and Deletion

Messages are allocated using the C++ new operator:

 MessageType *msgptr =
  new [(int sz1, int sz2, ... , int priobits=0)] MessageType[(constructor arguments)];

The optional arguments to the new operator are used when allocating messages with variable length arrays or prioritized messages. sz1, sz2, ... denote the size (in appropriate units) of the memory blocks that need to be allocated and assigned to the pointers that the message contains. The priobits argument denotes the size of a bitfield (number of bits) that will be used to store the message priority.

For example, to allocate a message whose class declaration is:

class Message : public CMessage_Message {
  // .. fixed size message
  // .. data and method members
};

do the following:

Message *msg = new Message;

To allocate a message whose class declaration is:

class VarsizeMessage : public CMessage_VarsizeMessage {
 public:
  int *firstArray;
  double *secondArray;
};

do the following:

VarsizeMessage *msg = new (10, 20) VarsizeMessage;

This allocates a VarsizeMessage, in which firstArray points to an array of 10 ints and secondArray points to an array of 20 doubles. This is explained in detail in later sections.

To add a priority bitfield to this message,

VarsizeMessage *msg = new (10, 20, sizeof(int)*8) VarsizeMessage;

Note, you must provide number of bits which is used to store the priority as the priobits parameter. The section on prioritized execution describes how this bitfield is used.

In Section 3.4.3 we explain how messages can contain arbitrary pointers, and how the validity of such pointers can be maintained across processors in a distributed memory machine.

When a message is sent to a chare, the programmer relinquishes control of it; the space allocated to the message is freed by the system. When a message is received at an entry point it is not freed by the runtime system. It may be reused or deleted by the programmer. Messages can be deleted using the standard C++ delete operator.

There are no limitations of the methods of message classes except that the message class may not redefine operators new or delete.

3.4.2 Messages with Variable Length Arrays

An ordinary message in CHARM++ is a fixed size message that is allocated internally with an envelope which encodes the size of the message. Very often, the size of the data contained in a message is not known until runtime. One can use packed messages to alleviate this problem. However, it requires multiple memory allocations (one for the message, and another for the buffer.) This can be avoided by making use of a varsize message. In varsize messages, the space required for these variable length arrays is allocated with the message such that it is contiguous to the message.

Such a message is declared as

 message mtype {
   type1 var_name1[];
   type2 var_name2[];
   type3 var_name3[];
 };

in CHARM++ interface file. The class mtype has to inherit from CMessage_mtype. In addition, it has to contain variables of corresponding names pointing to appropriate types. If any of these variables (data members) are private or protected, it should declare class CMessage_mtype to be a ``friend'' class. Thus the mtype class declaration should be similar to:

class mtype : public CMessage_mtype {
 private:
   type1 *var_name1;
   type2 *var_name2;
   type3 *var_name3;
   friend class CMessage_mtype;
};

An Example

Suppose a CHARM++ message contains two variable length arrays of types int and double:

class VarsizeMessage: public CMessage_VarsizeMessage {
  public:
    int lengthFirst;
    int lengthSecond;
    int* firstArray;
    double* secondArray;
    // other functions here
};

Then in the .ci file, this has to be declared as:

message VarsizeMessage {
  int firstArray[];
  double secondArray[];
};

We specify the types and actual names of the fields that contain variable length arrays. The dimensions of these arrays are NOT specified in the interface file, since they will be specified in the constructor of the message when message is created. In the .h or .C file, this class is declared as:

class VarsizeMessage : public CMessage_VarsizeMessage {
  public:
    int lengthFirst;
    int lengthSecond;
    int* firstArray;
    double* secondArray;
    // other functions here
};

The interface translator generates the CMessage_VarsizeMessage class, which contains code to properly allocate, pack and unpack the VarsizeMessage.

One can allocate messages of the VarsizeMessage class as follows:

// firstArray will have 4 elements
// secondArray will have 5 elements
VarsizeMessage* p = new(4, 5, 0) VarsizeMessage;
p->firstArray[2] = 13;     // the arrays have already been allocated
p->secondArray[4] = 6.7;

Another way of allocating a varsize message is to pass a sizes in an array instead of the parameter list. For example,

int sizes[2];
sizes[0] = 4;               // firstArray will have 4 elements
sizes[1] = 5;               // secondArray will have 5 elements
VarsizeMessage* p = new(sizes, 0) VarsizeMessage;
p->firstArray[2] = 13;     // the arrays have already been allocated
p->secondArray[4] = 6.7;

No special handling is needed for deleting varsize messages.

3.4.3 Message Packing

The CHARM++ interface translator generates implementation for three static methods for the message class CMessage_mtype. These methods have the prototypes:

    static void* alloc(int msgnum, size_t size, int* array, int priobits);
    static void* pack(mtype*);
    static mtype* unpack(void*);

One may choose not to use the translator-generated methods and may override these implementations with their own alloc, pack and unpack static methods of the mtype class. The alloc method will be called when the message is allocated using the C++ new operator. The programmer never needs to explicitly call it. Note that all elements of the message are allocated when the message is created with new. There is no need to call new to allocate any of the fields of the message. This differs from a packed message where each field requires individual allocation. The alloc method should actually allocate the message using CkAllocMsg, whose signature is given below:

void *CkAllocMsg(int msgnum, int size, int priobits);

For varsize messages, these static methods alloc, pack, and unpack are generated by the interface translator. For example, these methods for the VarsizeMessage class above would be similar to:

// allocate memory for varmessage so charm can keep track of memory
static void* alloc(int msgnum, size_t size, int* array, int priobits)
{
  int totalsize, first_start, second_start;
  // array is passed in when the message is allocated using new (see below).
  // size is the amount of space needed for the part of the message known
  // about at compile time.  Depending on their values, sometimes a segfault
  // will occur if memory addressing is not on 8-byte boundary, so altered
  // with ALIGN8
  first_start = ALIGN8(size);  // 8-byte align with this macro
  second_start = ALIGN8(first_start + array[0]*sizeof(int));
  totalsize = second_start + array[1]*sizeof(double);
  VarsizeMessage* newMsg =
    (VarsizeMessage*) CkAllocMsg(msgnum, totalsize, priobits);
  // make firstArray point to end of newMsg in memory
  newMsg->firstArray = (int*) ((char*)newMsg + first_start);
  // make secondArray point to after end of firstArray in memory
  newMsg->secondArray = (double*) ((char*)newMsg + second_start);

  return (void*) newMsg;
}

// returns pointer to memory containing packed message
static void* pack(VarsizeMessage* in)
{
  // set firstArray an offset from the start of in
  in->firstArray = (int*) ((char*)in->firstArray - (char*)in);
  // set secondArray to the appropriate offset
  in->secondArray = (double*) ((char*)in->secondArray - (char*)in);
  return in;
}

// returns new message from raw memory
static VarsizeMessage* VarsizeMessage::unpack(void* inbuf)
{
  VarsizeMessage* me = (VarsizeMessage*)inbuf;
  // return first array to absolute address in memory
  me->firstArray = (int*) ((size_t)me->firstArray + (char*)me);
  // likewise for secondArray
  me->secondArray = (double*) ((size_t)me->secondArray + (char*)me);
  return me;
}

The pointers in a varsize message can exist in two states. At creation, they are valid C++ pointers to the start of the arrays. After packing, they become offsets from the address of the pointer variable to the start of the pointed-to data. Unpacking restores them to pointers.

3.4.4 Custom Packed Messages

In many cases, a message must store a non-linear data structure using pointers. Examples of these are binary trees, hash tables etc. Thus, the message itself contains only a pointer to the actual data. When the message is sent to the same processor, these pointers point to the original locations, which are within the address space of the same processor. However, when such a message is sent to other processors, these pointers will point to invalid locations.

Thus, the programmer needs a way to ``serialize'' these messages only if the message crosses the address-space boundary. CHARM++ provides a way to do this serialization by allowing the developer to override the default serialization methods generated by the CHARM++ interface translator. Note that this low-level serialization has nothing to do with parameter marshalling or the PUP framework described later.

Packed messages are declared in the .ci file the same way as ordinary messages:

message PMessage;

Like all messages, the class PMessage needs to inherit from CMessage_PMessage and should provide two static methods: pack and unpack. These methods are called by the CHARM++ runtime system, when the message is determined to be crossing address-space boundary. The prototypes for these methods are as follows:

static void *PMessage::pack(PMessage *in);
static PMessage *PMessage::unpack(void *in);

Typically, the following tasks are done in pack method:

• Determine size of the buffer needed to serialize message data.

• Allocate buffer using the CkAllocBuffer function. This function takes in two parameters: input message, and size of the buffer needed, and returns the buffer.

• Serialize message data into buffer (alongwith any control information needed to de-serialize it on the receiving side.

• Free resources occupied by message (including message itself.)

On the receiving processor, the unpack method is called. Typically, the following tasks are done in the unpack method:

• Allocate message using CkAllocBuffer function. Do not use new to allocate message here. If the message constructor has to be called, it can be done using the in-place new operator.

• De-serialize message data from input buffer into the allocated message.

• Free the input buffer using CkFreeMsg.

Here is an example of a packed-message implementation:

// File: pgm.ci
mainmodule PackExample {
  ...
  message PackedMessage;
  ...
};

// File: pgm.h
...
class PackedMessage : public CMessage_PackedMessage
{
  public:
    BinaryTree<char> btree; // A non-linear data structure
    static void* pack(PackedMessage*);
    static PackedMessage* unpack(void*);
    ...
};
...

// File: pgm.C
...
void*
PackedMessage::pack(PackedMessage* inmsg)
{
  int treesize = inmsg->btree.getFlattenedSize();
  int totalsize = treesize + sizeof(int);
  char *buf = (char*)CkAllocBuffer(inmsg, totalsize);
  // buf is now just raw memory to store the data structure
  int num_nodes = inmsg->btree.getNumNodes();
  memcpy(buf, &num_nodes, sizeof(int));  // copy numnodes into buffer
  buf = buf + sizeof(int);               // don't overwrite numnodes
  // copies into buffer, give size of buffer minus header
  inmsg->btree.Flatten((void*)buf, treesize);    
  buf = buf - sizeof(int);              // don't lose numnodes
  delete inmsg;
  return (void*) buf;
}

PackedMessage*
PackedMessage::unpack(void* inbuf)
{
  // inbuf is the raw memory allocated and assigned in pack
  char* buf = (char*) inbuf;
  int num_nodes;
  memcpy(&num_nodes, buf, sizeof(int));
  buf = buf + sizeof(int);
  // allocate the message through charm kernel
  PackedMessage* pmsg =
    (PackedMessage*)CkAllocBuffer(inbuf, sizeof(PackedMessage));
  // call "inplace" constructor of PackedMessage that calls constructor
  // of PackedMessage using the memory allocated by CkAllocBuffer,
  // takes a raw buffer inbuf, the number of nodes, and constructs the btree
  pmsg = new ((void*)pmsg) PackedMessage(buf, num_nodes);  
  CkFreeMsg(inbuf);
  return pmsg;
}
...
PackedMessage* pm = new PackedMessage();  // just like always
pm->btree.Insert('A');
...

While serializing an arbitrary data structure into a flat buffer, one must be very wary of any possible alignment problems. Thus, if possible, the buffer itself should be declared to be a flat struct. This will allow the C++ compiler to ensure proper alignment of all its member fields.

3.4.5 Prioritized Execution

By default, CHARM++ will process the messages you send in roughly FIFO order. For most programs, this behavior is fine. However, some programs need more explicit control over the order in which messages are processed. CHARM++ allows you to control queueing behavior on a per-message basis.

The simplest call available to change the order in which messages are processed is CkSetQueueing.

void CkSetQueueing(MsgType message, int queueingtype)

where queueingtype is one of the following constants:

  CK_QUEUEING_FIFO
  CK_QUEUEING_LIFO
  CK_QUEUEING_IFIFO
  CK_QUEUEING_ILIFO
  CK_QUEUEING_BFIFO
  CK_QUEUEING_BLIFO

The first two options, CK_QUEUEING_FIFO and CK_QUEUEING_LIFO, are used as follows:

  MsgType *msg1 = new MsgType ;
  CkSetQueueing(msg1, CK_QUEUEING_FIFO);

  MsgType *msg2 = new MsgType ;
  CkSetQueueing(msg2, CK_QUEUEING_LIFO);

When message msg1 arrives at its destination, it will be pushed onto the end of the message queue as usual. However, when msg2 arrives, it will be pushed onto the front of the message queue.

The other four options involve the use of priorities. To attach a priority field to a message, one needs to set aside space in the message's buffer while allocating the message. To achieve this, the size of the priority field in bits should be specified as a placement argument to the new operator, as described in Section 3.4.1. Although the size of the priority field is specified in bits, it is always padded to an integral number of ints. A pointer to the priority part of the message buffer can be obtained with this call:

unsigned int *CkPriorityPtr(MsgType msg)

There are two kinds of priorities which can be attached to a message: integer priorities and bitvector priorities. Integer priorities are quite straightforward. One allocates a message, setting aside enough space (in bits) in the message to hold the priority, which is an integer. One then stores the priority in the message. Finally, one informs the system that the message contains an integer priority using CkSetQueueing:

  MsgType *msg = new (8*sizeof(int)) MsgType;
  *CkPriorityPtr(msg) = prio;
  CkSetQueueing(msg, CK_QUEUEING_IFIFO);

The predefined constant CK_QUEUEING_IFIFO indicates that the message contains an integer priority, and that if there are other messages of the same priority, they should be sequenced in FIFO order (relative to each other). Similarly, a CK_QUEUEING_ILIFO is available. Note that MAXINT is the lowest priority, and NEGATIVE_MAXINT is the highest priority.

Bitvector priorities are somewhat more complicated. Bitvector priorities are arbitrary-length bit-strings representing fixed-point numbers in the range 0 to 1. For example, the bit-string ``001001'' represents the number .001001binary. As with the simpler kind of priority, higher numbers represent lower priorities. Unlike the simpler kind of priority, bitvectors can be of arbitrary length, therefore, the priority numbers they represent can be of arbitrary precision.

Arbitrary-precision priorities are often useful in AI search-tree applications. Suppose we have a heuristic suggesting that tree node should be searched before tree node . We therefore designate that node and its descendants will use high priorities, and that node and its descendants will use lower priorities. We have effectively split the range of possible priorities in two. If several such heuristics fire in sequence, we can easily split the priority range in two enough times that no significant bits remain, and the search begins to fail for lack of meaningful priorities to assign. The solution is to use arbitrary-precision priorities, i.e. bitvector priorities.

To assign a bitvector priority, two methods are available. The first is to obtain a pointer to the priority field using CkPriorityPtr, and to then manually set the bits using the bit-setting operations inherent to C. To achieve this, one must know the format of the bitvector, which is as follows: the bitvector is represented as an array of unsigned integers. The most significant bit of the first integer contains the first bit of the bitvector. The remaining bits of the first integer contain the next 31 bits of the bitvector. Subsequent integers contain 32 bits each. If the size of the bitvector is not a multiple of 32, then the last integer contains 0 bits for padding in the least-significant bits of the integer.

The second way to assign priorities is only useful for those who are using the priority range-splitting described above. The root of the tree is assigned the null priority-string. Each child is assigned its parent's priority with some number of bits concatenated. The net effect is that the entire priority of a branch is within a small epsilon of the priority of its root.

It is possible to utilize unprioritized messages, integer priorities, and bitvector priorities in the same program. The messages will be processed in roughly the following order:

• Among messages enqueued with bitvector priorities, the messages are dequeued according to their priority. The priority ``0000...'' is dequeued first, and ``1111...'' is dequeued last.

• Unprioritized messages are treated as if they had the priority ``1000...'' (which is the ``middle'' priority, it lies exactly halfway between ``0000...'' and ``1111...'').

• Integer priorities are converted to bitvector priorities. They are normalized so that the integer priority of zero is converted to ``1000...'' (the ``middle'' priority). To be more specific, the conversion is performed by adding 0x80000000 to the integer, and then treating the resulting 32-bit quantity as a 32-bit bitvector priority.

• Among messages with the same priority, messages are dequeued in FIFO order or LIFO order, depending upon which queuing strategy was used.

A final warning about prioritized execution: CHARM++ always processes messages in roughly the order you specify; it never guarantees to deliver the messages in precisely the order you specify. However, it makes a serious attempt to be ``close'', so priorities can strongly affect the efficiency of your program.

3.4.6 Immediate Messages

Immediate messages are specical messages that skip the Charm scheduler, they can be executed in an ``immediate'' fashion even in the middle of a normal running entry method. They are supported only in nodegroup. Also see Section 3.2.1 and example in charm/pgms/charm++/megatest/immediatering.C.