From 72745193f51aeca9f37836681526099f89b0dd79 Mon Sep 17 00:00:00 2001 From: adash Date: Thu, 30 Jul 2009 22:18:14 +0000 Subject: [PATCH] 1. runtime changes for a simple probability model to decide when objects are risky 2. Keep track of average size of transactions that accessed objects, causing the transaction to abort. Keep average size info per each object type --- .../src/Benchmarks/SingleTM/KMeans/makefile | 2 +- Robust/src/IR/Flat/BuildCode.java | 6 +- Robust/src/Runtime/DSTM/interface/signal.c | 2 +- Robust/src/Runtime/STM/stm.c | 148 +++++++++++++----- Robust/src/Runtime/STM/tm.h | 17 +- Robust/src/Runtime/runtime.c | 2 +- Robust/src/Runtime/thread.c | 3 +- 7 files changed, 127 insertions(+), 53 deletions(-) diff --git a/Robust/src/Benchmarks/SingleTM/KMeans/makefile b/Robust/src/Benchmarks/SingleTM/KMeans/makefile index 9ad6f192..0277a56a 100644 --- a/Robust/src/Benchmarks/SingleTM/KMeans/makefile +++ b/Robust/src/Benchmarks/SingleTM/KMeans/makefile @@ -11,7 +11,7 @@ include ../common/Makefile.flags include ../common/Makefile.builds -FLAGSSTATS=-mainclass ${MAINCLASS} -singleTM -nooptimize -debug -joptimize -32bit -abcclose -dcopts -transstats -arraypad -stmstats +FLAGSSTATS=-mainclass ${MAINCLASS} -singleTM -optimize -debug -joptimize -32bit -abcclose -dcopts -transstats -arraypad -stmstats stmlock: ../../../buildscript ${FLAGSSTATS} -o STATS${MAINCLASS} ${SRC} diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index ad5f6c1e..0fd4ac1f 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -363,8 +363,8 @@ public class BuildCode { if (state.DSM||state.SINGLETM) { outmethod.println("#ifdef TRANSSTATS \n"); outmethod.println("printf(\"****** Transaction Stats ******\\n\");"); - outmethod.println("printf(\"numTransAbort= %d\\n\", numTransAbort);"); outmethod.println("printf(\"numTransCommit= %d\\n\", numTransCommit);"); + outmethod.println("printf(\"numTransAbort= %d\\n\", numTransAbort);"); outmethod.println("printf(\"nSoftAbort= %d\\n\", nSoftAbort);"); if (state.DSM) { outmethod.println("printf(\"nchashSearch= %d\\n\", nchashSearch);"); @@ -378,7 +378,7 @@ public class BuildCode { outmethod.println("printf(\"nSoftAbortCommit= %d\\n\", nSoftAbortCommit);"); outmethod.println("#ifdef STMSTATS\n"); outmethod.println("for(i=0; iabortCount > MAXABORTS && (x->riskyflag != 1)) { + float transAbortProb = (PERCENT_ALLOWED_ABORT*FACTOR)/(float)typesCausingAbort[TYPE(x)].numaccess; + float ObjAbortProb = x->abortCount/(float) (x->accessCount); + DEBUGSTM("ABORTSTATS: oid= %x, transAbortProb= %3.2f, ObjAbortProb= %3.2f, numaccess= %3d, type= %2d, abortCount= %3d, accessCount= %3d\n", OID(x), transAbortProb, ObjAbortProb, typesCausingAbort[TYPE(x)].numaccess, TYPE(x), x->abortCount, x->accessCount); + /* Condition for locking objects */ + if ((ObjAbortProb > transAbortProb) && (x->riskyflag != 1)) { //makes riskflag sticky pthread_mutex_lock(&lockedobjstore); if (objlockscope->offsetabortCount++; ObjSeqId = headeraddr->accessCount; - (typesCausingAbort[TYPE(header)])++; - getTotalAbortCount(i+1, size, (void *)(curr->next), numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId); + (typesCausingAbort[TYPE(header)]).numabort++; + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + objtypetraverse[TYPE(header)]=1; + getTotalAbortCount(i+1, size, (void *)(curr->next), numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse); #endif DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version); @@ -574,12 +597,15 @@ int traverseCache() { } transAbortProcess(oidwrlocked, numoidwrlocked); #ifdef STMSTATS - ObjSeqId = headeraddr->accessCount; header->abortCount++; - (typesCausingAbort[TYPE(header)])++; + ObjSeqId = headeraddr->accessCount; + (typesCausingAbort[TYPE(header)]).numabort++; + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + objtypetraverse[TYPE(header)]=1; + //(typesCausingAbort[TYPE(header)])++; #endif #if defined(STMSTATS)||defined(SOFTABORT) - if(getTotalAbortCount(i+1, size, (void *)(curr->next), numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId)) + if(getTotalAbortCount(i+1, size, (void *)(curr->next), numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse)) softabort=0; #endif DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); @@ -638,10 +664,12 @@ int traverseCache() { #ifdef STMSTATS ObjSeqId = headeraddr->accessCount; header->abortCount++; - (typesCausingAbort[TYPE(header)])++; + (typesCausingAbort[TYPE(header)]).numabort++; + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + objtypetraverse[TYPE(header)]=1; #endif #if defined(STMSTATS)||defined(SOFTABORT) - if(getTotalAbortCount(i+1, size, (void *)(curr->next), numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId)) + if(getTotalAbortCount(i+1, size, (void *)(curr->next), numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse)) softabort=0; #endif DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); @@ -674,8 +702,10 @@ int traverseCache() { #ifdef STMSTATS ObjSeqId = oidrdage[i]; header->abortCount++; - (typesCausingAbort[TYPE(header)])++; - getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId); + (typesCausingAbort[TYPE(header)]).numabort++; + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + objtypetraverse[TYPE(header)]=1; + getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse); #endif DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version); @@ -691,8 +721,10 @@ int traverseCache() { #ifdef STMSTATS ObjSeqId = oidrdage[i]; header->abortCount++; - (typesCausingAbort[TYPE(header)])++; - getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId); + (typesCausingAbort[TYPE(header)]).numabort++; + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + objtypetraverse[TYPE(header)]=1; + getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse); #endif DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version); @@ -713,10 +745,12 @@ int traverseCache() { #ifdef STMSTATS ObjSeqId = oidrdage[i]; header->abortCount++; - (typesCausingAbort[TYPE(header)])++; + (typesCausingAbort[TYPE(header)]).numabort++; + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + objtypetraverse[TYPE(header)]=1; #endif #if defined(STMSTATS)||defined(SOFTABORT) - if(getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId)) + if(getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse)) softabort=0; #endif DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); @@ -856,7 +890,10 @@ int alttraverseCache() { void ** oidwrlocked; allocarrays; int ObjSeqId; + int objtypetraverse[TOTALNUMCLASSANDARRAY]; + for(i=0; iabortCount++; ObjSeqId = headeraddr->accessCount; - (typesCausingAbort[TYPE(header)])++; - getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId); + (typesCausingAbort[TYPE(header)]).numabort++; + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + objtypetraverse[TYPE(header)]=1; + getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse); #endif DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version); @@ -894,10 +933,12 @@ int alttraverseCache() { #ifdef STMSTATS header->abortCount++; ObjSeqId = headeraddr->accessCount; - (typesCausingAbort[TYPE(header)])++; + (typesCausingAbort[TYPE(header)]).numabort++; + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + objtypetraverse[TYPE(header)]=1; #endif #if defined(STMSTATS)||defined(SOFTABORT) - if(getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId)) + if(getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse)) softabort=0; #endif DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); @@ -947,10 +988,12 @@ int alttraverseCache() { #ifdef STMSTATS header->abortCount++; ObjSeqId = headeraddr->accessCount; - (typesCausingAbort[TYPE(header)])++; + (typesCausingAbort[TYPE(header)]).numabort++; + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + objtypetraverse[TYPE(header)]=1; #endif #if defined(STMSTATS)||defined(SOFTABORT) - if(getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId)) + if(getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse)) softabort=0; #endif DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); @@ -982,8 +1025,10 @@ int alttraverseCache() { #ifdef STMSTATS ObjSeqId = oidrdage[i]; header->abortCount++; - (typesCausingAbort[TYPE(header)])++; - getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId); + (typesCausingAbort[TYPE(header)]).numabort++; + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + objtypetraverse[TYPE(header)]=1; + getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse); #endif DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version); @@ -999,8 +1044,7 @@ int alttraverseCache() { #ifdef STMSTATS ObjSeqId = oidrdage[i]; header->abortCount++; - (typesCausingAbort[TYPE(header)])++; - getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId); + getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse); #endif DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version); @@ -1020,10 +1064,12 @@ int alttraverseCache() { #ifdef STMSTATS ObjSeqId = oidrdage[i]; header->abortCount++; - (typesCausingAbort[TYPE(header)])++; + (typesCausingAbort[TYPE(header)]).numabort++; + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + objtypetraverse[TYPE(header)]=1; #endif #if defined(STMSTATS)||defined(SOFTABORT) - if(getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId)) + if(getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse)) softabort=0; #endif DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version); @@ -1251,11 +1297,11 @@ void transAbortProcess(void **oidwrlocked, int numoidwrlocked) { * ========================================================================================= **/ int getTotalAbortCount(int start, int stop, void *startptr, int numoidrdlocked, - void *oidrdlocked, int *oidrdversion, int *oidrdage, int ObjSeqId) { + void *oidrdlocked, int *oidrdversion, int *oidrdage, int ObjSeqId, objheader_t *header, int *isObjTypeTraverse) { int i; int hardabort=0; int isFirstTime=0; - objheader_t *ObjToBeLocked=NULL; + objheader_t *ObjToBeLocked=header; chashlistnode_t *curr = (chashlistnode_t *) startptr; chashlistnode_t *ptr = c_table; /* First go through all objects left in the cache that have not been covered yet */ @@ -1277,7 +1323,7 @@ int getTotalAbortCount(int start, int stop, void *startptr, int numoidrdlocked, ObjSeqId = headeraddr->accessCount; ObjToBeLocked = header; } - (typesCausingAbort[TYPE(header)])++; + getTransSize(header, isObjTypeTraverse); #endif hardabort=1; } @@ -1299,7 +1345,7 @@ int getTotalAbortCount(int start, int stop, void *startptr, int numoidrdlocked, ObjSeqId = OidAge; ObjToBeLocked = header; } - (typesCausingAbort[TYPE(header)])++; + getTransSize(header, isObjTypeTraverse); #endif hardabort=1; } @@ -1307,8 +1353,9 @@ int getTotalAbortCount(int start, int stop, void *startptr, int numoidrdlocked, } /* Acquire lock on the oldest object accessed in the transaction cache */ - if(ObjToBeLocked != NULL) + if(ObjToBeLocked != NULL) { ABORTCOUNT(ObjToBeLocked); + } return hardabort; } @@ -1324,10 +1371,10 @@ int getTotalAbortCount(int start, int stop, void *startptr, int numoidrdlocked, * ========================================================================================= **/ int getTotalAbortCount2(void *startptr, int numoidrdlocked, void *oidrdlocked, - int *oidrdversion, int *oidrdage, int ObjSeqId) { + int *oidrdversion, int *oidrdage, int ObjSeqId, objheader_t *header, int *isObjTypeTraverse) { int hardabort=0; chashlistnode_t *curr = (chashlistnode_t *) startptr; - objheader_t *ObjToBeLocked=NULL; + objheader_t *ObjToBeLocked=header; /* Inner loop to traverse the linked list of the cache lookupTable */ while(curr != NULL) { @@ -1342,7 +1389,7 @@ int getTotalAbortCount2(void *startptr, int numoidrdlocked, void *oidrdlocked, ObjSeqId = headeraddr->accessCount; ObjToBeLocked = header; } - (typesCausingAbort[TYPE(header)])++; + getTransSize(header, isObjTypeTraverse); #endif hardabort=1; } @@ -1363,15 +1410,16 @@ int getTotalAbortCount2(void *startptr, int numoidrdlocked, void *oidrdlocked, ObjSeqId = OidAge; ObjToBeLocked = header; } - (typesCausingAbort[TYPE(header)])++; + getTransSize(header, isObjTypeTraverse); #endif hardabort=1; } } } - if(ObjToBeLocked!=NULL) + if(ObjToBeLocked!=NULL) { ABORTCOUNT(ObjToBeLocked); + } return hardabort; } @@ -1385,10 +1433,11 @@ int getTotalAbortCount2(void *startptr, int numoidrdlocked, void *oidrdlocked, * : oidrdage : array of ages of objects read ina transaction cache * : ObjSeqId : sequence Id/age to start the comparision with **/ -int getReadAbortCount(int start, int stop, void *oidrdlocked, int *oidrdversion, int *oidrdage, int ObjSeqId) { +int getReadAbortCount(int start, int stop, void *oidrdlocked, int *oidrdversion, + int *oidrdage, int ObjSeqId, objheader_t *header, int *isObjTypeTraverse) { int i; int hardabort=0; - objheader_t *ObjToBeLocked=NULL; + objheader_t *ObjToBeLocked=header; /* Go through oids read that are locked */ for(i = start; i < stop; i++) { @@ -1402,14 +1451,15 @@ int getReadAbortCount(int start, int stop, void *oidrdlocked, int *oidrdversion, ObjSeqId = OidAge; ObjToBeLocked = header; } - (typesCausingAbort[TYPE(header)])++; + getTransSize(header, isObjTypeTraverse); #endif hardabort=1; } } - if(ObjToBeLocked != NULL) + if(ObjToBeLocked != NULL) { ABORTCOUNT(ObjToBeLocked); + } return hardabort; } @@ -1471,4 +1521,18 @@ objheader_t * needLock(objheader_t *header, void *gl) { return header; } +/** + * Inline fuction to get Transaction size per object type for those + * objects that cause + * + **/ +/* +INLINE void getTransSize(objheader_t *header , int *isObjTypeTraverse) { + (typesCausingAbort[TYPE(header)]).numabort++; + if(isObjTypeTraverse[TYPE(header)] != 1) + (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements; + isObjTypeTraverse[TYPE(header)]=1; +} +*/ + #endif diff --git a/Robust/src/Runtime/STM/tm.h b/Robust/src/Runtime/STM/tm.h index 41a8f3b4..269fc561 100644 --- a/Robust/src/Runtime/STM/tm.h +++ b/Robust/src/Runtime/STM/tm.h @@ -150,6 +150,15 @@ extern __thread threadrec_t *trec; extern __thread struct objlist * lockedobjs; extern objlockstate_t *objlockscope; pthread_mutex_t lockedobjstore; + +typedef struct objtypestat { + int numabort; + int numaccess; +} objtypestat_t; + +/* Variables for probability model */ +#define PERCENT_ALLOWED_ABORT 10 +#define FACTOR 1 #endif @@ -165,7 +174,7 @@ extern int nSoftAbortCommit; #endif #ifdef STMSTATS -extern int typesCausingAbort[]; +extern objtypestat_t typesCausingAbort[]; #endif @@ -200,9 +209,9 @@ int altalttraverseCache(); void transAbortProcess(void **, int); void randomdelay(int); #if defined(STMSTATS)||defined(SOFTABORT) -int getTotalAbortCount(int, int, void *, int, void*, int*, int*, int); -int getTotalAbortCount2(void *, int, void *, int *, int*, int); -int getReadAbortCount(int, int, void*, int*, int*, int); +int getTotalAbortCount(int, int, void *, int, void*, int*, int*, int, objheader_t*, int*); +int getTotalAbortCount2(void *, int, void *, int *, int*, int, objheader_t*, int*); +int getReadAbortCount(int, int, void*, int*, int*, int, objheader_t*, int*); #endif #ifdef STMSTATS objheader_t * needLock(objheader_t *, void *); diff --git a/Robust/src/Runtime/runtime.c b/Robust/src/Runtime/runtime.c index e7de7f78..1bfca0db 100644 --- a/Robust/src/Runtime/runtime.c +++ b/Robust/src/Runtime/runtime.c @@ -191,7 +191,7 @@ void CALL11(___System______exit____I,int ___status___, int ___status___) { #ifdef STMSTATS int i; for(i=0; i