Robust/src/Runtime/DSTM/interface/prefetch.c

   1 #include "prefetch.h"
   2 #include "prelookup.h"
   3
   4 /* Steps for the new prefetch call */
   5 // Function for new prefetch call
   6 void rangePrefetch(int prefetchsiteid, int ntuples, unsigned int *baseoids,
   7     unsigned short *numoffsets, short *offsets) {
   8   // a[0][1] - a[3][1] = a.0.3
   9   // a.f.h   = a.f.h
  10   // a.f.next.h = a.f.0.next.0.h
  11   // a.f.next.next.h  = a.f.next.2.h
  12   /* Allocate memory in prefetch queue and push the block there */
  13   int qnodesize = 2*sizeof(int)+ ntuples *(sizeof(unsigned int) + sizeof(unsigned short)) + numoffsets[ntuples -1] * sizeof(short);
  14   char *node = (char *) getmemory(qnodesize);
  15   int top = numoffsets[ntuples -1];
  16
  17   if(node == NULL)
  18     return;
  19
  20   int index = 0;
  21   *((int *)(node)) = prefetchsiteid;
  22   *((int *)(node + sizeof(int))) = ntuples;
  23   index = 2 * sizeof(int);
  24   memcpy(node+index, baseoids, ntuples * sizeof(unsigned int));
  25   index = index + ntuples *(sizeof(unsigned int));
  26   memcpy(node+index, numoffsets, ntuples * sizeof(unsigned short));
  27   index = index + ntuples *(sizeof(unsigned short));
  28   memcpy(node+index, offsets, top * sizeof(short));
  29
  30   movehead(qnodesize);
  31 }
  32
  33 void *transPrefetchNew() {
  34   while(1) {
  35     /* Read from prefetch queue */
  36     void *node = gettail();
  37     /* Check tuples if they are found locally */
  38     checkIfLocal(node);
  39
  40   }
  41 }
  42
  43 int getsize(short *ptr, int n) {
  44   int sum = 0, newsum, i;
  45   for (i = n-1; i >= 0; i--) {
  46     newsum = (1 + ptr[i])+((1 + ptr[i])*sum);
  47     sum = newsum;
  48   }
  49   return sum;
  50 }
  51
  52 void checkIfLocal(char *ptr) {
  53   int siteid = *(GET_SITEID(ptr));
  54   unsigned int *baseoids = GET_PTR_OID(ptr);
  55   unsigned int ntuples = *(GET_NTUPLES(ptr));
  56   unsigned short *endoffsets = GET_PTR_EOFF(ptr, ntuples);
  57   short *offsets = GET_PTR_ARRYFLD(ptr, ntuples);
  58   int i, j, k;
  59   int numLocal = 0;
  60
  61   prefetchpile_t * head=NULL;
  62
  63   // Iterate for each object
  64   for (i = 0; i < ntuples; i++) {
  65     int numoffset = (i == 0) ? endoffsets[0] : (endoffsets[i] - endoffsets[i-1]);
  66     int sizetmpObjSet = numoffset >> 1;
  67     unsigned short tmpobjset[sizetmpObjSet];
  68     int l;
  69     for (l = 0; l < sizetmpObjSet; l++) {
  70       tmpobjset[l] = GET_RANGE(offsets[2*l+1]);
  71     }
  72     int maxChldOids = getsize(tmpobjset, sizetmpObjSet)+1;
  73     unsigned int chldOffstFrmBase[maxChldOids];
  74     chldOffstFrmBase[0] = baseoids[i];
  75     int tovisit = 0, visited = -1;
  76     // Iterate for each element of offsets
  77     for (j = 0; j < numoffset; j++) {
  78       // Iterate over each element to be visited
  79       while (visited != tovisit) {
  80         if(chldOffstFrmBase[visited+1] == 0) {
  81           visited++;
  82           continue;
  83         }
  84         if (!isOidAvail(chldOffstFrmBase[visited+1])) {
  85           // Add to remote requests
  86           unsigned int oid = chldOffstFrmBase[visited+1];
  87           unsigned int * oidarray = NULL; //TODO FILL THIS ARRAY
  88           int machinenum = lhashSearch(oid);
  89           insertPile(machinenum, oidarray, numoffset-j, offsets, &head);
  90           break;
  91         } else {
  92           // iterate over each offset
  93           int retval;
  94           if((retval = lookForObjs(chldOffstFrmBase, offsets, &j,
  95               &visited, &tovisit)) == 0) {
  96             printf("%s() Error: Object not found %s at line %d\n",
  97                 __func__, __FILE__, __LINE__);
  98           }
  99         }
 100         visited++;
 101       }
 102     } // end iterate for each element of offsets
 103
 104     //Entire prefetch found locally
 105     if(j == numoffset) {
 106       numLocal++;
 107       goto tuple;
 108     }
 109 tuple:
 110     ;
 111   } // end iterate for each object
 112
 113   /* handle dynamic prefetching */
 114   handleDynPrefetching(numLocal, ntuples, siteid);
 115 }
 116
 117 int isOidAvail(unsigned int oid) {
 118   objheader_t * header;
 119   if((header=(objheader_t *)mhashSearch(oid))!=NULL) {
 120     //Found on machine
 121     return 1;
 122   } else if ((header=(objheader_t *)prehashSearch(oid))!=NULL) {
 123     return 1;
 124   } else {
 125     return 0;
 126   }
 127 }
 128
 129 int lookForObjs(int *chldOffstFrmBase, short *offsets,
 130     int *index, int *visited, int *tovisit) {
 131   objheader_t *header;
 132   unsigned int oid = chldOffstFrmBase[*visited+1];
 133   if((header = (objheader_t *)mhashSearch(oid))!= NULL) {
 134     //Found on machine
 135     ;
 136   } else if((header = (objheader_t *)prehashSearch(oid))!=NULL) {
 137     //Found in prefetch cache
 138     ;
 139   } else {
 140     printf("DEBUG->%s()THIS SHOULD NOR HAPPEN\n", __func__);
 141     return 0;
 142   }
 143
 144   if(TYPE(header) > NUMCLASSES) {
 145     int elementsize = classsize[TYPE(header)];
 146     struct ArrayObject *ao = (struct ArrayObject *) (((char *)header) + sizeof(objheader_t));
 147     int length = ao->___length___;
 148     /* Check if array out of bounds */
 149     int startindex = offsets[*index];
 150     int range = GET_RANGE(offsets[(*index)+1]);
 151     if(range > 0 && range < length) {
 152       short stride = GET_STRIDE(offsets[(*index)+1]);
 153       stride = stride + 1; //NOTE  bit pattern 000 => stride = 1, 001 => stride = 2
 154       int i;
 155       //check is stride +ve or negative
 156       if(GET_STRIDEINC(offsets[(*index)]+1)) { //-ve stride
 157         for(i = startindex; i <= range+1; i = i - stride) {
 158           unsigned int oid = 0;
 159           if((i < 0 || i >= length)) {
 160             //if yes treat the object as found
 161             oid = 0;
 162             continue;
 163           } else {
 164             // compute new object
 165             oid = *((unsigned int *)(((char *)ao) + sizeof(struct ArrayObject) + (elementsize*i)));
 166           }
 167           // add new object
 168           chldOffstFrmBase[*tovisit] = oid;
 169           *tovisit = *tovisit + 1;
 170         }
 171       } else { //+ve stride
 172         for(i = startindex; i <= range; i = i + stride) {
 173           unsigned int oid = 0;
 174           if(i < 0 || i >= length) {
 175             //if yes treat the object as found
 176             oid = 0;
 177             continue;
 178           } else {
 179             // compute new object
 180             oid = *((unsigned int *)(((char *)ao) + sizeof(struct ArrayObject) + (elementsize*i)));
 181           }
 182           // add new object
 183           chldOffstFrmBase[*tovisit] = oid;
 184           *tovisit = *tovisit + 1;
 185         }
 186       }
 187     } else if(range == 0) {
 188       if(startindex >=0 || startindex < length) {
 189         unsigned int oid = *((unsigned int *)(((char *)ao) + sizeof(struct ArrayObject) + (elementsize*startindex)));
 190         // add new object
 191         chldOffstFrmBase[*tovisit] = oid;
 192         *tovisit = *tovisit + 1;
 193       }
 194     }
 195   } else { //linked list
 196     int startindex = offsets[*index];
 197     int range = GET_RANGE(offsets[(*index)+1]);
 198     unsigned int oid;
 199     if(range == 0) {
 200       oid = *((unsigned int *)(((char *)header) + sizeof(objheader_t) + startindex));
 201       // add new object
 202       chldOffstFrmBase[*tovisit] = oid;
 203       *tovisit = *tovisit + 1;
 204     } else {
 205       int i;
 206       for(i = 0; i < range; i++) {
 207         oid = *((unsigned int *)(((char *)header) + sizeof(objheader_t) + startindex));
 208         // add new object
 209         chldOffstFrmBase[*tovisit] = oid;
 210         *tovisit = *tovisit + 1;
 211       }
 212     }
 213   }
 214   *index = *index + 2;
 215   return 1;
 216 }
 217
 218 #if 0
 219 int lookForObjs(unsigned int *oid, short *offset, int *numoids, int *newbase) {
 220   objheader_t *header;
 221   if((header = mhashSearch(*oid))!= NULL) {
 222     //Found on machine
 223     ;
 224   } else if((header = prehashSearch(*oid))!=NULL) {
 225     //Found in prefetch cache
 226     ;
 227   } else {
 228     return 0;
 229   }
 230
 231   if(TYPE(header) > NUMCLASSES) {
 232     int elementsize = classsize[TYPE(header)];
 233     struct ArrayObject *ao = (struct ArrayObject *) (((char *)header) + sizeof(objheader_t));
 234     int length = ao->___length___;
 235         /* Check if array out of bounds */
 236     if(offset[*newbase] < 0 || offset[*newbase] >= length) {
 237       //if yes treat the object as found
 238       (*oid)=0;
 239       return 1;
 240     } else {
 241       if(getOtherOid(header, ao, offset, numoids, newbase))
 242         return 1;
 243     }
 244   } else { //linked list
 245     //(*oid) = *((unsigned int *)(((char *)header) + sizeof(objheader_t) + offset));
 246     if(getNext(header, offset, numoids, newbase))
 247       return 1;
 248     //(*newbase)++;
 249   }
 250 }
 251
 252 void resolveArrays(unsigned int *arrayOfOids, short *offset, int *numoids, int *newbase) {
 253   /*
 254   int i;
 255   */
 256 }
 257
 258 int getOtherOid(header, ao, offset, numoids, newbase) {
 259   short range, stride;
 260   short startindex = offset[*newbase];
 261   int getnewbaseVal = *newbase + 1;
 262   if(getnewbaseVal == 0) {
 263     (*oid) = *((unsigned int *)(((char *)ao) + sizeof(struct ArrayObject) + (elementsize*startindex)));
 264     (*newbase) = (*newbase) + 2; //skip the immediate offset
 265     return 1;
 266   } else if(getnewbaseVal > 0) {
 267     /* Resolve the oids within a given range */
 268     (*newbase)++;
 269     range = GET_RANGE(offset[*newbase]);
 270     stride = GET_STRIDE((void *)(offset[*newbase]));
 271     stride = stride + 1; //NOTE 000 => stride = 1, 001 => stride = 2
 272     int index = 0;
 273     unsigned int arrayOfOids[range+1];
 274     if(GET_STRIDEINC(offset[*newbase])) { //-ve stride
 275       int i;
 276       for(i = startindex; i <= range; i = i - stride) {
 277         if(i < 0 || i >= length) {
 278           //if yes treat the object as found
 279           (*oid)=0;
 280           return 1;
 281         }
 282         arrayOfOids[index] = *((unsigned int *)(((char *)ao) + sizeof(struct ArrayObject) + (elementsize*i)));
 283         index++;
 284       }
 285     } else { //+ve stride
 286       int i;
 287       for(i = startindex; i <= range; i = i + stride) {
 288         if(i < 0 || i >= length) {
 289           //if yes treat the object as found
 290           (*oid)=0;
 291           return 1;
 292         }
 293         arrayOfOids[index] = *((unsigned int *)(((char *)ao) + sizeof(struct ArrayObject) + (elementsize*i)));
 294         index++;
 295       }
 296     }
 297     //(*oid) = *((unsigned int *)(((char *)ao) + sizeof(struct ArrayObject) + (elementsize*startindex)));
 298     (*newbase) = (*newbase) + 2;
 299     return 1;
 300   } else {
 301     ;
 302   }
 303 }
 304
 305
 306 void checkIfLocal(char *ptr) {
 307   int siteid = *(GET_SITEID(ptr));
 308   int ntuples = *(GET_NTUPLES(ptr));
 309   unsigned int *baseoids = GET_PTR_OID(ptr);
 310   unsigned short *numoffsets = GET_PTR_EOFF(ptr, ntuples);
 311   short *offsets = GET_PTR_ARRYFLD(ptr, ntuples);
 312   prefetchpile_t * head=NULL;
 313   int numLocal = 0;
 314
 315   int i ;
 316   for(i=0; i<ntuples; i++) {
 317     unsigned short baseindex=(i==0) ? 0 : numoffsets[i -1];
 318     unsigned short endindex = numoffsets[i];
 319     unsigned int oid = baseoids[i];
 320     int numoids = 0;
 321     if(oid == 0)
 322       continue;
 323
 324     //Look up fields locally
 325     int newbase;
 326     for(newbase=baseindex; newbase<endindex; ) {
 327       if(!lookForObjs(&oid, &offsets[newbase], &numoids, &newbase)) {
 328         break;
 329       }
 330       //Ended in a null pointer
 331       if(oid == 0)
 332         goto tuple;
 333     }
 334
 335     //Add to remote request
 336     machinenum=lhashSearch(oid);
 337     // Create an array of oids and offsets
 338     unsigned int arrayoid[numoids];
 339     unsigned short arraynumoffset[numoids];
 340     void *arryfields[numoids];
 341     for(i = 0; i<numoids; i++) {
 342       arrayoid[i] = oid;
 343       arraynumoffset[i] = endindex - newbase;
 344       arryfields[i] = (void*)(&arryfields[newbase]);
 345     }
 346     //insertPile(machinenum, oid, endindex-newbase, &arryfields[newbase], &head);
 347     insertPile(machinenum, arrayoid, arraynumoffset, arryfields, &head);
 348 tuple:
 349     ;
 350   }
 351 }
 352 #endif