Robust/src/Runtime/mlp_runtime.c

   1 #include "runtime.h"
   2
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <assert.h>
   6
   7 #include "mem.h"
   8 #include "mlp_runtime.h"
   9 #include "workschedule.h"
  10
  11
  12 /*
  13 __thread struct Queue* seseCallStack;
  14 __thread pthread_once_t mlpOnceObj = PTHREAD_ONCE_INIT;
  15 void mlpInitOncePerThread() {
  16   seseCallStack = createQueue();
  17 }
  18 */
  19 __thread SESEcommon_p seseCaller;
  20
  21
  22 void* mlpAllocSESErecord( int size ) {
  23   void* newrec = RUNMALLOC( size );
  24   if( newrec == 0 ) {
  25     printf( "mlpAllocSESErecord did not obtain memory!\n" );
  26     exit( -1 );
  27   }
  28   return newrec;
  29 }
  30
  31
  32 void mlpFreeSESErecord( void* seseRecord ) {
  33   RUNFREE( seseRecord );
  34 }
  35
  36 MemoryQueue** mlpCreateMemoryQueueArray(int numMemoryQueue){
  37   int i;
  38   MemoryQueue** newMemoryQueue=(MemoryQueue**)RUNMALLOC( sizeof( MemoryQueue* ) * numMemoryQueue );
  39   for(i=0; i<numMemoryQueue; i++){
  40     newMemoryQueue[i]=createMemoryQueue();
  41   }
  42   return newMemoryQueue;
  43 }
  44
  45 REntry* mlpCreateREntryArray(){
  46   REntry* newREntryArray=(REntry*)RUNMALLOC(sizeof(REntry)*NUMRENTRY);
  47   return newREntryArray;
  48 }
  49
  50 REntry* mlpCreateFineREntry(int type, void* seseToIssue, void* dynID){
  51   REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
  52   newREntry->type=type;
  53   newREntry->seseRec=seseToIssue;
  54   newREntry->dynID=dynID;
  55   return newREntry;
  56 }
  57
  58 REntry* mlpCreateREntry(int type, void* seseToIssue){
  59   REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
  60   newREntry->type=type;
  61   newREntry->seseRec=seseToIssue;
  62   return newREntry;
  63 }
  64
  65 int isParent(REntry *r) {
  66   if (r->type==PARENTREAD || r->type==PARENTWRITE) {
  67     return TRUE;
  68   } else {
  69     return FALSE;
  70   }
  71 }
  72
  73 int isParentCoarse(REntry *r){
  74   if (r->type==PARENTCOARSE){
  75     return TRUE;
  76   }else{
  77     return FALSE;
  78   }
  79 }
  80
  81 int isFineRead(REntry *r) {
  82   if (r->type==READ || r->type==PARENTREAD) {
  83     return TRUE;
  84   } else {
  85     return FALSE;
  86   }
  87 }
  88
  89 int isFineWrite(REntry *r) {
  90   if (r->type==WRITE || r->type==PARENTWRITE) {
  91     return TRUE;
  92   } else {
  93     return FALSE;
  94   }
  95 }
  96
  97 int isCoarse(REntry *r){
  98   if(r->type==COARSE || r->type==PARENTCOARSE){
  99     return TRUE;
 100   } else {
 101     return FALSE;
 102   }
 103 }
 104
 105 int isSCC(REntry *r){
 106   if(r->type==SCCITEM){
 107     return TRUE;
 108   } else {
 109     return FALSE;
 110   }
 111 }
 112
 113 int isSingleItem(MemoryQueueItem *qItem){
 114   if(qItem->type==SINGLEITEM){
 115     return TRUE;
 116   } else {
 117     return FALSE;
 118   }
 119 }
 120
 121 int isHashtable(MemoryQueueItem *qItem){
 122   if(qItem->type==HASHTABLE){
 123     return TRUE;
 124   } else {
 125     return FALSE;
 126   }
 127 }
 128
 129 int isVector(MemoryQueueItem *qItem){
 130   if(qItem->type==VECTOR){
 131     return TRUE;
 132   } else {
 133     return FALSE;
 134   }
 135 }
 136
 137 int isReadBinItem(BinItem* b){
 138   if(b->type==READBIN){
 139     return TRUE;
 140   }else{
 141     return FALSE;
 142   }
 143 }
 144
 145 int isWriteBinItem(BinItem* b){
 146   if(b->type==WRITEBIN){
 147     return TRUE;
 148   }else{
 149     return FALSE;
 150   }
 151 }
 152
 153 int generateKey(unsigned int data){
 154   return (data&H_MASK)>> 4;
 155 }
 156
 157 Hashtable* createHashtable(){
 158   int i=0;
 159   Hashtable* newTable=(Hashtable*)RUNMALLOC(sizeof(Hashtable));
 160   newTable->item.type=HASHTABLE;
 161   for(i=0;i<NUMBINS;i++){
 162     newTable->array[i]=(BinElement*)RUNMALLOC(sizeof(BinElement));
 163     newTable->array[i]->head=NULL;
 164     newTable->array[i]->tail=NULL;
 165   }
 166   newTable->unresolvedQueue=NULL;
 167   return newTable;
 168 }
 169
 170 WriteBinItem* createWriteBinItem(){
 171   WriteBinItem* binitem=(WriteBinItem*)RUNMALLOC(sizeof(WriteBinItem));
 172   binitem->item.type=WRITEBIN;
 173   return binitem;
 174 }
 175
 176 ReadBinItem* createReadBinItem(){
 177   ReadBinItem* binitem=(ReadBinItem*)RUNMALLOC(sizeof(ReadBinItem));
 178   binitem->index=0;
 179   binitem->item.type=READBIN;
 180   return binitem;
 181 }
 182
 183 Vector* createVector(){
 184   Vector* vector=(Vector*)RUNMALLOC(sizeof(Vector));
 185   vector->index=0;
 186   vector->item.type=VECTOR;
 187   return vector;
 188 }
 189
 190 SCC* createSCC(){
 191   SCC* scc=(SCC*)RUNMALLOC(sizeof(SCC));
 192   scc->item.type=SINGLEITEM;
 193   return scc;
 194 }
 195
 196 MemoryQueue* createMemoryQueue(){
 197   MemoryQueue* queue = (MemoryQueue*)RUNMALLOC(sizeof(MemoryQueue));
 198   MemoryQueueItem* dummy=(MemoryQueueItem*)RUNMALLOC(sizeof(MemoryQueueItem));
 199   dummy->type=3; // dummy type
 200   dummy->total=0;
 201   dummy->status=READY;
 202   queue->head = dummy;
 203   queue->tail = dummy;
 204   return queue;
 205 }
 206
 207 int ADDRENTRY(MemoryQueue * q, REntry * r) {
 208   if (isFineRead(r) || isFineWrite(r)) {
 209     return ADDTABLE(q, r);
 210   } else if (isCoarse(r)) {
 211     return ADDVECTOR(q, r);
 212   } else if (isSCC(r)) {
 213     return ADDSCC(q, r);
 214   }
 215 }
 216
 217 int ADDTABLE(MemoryQueue *q, REntry *r) {
 218   if(!isHashtable(q->tail)) {
 219     //Fast Case
 220     MemoryQueueItem* tail=q->tail;
 221     if (isParent(r) && tail->total==0 && q->tail==q->head) {
 222       return READY;
 223     }
 224
 225     //Add table
 226     Hashtable* h=createHashtable();
 227     tail->next=(MemoryQueueItem*)h;
 228     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status********
 229     if (BARRIER() && tail->status==READY && tail->total==0 && q->tail==q->head) {
 230       //previous Q item is finished
 231       h->item.status=READY;
 232     }
 233     q->tail=(MemoryQueueItem*)h;
 234     // handle the the queue item case
 235     if(q->head->type==3){
 236       q->head=(MemoryQueueItem*)h;
 237     }
 238   }
 239
 240   //at this point, have table
 241   Hashtable* table=(Hashtable*)q->tail;
 242   r->hashtable=table;
 243   if(*(r->pointer)==0 || (*(r->pointer)!=0 && table->unresolvedQueue!=NULL)){
 244      struct Queue* val;
 245     // grab lock on the queue
 246     do {
 247       val=(struct Queue*)0x1;
 248       val=(struct Queue*)LOCKXCHG((unsigned INTPTR*)&(table->unresolvedQueue), (unsigned INTPTR)val);
 249     } while(val==(struct Queue*)0x1);
 250
 251     if(val==NULL){
 252       //first case
 253       if(*(r->pointer)!=0){
 254         // pointer is already resolved.
 255         table->unresolvedQueue=val; //released lock;
 256         return ADDTABLE(q,r);
 257       }
 258       table->unresolvedQueue=(struct Queue*)0x1;
 259       struct Queue* queue=createQueue();
 260       addNewItem(queue,r);
 261       atomic_inc(&table->item.total);
 262       table->unresolvedQueue=queue; // expose new queue
 263     }else{
 264       if(val==NULL){
 265         // someone else has already cleared all queue stuff
 266         table->unresolvedQueue=val; // released lock
 267         return ADDTABLE(q,r);
 268       }
 269       addNewItemBack(val,r);
 270       atomic_inc(&table->item.total);
 271       table->unresolvedQueue=val; // released lock
 272     }
 273     return NOTREADY;
 274   }
 275
 276   r->dynID=(void*)*(r->pointer); // interim fix.
 277   BinItem * val;
 278   int key=generateKey((unsigned int)(unsigned INTPTR)r->dynID);
 279   do {
 280     val=(BinItem*)0x1;
 281     BinElement* bin=table->array[key];
 282     val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);//note...talk to me about optimizations here.
 283   } while(val==(BinItem*)0x1);
 284   //at this point have locked bin
 285   if (val==NULL) {
 286     return EMPTYBINCASE(table, table->array[key], r, TRUE);
 287   } else {
 288     if (isFineWrite(r)) {
 289       return WRITEBINCASE(table, r, val, key, TRUE);
 290     } else if (isFineRead(r)) {
 291       return READBINCASE(table, r, val, key, TRUE);
 292     }
 293   }
 294 }
 295
 296 int ADDTABLEITEM(Hashtable* table, REntry* r){
 297   BinItem * val;
 298   int key=generateKey((unsigned int)(unsigned INTPTR)r->dynID);
 299   do {
 300     val=(BinItem*)0x1;
 301     BinElement* bin=table->array[key];
 302     val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);//note...talk to me about optimizations here.
 303   } while(val==(BinItem*)0x1);
 304   //at this point have locked bin
 305   if (val==NULL) {
 306     return EMPTYBINCASE(table, table->array[key], r, FALSE);
 307   } else {
 308     if (isFineWrite(r)) {
 309       return WRITEBINCASE(table, r, val, key, FALSE);
 310     } else if (isFineRead(r)) {
 311       return READBINCASE(table, r, val, key, FALSE);
 312     }
 313   }
 314 }
 315
 316 int EMPTYBINCASE(Hashtable *T, BinElement* be, REntry *r, int inc) {
 317   int retval;
 318   BinItem* b;
 319   if (isFineWrite(r)) {
 320     b=(BinItem*)createWriteBinItem();
 321     ((WriteBinItem*)b)->val=r;//<-only different statement
 322   } else if (isFineRead(r)) {
 323     b=(BinItem*)createReadBinItem();
 324     ReadBinItem* readbin=(ReadBinItem*)b;
 325     readbin->array[readbin->index++]=r;
 326   }
 327   b->total=1;
 328
 329   if (T->item.status==READY) {
 330     //current entry is ready
 331     b->status=READY;
 332     retval=READY;
 333     if (isParent(r)) {
 334       be->head=NULL; // released lock
 335       return retval;
 336     }
 337   } else {
 338     b->status=NOTREADY;
 339     retval=NOTREADY;
 340   }
 341
 342   if(inc){
 343     atomic_inc(&T->item.total);
 344   }
 345   r->hashtable=T;
 346   r->binitem=b;
 347   be->tail=b;
 348   be->head=b;//released lock
 349   return retval;
 350 }
 351
 352 int WRITEBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) {
 353   //chain of bins exists => tail is valid
 354   //if there is something in front of us, then we are not ready
 355
 356   int retval;
 357   BinElement* be=T->array[key];
 358
 359   BinItem *bintail=be->tail;
 360
 361   WriteBinItem *b=createWriteBinItem();
 362   b->val=r;
 363   b->item.total=1;
 364
 365   // note: If current table clears all dependencies, then write bin is ready
 366   if (T->item.total==0){
 367     retval=READY;
 368   }else{
 369     retval=NOTREADY;
 370   }
 371   b->item.status=retval;
 372   //  b->item.status=NOTREADY;
 373
 374   if(inc){
 375     atomic_inc(&T->item.total);
 376   }
 377
 378   r->hashtable=T;
 379   r->binitem=(BinItem*)b;
 380
 381   be->tail->next=(BinItem*)b;
 382   be->tail=(BinItem*)b;
 383   be->head=val;
 384   return retval;
 385 }
 386
 387 READBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) {
 388   BinItem * bintail=T->array[key]->tail;
 389   if (isReadBinItem(bintail)) {
 390     return TAILREADCASE(T, r, val, bintail, key);
 391   } else if (!isReadBinItem(bintail)) {
 392     TAILWRITECASE(T, r, val, bintail, key);
 393     return NOTREADY;
 394   }
 395 }
 396
 397 int TAILREADCASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
 398   ReadBinItem * readbintail=(ReadBinItem*)T->array[key]->tail;
 399   int status, retval;
 400   if (readbintail->item.status=READY) {
 401     status=READY;
 402     retval=READY;
 403     if (isParent(r)) {
 404       T->array[key]->head=val;//released lock
 405       return READY;
 406     }
 407   } else {
 408     status=NOTREADY;
 409     retval=NOTREADY;
 410   }
 411
 412   if (readbintail->index==NUMREAD) { // create new read group
 413     ReadBinItem* rb=createReadBinItem();
 414     rb->array[rb->index++]=r;
 415     rb->item.total=1;//safe only because item could not have started
 416     rb->item.status=status;
 417     T->array[key]->tail->next=(BinItem*)rb;
 418     T->array[key]->tail=(BinItem*)rb;
 419     r->binitem=(BinItem*)rb;
 420   } else { // group into old tail
 421     readbintail->array[readbintail->index++]=r;
 422     atomic_inc(&readbintail->item.total);
 423     r->binitem=(BinItem*)readbintail;
 424     //printf("grouping with %d\n",readbintail->index);
 425   }
 426   if(inc){
 427     atomic_inc(&T->item.total);
 428   }
 429   r->hashtable=T;
 430   T->array[key]->head=val;//released lock
 431   return retval;
 432 }
 433
 434 TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
 435   //  WriteBinItem* wb=createWriteBinItem();
 436   //wb->val=r;
 437   //wb->item.total=1;//safe because item could not have started
 438   //wb->item.status=NOTREADY;
 439   ReadBinItem* rb=createReadBinItem();
 440   rb->array[rb->index++]=r;
 441   rb->item.total=1;//safe because item could not have started
 442   rb->item.status=NOTREADY;
 443   if(inc){
 444     atomic_inc(&T->item.total);
 445   }
 446   r->hashtable=T;
 447   r->binitem=(BinItem*)rb;
 448   T->array[key]->tail->next=(BinItem*)rb;
 449   T->array[key]->tail=(BinItem*)rb;
 450   T->array[key]->head=val;//released lock
 451 }
 452
 453 ADDVECTOR(MemoryQueue *Q, REntry *r) {
 454   if(!isVector(Q->tail)) {
 455     //Fast Case
 456     if (isParentCoarse(r) && Q->tail->total==0 && Q->tail==Q->head) {
 457       return READY;
 458     }
 459
 460     //added vector
 461     Vector* V=createVector();
 462     Q->tail->next=(MemoryQueueItem*)V;
 463     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 464     if (BARRIER() && Q->tail->status==READY&&Q->tail->total==0) {
 465       //previous Q item is finished
 466       V->item.status=READY;
 467     }
 468     Q->tail=(MemoryQueueItem*)V;
 469     // handle the the queue item case
 470     if(Q->head->type==3){
 471       Q->head=(MemoryQueueItem*)V;
 472     }
 473   }
 474   //at this point, have vector
 475   Vector* V=(Vector*)Q->tail;
 476   if (V->index==NUMITEMS) {
 477     //vector is full
 478     //added vector
 479     V=createVector();
 480     V->item.status=NOTREADY;
 481     Q->tail->next=(MemoryQueueItem*)V;
 482     //***NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 483     if (BARRIER() && Q->tail->status==READY) {
 484       V->item.status=READY;
 485     }
 486     Q->tail=(MemoryQueueItem*)V;
 487   }
 488
 489   atomic_inc(&V->item.total);
 490   //expose entry
 491   int index=V->index;
 492   V->array[index]=r;
 493   //*****NEED memory barrier here to ensure compiler does not reorder writes to V.array and V.index
 494   BARRIER();
 495   V->index++;
 496   //*****NEED memory barrier here to ensure compiler does not cache V.status*********
 497   r->vector=V;
 498   if (BARRIER() && V->item.status==READY) {
 499     void* flag=NULL;
 500     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(V->array[index]), (unsigned INTPTR)flag);
 501     if (flag!=NULL) {
 502       if (isParent(r)) { //parent's retire immediately
 503         atomic_dec(&V->item.total);
 504       }
 505       return READY;
 506     } else {
 507       return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
 508     }
 509   } else {
 510     return NOTREADY;
 511   }
 512 }
 513
 514
 515 //SCC's don't come in parent variety
 516 ADDSCC(MemoryQueue *Q, REntry *r) {
 517   //added SCC
 518   SCC* S=createSCC();
 519   S->item.total=1;
 520   S->val=r;
 521   r->scc=S;
 522   Q->tail->next=(MemoryQueueItem*)S;
 523   //*** NEED BARRIER HERE
 524   if (BARRIER() && Q->tail->status==READY && Q->tail->total==0 && Q->tail==Q->head) {
 525     //previous Q item is finished
 526     S->item.status=READY;
 527     Q->tail=(MemoryQueueItem*)S;
 528     // handle the the queue item case
 529     if(Q->head->type==3){
 530       Q->head=(MemoryQueueItem*)S;
 531     }
 532     void* flag=NULL;
 533     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
 534     if (flag!=NULL) {
 535       return READY;
 536     } else {
 537       return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
 538     }
 539   } else {
 540     Q->tail=(MemoryQueueItem*)S;
 541     return NOTREADY;
 542   }
 543 }
 544
 545
 546 void RETIRERENTRY(MemoryQueue* Q, REntry * r) {
 547   if (isFineWrite(r)||isFineRead(r)) {
 548     RETIREHASHTABLE(Q, r);
 549   } else if (isCoarse(r)) {
 550     RETIREVECTOR(Q, r);
 551   } else if (isSCC(r)) {
 552     RETIRESCC(Q, r);
 553   }
 554 }
 555
 556 RETIRESCC(MemoryQueue *Q, REntry *r) {
 557   SCC* s=r->scc;
 558   s->item.total=0;//don't need atomicdec
 559   RESOLVECHAIN(Q);
 560 }
 561
 562
 563 RETIREHASHTABLE(MemoryQueue *q, REntry *r) {
 564   Hashtable *T=r->hashtable;
 565   BinItem *b=r->binitem;
 566   RETIREBIN(T,r,b);
 567   atomic_dec(&T->item.total);
 568   if (T->item.next!=NULL && T->item.total==0) {
 569     RESOLVECHAIN(q);
 570   }
 571 }
 572
 573 RETIREBIN(Hashtable *T, REntry *r, BinItem *b) {
 574   int key=generateKey((unsigned int)(unsigned INTPTR)r->dynID);
 575   if(isFineRead(r)) {
 576     atomic_dec(&b->total);
 577   }
 578   if (isFineWrite(r) || (isFineRead(r) && b->next!=NULL && b->total==0)) {
 579       // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 580     BinItem * val;
 581     do {
 582       val=(BinItem*)0x1;
 583       val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(T->array[key]->head), (unsigned INTPTR)val);
 584     } while(val==(BinItem*)0x1);
 585     // at this point have locked bin
 586     BinItem *ptr=val;
 587     int haveread=FALSE;
 588      int i;
 589     while (ptr!=NULL) {
 590        if (isReadBinItem(ptr)) {
 591         ReadBinItem* rptr=(ReadBinItem*)ptr;
 592         if (rptr->item.status==NOTREADY) {
 593           for (i=0;i<rptr->index;i++) {
 594             resolveDependencies(rptr->array[i]);
 595             if (isParent(rptr->array[i])) {
 596               //parents go immediately
 597               atomic_dec(&rptr->item.total);
 598               atomic_dec(&T->item.total);
 599             }
 600           }
 601         }
 602         rptr->item.status=READY;
 603         if (rptr->item.next==NULL) {
 604           break;
 605         }
 606         if (rptr->item.total!=0) {
 607           haveread=TRUE;
 608         } else if ((BinItem*)rptr==val) {
 609           val=val->next;
 610         }
 611       } else if(isWriteBinItem(ptr)) {
 612         if (haveread)
 613           break;
 614         if(ptr->status==NOTREADY){
 615           resolveDependencies(((WriteBinItem*)ptr)->val);
 616           ptr->status=READY;
 617           if(isParent(((WriteBinItem*)ptr)->val)){
 618             atomic_dec(&T->item.total);
 619             val=val->next;
 620           }else
 621             break;
 622         }else{ // write bin is already resolved
 623           val=val->next;
 624         }
 625         /*
 626         if(ptr->status==NOTREADY) {
 627           resolveDependencies(((WriteBinItem*)ptr)->val);
 628         }
 629           ptr->status=READY;
 630           if (isParent(((WriteBinItem*)ptr)->val)) {
 631             atomic_dec(&T->item.total);
 632             //val=val->next;
 633             val=ptr->next;
 634           } else
 635             break;
 636         }
 637         */
 638       }
 639       ptr=ptr->next;
 640     }
 641     T->array[key]->head=val; // release lock
 642   }
 643 }
 644
 645
 646 RETIREVECTOR(MemoryQueue *Q, REntry *r) {
 647   Vector* V=r->vector;
 648   atomic_dec(&V->item.total);
 649   if (V->item.next!=NULL && V->item.total==0) { //NOTE: ORDERING CRUCIAL HERE
 650     RESOLVECHAIN(Q);
 651   }
 652 }
 653
 654 RESOLVECHAIN(MemoryQueue *Q) {
 655   while(TRUE) {
 656     MemoryQueueItem* head=Q->head;
 657     if (head->next==NULL||head->total!=0) {
 658       //item is not finished
 659       if (head->status!=READY) {
 660         //need to update status
 661         head->status=READY;
 662         if (isHashtable(head)) {
 663           RESOLVEHASHTABLE(Q, head);
 664         } else if (isVector(head)) {
 665           RESOLVEVECTOR(Q, head);
 666         } else if (isSingleItem(head)) {
 667           RESOLVESCC(head);
 668         }
 669         if (head->next==NULL)
 670           break;
 671         if (head->total!=0)
 672           break;
 673       } else
 674         break;
 675     }
 676     MemoryQueueItem* nextitem=head->next;
 677     CAS((unsigned INTPTR*)&(Q->head), (unsigned INTPTR)head, (unsigned INTPTR)nextitem);
 678     //oldvalue not needed...  if we fail we just repeat
 679   }
 680 }
 681
 682
 683 RESOLVEHASHTABLE(MemoryQueue *Q, Hashtable *T) {
 684   int binidx;
 685   for (binidx=0;binidx<NUMBINS;binidx++) {
 686     BinElement* bin=T->array[binidx];
 687     BinItem* val;
 688     do {
 689       val=(BinItem*)1;
 690       val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);
 691     } while (val==(BinItem*)1);
 692     //at this point have locked bin
 693     int haveread=FALSE;
 694     BinItem* ptr=val;
 695     if(ptr!=NULL&&ptr->status==NOTREADY) {
 696       do {
 697         if (isWriteBinItem(ptr)) {
 698           if (haveread)
 699             break;
 700           resolveDependencies(((WriteBinItem*)ptr)->val);
 701           ptr->status=READY;
 702           if (isParent(((WriteBinItem*)ptr)->val)) {
 703             atomic_dec(&T->item.total);
 704             val=val->next;
 705           } else
 706             break;
 707         } else if (isReadBinItem(ptr)) {
 708           int i;
 709           ReadBinItem* rptr=(ReadBinItem*)ptr;
 710           for(i=0;i<rptr->index;i++) {
 711             resolveDependencies(rptr->array[i]);
 712             if (isParent(rptr->array[i])) {
 713               atomic_dec(&rptr->item.total);
 714               atomic_dec(&T->item.total);
 715             }
 716           }
 717           if (rptr->item.next==NULL||rptr->item.total!=0) {
 718             haveread=TRUE;
 719           } else if((BinItem*)rptr==val) {
 720             val=val->next;
 721           }
 722           rptr->item.status=READY; {
 723           }
 724           ptr=ptr->next;
 725         }
 726       }while(ptr!=NULL);
 727     }
 728     bin->head=val; // released lock;
 729   }
 730 }
 731
 732 RESOLVEVECTOR(MemoryQueue *q, Vector *V) {
 733   int i;
 734   Vector* tmp=V;
 735   //handle ready cases
 736   while(TRUE) {
 737     //enqueue everything
 738     for (i=0;i<NUMITEMS;i++) {
 739       REntry* val=NULL;
 740       val=(REntry*)LOCKXCHG((unsigned INTPTR*)&(tmp->array[i]), (unsigned INTPTR)val);
 741       if (val!=NULL) {
 742         resolveDependencies(val);
 743         if (isParent(val)) {
 744           atomic_dec(&tmp->item.total);
 745         }
 746       }
 747     }
 748     if (tmp->item.next!=NULL&&isVector(tmp->item.next)) {
 749       tmp=(Vector*)tmp->item.next;
 750     } else {
 751       break;
 752     }
 753   }
 754 }
 755
 756 RESOLVESCC(SCC *S) {
 757   //precondition: SCC's state is READY
 758   void* flag=NULL;
 759   flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
 760   if (flag!=NULL) {
 761     resolveDependencies(flag);
 762   }
 763 }
 764
 765
 766 resolveDependencies(REntry* rentry){
 767   SESEcommon* seseCommon=(SESEcommon*)rentry->seseRec;
 768   if(rentry->type==READ || rentry->type==WRITE || rentry->type==COARSE || rentry->type==SCCITEM){
 769     if( atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies)) ){
 770       workScheduleSubmit(seseCommon);
 771     }
 772   }else if(rentry->type==PARENTREAD || rentry->type==PARENTWRITE ||rentry->type==PARENTCOARSE){
 773      psem_give(&(rentry->parentStallSem));
 774   }
 775 }
 776
 777 resolvePointer(REntry* rentry){
 778   rentry->dynID=(void*)*(rentry->pointer); // interim.
 779   Hashtable* table=rentry->hashtable;
 780   struct Queue* val;
 781   do {
 782     val=(struct Queue*)0x1;
 783     val=(struct Queue*)LOCKXCHG((unsigned INTPTR*)&(table->unresolvedQueue), (unsigned INTPTR)val);
 784   } while(val==(struct Queue*)0x1);
 785   if(val!=NULL && getHead(val)->objectptr==rentry){
 786     // handling pointer is the first item of the queue
 787     // start to resolve until it reaches unresolved pointer or end of queue
 788     do{
 789       struct QueueItem* head=getHead(val);
 790       if(head!=NULL){
 791         REntry* rentry=(REntry*)head->objectptr;
 792         if(*(rentry->pointer)==0){
 793           // encounters following unresolved pointer
 794           table->unresolvedQueue=val;//released lock
 795           break;
 796         }
 797         removeItem(val,head);
 798         if(ADDTABLEITEM(table, rentry)==READY){
 799           SESEcommon* seseCommon=(SESEcommon*)rentry->seseRec;
 800           atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies));
 801         }
 802       }else{
 803         table->unresolvedQueue=NULL; // set hashtable as normal-mode.
 804         break;
 805       }
 806     }while(TRUE);
 807   }else{
 808     table->unresolvedQueue=val;//released lock;
 809   }
 810 }
 811