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   return newTable;
 167 }
 168
 169 WriteBinItem* createWriteBinItem(){
 170   WriteBinItem* binitem=(WriteBinItem*)RUNMALLOC(sizeof(WriteBinItem));
 171   binitem->item.type=WRITEBIN;
 172   return binitem;
 173 }
 174
 175 ReadBinItem* createReadBinItem(){
 176   ReadBinItem* binitem=(ReadBinItem*)RUNMALLOC(sizeof(ReadBinItem));
 177   binitem->index=0;
 178   binitem->item.type=READBIN;
 179   return binitem;
 180 }
 181
 182 Vector* createVector(){
 183   Vector* vector=(Vector*)RUNMALLOC(sizeof(Vector));
 184   vector->index=0;
 185   vector->item.type=VECTOR;
 186   return vector;
 187 }
 188
 189 SCC* createSCC(){
 190   SCC* scc=(SCC*)RUNMALLOC(sizeof(SCC));
 191   scc->item.type=SINGLEITEM;
 192   return scc;
 193 }
 194
 195 MemoryQueue* createMemoryQueue(){
 196   MemoryQueue* queue = (MemoryQueue*)RUNMALLOC(sizeof(MemoryQueue));
 197   MemoryQueueItem* dummy=(MemoryQueueItem*)RUNMALLOC(sizeof(MemoryQueueItem));
 198   dummy->type=3; // dummy type
 199   dummy->total=0;
 200   dummy->status=READY;
 201   queue->head = dummy;
 202   queue->tail = dummy;
 203   return queue;
 204 }
 205
 206 int ADDRENTRY(MemoryQueue * q, REntry * r) {
 207   if (isFineRead(r) || isFineWrite(r)) {
 208     return ADDTABLE(q, r);
 209   } else if (isCoarse(r)) {
 210     return ADDVECTOR(q, r);
 211   } else if (isSCC(r)) {
 212     return ADDSCC(q, r);
 213   }
 214 }
 215
 216 int ADDTABLE(MemoryQueue *q, REntry *r) {
 217   if(!isHashtable(q->tail)) {
 218     //Fast Case
 219     MemoryQueueItem* tail=q->tail;
 220     if (isParent(r) && tail->total==0 && q->tail==q->head) {
 221       return READY;
 222     }
 223
 224     //Add table
 225     Hashtable* h=createHashtable();
 226     tail->next=(MemoryQueueItem*)h;
 227     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status********
 228     if (BARRIER() && tail->status==READY && tail->total==0 && q->tail==q->head) {
 229       //previous Q item is finished
 230       h->item.status=READY;
 231     }
 232     q->tail=(MemoryQueueItem*)h;
 233     // handle the the queue item case
 234     if(q->head->type==3){
 235       q->head=(MemoryQueueItem*)h;
 236     }
 237   }
 238
 239   //at this point, have table
 240   Hashtable* table=(Hashtable*)q->tail;
 241   BinItem * val;
 242   int key=generateKey((unsigned int)(unsigned INTPTR)r->dynID);
 243   do {
 244     val=(BinItem*)0x1;
 245     BinElement* bin=table->array[key];
 246     val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);//note...talk to me about optimizations here.
 247   } while(val==(BinItem*)0x1);
 248   //at this point have locked bin
 249   if (val==NULL) {
 250     return EMPTYBINCASE(table, table->array[key], r);
 251   } else {
 252     if (isFineWrite(r)) {
 253       return WRITEBINCASE(table, r, val, key);
 254     } else if (isFineRead(r)) {
 255       return READBINCASE(table, r, val, key);
 256     }
 257   }
 258 }
 259
 260 int EMPTYBINCASE(Hashtable *T, BinElement* be, REntry *r) {
 261   int retval;
 262   BinItem* b;
 263   if (isFineWrite(r)) {
 264     b=(BinItem*)createWriteBinItem();
 265     ((WriteBinItem*)b)->val=r;//<-only different statement
 266   } else if (isFineRead(r)) {
 267     b=(BinItem*)createReadBinItem();
 268     ReadBinItem* readbin=(ReadBinItem*)b;
 269     readbin->array[readbin->index++]=r;
 270   }
 271   b->total=1;
 272
 273   if (T->item.status==READY) {
 274     //current entry is ready
 275     b->status=READY;
 276     retval=READY;
 277     if (isParent(r)) {
 278       be->head=NULL; // released lock
 279       return retval;
 280     }
 281   } else {
 282     b->status=NOTREADY;
 283     retval=NOTREADY;
 284   }
 285
 286   atomic_inc(&T->item.total);
 287   r->hashtable=T;
 288   r->binitem=b;
 289   be->tail=b;
 290   be->head=b;//released lock
 291   return retval;
 292 }
 293
 294 int WRITEBINCASE(Hashtable *T, REntry *r, BinItem *val, int key) {
 295   //chain of bins exists => tail is valid
 296   //if there is something in front of us, then we are not ready
 297
 298   int retval;
 299   BinElement* be=T->array[key];
 300
 301   BinItem *bintail=be->tail;
 302
 303   WriteBinItem *b=createWriteBinItem();
 304   b->val=r;
 305   b->item.total=1;
 306
 307   // note: If current table clears all dependencies, then write bin is ready
 308   if (T->item.total==0){
 309     retval=READY;
 310   }else{
 311     retval=NOTREADY;
 312   }
 313   b->item.status=retval;
 314   //  b->item.status=NOTREADY;
 315
 316   atomic_inc(&T->item.total);
 317
 318   r->hashtable=T;
 319   r->binitem=(BinItem*)b;
 320
 321   be->tail->next=(BinItem*)b;
 322   be->tail=(BinItem*)b;
 323   be->head=val;
 324   return retval;
 325 }
 326
 327 READBINCASE(Hashtable *T, REntry *r, BinItem *val, int key) {
 328   BinItem * bintail=T->array[key]->tail;
 329   if (isReadBinItem(bintail)) {
 330     return TAILREADCASE(T, r, val, bintail, key);
 331   } else if (!isReadBinItem(bintail)) {
 332     TAILWRITECASE(T, r, val, bintail, key);
 333     return NOTREADY;
 334   }
 335 }
 336
 337 int TAILREADCASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key) {
 338   ReadBinItem * readbintail=(ReadBinItem*)T->array[key]->tail;
 339   int status, retval;
 340   if (readbintail->item.status=READY) {
 341     status=READY;
 342     retval=READY;
 343     if (isParent(r)) {
 344       T->array[key]->head=val;//released lock
 345       return READY;
 346     }
 347   } else {
 348     status=NOTREADY;
 349     retval=NOTREADY;
 350   }
 351
 352   if (readbintail->index==NUMREAD) { // create new read group
 353     ReadBinItem* rb=createReadBinItem();
 354     rb->array[rb->index++]=r;
 355     rb->item.total=1;//safe only because item could not have started
 356     rb->item.status=status;
 357     T->array[key]->tail->next=(BinItem*)rb;
 358     T->array[key]->tail=(BinItem*)rb;
 359     r->binitem=(BinItem*)rb;
 360   } else { // group into old tail
 361     readbintail->array[readbintail->index++]=r;
 362     atomic_inc(&readbintail->item.total);
 363     r->binitem=(BinItem*)readbintail;
 364     //printf("grouping with %d\n",readbintail->index);
 365   }
 366   atomic_inc(&T->item.total);
 367   r->hashtable=T;
 368   T->array[key]->head=val;//released lock
 369   return retval;
 370 }
 371
 372 TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key) {
 373   //  WriteBinItem* wb=createWriteBinItem();
 374   //wb->val=r;
 375   //wb->item.total=1;//safe because item could not have started
 376   //wb->item.status=NOTREADY;
 377   ReadBinItem* rb=createReadBinItem();
 378   rb->array[rb->index++]=r;
 379   rb->item.total=1;//safe because item could not have started
 380   rb->item.status=NOTREADY;
 381   atomic_inc(&T->item.total);
 382   r->hashtable=T;
 383   r->binitem=(BinItem*)rb;
 384   T->array[key]->tail->next=(BinItem*)rb;
 385   T->array[key]->tail=(BinItem*)rb;
 386   T->array[key]->head=val;//released lock
 387 }
 388
 389 ADDVECTOR(MemoryQueue *Q, REntry *r) {
 390   if(!isVector(Q->tail)) {
 391     //Fast Case
 392     if (isParentCoarse(r) && Q->tail->total==0 && Q->tail==Q->head) {
 393       return READY;
 394     }
 395
 396     //added vector
 397     Vector* V=createVector();
 398     Q->tail->next=(MemoryQueueItem*)V;
 399     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 400     if (BARRIER() && Q->tail->status==READY&&Q->tail->total==0) {
 401       //previous Q item is finished
 402       V->item.status=READY;
 403     }
 404     Q->tail=(MemoryQueueItem*)V;
 405     // handle the the queue item case
 406     if(Q->head->type==3){
 407       Q->head=(MemoryQueueItem*)V;
 408     }
 409   }
 410   //at this point, have vector
 411   Vector* V=(Vector*)Q->tail;
 412   if (V->index==NUMITEMS) {
 413     //vector is full
 414     //added vector
 415     V=createVector();
 416     V->item.status=NOTREADY;
 417     Q->tail->next=(MemoryQueueItem*)V;
 418     //***NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 419     if (BARRIER() && Q->tail->status==READY) {
 420       V->item.status=READY;
 421     }
 422     Q->tail=(MemoryQueueItem*)V;
 423   }
 424
 425   atomic_inc(&V->item.total);
 426   //expose entry
 427   int index=V->index;
 428   V->array[index]=r;
 429   //*****NEED memory barrier here to ensure compiler does not reorder writes to V.array and V.index
 430   BARRIER();
 431   V->index++;
 432   //*****NEED memory barrier here to ensure compiler does not cache V.status*********
 433   r->vector=V;
 434   if (BARRIER() && V->item.status==READY) {
 435     void* flag=NULL;
 436     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(V->array[index]), (unsigned INTPTR)flag);
 437     if (flag!=NULL) {
 438       if (isParent(r)) { //parent's retire immediately
 439         atomic_dec(&V->item.total);
 440       }
 441       return READY;
 442     } else {
 443       return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
 444     }
 445   } else {
 446     return NOTREADY;
 447   }
 448 }
 449
 450
 451 //SCC's don't come in parent variety
 452 ADDSCC(MemoryQueue *Q, REntry *r) {
 453   //added SCC
 454   SCC* S=createSCC();
 455   S->item.total=1;
 456   S->val=r;
 457   r->scc=S;
 458   Q->tail->next=(MemoryQueueItem*)S;
 459   //*** NEED BARRIER HERE
 460   if (BARRIER() && Q->tail->status==READY && Q->tail->total==0 && Q->tail==Q->head) {
 461     //previous Q item is finished
 462     S->item.status=READY;
 463     Q->tail=(MemoryQueueItem*)S;
 464     // handle the the queue item case
 465     if(Q->head->type==3){
 466       Q->head=(MemoryQueueItem*)S;
 467     }
 468     void* flag=NULL;
 469     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
 470     if (flag!=NULL) {
 471       return READY;
 472     } else {
 473       return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
 474     }
 475   } else {
 476     Q->tail=(MemoryQueueItem*)S;
 477     return NOTREADY;
 478   }
 479 }
 480
 481
 482 void RETIRERENTRY(MemoryQueue* Q, REntry * r) {
 483   if (isFineWrite(r)||isFineRead(r)) {
 484     RETIREHASHTABLE(Q, r);
 485   } else if (isCoarse(r)) {
 486     RETIREVECTOR(Q, r);
 487   } else if (isSCC(r)) {
 488     RETIRESCC(Q, r);
 489   }
 490 }
 491
 492 RETIRESCC(MemoryQueue *Q, REntry *r) {
 493   SCC* s=r->scc;
 494   s->item.total=0;//don't need atomicdec
 495   RESOLVECHAIN(Q);
 496 }
 497
 498
 499 RETIREHASHTABLE(MemoryQueue *q, REntry *r) {
 500   Hashtable *T=r->hashtable;
 501   BinItem *b=r->binitem;
 502   RETIREBIN(T,r,b);
 503   atomic_dec(&T->item.total);
 504   if (T->item.next!=NULL && T->item.total==0) {
 505     RESOLVECHAIN(q);
 506   }
 507 }
 508
 509 RETIREBIN(Hashtable *T, REntry *r, BinItem *b) {
 510   int key=generateKey((unsigned int)(unsigned INTPTR)r->dynID);
 511   if(isFineRead(r)) {
 512     atomic_dec(&b->total);
 513   }
 514   if (isFineWrite(r) || (isFineRead(r) && b->next!=NULL && b->total==0)) {
 515       // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 516     BinItem * val;
 517     do {
 518       val=(BinItem*)0x1;
 519       val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(T->array[key]->head), (unsigned INTPTR)val);
 520     } while(val==(BinItem*)0x1);
 521     // at this point have locked bin
 522     BinItem *ptr=val;
 523     int haveread=FALSE;
 524      int i;
 525     while (ptr!=NULL) {
 526        if (isReadBinItem(ptr)) {
 527         ReadBinItem* rptr=(ReadBinItem*)ptr;
 528         if (rptr->item.status==NOTREADY) {
 529           for (i=0;i<rptr->index;i++) {
 530             resolveDependencies(rptr->array[i]);
 531             if (isParent(rptr->array[i])) {
 532               //parents go immediately
 533               atomic_dec(&rptr->item.total);
 534               atomic_dec(&T->item.total);
 535             }
 536           }
 537         }
 538         rptr->item.status=READY;
 539         if (rptr->item.next==NULL) {
 540           break;
 541         }
 542         if (rptr->item.total!=0) {
 543           haveread=TRUE;
 544         } else if ((BinItem*)rptr==val) {
 545           val=val->next;
 546         }
 547       } else if(isWriteBinItem(ptr)) {
 548         if (haveread)
 549           break;
 550         if(ptr->status==NOTREADY){
 551           resolveDependencies(((WriteBinItem*)ptr)->val);
 552           ptr->status=READY;
 553           if(isParent(((WriteBinItem*)ptr)->val)){
 554             atomic_dec(&T->item.total);
 555             val=val->next;
 556           }else
 557             break;
 558         }else{ // write bin is already resolved
 559           val=val->next;
 560         }
 561         /*
 562         if(ptr->status==NOTREADY) {
 563           resolveDependencies(((WriteBinItem*)ptr)->val);
 564         }
 565           ptr->status=READY;
 566           if (isParent(((WriteBinItem*)ptr)->val)) {
 567             atomic_dec(&T->item.total);
 568             //val=val->next;
 569             val=ptr->next;
 570           } else
 571             break;
 572         }
 573         */
 574       }
 575       ptr=ptr->next;
 576     }
 577     T->array[key]->head=val; // release lock
 578   }
 579 }
 580
 581
 582 RETIREVECTOR(MemoryQueue *Q, REntry *r) {
 583   Vector* V=r->vector;
 584   atomic_dec(&V->item.total);
 585   if (V->item.next!=NULL && V->item.total==0) { //NOTE: ORDERING CRUCIAL HERE
 586     RESOLVECHAIN(Q);
 587   }
 588 }
 589
 590 RESOLVECHAIN(MemoryQueue *Q) {
 591   while(TRUE) {
 592     MemoryQueueItem* head=Q->head;
 593     if (head->next==NULL||head->total!=0) {
 594       //item is not finished
 595       if (head->status!=READY) {
 596         //need to update status
 597         head->status=READY;
 598         if (isHashtable(head)) {
 599           RESOLVEHASHTABLE(Q, head);
 600         } else if (isVector(head)) {
 601           RESOLVEVECTOR(Q, head);
 602         } else if (isSingleItem(head)) {
 603           RESOLVESCC(head);
 604         }
 605         if (head->next==NULL)
 606           break;
 607         if (head->total!=0)
 608           break;
 609       } else
 610         break;
 611     }
 612     MemoryQueueItem* nextitem=head->next;
 613     CAS((unsigned INTPTR*)&(Q->head), (unsigned INTPTR)head, (unsigned INTPTR)nextitem);
 614     //oldvalue not needed...  if we fail we just repeat
 615   }
 616 }
 617
 618
 619 RESOLVEHASHTABLE(MemoryQueue *Q, Hashtable *T) {
 620   int binidx;
 621   for (binidx=0;binidx<NUMBINS;binidx++) {
 622     BinElement* bin=T->array[binidx];
 623     BinItem* val;
 624     do {
 625       val=(BinItem*)1;
 626       val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);
 627     } while (val==(BinItem*)1);
 628     //at this point have locked bin
 629     int haveread=FALSE;
 630     BinItem* ptr=val;
 631     if(ptr!=NULL&&ptr->status==NOTREADY) {
 632       do {
 633         if (isWriteBinItem(ptr)) {
 634           if (haveread)
 635             break;
 636           resolveDependencies(((WriteBinItem*)ptr)->val);
 637           ptr->status=READY;
 638           if (isParent(((WriteBinItem*)ptr)->val)) {
 639             atomic_dec(&T->item.total);
 640             val=val->next;
 641           } else
 642             break;
 643         } else if (isReadBinItem(ptr)) {
 644           int i;
 645           ReadBinItem* rptr=(ReadBinItem*)ptr;
 646           for(i=0;i<rptr->index;i++) {
 647             resolveDependencies(rptr->array[i]);
 648             if (isParent(rptr->array[i])) {
 649               atomic_dec(&rptr->item.total);
 650               atomic_dec(&T->item.total);
 651             }
 652           }
 653           if (rptr->item.next==NULL||rptr->item.total!=0) {
 654             haveread=TRUE;
 655           } else if((BinItem*)rptr==val) {
 656             val=val->next;
 657           }
 658           rptr->item.status=READY; {
 659           }
 660           ptr=ptr->next;
 661         }
 662       }while(ptr!=NULL);
 663     }
 664     bin->head=val; // released lock;
 665   }
 666 }
 667
 668 RESOLVEVECTOR(MemoryQueue *q, Vector *V) {
 669   int i;
 670   Vector* tmp=V;
 671   //handle ready cases
 672   while(TRUE) {
 673     //enqueue everything
 674     for (i=0;i<NUMITEMS;i++) {
 675       REntry* val=NULL;
 676       val=(REntry*)LOCKXCHG((unsigned INTPTR*)&(tmp->array[i]), (unsigned INTPTR)val);
 677       if (val!=NULL) {
 678         resolveDependencies(val);
 679         if (isParent(val)) {
 680           atomic_dec(&tmp->item.total);
 681         }
 682       }
 683     }
 684     if (tmp->item.next!=NULL&&isVector(tmp->item.next)) {
 685       tmp=(Vector*)tmp->item.next;
 686     } else {
 687       break;
 688     }
 689   }
 690 }
 691
 692 RESOLVESCC(SCC *S) {
 693   //precondition: SCC's state is READY
 694   void* flag=NULL;
 695   flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
 696   if (flag!=NULL) {
 697     resolveDependencies(flag);
 698   }
 699 }
 700
 701
 702 resolveDependencies(REntry* rentry){
 703   SESEcommon* seseCommon=(SESEcommon*)rentry->seseRec;
 704   if(rentry->type==READ || rentry->type==WRITE || rentry->type==COARSE || rentry->type==SCCITEM){
 705     if( atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies)) ){
 706       workScheduleSubmit(seseCommon);
 707     }
 708   }else if(rentry->type==PARENTREAD || rentry->type==PARENTWRITE ||rentry->type==PARENTCOARSE){
 709      psem_give(&(rentry->parentStallSem));
 710   }
 711 }
 712