src/ck-ldb/LBComm.C

   1 /**
   2  * \addtogroup CkLdb
   3 */
   4 /*@{*/
   5
   6 #include <converse.h>
   7
   8 #if CMK_LBDB_ON
   9
  10 #include <math.h>
  11 #include "LBComm.h"
  12 #include <set>
  13
  14 #include "TopoManager.h"
  15
  16 // Hash table mostly based on open hash table from Introduction to
  17 // Algorithms by Cormen, Leiserson, and Rivest
  18
  19 // Moved comparison function to LDObjIDEqual
  20
  21 // static inline bool ObjIDEqual(const LDObjid i1, const LDObjid i2)
  22 // {
  23 //   return (bool)(i1.id[0] == i2.id[0]
  24 //       && i1.id[1] == i2.id[1] && i1.id[2] == i2.id[2]
  25 //       && i1.id[3] == i2.id[3]);
  26 // };
  27
  28 LBCommData* LBCommTable::HashInsert(const LBCommData &data)
  29 {
  30   if (in_use > cur_sz/2)
  31     Resize();
  32   int i = 0;
  33   int j;
  34   do {
  35     j = data.hash(i,cur_sz);
  36     //    CmiPrintf("Hashing to %d, %d %d\n",j,i,cur_sz);
  37     if (state[j] == nil) {
  38       state[j] = InUse;
  39       set[j] = data;
  40       in_use++;
  41       return &set[j];
  42     } else i++;
  43   } while (i != cur_sz);
  44
  45   // No room for item, but I should never get here, because I would have
  46   // resized the list
  47   CmiPrintf("HashInsert Couldn't insert!\n");
  48   return 0;
  49 }
  50
  51 LBCommData* LBCommTable::HashSearch(const LBCommData &data)
  52 {
  53   int i=0;
  54   int j;
  55   do {
  56     j = data.hash(i,cur_sz);
  57     if (state[j] != nil && set[j].equal(data)) {
  58       return &set[j];
  59     }
  60     i++;
  61   } while (state[j] != nil && i != cur_sz);
  62   return 0;
  63 }
  64
  65 LBCommData* LBCommTable::HashInsertUnique(const LBCommData &data)
  66 {
  67   LBCommData* item = HashSearch(data);
  68   if (!item) {
  69     item = HashInsert(data);
  70   }
  71   return item;
  72 }
  73
  74 void LBCommTable::Resize()
  75 {
  76   LBCommData* old_set = set;
  77   TableState* old_state = state;
  78   int old_sz = cur_sz;
  79
  80   NewTable(old_sz*2);
  81   for(int i=0; i < old_sz; i++) {
  82     if (old_state[i] == InUse)
  83       HashInsert(old_set[i]);
  84   }
  85   delete [] old_set;
  86   delete [] old_state;
  87 }
  88
  89 bool LBCommData::equal(const LBCommData &d2) const
  90 {
  91   if (from_proc()) {
  92     if (src_proc != d2.src_proc)
  93       return false;
  94   } else {
  95     if (!LDOMidEqual(srcObj.omID(), d2.srcObj.omID())
  96         || !LDObjIDEqual(srcObj.objID(),d2.srcObj.objID()) )
  97       return false;
  98   }
  99   return (bool)(destObj == d2.destObj);
 100 }
 101
 102 int LBCommData::compute_key()
 103 {
 104   int kstring[80];
 105   char* kptr = (char*)((void*)(&(kstring[0])));
 106   int pcount;
 107
 108   if (from_proc()) {
 109     pcount = sprintf(kptr,"%d",src_proc);
 110     kptr += pcount;
 111   } else {
 112     pcount = sprintf(kptr,"%d%d%d%d%d",srcObj.omID().id.idx,
 113                      srcObj.id.id[0],srcObj.id.id[1],
 114                      srcObj.id.id[2],srcObj.id.id[3]);
 115     kptr += pcount;
 116   }
 117
 118   //CmiAssert(destObj.get_type() == LD_OBJ_MSG);
 119   switch (destObj.get_type()) {
 120   case LD_PROC_MSG:
 121        pcount += sprintf(kptr,"%d", destObj.proc());
 122        break;
 123   case LD_OBJ_MSG: {
 124        LDObjKey &destKey = destObj.get_destObj();
 125        pcount += sprintf(kptr,"%d%d%d%d%dXXXXXXXX",destKey.omID().id.idx,
 126                     destKey.objID().id[0],destKey.objID().id[1],
 127                     destKey.objID().id[2],destKey.objID().id[3]);
 128        pcount -= 8;  /* The 'X's insure that the next few bytes are fixed */
 129        break;
 130        }
 131   case LD_OBJLIST_MSG: {
 132        int len;
 133        LDObjKey *destKeys = destObj.get_destObjs(len);
 134        CmiAssert(len>0);
 135        pcount += sprintf(kptr,"%d%d%d%d%dXXXXXXXX",destKeys[0].omID().id.idx,
 136                     destKeys[0].objID().id[0],destKeys[0].objID().id[1],
 137                     destKeys[0].objID().id[2],destKeys[0].objID().id[3]);
 138        pcount -= 8;  /* The 'X's insure that the next few bytes are fixed */
 139        break;
 140        }
 141   }
 142
 143   int k=-1;
 144   for(int i=0; i < (pcount+3)/4; i++)
 145     k ^= kstring[i];
 146
 147   // CmiPrintf("New key %d, %s\n",k,kstring);
 148
 149   return k;
 150 }
 151
 152 int LBCommData::hash(const int i, const int m) const
 153 {
 154   const double a = 0.6803398875;
 155   const int k = key();
 156   const double ka = k * a;
 157
 158   int h1 = (int) floor(m*(ka-floor(ka)));
 159   int h2 = 1;  // Should be odd, to guarantee that h2 and size of table
 160                // are relatively prime.
 161
 162   //  CmiPrintf("k=%d h1=%d h2=%d m=%d\n",k,h1,h2,m);
 163   return (h1 + i * h2) % m;
 164 }
 165
 166 void LBCommTable::GetCommData(LDCommData* data)
 167 {
 168   LDCommData* out=data;
 169   LBCommData* curtable=set;
 170   TableState* curstate=state;
 171   int i;
 172
 173   for(i=0; i < cur_sz; i++, curtable++, curstate++) {
 174     if (*curstate == InUse) {
 175       out->clearHash();
 176       if (curtable->from_proc()) {
 177         out->src_proc = curtable->src_proc;
 178       } else {
 179         out->src_proc = -1;
 180         out->sender.omID() = curtable->srcObj.omID();
 181         out->sender.objID() = curtable->srcObj.objID();
 182       }
 183       out->receiver = curtable->destObj;
 184       out->messages = curtable->n_messages;
 185       out->bytes = curtable->n_bytes;
 186       out++;
 187     }
 188   }
 189 }
 190
 191 struct LDCommDescComp {
 192   bool operator() (const LDCommDesc& lhs, const LDCommDesc &rhs) const {
 193     return (lhs.get_destObj() < rhs.get_destObj());
 194   }
 195 };
 196
 197 void LBCommTable::GetCommInfo(int& bytes, int& msgs, int& outsidepemsgs, int&
 198     outsidepebytes, int& num_nghbor, int& hops, int& hopbytes) {
 199
 200   LBCommData* curtable=set;
 201   TableState* curstate=state;
 202   int i;
 203   bytes = 0;
 204   msgs = 0;
 205   outsidepemsgs = 0;
 206   outsidepebytes = 0;
 207   hops = 0;
 208   hopbytes = 0;
 209   std::set<LDCommDesc, LDCommDescComp> num_neighbors;
 210
 211   int h;
 212
 213   for(i=0; i < cur_sz; i++, curtable++, curstate++) {
 214     if (*curstate == InUse) {
 215       msgs += curtable->n_messages;
 216       bytes += curtable->n_bytes;
 217       if (curtable->destObj.get_type() == LD_OBJ_MSG) {
 218         num_neighbors.insert(curtable->destObj);
 219       }
 220
 221       if (curtable->destObj.lastKnown() != CkMyPe()) {
 222         outsidepebytes += curtable->n_bytes;
 223         outsidepemsgs += curtable->n_messages;
 224         if(curtable->destObj.lastKnown()>=0 && curtable->destObj.lastKnown()<CkNumPes()){
 225           TopoManager_getHopsBetweenPeRanks(CkMyPe(), curtable->destObj.lastKnown(), &h);
 226           hops += curtable->n_messages * h;
 227           hopbytes += curtable->n_bytes * h;
 228         }
 229       }
 230     }
 231   }
 232   num_nghbor = num_neighbors.size();
 233 }
 234
 235 #endif // CMK_LBDB_ON
 236
 237 /*@}*/