8 #include "mlp_runtime.h"
9 #include "workschedule.h"
13 __thread struct Queue* seseCallStack;
14 __thread pthread_once_t mlpOnceObj = PTHREAD_ONCE_INIT;
15 void mlpInitOncePerThread() {
16 seseCallStack = createQueue();
19 __thread SESEcommon_p seseCaller;
22 void* mlpAllocSESErecord( int size ) {
23 void* newrec = RUNMALLOC( size );
25 printf( "mlpAllocSESErecord did not obtain memory!\n" );
32 void mlpFreeSESErecord( void* seseRecord ) {
33 RUNFREE( seseRecord );
36 MemoryQueue** mlpCreateMemoryQueueArray(int numMemoryQueue){
38 MemoryQueue** newMemoryQueue=(MemoryQueue**)RUNMALLOC( sizeof( MemoryQueue* ) * numMemoryQueue );
39 for(i=0; i<numMemoryQueue; i++){
40 newMemoryQueue[i]=createMemoryQueue();
42 return newMemoryQueue;
45 REntry* mlpCreateREntryArray(){
46 REntry* newREntryArray=(REntry*)RUNMALLOC(sizeof(REntry)*NUMRENTRY);
47 return newREntryArray;
50 REntry* mlpCreateFineREntry(int type, void* seseToIssue, void* dynID){
51 REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
53 newREntry->seseRec=seseToIssue;
54 newREntry->dynID=dynID;
58 REntry* mlpCreateREntry(int type, void* seseToIssue){
59 REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
61 newREntry->seseRec=seseToIssue;
65 int isParent(REntry *r) {
66 if (r->type==PARENTREAD || r->type==PARENTWRITE) {
73 int isParentCoarse(REntry *r){
74 if (r->type==PARENTCOARSE){
81 int isFineRead(REntry *r) {
82 if (r->type==READ || r->type==PARENTREAD) {
89 int isFineWrite(REntry *r) {
90 if (r->type==WRITE || r->type==PARENTWRITE) {
97 int isCoarse(REntry *r){
98 if(r->type==COARSE || r->type==PARENTCOARSE){
105 int isSCC(REntry *r){
106 if(r->type==SCCITEM){
113 int isSingleItem(MemoryQueueItem *qItem){
114 if(qItem->type==SINGLEITEM){
121 int isHashtable(MemoryQueueItem *qItem){
122 if(qItem->type==HASHTABLE){
129 int isVector(MemoryQueueItem *qItem){
130 if(qItem->type==VECTOR){
137 int isReadBinItem(BinItem* b){
138 if(b->type==READBIN){
145 int isWriteBinItem(BinItem* b){
146 if(b->type==WRITEBIN){
153 int generateKey(unsigned int data){
154 return (data&H_MASK)>> 4;
157 Hashtable* createHashtable(){
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;
169 WriteBinItem* createWriteBinItem(){
170 WriteBinItem* binitem=(WriteBinItem*)RUNMALLOC(sizeof(WriteBinItem));
171 binitem->item.type=WRITEBIN;
175 ReadBinItem* createReadBinItem(){
176 ReadBinItem* binitem=(ReadBinItem*)RUNMALLOC(sizeof(ReadBinItem));
178 binitem->item.type=READBIN;
182 Vector* createVector(){
183 Vector* vector=(Vector*)RUNMALLOC(sizeof(Vector));
185 vector->item.type=VECTOR;
190 SCC* scc=(SCC*)RUNMALLOC(sizeof(SCC));
191 scc->item.type=SINGLEITEM;
195 MemoryQueue* createMemoryQueue(){
196 MemoryQueue* queue = (MemoryQueue*)RUNMALLOC(sizeof(MemoryQueue));
197 MemoryQueueItem* dummy=(MemoryQueueItem*)RUNMALLOC(sizeof(MemoryQueueItem));
198 dummy->type=3; // dummy type
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)) {
216 int ADDTABLE(MemoryQueue *q, REntry *r) {
217 if(!isHashtable(q->tail)) {
219 MemoryQueueItem* tail=q->tail;
220 if (isParent(r) && tail->total==0 && q->tail==q->head) {
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;
232 q->tail=(MemoryQueueItem*)h;
233 // handle the the queue item case
234 if(q->head->type==3){
235 q->head=(MemoryQueueItem*)h;
239 //at this point, have table
240 Hashtable* table=(Hashtable*)q->tail;
242 int key=generateKey((unsigned int)r->dynID);
245 BinElement* bin=table->array[key];
246 val=(BinItem*)LOCKXCHG((unsigned int*)&(bin->head), (unsigned int)val);//note...talk to me about optimizations here.
247 } while(val==(BinItem*)0x1);
248 //at this point have locked bin
250 return EMPTYBINCASE(table, table->array[key], r);
252 if (isFineWrite(r)) {
253 return WRITEBINCASE(table, r, val, key);
254 } else if (isFineRead(r)) {
255 return READBINCASE(table, r, val, key);
260 int EMPTYBINCASE(Hashtable *T, BinElement* be, REntry *r) {
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;
273 if (T->item.status==READY) {
274 //current entry is ready
278 be->head=NULL; // released lock
286 atomic_inc(&T->item.total);
290 be->head=b;//released lock
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
299 BinElement* be=T->array[key];
301 BinItem *bintail=be->tail;
303 WriteBinItem *b=createWriteBinItem();
307 // note: If current table clears all dependencies, then write bin is ready
308 if (T->item.total==0){
313 b->item.status=retval;
314 // b->item.status=NOTREADY;
316 atomic_inc(&T->item.total);
319 r->binitem=(BinItem*)b;
321 be->tail->next=(BinItem*)b;
322 be->tail=(BinItem*)b;
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);
337 int TAILREADCASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key) {
338 ReadBinItem * readbintail=(ReadBinItem*)T->array[key]->tail;
340 if (readbintail->item.status=READY) {
344 T->array[key]->head=val;//released lock
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);
366 atomic_inc(&T->item.total);
368 T->array[key]->head=val;//released lock
372 TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key) {
373 // WriteBinItem* wb=createWriteBinItem();
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);
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
389 ADDVECTOR(MemoryQueue *Q, REntry *r) {
390 if(!isVector(Q->tail)) {
392 if (isParentCoarse(r) && Q->tail->total==0 && Q->tail==Q->head) {
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;
404 Q->tail=(MemoryQueueItem*)V;
405 // handle the the queue item case
406 if(Q->head->type==3){
407 Q->head=(MemoryQueueItem*)V;
410 //at this point, have vector
411 Vector* V=(Vector*)Q->tail;
412 if (V->index==NUMITEMS) {
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;
422 Q->tail=(MemoryQueueItem*)V;
425 atomic_inc(&V->item.total);
429 //*****NEED memory barrier here to ensure compiler does not reorder writes to V.array and V.index
432 //*****NEED memory barrier here to ensure compiler does not cache V.status*********
434 if (BARRIER() && V->item.status==READY) {
436 flag=(void*)LOCKXCHG((unsigned int*)&(V->array[index]), (unsigned int)flag);
438 if (isParent(r)) { //parent's retire immediately
439 atomic_dec(&V->item.total);
443 return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
451 //SCC's don't come in parent variety
452 ADDSCC(MemoryQueue *Q, REntry *r) {
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;
469 flag=(void*)LOCKXCHG((unsigned int*)&(S->val), (unsigned int)flag);
473 return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
476 Q->tail=(MemoryQueueItem*)S;
482 void RETIRERENTRY(MemoryQueue* Q, REntry * r) {
483 if (isFineWrite(r)||isFineRead(r)) {
484 RETIREHASHTABLE(Q, r);
485 } else if (isCoarse(r)) {
487 } else if (isSCC(r)) {
492 RETIRESCC(MemoryQueue *Q, REntry *r) {
494 s->item.total=0;//don't need atomicdec
499 RETIREHASHTABLE(MemoryQueue *q, REntry *r) {
500 Hashtable *T=r->hashtable;
501 BinItem *b=r->binitem;
503 atomic_dec(&T->item.total);
504 if (T->item.next!=NULL && T->item.total==0) {
509 RETIREBIN(Hashtable *T, REntry *r, BinItem *b) {
510 int key=generateKey((unsigned int)r->dynID);
512 atomic_dec(&b->total);
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
519 val=(BinItem*)LOCKXCHG((unsigned int*)&(T->array[key]->head), (unsigned int)val);
520 } while(val==(BinItem*)1);
521 // at this point have locked bin
527 if (isReadBinItem(ptr)) {
528 ReadBinItem* rptr=(ReadBinItem*)ptr;
529 if (rptr->item.status==NOTREADY) {
530 for (i=0;i<rptr->index;i++) {
531 resolveDependencies(rptr->array[i]);
532 if (isParent(rptr->array[i])) {
533 //parents go immediately
534 atomic_dec(&rptr->item.total);
535 atomic_dec(&T->item.total);
539 rptr->item.status=READY;
540 if (rptr->item.next==NULL) {
543 if (rptr->item.total!=0) {
545 } else if ((BinItem*)rptr==val) {
548 } else if(isWriteBinItem(ptr)) {
551 if(ptr->status==NOTREADY){
552 resolveDependencies(((WriteBinItem*)ptr)->val);
554 if(isParent(((WriteBinItem*)ptr)->val)){
555 atomic_dec(&T->item.total);
559 }else{ // write bin is already resolved
563 if(ptr->status==NOTREADY) {
564 resolveDependencies(((WriteBinItem*)ptr)->val);
567 if (isParent(((WriteBinItem*)ptr)->val)) {
568 atomic_dec(&T->item.total);
578 T->array[key]->head=val; // release lock
583 RETIREVECTOR(MemoryQueue *Q, REntry *r) {
585 atomic_dec(&V->item.total);
586 if (V->item.next!=NULL && V->item.total==0) { //NOTE: ORDERING CRUCIAL HERE
591 RESOLVECHAIN(MemoryQueue *Q) {
593 MemoryQueueItem* head=Q->head;
594 if (head->next==NULL||head->total!=0) {
595 //item is not finished
596 if (head->status!=READY) {
597 //need to update status
599 if (isHashtable(head)) {
600 RESOLVEHASHTABLE(Q, head);
601 } else if (isVector(head)) {
602 RESOLVEVECTOR(Q, head);
603 } else if (isSingleItem(head)) {
606 if (head->next==NULL)
613 MemoryQueueItem* nextitem=head->next;
614 CAS32((unsigned int*)&(Q->head), (unsigned int)head, (unsigned int)nextitem);
615 //oldvalue not needed... if we fail we just repeat
620 RESOLVEHASHTABLE(MemoryQueue *Q, Hashtable *T) {
622 for (binidx=0;binidx<NUMBINS;binidx++) {
623 BinElement* bin=T->array[binidx];
627 val=(BinItem*)LOCKXCHG((unsigned int*)&(bin->head), (unsigned int)val);
628 } while (val==(BinItem*)1);
629 //at this point have locked bin
632 if(ptr!=NULL&&ptr->status==NOTREADY) {
634 if (isWriteBinItem(ptr)) {
637 resolveDependencies(((WriteBinItem*)ptr)->val);
639 if (isParent(((WriteBinItem*)ptr)->val)) {
640 atomic_dec(&T->item.total);
644 } else if (isReadBinItem(ptr)) {
646 ReadBinItem* rptr=(ReadBinItem*)ptr;
647 for(i=0;i<rptr->index;i++) {
648 resolveDependencies(rptr->array[i]);
649 if (isParent(rptr->array[i])) {
650 atomic_dec(&rptr->item.total);
651 atomic_dec(&T->item.total);
654 if (rptr->item.next==NULL||rptr->item.total!=0) {
656 } else if((BinItem*)rptr==val) {
659 rptr->item.status=READY; {
665 bin->head=val; // released lock;
669 RESOLVEVECTOR(MemoryQueue *q, Vector *V) {
675 for (i=0;i<NUMITEMS;i++) {
677 val=(REntry*)LOCKXCHG((unsigned int*)&(tmp->array[i]), (unsigned int)val);
679 resolveDependencies(val);
681 atomic_dec(&tmp->item.total);
685 if (tmp->item.next!=NULL&&isVector(tmp->item.next)) {
686 tmp=(Vector*)tmp->item.next;
694 //precondition: SCC's state is READY
696 flag=(void*)LOCKXCHG((unsigned int*)&(S->val), (unsigned int)flag);
698 resolveDependencies(flag);
703 resolveDependencies(REntry* rentry){
704 SESEcommon* seseCommon=(SESEcommon*)rentry->seseRec;
705 if(rentry->type==READ || rentry->type==WRITE || rentry->type==COARSE || rentry->type==SCCITEM){
706 if( atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies)) ){
707 workScheduleSubmit(seseCommon);
709 }else if(rentry->type==PARENTREAD || rentry->type==PARENTWRITE ||rentry->type==PARENTCOARSE){
710 psem_give(&(rentry->parentStallSem));