14. Sections: Subsets of a Chare Array/Group

Charm++ supports defining and communicating with subsets of a chare array or group. This entity is called a chare array section or a group section (section). Section elements are addressed via a section proxy. Charm++ also supports sections which are a subset of elements of multiple chare arrays/groups of the same type (see 14.5). Multicast operations, a broadcast to all members of a section, are directly supported by the section proxy. For array sections, multicast operations by default use optimized spanning trees via the CkMulticast library in Charm++ . For group sections, multicast operations by default use an unoptimized direct-sending implementation. To optimize messaging, group sections need to be manually delegated to CkMulticast (see 14.6). Reductions are also supported for both arrays and group sections via the CkMulticast library. Array and group sections work in mostly the same way. Check examples/charm++/groupsection for a group section example and examples/charm++/arraysection for an array section example.

14.1 Section Creation

14.1.1 Array sections

For each chare array ``A'' declared in a ci file, a section proxy of type ``CProxySection_A'' is automatically generated in the decl and def header files. You can create an array section in your application by invoking ckNew() function of the CProxySection. The user will need to provide array indexes of all the array section members through either explicit enumeration, or an index range expression. For example, for a 3D array:

  std::vector<CkArrayIndex3D> elems;  // add array indices
  for (int i=0; i<10; i++)
    for (int j=0; j<20; j+=2)
      for (int k=0; k<30; k+=2)
         elems.emplace_back(i, j, k);
  CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, elems);

Alternatively, one can do the same thing by providing the index range [lbound:ubound:stride] for each dimension:

  CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, 0, 9, 1, 0, 19, 2, 0, 29, 2);

The above code creates a section proxy that contains array elements [0:9, 0:19:2, 0:29:2]. For user-defined array index other than CkArrayIndex1D to CkArrayIndex6D, one needs to use the generic array index type: CkArrayIndex.

  std::vector<CkArrayIndex> elems;  // add array indices
  CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, elems);

14.1.2 Group sections

Group sections are created in the same way as array sections. A group ``A'' will have an associated ``CProxySection_A'' type which is used to create a section and obtain a proxy. In this case, ckNew() will receive the list of PE IDs which will form the section. See examples/charm++/groupsection for an example.

It is important to note that Charm++ does not automatically delegate group sections to the internal CkMulticast library, and instead defaults to a point-to-point implementation of multicasts. To use CkMulticast with group sections, the user must manually delegate after invoking group creation. See 14.6 for information on how to do this.

14.1.3 Creation order restrictions

Important: Array sections should be created in post-constructor entry methods to avoid race conditions.

If the user wants to invoke section creation from a group, special care must be taken that the collection for which we are creating a section (array or group) already exists.

For example, suppose a user wants to create a section of array ``A'' from an entry method in group ``G''. Because groups are created before arrays in Charm++ , and there is no guarantee of creation order of groups, there is a risk that array A's internal structures have not been initialized yet on every PE, causing section creation to fail. As such, the application must ensure that A has been created before attempting to create a section.

If the section is created from inside an array element there is no such risk.

14.2 Section Multicasts

Once the proxy is obtained at section creation time, the user can broadcast to all the section members, like this:

  CProxySection_Hello proxy;
  proxy.someEntry(...)          // section broadcast

See examples/charm++/arraysection for examples on how sections are used.

You can send the section proxy in a message to another processor, and still safely invoke the entry functions on the section proxy.

14.2.1 Optimized multicast via CkMulticast

Charm++ has a built-in CkMulticast library that optimizes section communications. By default, the Charm++ runtime system will use this library for array and cross-array sections. For group sections, the user must manually delegate the section proxy to CkMulticast (see 14.6).

By default, CkMulticast builds a spanning tree for multicast/reduction with a factor of 2 (binary tree). One can specify a different branching factor when creating the section.

  CProxySection_Hello sectProxy = CProxySection_Hello::ckNew(..., 3); // factor is 3

Note, to use CkMulticast library, all multicast messages must inherit from CkMcastBaseMsg, as the following example shows. Note that CkMcastBaseMsg must come first, this is IMPORTANT for CkMulticast library to retrieve section information out of the message.

class HiMsg : public CkMcastBaseMsg, public CMessage_HiMsg

  int *data;

Due to this restriction, when using CkMulticast you must define messages explicitly for multicast entry functions and no parameter marshalling can be used.

14.3 Section Reductions

Reductions over the elements of a section are supported through the CkMulticast library. As such, to perform reductions, the section must have been delegated to CkMulticast, either automatically (which is the default case for array sections), or manually for group sections.

Since an array element can be a member of multiple array sections, it is necessary to disambiguate between which array section reduction it is participating in each time it contributes to one. For this purpose, a data structure called ``CkSectionInfo'' is created by CkMulticast library for each array section that the array element belongs to. During a section reduction, the array element must pass the CkSectionInfo as a parameter in the contribute(). The CkSectionInfo for a section can be retrieved from a message in a multicast entry point using function call CkGetSectionInfo:

  CkSectionInfo cookie;

  void SayHi(HiMsg *msg)
    CkGetSectionInfo(cookie, msg);     // update section cookie every time
    int data = thisIndex;
    CProxySection_Hello::contribute(sizeof(int), &data, CkReduction::sum_int, cookie, cb);

Note that the cookie cannot be used as a one-time local variable in the function, the same cookie is needed for the next contribute. This is because the cookie includes some context-sensitive information (e.g., the reduction counter). Subsequent invocations of CkGetSectionInfo() only updates part of the data in the cookie, rather than creating a brand new one.

Similar to array reductions, to use section-based reductions, a reduction client CkCallback object must be created. You may pass the client callback as an additional parameter to contribute. If different contribute calls to the same reduction operation pass different callbacks, some (unspecified, unreliable) callback will be chosen for use.

See the following example:

    CkCallback cb(CkIndex_myArrayType::myReductionEntry(NULL),thisProxy); 
    CProxySection_Hello::contribute(sizeof(int), &data, CkReduction::sum_int, cookie, cb);

As in an array reduction, users can use built-in reduction types (Section 4.6.1) or define his/her own reducer functions (Section 17.2).

14.4 Section Operations and Migration

When using a section reduction, you don't need to worry about migrations of array elements. When migration happens, an array element in the array section can still use the CkSectionInfo it stored previously for doing a reduction. Reduction messages will be correctly delivered but may not be as efficient until a new multicast spanning tree is rebuilt internally in the CkMulticastMgr library. When a new spanning tree is rebuilt, an updated CkSectionInfo is passed along with a multicast message, so it is recommended that CkGetSectionInfo() function is always called when a multicast message arrives (as shown in the above SayHi example).

In the case where a multicast root migrates, the library must reconstruct the spanning tree to get optimal performance. One will get the following warning message if this is not done: ``Warning: Multicast not optimized after multicast root migrated.'' In the current implementation, the user needs to initiate the rebuilding process using resetSection.

void Foo::pup(PUP::er & p) 
    // if I am multicast root and it is unpacking
   if (ismcastroot && p.isUnpacking()) 
      CProxySection_Foo   fooProxy;    // proxy for the section
        // you may want to reset reduction client to root
      CkCallback *cb = new CkCallback(...);

14.5 Cross Array Sections

Cross array sections contain elements from multiple arrays. Construction and use of cross array sections is similar to normal array sections with the following restrictions.

Note: cross section logic also works for groups with analogous characteristics.

Given three arrays declared thusly:

   std::vector<CkArrayID> aidArr(3);
   for (int i=0; i<3; i++)
       CProxy_multisectiontest_array1d Aproxy = CProxy_multisectiontest_array1d::ckNew(masterproxy.ckGetGroupID(), ArraySize);
       aidArr[i] = Aproxy.ckGetArrayID();

One can make a section including the lower half elements of all three arrays as follows:

   int aboundary = ArraySize/2;
   int afloor = aboundary;
   int aceiling = ArraySize-1;
   int asectionSize = aceiling-afloor+1;
   // cross section lower half of each array
   std::vector<std::vector<CkArrayIndex> > aelems(3);
   for (int k=0; k<3; k++)
       for (int i=afloor,j=0; i<=aceiling; i++,j++)
         aelems[k][j] = CkArrayIndex1D(i);
   CProxySection_multisectiontest_array1d arrayLowProxy(aidArr, aelems);

The resulting cross section proxy, as in the example arrayLowProxy, can then be used for multicasts in the same way as a normal array section.

Note: For simplicity the above example has all arrays and sections of uniform size. The size of each array and the number of elements in each array within a section can all be set independently. For a more concrete example on how to use cross array section reduction, please refer to: examples/charm++/hello/xarraySection.

14.6 Manual Delegation

By default Charm++ uses the CkMulticast library for optimized broadcasts and reductions on array sections, but advanced Charm++ users can choose to delegate14.1sections to custom libraries (called delegation managers). Note that group sections are not automatically delegated to CkMulticast and hence must be manually delegated to this library to benefit from the optimized multicast tree implementation. This is explained in this section, and see examples/charm++/groupsection for an example.

While creating a chare array one can set the auto delegation flag to false in CkArrayOptions and the runtime system will not use the default CkMulticast library. A CkMulticastMgr (or any other delegation manager) group can then be created by the user, and any section delegated to it.

One only needs to create one delegation manager group, and it can serve all multicast/reduction delegations for different array/group sections in an application. In the following we show a manual delegation example using CkMulticast (the same can be applied to custom delegation managers):

  CkArrayOptions opts(...);
  opts.setSectionAutoDelegate(false); // manual delegation
  CProxy_Hello arrayProxy = CProxy_Hello::ckNew(opts,...);
  CProxySection_Hello sectProxy = CProxySection_Hello::ckNew(...);
  CkGroupID mCastGrpId = CProxy_CkMulticastMgr::ckNew();
  CkMulticastMgr *mCastGrp = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();

  sectProxy.ckSectionDelegate(mCastGrp);  // initialize section proxy

  sectProxy.someEntry(...)           // multicast via delegation library as before

One can also set the default branching factor when creating a CkMulticastMgr group. Sections created via this manager will use the specified branching factor for their multicast tree. For example,

  CkGroupID mCastGrpId = CProxy_CkMulticastMgr::ckNew(3);   // factor is 3

Contributing using a custom CkMulticastMgr group:

  CkSectionInfo cookie;

  void SayHi(HiMsg *msg)
    CkGetSectionInfo(cookie, msg);     // update section cookie every time
    int data = thisIndex;
    CkCallback cb(CkIndex_myArrayType::myReductionEntry(NULL),thisProxy);
    mcastGrp->contribute(sizeof(int), &data, CkReduction::sum_int, cookie, cb);

Setting default reduction client for a section when using manual delegation:

  CProxySection_Hello sectProxy;
  CkMulticastMgr *mcastGrp = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
  mcastGrp->setReductionClient(sectProxy, new CkCallback(...));

Writing the pup method:

void Foo::pup(PUP::er & p) 
    // if I am multicast root and it is unpacking
   if (ismcastroot && p.isUnpacking()) 
      CProxySection_Foo   fooProxy;    // proxy for the section
      CkMulticastMgr *mg = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
        // you may want to reset reduction client to root
      CkCallback *cb = new CkCallback(...);
      mg->setReductionClient(mcp, cb);