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 (srcObj.omID() != d2.srcObj.omID()
  96         || 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%" PRIu64 "",srcObj.omID().id.idx,
 113                      srcObj.id);
 114     kptr += pcount;
 115   }
 116
 117   //CmiAssert(destObj.get_type() == LD_OBJ_MSG);
 118   switch (destObj.get_type()) {
 119   case LD_PROC_MSG:
 120        pcount += sprintf(kptr,"%d", destObj.proc());
 121        break;
 122   case LD_OBJ_MSG: {
 123        LDObjKey &destKey = destObj.get_destObj();
 124        pcount += sprintf(kptr,"%d%" PRIu64 "XXXXXXXX",destKey.omID().id.idx,
 125                     destKey.objID());
 126        pcount -= 8;  /* The 'X's insure that the next few bytes are fixed */
 127        break;
 128        }
 129   case LD_OBJLIST_MSG: {
 130        int len;
 131        const LDObjKey *destKeys = destObj.get_destObjs(len);
 132        CmiAssert(len>0);
 133        pcount += sprintf(kptr,"%d%" PRIu64 "XXXXXXXX",destKeys[0].omID().id.idx,
 134                     destKeys[0].objID());
 135        pcount -= 8;  /* The 'X's insure that the next few bytes are fixed */
 136        break;
 137        }
 138   }
 139
 140   int k=-1;
 141   for(int i=0; i < (pcount+3)/4; i++)
 142     k ^= kstring[i];
 143
 144   // CmiPrintf("New key %d, %s\n",k,kstring);
 145
 146   return k;
 147 }
 148
 149 int LBCommData::hash(const int i, const int m) const
 150 {
 151   const double a = 0.6803398875;
 152   const int k = key();
 153   const double ka = k * a;
 154
 155   int h1 = (int) floor(m*(ka-floor(ka)));
 156   int h2 = 1;  // Should be odd, to guarantee that h2 and size of table
 157                // are relatively prime.
 158
 159   //  CmiPrintf("k=%d h1=%d h2=%d m=%d\n",k,h1,h2,m);
 160   return (h1 + i * h2) % m;
 161 }
 162
 163 void LBCommTable::GetCommData(LDCommData* data)
 164 {
 165   LDCommData* out=data;
 166   LBCommData* curtable=set;
 167   TableState* curstate=state;
 168   int i;
 169
 170   for(i=0; i < cur_sz; i++, curtable++, curstate++) {
 171     if (*curstate == InUse) {
 172       out->clearHash();
 173       if (curtable->from_proc()) {
 174         out->src_proc = curtable->src_proc;
 175       } else {
 176         out->src_proc = -1;
 177         out->sender.omID() = curtable->srcObj.omID();
 178         out->sender.objID() = curtable->srcObj.objID();
 179       }
 180       out->receiver = curtable->destObj;
 181       out->messages = curtable->n_messages;
 182       out->bytes = curtable->n_bytes;
 183       out++;
 184     }
 185   }
 186 }
 187
 188 struct LDCommDescComp {
 189   bool operator() (const LDCommDesc& lhs, const LDCommDesc &rhs) const {
 190     return (lhs.get_destObj() < rhs.get_destObj());
 191   }
 192 };
 193
 194 void LBCommTable::GetCommInfo(int& bytes, int& msgs, int& outsidepemsgs, int&
 195     outsidepebytes, int& num_nghbor, int& hops, int& hopbytes) {
 196
 197   LBCommData* curtable=set;
 198   TableState* curstate=state;
 199   int i;
 200   bytes = 0;
 201   msgs = 0;
 202   outsidepemsgs = 0;
 203   outsidepebytes = 0;
 204   hops = 0;
 205   hopbytes = 0;
 206   std::set<LDCommDesc, LDCommDescComp> num_neighbors;
 207
 208   int h;
 209
 210   for(i=0; i < cur_sz; i++, curtable++, curstate++) {
 211     if (*curstate == InUse) {
 212       msgs += curtable->n_messages;
 213       bytes += curtable->n_bytes;
 214       if (curtable->destObj.get_type() == LD_OBJ_MSG) {
 215         num_neighbors.insert(curtable->destObj);
 216       }
 217
 218       if (curtable->destObj.lastKnown() != CkMyPe()) {
 219         outsidepebytes += curtable->n_bytes;
 220         outsidepemsgs += curtable->n_messages;
 221         if(curtable->destObj.lastKnown()>=0 && curtable->destObj.lastKnown()<CkNumPes()){
 222           TopoManager_getHopsBetweenPeRanks(CkMyPe(), curtable->destObj.lastKnown(), &h);
 223           hops += curtable->n_messages * h;
 224           hopbytes += curtable->n_bytes * h;
 225         }
 226       }
 227     }
 228   }
 229   num_nghbor = num_neighbors.size();
 230 }
 231
 232 #endif // CMK_LBDB_ON
 233
 234 /*@}*/