ProxyMgr.C

Go to the documentation of this file.

#include "InfoStream.h"
#include "main.h"
#include "BOCgroup.h"
#include "ProxyMgr.decl.h"
#include "ProxyMgr.h"
#include "PatchMap.inl"
#include "ProxyPatch.h"
#include "ComputeMap.h"
#include "HomePatch.h"
#include <string.h>
#include "ProcessorPrivate.h"
#include "packmsg.h"
#include "Priorities.h"
#ifndef _NO_ALLOCA_H
#include <alloca.h>
#endif
#ifndef _NO_MALLOC_H
#include <malloc.h>
#endif


#if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR) && (CMK_SMP) && defined(NAMDSRC_IMMQD_HACK)
#include "qd.h"
#endif

//#define DEBUGM
#define MIN_DEBUG_LEVEL 2
#include "Debug.h"

int proxySendSpanning   = 0;
int proxyRecvSpanning   = 0;
const int proxySpanDim  = 9;
const int inNodeProxySpanDim = 16;

PACK_MSG(ProxyAtomsMsg,
  PACK(patch);
  PACK_RESIZE(atomIDList);
)

PACK_MSG(ProxySpanningTreeMsg,
  PACK(patch);
  PACK(node);
  PACK_RESIZE(tree);
)

void* ProxyResultMsg::pack(ProxyResultMsg *msg) {

  int msg_size = 0;
  msg_size += sizeof(msg->node);
  msg_size += sizeof(msg->patch);

  int j;
  for ( j = 0; j < Results::maxNumForces; ++j ) {
    int array_size = msg->forceList[j].size();
    msg_size += sizeof(array_size);
    msg_size += array_size * sizeof(char);    
    msg_size = ALIGN_8 (msg_size);
    Force* f = msg->forceList[j].begin();
    int nonzero_count = 0;
    for ( int i = 0; i < array_size; ++i ) {
      if ( f[i].x != 0. || f[i].y != 0. || f[i].z != 0. ) { ++nonzero_count; }
    }
    msg_size += nonzero_count * sizeof(Vector);
  }

  void *msg_buf = CkAllocBuffer(msg,msg_size);
  char *msg_cur = (char *)msg_buf;

  CmiMemcpy((void*)msg_cur,(void*)(&(msg->node)),sizeof(msg->node));
  msg_cur += sizeof(msg->node);
  CmiMemcpy((void*)msg_cur,(void*)(&(msg->patch)),sizeof(msg->patch));
  msg_cur += sizeof(msg->patch);
  for ( j = 0; j < Results::maxNumForces; ++j ) {
    int array_size = msg->forceList[j].size();
    *(int *) msg_cur = array_size;
    msg_cur += sizeof(int);
    char *nonzero = msg_cur;
    msg_cur += array_size * sizeof(char);
    msg_cur = (char *)ALIGN_8 (msg_cur);
    Vector *farr = (Vector *)msg_cur;
    Force* f = msg->forceList[j].begin();

    for ( int i = 0; i < array_size; ++i ) {
      if ( f[i].x != 0. || f[i].y != 0. || f[i].z != 0. ) {
        nonzero[i] = 1;
        farr->x = f[i].x;
        farr->y = f[i].y;
        farr->z = f[i].z;
        farr ++;
      } else {
        nonzero[i] = 0;
      }
    }
    msg_cur = (char *) farr;      
  }

  delete msg;
  return msg_buf;
}

ProxyResultMsg* ProxyResultMsg::unpack(void *ptr) {

  void *vmsg = CkAllocBuffer(ptr,sizeof(ProxyResultMsg));
  ProxyResultMsg *msg = new (vmsg) ProxyResultMsg;
  char *msg_cur = (char*)ptr;

  CmiMemcpy((void*)(&(msg->node)),(void*)msg_cur,sizeof(msg->node));
  msg_cur += sizeof(msg->node);
  CmiMemcpy((void*)(&(msg->patch)),(void*)msg_cur,sizeof(msg->patch));
  msg_cur += sizeof(msg->patch);
  int j;
  for ( j = 0; j < Results::maxNumForces; ++j ) {
    int array_size = *(int *) msg_cur;
    msg_cur += sizeof(array_size);
    msg->forceList[j].resize(array_size);
    char *nonzero = msg_cur;
    msg_cur += array_size * sizeof(char);    
    msg_cur = (char *)ALIGN_8 (msg_cur);
    Vector* farr = (Vector *) msg_cur;
    Force* f = msg->forceList[j].begin();
    for ( int i = 0; i < array_size; ++i ) {
      if ( nonzero[i] ) {
        f[i].x = farr->x;
        f[i].y = farr->y;
        f[i].z = farr->z;
        farr++;
      } else {
        f[i].x = 0.;  f[i].y = 0.;  f[i].z = 0.;
      }
    }    
    msg_cur = (char *) farr;
  }

  CkFreeMsg(ptr);
  return msg;
}

ProxyResultVarsizeMsg *ProxyResultVarsizeMsg::getANewMsg(NodeID nid, PatchID pid, int prioSize, ForceList *fls){

    //1. decide the length of forceArr and iszero field.
    int tmpLen[Results::maxNumForces];
    int iszeroLen = 0;
    for (int i=0; i<Results::maxNumForces; i++){
        tmpLen[i] = fls[i].size();
        iszeroLen += tmpLen[i];
    }
    char *tmpIszero = new char[iszeroLen];
    char *iszeroPtr = tmpIszero;
    int fArrLen = 0;
    for(int i=0; i<Results::maxNumForces; i++) {        
        Force *fiPtr = fls[i].begin();
        for(int j=0; j<tmpLen[i]; j++, fiPtr++, iszeroPtr++) {         
            if(fiPtr->x!=0.0 || fiPtr->y!=0.0 || fiPtr->z!=0) {
                *iszeroPtr=0;
                fArrLen++;
            }else{
                *iszeroPtr=1;
            }            
        }
    }

    //2. Ready to create the msg, and set all fields
    ProxyResultVarsizeMsg *retmsg = new(fArrLen, iszeroLen, prioSize)ProxyResultVarsizeMsg;
    retmsg->node = nid;
    retmsg->patch = pid;
    memcpy(retmsg->flLen, tmpLen, sizeof(int)*Results::maxNumForces);
    iszeroPtr = tmpIszero;
    Force *forcePtr = retmsg->forceArr;
    for(int i=0; i<Results::maxNumForces; i++) {        
        Force *fiPtr = fls[i].begin();
        for(int j=0; j<tmpLen[i]; j++, fiPtr++, iszeroPtr++) {
            if((*iszeroPtr)!=1) {
                forcePtr->x = fiPtr->x;
                forcePtr->y = fiPtr->y;
                forcePtr->z = fiPtr->z;
                forcePtr++;
            }            
        }
    }
    memcpy(retmsg->isZero, tmpIszero, sizeof(char)*iszeroLen);
    delete [] tmpIszero;
    return retmsg;
}

ProxyNodeAwareSpanningTreeMsg *ProxyNodeAwareSpanningTreeMsg::getANewMsg(PatchID pid, NodeID nid, proxyTreeNode *tree, int size){
    int numAllPes = 0;
    for(int i=0; i<size; i++) {
        numAllPes += tree[i].numPes;
    }
    ProxyNodeAwareSpanningTreeMsg *retmsg = new(size, numAllPes, 0) ProxyNodeAwareSpanningTreeMsg;
    retmsg->patch = pid;
    retmsg->procID = nid;
    retmsg->numNodesWithProxies = size;    
    int *pAllPes = retmsg->allPes;
    for(int i=0; i<size; i++) {
        retmsg->numPesOfNode[i] = tree[i].numPes;
        for(int j=0; j<tree[i].numPes; j++) {
            *pAllPes = tree[i].peIDs[j];
            pAllPes++;
        }
    }
    return retmsg;
}

//Only available when macro PROCTRACE_DEBUG is defined
void ProxyNodeAwareSpanningTreeMsg::printOut(char *tag){
#ifdef PROCTRACE_DEBUG
    DebugFileTrace *dft = DebugFileTrace::Object();
    dft->openTrace();
    const char *patchname = "ProxyPatch";
    if(procID == CkMyPe()) patchname = "HomePatch";
    dft->writeTrace("%s: %s[%d] on proc %d node %d has ST (src %d) with %d nodes: \n", tag, patchname, patch, CkMyPe(), CkMyNode(), procID, numNodesWithProxies);
    if(numNodesWithProxies==0) {
        dft->closeTrace();
        return;
    }
    dft->writeTrace("%s: ===%d===pes/node: ", tag, patch);
    for(int i=0; i<numNodesWithProxies; i++) {
        dft->writeTrace("%d ", numPesOfNode[i]);
    }
    dft->writeTrace("\n%s: ===%d===pe list: ", tag, patch);
    int *p = allPes;
    for(int i=0; i<numNodesWithProxies; i++) {
        for(int j=0; j<numPesOfNode[i]; j++) {
            dft->writeTrace("%d ", *p);
            p++;
        }
    }
    dft->writeTrace("\n");    
    dft->closeTrace();
#endif
}

// for spanning tree
void* ProxyCombinedResultMsg::pack(ProxyCombinedResultMsg *msg) {
  int msg_size = 0;
  msg_size += sizeof(int) + msg->nodes.size()*sizeof(NodeID);
  #if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR)
  msg_size += sizeof(msg->destPe);
  #if CMK_SMP && defined(NAMDSRC_IMMQD_HACK)
  msg_size += sizeof(msg->isFromImmMsgCall);
  #endif
  #endif  
  msg_size += sizeof(msg->patch);
  int j;
  for ( j = 0; j < Results::maxNumForces; ++j ) {
    int array_size = msg->forceList[j].size();
    msg_size += sizeof(array_size);
    msg_size += array_size * sizeof(char);
    msg_size = ALIGN_8 (msg_size);

    Force* f = msg->forceList[j].begin();
    int nonzero_count = 0;
    for ( int i = 0; i < array_size; ++i ) {
      if ( f[i].x != 0. || f[i].y != 0. || f[i].z != 0. ) { ++nonzero_count; }
    }
    msg_size += nonzero_count * sizeof(Force);
  }

  void *msg_buf = CkAllocBuffer(msg,msg_size);
  char *msg_cur = (char *)msg_buf;

  int nodeSize = msg->nodes.size();
  CmiMemcpy((void*)msg_cur,(void*)(&nodeSize), sizeof(nodeSize));
  msg_cur += sizeof(nodeSize);
  for (int i=0; i<nodeSize; i++) {
    CmiMemcpy((void*)msg_cur,(void*)(&msg->nodes[i]), sizeof(NodeID));
    msg_cur += sizeof(NodeID);
  }
  #if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR)
  CmiMemcpy((void*)msg_cur,(void*)(&(msg->destPe)),sizeof(msg->destPe));
  msg_cur += sizeof(msg->destPe);
  #if CMK_SMP && defined(NAMDSRC_IMMQD_HACK)
  CmiMemcpy((void*)msg_cur, (void*)(&(msg->isFromImmMsgCall)), sizeof(msg->isFromImmMsgCall));
  msg_cur += sizeof(msg->isFromImmMsgCall);
  #endif
  #endif
  CmiMemcpy((void*)msg_cur,(void*)(&(msg->patch)),sizeof(msg->patch));
  msg_cur += sizeof(msg->patch);
  for ( j = 0; j < Results::maxNumForces; ++j ) {
    int array_size = msg->forceList[j].size();
    CmiMemcpy((void*)msg_cur,(void*)(&array_size),sizeof(array_size));
    msg_cur += sizeof(array_size);
    char *nonzero = msg_cur;
    msg_cur += array_size * sizeof(char);
    msg_cur = (char *)ALIGN_8 (msg_cur);
    Vector *farr = (Vector *) msg_cur; 
    Force* f = msg->forceList[j].begin();

    for ( int i = 0; i < array_size; ++i ) {
      if ( f[i].x != 0. || f[i].y != 0. || f[i].z != 0. ) {
        nonzero[i] = 1;
        farr->x  =  f[i].x;
        farr->y  =  f[i].y;
        farr->z  =  f[i].z;

        farr ++;
      } else {
        nonzero[i] = 0;
      }
    }
    msg_cur = (char *) farr;
  }

  delete msg;
  return msg_buf;
}

ProxyCombinedResultMsg* ProxyCombinedResultMsg::unpack(void *ptr) {
  void *vmsg = CkAllocBuffer(ptr,sizeof(ProxyCombinedResultMsg));
  ProxyCombinedResultMsg *msg = new (vmsg) ProxyCombinedResultMsg;
  char *msg_cur = (char*)ptr;

  int nodeSize;
  CmiMemcpy((void*)(&nodeSize),(void*)msg_cur,sizeof(nodeSize));
  msg_cur += sizeof(nodeSize);
  for (int i=0; i<nodeSize; i++) {
    msg->nodes.add(*(int *)msg_cur);
    msg_cur += sizeof(NodeID);
  }
  #if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR)
  CmiMemcpy((void*)(&(msg->destPe)),(void*)msg_cur,sizeof(msg->destPe));
  msg_cur += sizeof(msg->destPe);
  #if CMK_SMP && defined(NAMDSRC_IMMQD_HACK)
  CmiMemcpy((void *)(&(msg->isFromImmMsgCall)), (void*)msg_cur, sizeof(msg->isFromImmMsgCall));
  msg_cur += sizeof(msg->isFromImmMsgCall);  
  #endif
  #endif
  CmiMemcpy((void*)(&(msg->patch)),(void*)msg_cur,sizeof(msg->patch));
  msg_cur += sizeof(msg->patch);
  int j;
  for ( j = 0; j < Results::maxNumForces; ++j ) {
    int array_size;
    CmiMemcpy((void*)(&array_size),(void*)msg_cur,sizeof(array_size));
    msg_cur += sizeof(array_size);
    msg->forceList[j].resize(array_size);
    char *nonzero = msg_cur;
    msg_cur += array_size * sizeof(char);
    msg_cur = (char *)ALIGN_8 (msg_cur);
    Vector* farr = (Vector *) msg_cur;
    Force* f = msg->forceList[j].begin();

    for ( int i = 0; i < array_size; ++i ) {
      if ( nonzero[i] ) {
        f[i].x = farr->x;
        f[i].y = farr->y;
        f[i].z = farr->z;
        farr++;
      } else {
        f[i].x = 0.;  f[i].y = 0.;  f[i].z = 0.;
      }
    }
    msg_cur = (char *) farr;
  }

  CkFreeMsg(ptr);
  return msg;
}

// class static
int ProxyMgr::nodecount = 0;

ProxyMgr::ProxyMgr() { 
  if (CkpvAccess(ProxyMgr_instance)) {
    NAMD_bug("Tried to create ProxyMgr twice.");
  }
  CkpvAccess(ProxyMgr_instance) = this;
}

ProxyMgr::~ProxyMgr() { 
  removeProxies();
  CkpvAccess(ProxyMgr_instance) = NULL;
}


void ProxyMgr::setSendSpanning() {
  proxySendSpanning = 1;
}

int ProxyMgr::getSendSpanning() {
  return proxySendSpanning;
}

void ProxyMgr::setRecvSpanning() {
  proxyRecvSpanning = 1;
}

int ProxyMgr::getRecvSpanning() {
  return proxyRecvSpanning;
}

ProxyTree &ProxyMgr::getPtree() {
  return ptree;
}

void ProxyMgr::removeProxies(void)
{
  ProxySetIter pi(proxySet);
  for ( pi = pi.begin(); pi != pi.end(); pi++)
  {
    delete pi->proxyPatch;
  }
  proxySet.clear();
}

void ProxyMgr::removeUnusedProxies(void)
{
  ResizeArray<PatchID> toDelete;
  ProxySetIter pi(proxySet);
  for ( pi = pi.begin(); pi != pi.end(); pi++)
  {
    if ( pi->proxyPatch->getNumComputes() == 0 ) {
      toDelete.add(pi->patchID);
      //fprintf(stderr, "Proxy Deleted Patch %d Proc %d", pi->patchID, CkMyPe());
    }
  }
  PatchID *pidi = toDelete.begin();
  for ( ; pidi != toDelete.end(); ++pidi ) {
    removeProxy(*pidi);
  }
}

// Figure out which proxies we need and create them
void ProxyMgr::createProxies(void)
{
  // Delete the old proxies.
  removeProxies();

  PatchMap *patchMap = PatchMap::Object();
  int numPatches = patchMap->numPatches();
  int myNode = CkMyPe();
  enum PatchFlag { Unknown, Home, NeedProxy };
  int *patchFlag = new int[numPatches]; 
  int i, j;

  // Note all home patches.
  for ( i = 0; i < numPatches; ++i )
  {
    patchFlag[i] = ( patchMap->node(i) == myNode ) ? Home : Unknown;
  }

  // Add all upstream neighbors.
  PatchID neighbors[PatchMap::MaxOneAway];
  PatchIDList basepids;
  patchMap->basePatchIDList(myNode,basepids);
  for ( i = 0; i < basepids.size(); ++i )
  {
    if ( patchMap->node(basepids[i]) != myNode ) {
        patchFlag[basepids[i]] = NeedProxy;
    }
    int numNeighbors = patchMap->upstreamNeighbors(basepids[i],neighbors);
    for ( j = 0; j < numNeighbors; ++j )
    {
      if ( ! patchFlag[neighbors[j]] ) {
        patchFlag[neighbors[j]] = NeedProxy;
      }
    }
  }

  // Check all patch-based compute objects.
  ComputeMap *computeMap = ComputeMap::Object();
  int nc = computeMap->numComputes();
  for ( i = 0; i < nc; ++i )
  {
    if ( computeMap->node(i) != myNode || !computeMap->isPatchBased(i) ) 
      continue;
    int numPid = computeMap->numPids(i);
    for ( j = 0; j < numPid; ++j )
    {
      int pid = computeMap->pid(i,j);
      if ( ! patchFlag[pid] ) {
        patchFlag[pid] = NeedProxy;
      }
    }
  }
  
  // Create proxy list
  for ( i = 0; i < numPatches; ++i ) {
    if ( patchFlag[i] == NeedProxy )
    { // create proxy patch
      ProxyPatch *proxy = new ProxyPatch(i);
      proxySet.add(ProxyElem(i, proxy));
      patchMap->registerPatch(i, proxy);
    }
  }
  delete[] patchFlag;
}

void
ProxyMgr::createProxy(PatchID pid) {
  Patch *p = PatchMap::Object()->patch(pid);
  if (!p) {
     DebugM(4,"createProxy("<<pid<<")\n");
     ProxyPatch *proxy = new ProxyPatch(pid);
     proxySet.add(ProxyElem(pid,proxy));
     PatchMap::Object()->registerPatch(pid,proxy);
  }
  else {
     DebugM(4,"createProxy("<<pid<<") found " << p->getPatchID() << "\n");
  }
    
}

void
ProxyMgr::removeProxy(PatchID pid) {
  ProxyElem *p = proxySet.find(ProxyElem(pid));
  if (p) { 
    PatchMap::Object()->unregisterPatch(pid,p->proxyPatch);
    delete p->proxyPatch;
    proxySet.del(ProxyElem(pid));
    // iout << iINFO << "Removing unused proxy " << pid << " on " << iPE << ".\n" << endi;
  }
}
  
void
ProxyMgr::registerProxy(PatchID pid) {
  // determine which node gets message
  NodeID node = PatchMap::Object()->node(pid);

  RegisterProxyMsg *msg = new RegisterProxyMsg;

  msg->node=CkMyPe();
  msg->patch = pid;

  CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
  cp[node].recvRegisterProxy(msg);
}

void
ProxyMgr::recvRegisterProxy(RegisterProxyMsg *msg) {
  HomePatch *homePatch = PatchMap::Object()->homePatch(msg->patch);
  homePatch->registerProxy(msg); // message deleted in registerProxy()
}

void
ProxyMgr::unregisterProxy(PatchID pid) {
  // determine which node gets message
  NodeID node = PatchMap::Object()->node(pid);

  UnregisterProxyMsg *msg = new UnregisterProxyMsg;

  msg->node=CkMyPe();
  msg->patch = pid;

  CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
  cp[node].recvUnregisterProxy(msg);
}

void
ProxyMgr::recvUnregisterProxy(UnregisterProxyMsg *msg) {
  HomePatch *homePatch = PatchMap::Object()->homePatch(msg->patch);
  homePatch->unregisterProxy(msg); // message deleted in registerProxy()
}

void 
ProxyMgr::buildProxySpanningTree()
{
  PatchIDList pids;
  if (!CkMyPe()) iout << iINFO << "Building spanning tree ... send: " << proxySendSpanning << " recv: " << proxyRecvSpanning << "\n" << endi;
  PatchMap::Object()->homePatchIDList(pids);
  for (int i=0; i<pids.size(); i++) {
    HomePatch *home = PatchMap::Object()->homePatch(pids[i]);
    if (home == NULL) CkPrintf("ERROR: homepatch NULL\n");
#ifdef NODEAWARE_PROXY_SPANNINGTREE
    home->buildNodeAwareSpanningTree();
#else
    home->buildSpanningTree();
#endif
  }
}

void 
ProxyMgr::buildProxySpanningTree2()
{
  PatchIDList pids;
  PatchMap::Object()->homePatchIDList(pids);
  for (int i=0; i<pids.size(); i++) {
    HomePatch *home = PatchMap::Object()->homePatch(pids[i]);
    if (home == NULL) CkPrintf("ERROR: homepatch NULL\n");
    home->sendProxies();
  }
}

void 
ProxyMgr::sendProxies(int pid, int *list, int n)
{
  CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
  cp[0].recvProxies(pid, list, n);
}

//The value defines the max number of intermediate proxies (acting
//as the node to relay proxy msgs to children) allowed to reside 
//on a physical node for proxy spanning tree
#define MAX_INTERNODE 1

// only on PE 0
void 
ProxyMgr::recvProxies(int pid, int *list, int n)
{
  int nPatches = PatchMap::Object()->numPatches();
  if (ptree.proxylist == NULL)
    ptree.proxylist = new NodeIDList[nPatches];
  ptree.proxylist[pid].resize(n);
  for (int i=0; i<n; i++)
    ptree.proxylist[pid][i] = list[i];
  ptree.proxyMsgCount ++;
  if (ptree.proxyMsgCount == nPatches) {
    ptree.proxyMsgCount = 0;
    // building and sending of trees is done in two steps now
    // so that the building step can be shifted to the load balancer
#ifdef NODEAWARE_PROXY_SPANNINGTREE
    buildNodeAwareSpanningTree0();
#else
    buildSpanningTree0();    
#endif
    sendSpanningTrees();
  }
}

//
// XXX static and global variables are unsafe for shared memory builds.
// The global and static vars should be eliminated.  
// Unfortunately, the routines that use these below are actually 
// in use in NAMD.
//
extern double *cpuloads;
static int *procidx = NULL;
static double averageLoad = 0.0;

static int compLoad(const void *a, const void *b)
{
  int i1 = *(int *)a;
  int i2 = *(int *)b;
  double d1 = cpuloads[i1];
  double d2 = cpuloads[i2];
  if (d1 < d2) 
    return 1;
  else if (d1 == d2) 
    return 0;
  else 
    return -1;
  // sort from high to low
}

static void processCpuLoad()
{
  int i;
  if (!procidx) {
    procidx = new int[CkNumPes()];
  }
  for (i=0; i<CkNumPes(); i++) procidx[i] = i;
  qsort(procidx, CkNumPes(), sizeof(int), compLoad);

  double averageLoad = 0.0;
  for (i=0; i<CkNumPes(); i++) averageLoad += cpuloads[i];
  averageLoad /= CkNumPes();
//  iout << "buildSpanningTree1: no intermediate node on " << procidx[0] << " " << procidx[1] << endi;

}

static int noInterNode(int p)
{
  int exclude = 0;
  if(CkNumPes()<1025)
    exclude = 5;
  else if(CkNumPes()<4097)
    exclude = 10;
  else if(CkNumPes()<8193)
    exclude = 40;
  else if(CkNumPes()<16385)
    exclude = 40;
  else
    exclude = 80;
  for (int i=0; i<exclude; i++) if (procidx[i] == p) return 1;
//  if (cpuloads[p] > averageLoad) return 1;
  return 0;
}

#ifdef NODEAWARE_PROXY_SPANNINGTREE
//only on PE 0
void ProxyMgr::buildNodeAwareSpanningTree0(){
    int numPatches = PatchMap::Object()->numPatches();
    if (ptree.naTrees == NULL) ptree.naTrees = new proxyTreeNodeList[numPatches];
    //each element indiates the number of proxies residing on this node    
    int *proxyNodeMap = new int[CkNumNodes()];    
    for (int pid=0; pid<numPatches; pid++)     
        buildSinglePatchNodeAwareSpanningTree(pid, ptree.proxylist[pid], ptree.naTrees[pid], proxyNodeMap);
       

    //Debug
    //printf("#######################Naive ST#######################\n");
    //printProxySpanningTree();

    //Now the naive spanning tree has been constructed and stored in oneNATree;
    //Afterwards, some optimizations on this naive spanning tree could be done.
    //except the first element as the tree root always contains the processor
    //that has home patch

    //1st Optimization: reduce intermediate nodes as much as possible. In details,
    //the optimal case is that on a single physical smp node, there should be no
    //two proxies who act as the intermediate nodes to pass information to childrens
    //in the spanning tree. E.g, for patch A's proxy spanning tree, it has a node X as
    //its intermediate node. However, for patch B's, it also has a node X as its intermediate
    //node. We should avoid this situation as node X becomes the bottleneck as it has twice
    //amount of work to process now.
    //Step1: foward to the first patch that has proxies
    //Now proxyNodeMap records the info that how many intermediate nodes on a node
    memset(proxyNodeMap, 0, sizeof(int)*CkNumNodes());
    int pid=0;
    for(;pid<numPatches; pid++) {
        if(ptree.proxylist[pid].size()>0) break;
    }
    if(pid==numPatches) {
        delete [] proxyNodeMap;
        return;
    }
    proxyTreeNodeList onePatchT = ptree.naTrees[pid];
    //If a node is an intermediate node, then its idx should satisfy
    //idx*proxySpanDim + 1 < onePatchT.size()
    int lastInterNodeIdx = (onePatchT.size()-2)/proxySpanDim;
    for(int i=1; i<lastInterNodeIdx; i++) { //excluding the root node
        int nid = onePatchT.item(i).nodeID;
        proxyNodeMap[nid]++;
    }
    //Step2: iterate over each patch's proxy spanning tree to adjust
    //the tree node positions. The bad thing here is that it may involve
    //many memory allocations and deallocation for small-size (~100bytes)
    //chunks.
    pid++; //advance to the next patch
    for(; pid<numPatches; pid++) {
        if(ptree.proxylist[pid].size()==0) continue;
        onePatchT = ptree.naTrees[pid];
        lastInterNodeIdx = (onePatchT.size()-2)/proxySpanDim;
        for(int i=1; i<=lastInterNodeIdx; i++) {
            int nid = onePatchT.item(i).nodeID;
            if(proxyNodeMap[nid]<MAX_INTERNODE) {
                proxyNodeMap[nid]++;
                continue;
            }
            //the position is occupied, so search the children
            //nodes to see whether there's one to swap this node
            //if not found, find the first position that has smallest
            //amount of nodes.
            int leastIdx = -1;
            int leastAmount = ~(1<<31);
            //iterate children nodes
            int swapPos;
            for(swapPos=lastInterNodeIdx+1; swapPos<onePatchT.size(); swapPos++) {
                int chiNId = onePatchT.item(swapPos).nodeID;
                if(proxyNodeMap[chiNId]<MAX_INTERNODE) {
                    break;
                }
                if(proxyNodeMap[chiNId]<leastAmount) {
                    leastAmount = proxyNodeMap[chiNId];
                    leastIdx = swapPos;
                }
            }
            CmiAssert(leastIdx!=-1); //because the above loop at least executes once
            if(swapPos==onePatchT.size()) {
                //indicate we cannot find a physical node which
                //still allows the intermediate proxy.
                swapPos = leastIdx;
            }
            //swap the current proxy tree node "i" with node "swapPos"
            proxyTreeNode *curNode = &onePatchT.item(i);
            proxyTreeNode *swapNode = &onePatchT.item(swapPos);
            proxyNodeMap[swapNode->nodeID]++; //update the proxyNodeMap record
            int tmp = curNode->nodeID;
            curNode->nodeID = swapNode->nodeID;
            swapNode->nodeID = tmp;
            tmp = curNode->numPes;
            int tmpPes[tmp];
            memcpy(tmpPes, curNode->peIDs, sizeof(int)*tmp);
            delete [] curNode->peIDs;
            curNode->numPes = swapNode->numPes;
            curNode->peIDs = new int[swapNode->numPes];
            memcpy(curNode->peIDs, swapNode->peIDs, sizeof(int)*swapNode->numPes);
            swapNode->numPes = tmp;
            delete [] swapNode->peIDs;
            swapNode->peIDs = new int[tmp];
            memcpy(swapNode->peIDs, tmpPes, sizeof(int)*tmp);                      
        }
    }
    delete [] proxyNodeMap;    

    //Debug
    //printf("#######################After 1st optimization#######################\n");
    //printProxySpanningTree();

    //2nd optimization: similar to the 1st optimization but now thinking in
    //the core level. If we cannot avoid place two intermediate proxy
    //on the same node, we'd better to place them in different cores inside
    //the node
    if(CmiMyNodeSize()==1) {
        //No need to perform the second optimization as every node has only 1 core
        return;
    }
    int *proxyCoreMap = new int[CkNumPes()];
    memset(proxyCoreMap, 0, sizeof(int)*CkNumPes());
    //Step1: forward to the first patch that has proxies
    pid=0;
    for(;pid<numPatches; pid++) {
        if(ptree.proxylist[pid].size()>0) break;
    }
    if(pid==numPatches) {
        delete [] proxyCoreMap;
        return;
    }
    onePatchT = ptree.naTrees[pid];
    //If a node is an intermediate node, then its idx should satisfy
    //idx*proxySpanDim + 1 < onePatchT.size()
    lastInterNodeIdx = (onePatchT.size()-2)/proxySpanDim;
    for(int i=1; i<lastInterNodeIdx; i++) { //excluding the root node
        int rootProcID = onePatchT.item(i).peIDs[0];
        proxyCoreMap[rootProcID]++;
    }
    //Step2: iterate over each patch's proxy spanning tree to adjust
    //the root's position of intermediate proxies.
    pid++; //advance to the next patch
    for(; pid<numPatches; pid++) {
        if(ptree.proxylist[pid].size()==0) continue;
        onePatchT = ptree.naTrees[pid];
        lastInterNodeIdx = (onePatchT.size()-2)/proxySpanDim;
        for(int i=1; i<=lastInterNodeIdx; i++) {
            proxyTreeNode *curNode = &onePatchT.item(i);
            int rootProcID = curNode->peIDs[0];
            if(curNode->numPes==1 || proxyCoreMap[rootProcID]<MAX_INTERNODE){
                //if this node contains only 1 core, then we have to leave it as it is
                //because there are no other cores in the same node that could be used to
                //adjust
                proxyCoreMap[rootProcID]++;
                continue;
            }
            
            //foound more than MAX_INTERNODE intermediate proxies on the same core,
            //adjust the root id of the core of this proxy tree node
            int leastIdx = -1;
            int leastAmount = ~(1<<31);
            //iterate children nodes
            int swapPos;
            
            for(swapPos=1; swapPos<curNode->numPes; swapPos++) {
                int otherCoreID = curNode->peIDs[swapPos];
                if(proxyCoreMap[otherCoreID]<MAX_INTERNODE) {
                    break;
                }
                if(proxyCoreMap[otherCoreID]<leastAmount) {
                    leastAmount = proxyCoreMap[otherCoreID];
                    leastIdx = swapPos;
                }
            }
            CmiAssert(leastIdx!=-1); //because the above loop body must execute at least once
            if(swapPos==curNode->numPes) {
                //indicate we cannot find a physical node which
                //still allows the intermediate proxy.
                swapPos = leastIdx;
            }
            int tmp = curNode->peIDs[swapPos];
            curNode->peIDs[swapPos] = curNode->peIDs[0];
            curNode->peIDs[0] = tmp;
            proxyCoreMap[tmp]++;
        }      
    }

    delete proxyCoreMap;

    //Debug
    //printf("#######################After 2nd optimization#######################\n");
    //printProxySpanningTree();
}

void ProxyMgr::buildSinglePatchNodeAwareSpanningTree(PatchID pid, NodeIDList &proxyList, 
                                                     proxyTreeNodeList &ptnTree, int *proxyNodeMap){       
    int numProxies = proxyList.size();
    if (numProxies == 0) {
        CkPrintf ("This is sheer evil in building node-aware spanning tree!\n\n");            
        return;
    }        
    
    memset(proxyNodeMap, 0, sizeof(int)*CkNumNodes());
    int proxyNodeList[numProxies+1]; //including the root node             
    
    //the processor id of home patch
    int hpProcID = PatchMap::Object()->node(pid);
    int hpNodeID = CkNodeOf(hpProcID);
    proxyNodeMap[hpNodeID]++;
    proxyNodeList[0] = hpNodeID;
    int numNodesWithProxies = 1;
    
    for(int i=0; i<numProxies; i++) {
        int procId = proxyList[i];
        int nodeId = CkNodeOf(procId);
        proxyNodeMap[nodeId]++;
        if(proxyNodeMap[nodeId]==1) {
            proxyNodeList[numNodesWithProxies] = nodeId;
            numNodesWithProxies++;
        }
    }
    proxyTreeNodeList &oneNATree = ptnTree;   // spanning tree
    oneNATree.resize(numNodesWithProxies);
    //initialize oneNATree
    for(int i=0; i<numNodesWithProxies; i++) {
        proxyTreeNode *oneNode = &oneNATree.item(i);
        delete oneNode->peIDs;
        oneNode->nodeID = proxyNodeList[i];
        oneNode->peIDs = new int[proxyNodeMap[oneNode->nodeID]];                        
        oneNode->numPes = 0; //initially set to zero as used for incrementing later
    }
    
    //set up the tree root which contains the home patch processor
    proxyTreeNode *rootnode = &oneNATree.item(0);
    rootnode->peIDs[0] = hpProcID;
    rootnode->numPes++;
    
    for(int i=0; i<numProxies; i++) {
        int procId = proxyList[i];
        int nodeId = CkNodeOf(procId);
        int idxInTree = -1;
        for(int j=0; j<numNodesWithProxies; j++) {
            if(proxyNodeList[j] == nodeId) {
                idxInTree = j;
                break;
            }
        }
        CmiAssert(idxInTree!=-1);
        proxyTreeNode *oneNode = &oneNATree.item(idxInTree);
        oneNode->peIDs[oneNode->numPes] = procId;
        oneNode->numPes++;
    }
}
#else //branch of NODEAWARE_PROXY_SPANNINGTREE
// only on PE 0
void 
ProxyMgr::buildSpanningTree0()
{
  int i;

  processCpuLoad();

  int *numPatchesOnNode = new int[CkNumPes()];
  int numNodesWithPatches = 0;
  for (i=0; i<CkNumPes(); i++) numPatchesOnNode[i] = 0;
  int numPatches = PatchMap::Object()->numPatches();
  for (i=0; i<numPatches; i++) {
    int node = PatchMap::Object()->node(i);
    numPatchesOnNode[node]++;
    if (numPatchesOnNode[node] == 1)
      numNodesWithPatches ++;
  }
  int patchNodesLast =
    ( numNodesWithPatches < ( 0.7 * CkNumPes() ) );
  int *ntrees = new int[CkNumPes()];
  for (i=0; i<CkNumPes(); i++) ntrees[i] = 0;
  if (ptree.trees == NULL) ptree.trees = new NodeIDList[numPatches];
  for (int pid=0; pid<numPatches; pid++) 
  {
    int numProxies = ptree.proxylist[pid].size();
    if (numProxies == 0) {
      CkPrintf ("This is sheer evil!\n\n");
      //ProxyMgr::Object()->sendSpanningTreeToHomePatch(pid, NULL, 0);
      return;
    }
    NodeIDList &tree = ptree.trees[pid];   // spanning tree
    NodeIDList oldtree = tree;
    tree.resize(numProxies+1);
    tree.setall(-1);
    tree[0] = PatchMap::Object()->node(pid);
    int s=1, e=numProxies;
    int nNonPatch = 0;
    int treesize = 1;
    int pp;

    // keep tree persistent for non-intermediate nodes
    for (pp=0; pp<numProxies; pp++) {
      int p = ptree.proxylist[pid][pp];
      int oldindex = oldtree.find(p);
      if (oldindex != -1 && oldindex <= numProxies) {
        int isIntermediate = (oldindex*proxySpanDim+1 <= numProxies);
        if (!isIntermediate) {
          tree[oldindex] = p;
        }
        else if (ntrees[p] < MAX_INTERNODE) {
          tree[oldindex] = p;
          ntrees[p] ++;
        }
      }
    }

    for (pp=0; pp<numProxies; pp++) {
      int p = ptree.proxylist[pid][pp];              // processor number
      if (tree.find(p) != -1) continue;        // already used
      treesize++;
      if (patchNodesLast && numPatchesOnNode[p] ) {
        while (tree[e] != -1) { e--; if (e==-1) e = numProxies; }
        tree[e] = p;
        int isIntermediate = (e*proxySpanDim+1 <= numProxies);
        if (isIntermediate) ntrees[p]++;
      }
      else {
        while (tree[s] != -1) { s++; if (s==numProxies+1) s = 1; }
        int isIntermediate = (s*proxySpanDim+1 <= numProxies);
        if (isIntermediate && (ntrees[p] >= MAX_INTERNODE || noInterNode(p))) {   // TOO MANY INTERMEDIATE TREES
        //if (isIntermediate && ntrees[p] >= MAX_INTERNODE)    // TOO MANY INTERMEDIATE TREES
          while (tree[e] != -1) { e--; if (e==-1) e = numProxies; }
          tree[e] = p;
          isIntermediate = (e*proxySpanDim+1 <= numProxies);
          if (isIntermediate) ntrees[p]++;
        }
        else {
          tree[s] = p;
          nNonPatch++;
          if (isIntermediate) ntrees[p]++;
        }
      }
    }
    // send homepatch's proxy tree
    if(ptree.sizes)
      ptree.sizes[pid] = treesize;
    //ProxyMgr::Object()->sendSpanningTreeToHomePatch(pid, &tree[0], treesize);
  }
  /*for (i=0; i<CkNumPes(); i++) {
    if (ntrees[i] > MAX_INTERNODE) iout << "Processor " << i << "has (guess) " << ntrees[i] << " intermediate nodes." << endi;
  }*/
  delete [] ntrees;
  delete [] numPatchesOnNode;
}
#endif

void ProxyMgr::sendSpanningTrees()
{
  int numPatches = PatchMap::Object()->numPatches();
  for (int pid=0; pid<numPatches; pid++) {
    int numProxies = ptree.proxylist[pid].size();
#ifdef NODEAWARE_PROXY_SPANNINGTREE
    if (numProxies == 0)
      ProxyMgr::Object()->sendNodeAwareSpanningTreeToHomePatch(pid, NULL, 0);
    else {
      ProxyMgr::Object()->sendNodeAwareSpanningTreeToHomePatch(pid, ptree.naTrees[pid].begin(), ptree.naTrees[pid].size());
    }
#else
    if (numProxies == 0)
      ProxyMgr::Object()->sendSpanningTreeToHomePatch(pid, NULL, 0);
    else {
      ProxyMgr::Object()->sendSpanningTreeToHomePatch(pid, ptree.trees[pid].begin(), ptree.trees[pid].size());
    }
#endif
  }
}

void ProxyMgr::sendSpanningTreeToHomePatch(int pid, int *tree, int n)
{
  CProxy_ProxyMgr cp(thisgroup);
  cp[PatchMap::Object()->node(pid)].recvSpanningTreeOnHomePatch(pid, tree, n);
}

void ProxyMgr::recvSpanningTreeOnHomePatch(int pid, int *tree, int n)
{
  HomePatch *p = PatchMap::Object()->homePatch(pid);
  p->recvSpanningTree(tree, n);
}

void ProxyMgr::sendNodeAwareSpanningTreeToHomePatch(int pid, proxyTreeNode *tree, int n)
{
  CProxy_ProxyMgr cp(thisgroup);
  ProxyNodeAwareSpanningTreeMsg *msg = ProxyNodeAwareSpanningTreeMsg::getANewMsg(pid, -1, tree, n);
  cp[PatchMap::Object()->node(pid)].recvNodeAwareSpanningTreeOnHomePatch(msg);
}

void ProxyMgr::recvNodeAwareSpanningTreeOnHomePatch(ProxyNodeAwareSpanningTreeMsg *msg)
{
  HomePatch *p = PatchMap::Object()->homePatch(msg->patch);
  p->recvNodeAwareSpanningTree(msg);
  delete msg;
}

void 
ProxyMgr::sendSpanningTree(ProxySpanningTreeMsg *msg) {
  CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
  cp[msg->tree[0]].recvSpanningTree(msg);
}

void ProxyMgr::sendNodeAwareSpanningTree(ProxyNodeAwareSpanningTreeMsg *msg){
  CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
  int pe = msg->allPes[0]; //the root procID

#if defined(PROCTRACE_DEBUG) && defined(NAST_DEBUG)
  DebugFileTrace *dft = DebugFileTrace::Object();
  dft->openTrace();
  dft->writeTrace("PMgr::sndST: from proc %d for patch[%d]\n", pe, msg->patch);
  dft->closeTrace();
#endif

  cp[pe].recvNodeAwareSpanningTree(msg);
}

void 
ProxyMgr::recvSpanningTree(ProxySpanningTreeMsg *msg) {
  int size = msg->tree.size();
  int child[proxySpanDim];
  int nChild = 0;
  int i;
  ProxyPatch *proxy = (ProxyPatch *) PatchMap::Object()->patch(msg->patch);
  for (i=0; i<proxySpanDim; i++) {
    if (size > i+1) { child[i] = msg->tree[i+1]; nChild++; }
  }
  if (!PatchMap::Object()->homePatch(msg->patch)) {
    proxy->setSpanningTree(msg->node, child, nChild);
  }

  // build subtree and pass down
  if (nChild == 0) return;

  nodecount ++;
  //if (nodecount > MAX_INTERNODE) 
  //  iout << "Processor " << CkMyPe() << "has (actual) " << nodecount << " intermediate nodes." << endi;

//CkPrintf("[%d] %d:(%d) %d %d %d %d %d\n", CkMyPe(), msg->patch, size, msg->tree[0], msg->tree[1], msg->tree[2], msg->tree[3], msg->tree[4]);
  NodeIDList *tree = new NodeIDList[proxySpanDim];
  int level = 1, index=1;
  int done = 0;
  while (!done) {
    for (int n=0; n<nChild; n++) {
      if (done) break;
      for (int j=0; j<level; j++) {
       if (index >= size) { done = 1; break; }
       tree[n].add(msg->tree[index]);
       index++;
      }
    }
    level *=proxySpanDim;
  }

  ProxyMgr *proxyMgr = ProxyMgr::Object();
  for (i=0; i<proxySpanDim; i++) {
    if (tree[i].size()) {
      ProxySpanningTreeMsg *cmsg = new ProxySpanningTreeMsg;
      cmsg->patch = msg->patch;
      cmsg->node = CkMyPe();
      cmsg->tree = tree[i];
      proxyMgr->sendSpanningTree(cmsg);
    }
  }

  delete [] tree;
  delete msg;
}

//NOTE: have not considered how to deal with spanning tree inside a single physical node
//--Chao Mei
void ProxyMgr::recvNodeAwareSpanningTree(ProxyNodeAwareSpanningTreeMsg *msg){

    #if defined(PROCTRACE_DEBUG) && defined(NAST_DEBUG)
    DebugFileTrace *dft = DebugFileTrace::Object();
    dft->openTrace();
    dft->writeTrace("PMgr::recvST0 for patch[%d] with #nodes=%d\n", msg->patch, msg->numNodesWithProxies);
    dft->closeTrace();
    msg->printOut("PMgr::recvST");
    #endif

    //This function is divided into three parts. The tree root is msg->allPes[0]
    //1. set up its own immediate childrens
    int treesize = msg->numNodesWithProxies;    
    int iNChild = 0; //number of internal children
    int eNChild = 0; //number of external children
    if(treesize>0){
        iNChild = (msg->numPesOfNode[0]-1); //exclude the root itself
        eNChild = (proxySpanDim>(treesize-1))?(treesize-1):proxySpanDim;
    }
    int numChild = iNChild + eNChild;
    if(numChild==0){
        ProxyPatch *proxy = (ProxyPatch *) PatchMap::Object()->patch(msg->patch);
        proxy->setSpanningTree(msg->procID, NULL, 0);
        #ifdef USE_NODEPATCHMGR
        //set up proxyInfo inside NodeProxyMgr
        if(!PatchMap::Object()->homePatch(msg->patch)){
            //only when this processor contains a proxy patch of "msg->patch"
            //is the patch registeration in NodeProxyMgr needed,
            //and itself needs to be registered
            CProxy_NodeProxyMgr pm(CkpvAccess(BOCclass_group).nodeProxyMgr);
            NodeProxyMgr *npm = pm[CkMyNode()].ckLocalBranch();        
            npm->registerPatch(msg->patch, msg->numPesOfNode[0], msg->allPes);            
        }
        //set children in terms of node ids
        proxy->setSTNodeChildren(0, NULL);       
        #endif
        return;
    }

    nodecount++;
    //if (nodecount > MAX_INTERNODE) 
    //  iout << "Processor " << CkMyPe() << "has (actual) " << nodecount << " intermediate nodes." << endi;

    if(!PatchMap::Object()->homePatch(msg->patch)){
        //the home patch of this spanning tree has been already set up for its childrens
        ProxyPatch *proxy = (ProxyPatch *) PatchMap::Object()->patch(msg->patch);
        int *children = (int*)alloca(numChild*sizeof(int));
        //add external children
        int *p = msg->allPes + msg->numPesOfNode[0];
        for(int i=0; i<eNChild; i++) {
            children[i] = *p;
            p += msg->numPesOfNode[i+1];
        }
        //add internal children
        for(int i=eNChild, j=1; i<numChild; i++, j++) {
            children[i] = msg->allPes[j]; 
        }
        proxy->setSpanningTree(msg->procID, children, numChild);

        #ifdef USE_NODEPATCHMGR
        //set up proxyInfo inside NodeProxyMgr
        CProxy_NodeProxyMgr pm(CkpvAccess(BOCclass_group).nodeProxyMgr);
        NodeProxyMgr *npm = pm[CkMyNode()].ckLocalBranch();        
        npm->registerPatch(msg->patch, msg->numPesOfNode[0], msg->allPes);        

        //set children in terms of node ids
        int nodeChildren[eNChild+1];
        p = msg->allPes + msg->numPesOfNode[0];
        for(int i=0; i<eNChild; i++) {
            nodeChildren[i] = CkNodeOf(*p);
            p += msg->numPesOfNode[i+1];
        }
        //the last entry always stores the node id that contains this proxy
        nodeChildren[eNChild] = CkNodeOf(msg->allPes[0]);
        proxy->setSTNodeChildren(eNChild+1, nodeChildren);
        #endif
    }

    //2. send msgs for the tree to external children proxies
    if(eNChild > 0) {
        ResizeArray<int> *exTreeChildSize = new ResizeArray<int>[eNChild];
        ResizeArray<int *> *exTreeChildPtr = new ResizeArray<int *>[eNChild];    
    
        int nodesToCnt = 1; //the number of children each root (current root's 
                            //immedidate external nodes) has in each level
        int pos = 1; //track the iteration over msg->numPesOfNode and skip the current root
        int *pePtr = msg->allPes + msg->numPesOfNode[0];
        int done = 0;
        while(!done) {
            for(int childID=0; childID<eNChild;childID++) {
                //iterate nodes on each level
                for(int i=0; i<nodesToCnt; i++) {
                    int cursize = msg->numPesOfNode[pos];
                    exTreeChildSize[childID].add(cursize);
                    exTreeChildPtr[childID].add(pePtr);
                    pos++;
                    pePtr += cursize; 
                    if(pos==msg->numNodesWithProxies) {
                        done = 1;
                        break;
                    }
                }
                if(done) break;                         
            }
            nodesToCnt *= proxySpanDim;
        }
          
        for(int i=0; i<eNChild; i++) {                
            ResizeArray<int> *allSizes = &exTreeChildSize[i];
            ResizeArray<int *> *allPtrs = &exTreeChildPtr[i];
            int totalNodes = allSizes->size();
            int totalPes = 0;
            for(int j=0; j<totalNodes; j++) totalPes += allSizes->item(j);
            ProxyNodeAwareSpanningTreeMsg *cmsg = new(totalNodes, totalPes, 0) ProxyNodeAwareSpanningTreeMsg;
            cmsg->patch = msg->patch;
            cmsg->procID = CkMyPe();
            cmsg->numNodesWithProxies = totalNodes;
            int *pAllPes = cmsg->allPes;
            for(int j=0; j<totalNodes; j++) {
                int numPes = allSizes->item(j);
                cmsg->numPesOfNode[j] = numPes;
                memcpy(pAllPes, allPtrs->item(j), sizeof(int)*numPes);
                pAllPes += numPes;
            }
            #if defined(PROCTRACE_DEBUG) && defined(NAST_DEBUG)
            cmsg->printOut("sndExtChi:");
            #endif
            ProxyMgr::Object()->sendNodeAwareSpanningTree(cmsg);
        }    
        
        delete [] exTreeChildSize;
        delete [] exTreeChildPtr;  
    }

    //3. send msgs for the tree to the children proxies within the same (physical) node
    CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
    for(int i=0; i<iNChild; i++) {
        int pe = msg->allPes[i+1]; //excluding the root procID at allPes[0]
        #if defined(PROCTRACE_DEBUG) && defined(NAST_DEBUG)
        DebugFileTrace *dft = DebugFileTrace::Object();
        dft->openTrace();
        dft->writeTrace("Preparing send a msg to internal children for patch[%d] from proc %d to proc %d\n", 
                     msg->patch, CkMyPe(), pe);
        dft->closeTrace();
        #endif
        cp[pe].recvNodeAwareSTParent(msg->patch, CkMyPe());
    }    

    delete msg;
}

void ProxyMgr::recvNodeAwareSTParent(int patch, int parent){
#if defined(PROCTRACE_DEBUG) && defined(NAST_DEBUG)
    DebugFileTrace *dft = DebugFileTrace::Object();
    dft->openTrace();
    dft->writeTrace("PMgr::recvSTParent: for ProxyPatch[%d], parent is %d\n", patch, parent);
    dft->closeTrace();
#endif
    ProxyPatch *proxy = (ProxyPatch *) PatchMap::Object()->patch(patch);
    CmiAssert(proxy!=NULL);
    proxy->setSpanningTree(parent, NULL, 0);
}

void ProxyMgr::sendResults(ProxyResultVarsizeMsg *msg) {
    CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
    NodeID node = PatchMap::Object()->node(msg->patch);
    cp[node].recvResults(msg);
}

void ProxyMgr::recvResults(ProxyResultVarsizeMsg *msg) {
    HomePatch *home = PatchMap::Object()->homePatch(msg->patch);
    home->receiveResults(msg); // delete done in HomePatch::receiveResults()
}

void ProxyMgr::sendResults(ProxyResultMsg *msg) {
  CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
  NodeID node = PatchMap::Object()->node(msg->patch);
  cp[node].recvResults(msg);
}

void ProxyMgr::recvResults(ProxyResultMsg *msg) {
  HomePatch *home = PatchMap::Object()->homePatch(msg->patch);
  home->receiveResults(msg); // delete done in HomePatch::receiveResults()
}

void
ProxyMgr::sendResults(ProxyCombinedResultMsg *msg) {
  ProxyPatch *patch = (ProxyPatch *)PatchMap::Object()->patch(msg->patch);
  ProxyCombinedResultMsg *cMsg = patch->depositCombinedResultMsg(msg);
  if (cMsg) {    
    int destPe = patch->getSpanningTreeParent();
    CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
    if(destPe != CkMyPe()) {
#if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR)
      /*CkPrintf("ready to call node::recvImmRes on pe[%d] to dest[%d]\n", CkMyPe(), destPe);
      fflush(stdout);*/

      cMsg->destPe = destPe;
      CProxy_NodeProxyMgr cnp(CkpvAccess(BOCclass_group).nodeProxyMgr);
      cnp[CkNodeOf(destPe)].recvImmediateResults(cMsg);
#else    
      cp[destPe].recvImmediateResults(cMsg);
#endif
    }
    else{
      cp[destPe].recvResults(cMsg);
    }
  }
}

void
ProxyMgr::recvResults(ProxyCombinedResultMsg *msg) {
//Chao Mei: hack for QD in case of SMP with immediate msg
#if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR) && (CMK_SMP) && defined(NAMDSRC_IMMQD_HACK)
    if(proxyRecvSpanning && msg->isFromImmMsgCall){
//    CkPrintf("qdcreate called on pe[%d]\n", CkMyPe());
//    fflush(stdout);
        //To compensate for the counter loss for message creation
        //inside the process of immediate message on comm thread
        CkpvAccess(_qd)->create();
    }
#endif

  HomePatch *home = PatchMap::Object()->homePatch(msg->patch);
  if (home) {
    //printf("Home got a message\n");
    home->receiveResults(msg); // delete done in HomePatch::receiveResults()
  }
  else {
    NAMD_bug("ProxyMgr should receive result message on home processor");
  }
}

void ProxyMgr::recvImmediateResults(ProxyCombinedResultMsg *msg) {
  HomePatch *home = PatchMap::Object()->homePatch(msg->patch);
  if (home) {
    CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
    cp[CkMyPe()].recvResults(msg);
  }
  else {
    ProxyPatch *patch = (ProxyPatch *)PatchMap::Object()->patch(msg->patch);
    ProxyCombinedResultMsg *cMsg = patch->depositCombinedResultMsg(msg);
    if (cMsg) {
      CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
      cp[patch->getSpanningTreeParent()].recvImmediateResults(cMsg);
    }
  }
}

void NodeProxyMgr::recvImmediateResults(ProxyCombinedResultMsg *msg){
#if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR)
    //CkPrintf("recvImmRes called on comm thread%d pe[%d]\n", CkMyRank()==CmiMyNodeSize(), CkMyPe());
    //fflush(stdout);
    
    int destRank = CkRankOf(msg->destPe);
    PatchMap *pmap = localPatchMaps[destRank];
    HomePatch *home = pmap->homePatch(msg->patch);
    if (home) {
#if CMK_SMP && defined(NAMDSRC_IMMQD_HACK)
        msg->isFromImmMsgCall = (CkMyRank()==CkMyNodeSize());
#endif
        CProxy_ProxyMgr cp(localProxyMgr);        
        cp[msg->destPe].recvResults(msg);        
/*
        char *srcfrom = "Isfrom";
        if(CkMyRank()!=CmiMyNodeSize()) srcfrom="Notfrom";
      CkPrintf("%s comm thread from pe[%d]\n", srcfrom, CkMyPe());
      fflush(stdout);
*/  
    }
    else {
        ProxyPatch *patch = (ProxyPatch *)pmap->patch(msg->patch);
        ProxyCombinedResultMsg *cMsg = patch->depositCombinedResultMsg(msg);
        if (cMsg) {
            CProxy_NodeProxyMgr cnp(thisgroup);
            cMsg->destPe = patch->getSpanningTreeParent();
            cnp[CkNodeOf(cMsg->destPe)].recvImmediateResults(cMsg);            
        }
    }
#endif    
}

void
ProxyMgr::sendProxyData(ProxyDataMsg *msg, int pcnt, int *pids) {
#if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR)
    if(proxySendSpanning == 1) {
        CProxy_NodeProxyMgr cnp(CkpvAccess(BOCclass_group).nodeProxyMgr);
        for(int i=0; i<pcnt-1; i++) {
            ProxyDataMsg *copymsg = (ProxyDataMsg *)CkCopyMsg((void **)&msg);
            cnp[pids[i]].recvImmediateProxyData(copymsg);
        }
        cnp[pids[pcnt-1]].recvImmediateProxyData(msg);
        return;
    }
#endif
  CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
  cp.recvImmediateProxyData(msg,pcnt,pids);
}

void 
ProxyMgr::recvProxyData(ProxyDataMsg *msg) {
//Chao Mei: hack for QD in case of SMP with immediate msg
#if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR) && (CMK_SMP) && defined(NAMDSRC_IMMQD_HACK)
    if(proxySendSpanning && msg->isFromImmMsgCall){
//    CkPrintf("qdcreate called on pe[%d]\n", CkMyPe());
//    fflush(stdout);
        //To compensate for the counter loss for message creation
        //inside the process of immediate message on comm thread
        CkpvAccess(_qd)->create();
    }
#endif
  ProxyPatch *proxy = (ProxyPatch *) PatchMap::Object()->patch(msg->patch);
  proxy->receiveData(msg); // deleted in ProxyPatch::receiveAtoms()
}

void
ProxyMgr::recvImmediateProxyData(ProxyDataMsg *msg) {
  ProxyPatch *proxy = (ProxyPatch *) PatchMap::Object()->patch(msg->patch);  
  if (proxySendSpanning == 1) {
    // copy the message and send to spanning children
    int *pids = (int*)alloca(proxy->getSpanningTreeNChild()*sizeof(int));
    int npid = proxy->getSpanningTreeChild(pids);
    if (npid) {        
        ProxyDataMsg *newmsg = (ProxyDataMsg *)CkCopyMsg((void **)&msg);     

        ProxyMgr::Object()->sendProxyData(newmsg,npid,pids);
      #if 0
      //ChaoMei: buggy code??? the spanning tree doesn't always have 2 levels
      //At the second level of the tree immediate messages are not needed
      CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
      cp.recvProxyData(newmsg,npid,pids);
      #endif
    }
  }
  /* send to self via EP method to preserve priority */
  CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
  cp[CkMyPe()].recvProxyData(msg);
}

void NodeProxyMgr::recvImmediateProxyData(ProxyDataMsg *msg) {    
#if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR)
    CProxy_ProxyMgr cp(localProxyMgr);
    proxyTreeNode *ptn = proxyInfo[msg->patch];
    CmiAssert(ptn->numPes!=0);

    //re-send msg to this nodes's children nodes.
    //only the first pe of a node of node-aware ST should contain children nodes
    int rank = CkRankOf(ptn->peIDs[0]);
    PatchMap *pmap = localPatchMaps[rank];
    ProxyPatch *ppatch = (ProxyPatch *)pmap->patch(msg->patch);

    int npid = ppatch->getSTNNodeChild();
    int pids[npid];
    if(npid>0) {        
        ppatch->getSTNodeChild(pids);
        //only needs to send to other nodes, so check the last entry of pids.
        //This is because the data for proxies on the same node have been sent
        //by NodeProxyMgr.
        if(pids[npid-1]==CkMyNode()) npid--;
    }    
    CProxy_NodeProxyMgr cnp(thisgroup);
    for(int i=0; i<npid; i++) {
        ProxyDataMsg *copymsg = (ProxyDataMsg *)CkCopyMsg((void **)&msg);
        cnp[pids[i]].recvImmediateProxyData(copymsg);
    }    

    //re-send msg to it's internal cores
#if CMK_SMP && defined(NAMDSRC_IMMQD_HACK)
    msg->isFromImmMsgCall = (CkMyRank()==CkMyNodeSize());
#endif
    cp.recvProxyData(msg, ptn->numPes, ptn->peIDs);
#else
    CkAbort("Bad execution path to NodeProxyMgr::recvImmediateProxyData\n");
#endif
}

void
ProxyMgr::sendProxyAll(ProxyDataMsg *msg, int pcnt, int *pids) {
#if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR)
    if(proxySendSpanning == 1) {
        CProxy_NodeProxyMgr cnp(CkpvAccess(BOCclass_group).nodeProxyMgr);
        for(int i=0; i<pcnt-1; i++) {
            ProxyDataMsg *copymsg = (ProxyDataMsg *)CkCopyMsg((void **)&msg);
            cnp[pids[i]].recvImmediateProxyAll(copymsg);
        }
        cnp[pids[pcnt-1]].recvImmediateProxyAll(msg);
        return;
    }
#endif
  CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
  cp.recvImmediateProxyAll(msg,pcnt,pids);
}

void 
ProxyMgr::recvProxyAll(ProxyDataMsg *msg) {
//Chao Mei: hack for QD in case of SMP with immediate msg
#if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR) && (CMK_SMP) && defined(NAMDSRC_IMMQD_HACK)
    if(proxySendSpanning && msg->isFromImmMsgCall){
//    CkPrintf("qdcreate called on pe[%d]\n", CkMyPe());
//    fflush(stdout);
        //To compensate for the counter loss for message creation
        //inside the process of immediate message on comm thread
        CkpvAccess(_qd)->create();
    }
#endif

  ProxyPatch *proxy = (ProxyPatch *) PatchMap::Object()->patch(msg->patch);
  proxy->receiveAll(msg); // deleted in ProxyPatch::receiveAtoms()
}

void
ProxyMgr::recvImmediateProxyAll(ProxyDataMsg *msg) {
  ProxyPatch *proxy = (ProxyPatch *) PatchMap::Object()->patch(msg->patch);
  #if defined(PROCTRACE_DEBUG) && defined(NAST_DEBUG)
  DebugFileTrace *dft = DebugFileTrace::Object();
  dft->openTrace();
  dft->writeTrace("PMgr::recvImmPAll for patch[%d]\n", msg->patch);
  CmiAssert(proxy!=NULL);
  dft->writeTrace("PMgr::recvImmPAll assertion OK for patch[%d]\n", msg->patch);
  dft->closeTrace();
  #endif
  if (proxySendSpanning == 1) {
    // copy the message and send to spanning children
    int *pids = (int*)alloca(proxy->getSpanningTreeNChild()*sizeof(int));
    int npid = proxy->getSpanningTreeChild(pids);
    if (npid) {
        ProxyDataMsg *newmsg = (ProxyDataMsg *)CkCopyMsg((void **)&msg);      
      ProxyMgr::Object()->sendProxyAll(newmsg,npid,pids);
    }
  }
  /* send to self via EP method to preserve priority */
  CProxy_ProxyMgr cp(CkpvAccess(BOCclass_group).proxyMgr);
  cp[CkMyPe()].recvProxyAll(msg);
}

void NodeProxyMgr::recvImmediateProxyAll(ProxyDataMsg *msg) {    
#if defined(NODEAWARE_PROXY_SPANNINGTREE) && defined(USE_NODEPATCHMGR)
    CProxy_ProxyMgr cp(localProxyMgr);
    proxyTreeNode *ptn = proxyInfo[msg->patch];
    CmiAssert(ptn->numPes!=0);
    #if defined(PROCTRACE_DEBUG) && defined(NAST_DEBUG)
    //This could be executed on comm thd.
    printf("NodePMgr::recvImmPAll for patch[%d] on node %d rank %d, prepare to send proc ", msg->patch, CkMyNode(), CkMyRank());
    for(int i=0; i<ptn->numPes; i++) {
        printf("%d, ", ptn->peIDs[i]);
    }
    printf("\n");
    fflush(stdout);
    #endif

    //re-send msg to this nodes's children nodes.
    //only the first pe of a node of node-aware ST should contain children nodes
    int rank = CkRankOf(ptn->peIDs[0]);
    PatchMap *pmap = localPatchMaps[rank];
    ProxyPatch *ppatch = (ProxyPatch *)pmap->patch(msg->patch);

    int npid = ppatch->getSTNNodeChild();
    int pids[npid];
    if(npid>0) {        
        ppatch->getSTNodeChild(pids);
        //only needs to send to other nodes, so check the last entry of pids.
        //This is because the data for proxies on the same node have been sent
        //by NodeProxyMgr.
        if(pids[npid-1]==CkMyNode()) npid--;
    }
    
    CProxy_NodeProxyMgr cnp(thisgroup);
    for(int i=0; i<npid; i++) {
        ProxyDataMsg *copymsg = (ProxyDataMsg *)CkCopyMsg((void **)&msg);
        cnp[pids[i]].recvImmediateProxyAll(copymsg);
    }    

    //re-send msg to it's internal cores
#if CMK_SMP && defined(NAMDSRC_IMMQD_HACK)
    msg->isFromImmMsgCall = (CkMyRank()==CkMyNodeSize());
#endif
    cp.recvProxyAll(msg, ptn->numPes, ptn->peIDs);
#else
    CkAbort("Bad execution path to NodeProxyMgr::recvImmediateProxyData\n");
#endif
}

void ProxyMgr::printProxySpanningTree(){
#ifdef NODEAWARE_PROXY_SPANNINGTREE
    int numPatches = PatchMap::Object()->numPatches();
    for(int i=0; i<numPatches; i++) {
        proxyTreeNodeList oneList = ptree.naTrees[i];
        printf("ST tree for HomePatch[%d]: #nodes = %d\n", i, oneList.size()); 
        if(ptree.proxylist[i].size()==0) continue;
        printf("===%d=== pes/node: ", i);
        for(int j=0; j<oneList.size(); j++) {
            printf("%d ", oneList.item(j).numPes);
        }
        printf("\n");
        printf("===%d=== pe ids: ", i);
        for(int j=0; j<oneList.size(); j++) {
            for(int k=0; k<oneList.item(j).numPes; k++) {
                printf("%d ", oneList.item(j).peIDs[k]);
            }            
        }
        printf("\n");
    }    
    fflush(stdout);  
#else
    int numPatches = PatchMap::Object()->numPatches();
    for(int i=0; i<numPatches; i++) {
        NodeIDList oneList = ptree.trees[i];
        printf("ST tree for HomePatch[%d]: #nodes = %d\n", i, oneList.size()); 
        if(ptree.proxylist[i].size()==0) continue;        
        printf("===%d=== pe ids: ", i);
        for(int j=0; j<oneList.size(); j++) {            
            printf("%d ", oneList.item(j));            
        }
        printf("\n");
    }    
    fflush(stdout);  
#endif
}

void NodeProxyMgr::registerPatch(int patchID, int numPes, int *pes){
    if(proxyInfo[patchID]) {
        delete proxyInfo[patchID];
    }
    if(numPes == 0) {
        proxyInfo[patchID] = NULL;
    }else{
        proxyInfo[patchID] = new proxyTreeNode(CkNodeOf(pes[0]),numPes,pes);
    }
}

#include "ProxyMgr.def.h"

---