From 1c16f758a67865c2c7c5418062c461639a0e6ab1 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Thu, 29 Jan 2009 04:52:12 +0000 Subject: [PATCH] hacks to fix issues with benchmarks... and to optimize the transRead call --- .../Prefetch/2DConv/dsm/Convolution.java | 9 +- .../2DConv/javasingle/Convolution.java | 10 ++- .../Benchmarks/Prefetch/Em3d/dsm/Node2.java | 7 +- .../Prefetch/Em3d/javasingle/Node2.java | 7 +- Robust/src/Benchmarks/Prefetch/run.sh | 6 +- Robust/src/IR/Flat/BuildCode.java | 4 +- .../DSTM/interface/addPrefetchEnhance.c | 22 +++++ Robust/src/Runtime/DSTM/interface/clookup.c | 5 +- Robust/src/Runtime/DSTM/interface/clookup2.c | 79 ++++++++++------- Robust/src/Runtime/DSTM/interface/clookup2.h | 2 +- Robust/src/Runtime/DSTM/interface/trans.c | 85 +++++++++++++++++-- 11 files changed, 173 insertions(+), 63 deletions(-) diff --git a/Robust/src/Benchmarks/Prefetch/2DConv/dsm/Convolution.java b/Robust/src/Benchmarks/Prefetch/2DConv/dsm/Convolution.java index 91e7f856..3c97e4d4 100644 --- a/Robust/src/Benchmarks/Prefetch/2DConv/dsm/Convolution.java +++ b/Robust/src/Benchmarks/Prefetch/2DConv/dsm/Convolution.java @@ -14,9 +14,9 @@ public class Convolution extends Thread { int kernelHeight = 5; int kernelWidth = 5; double[][] kernel = new double[kernelHeight][kernelWidth]; + initKernel(kernel); atomic { - initKernel(kernel); double tempinput[][] = img.inputImage; double tempout[][] = img.outputImage; @@ -31,11 +31,12 @@ public class Convolution extends Thread { double tout[] = tempout[i]; tinput0 = tinput1; tinput1=tinput2; tinput2=tinput3; tinput3=tinput4; tinput4=tempinput[l]; for(int j=y0;jlookupTable->size; + struct chashentry *ptr = rec->lookupTable->table; + int i; + for(i = 0; i < size; i++) { + struct chashentry *curr = &ptr[i]; //for each entry in the cache lookupTable + if(curr->key == 0) + continue; + objheader_t *header1, *header2; + /* Not found in local machine's object store and found in prefetch cache */ + if((header1 = mhashSearch(curr->key)) == NULL && ((header2 = prehashSearch(curr->key)) != NULL)) { + /* Remove from prefetch cache */ + prehashRemove(curr->key); + } + } +} +#endif /* This function updates the prefetch cache with * entries from the transaction cache when a diff --git a/Robust/src/Runtime/DSTM/interface/clookup.c b/Robust/src/Runtime/DSTM/interface/clookup.c index 0f6fa5c0..fee16fa7 100644 --- a/Robust/src/Runtime/DSTM/interface/clookup.c +++ b/Robust/src/Runtime/DSTM/interface/clookup.c @@ -71,12 +71,13 @@ INLINE void * chashSearch(chashtable_t *table, unsigned int key) { //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE chashlistnode_t *node = &table->table[(key & table->mask)>>1]; - while(node != NULL) { + do { if(node->key == key) { return node->val; } node = node->next; - } + } while(node != NULL); + return NULL; } diff --git a/Robust/src/Runtime/DSTM/interface/clookup2.c b/Robust/src/Runtime/DSTM/interface/clookup2.c index 4fab4eb0..4ceb6221 100644 --- a/Robust/src/Runtime/DSTM/interface/clookup2.c +++ b/Robust/src/Runtime/DSTM/interface/clookup2.c @@ -1,4 +1,4 @@ -#include "clookup2.h" +#include "clookup.h" #define INLINE inline __attribute__((always_inline)) chashtable_t *chashCreate(unsigned int size, float loadfactor) { @@ -28,51 +28,63 @@ chashtable_t *chashCreate(unsigned int size, float loadfactor) { } //Finds the right bin in the hash table -static INLINE unsigned int chashFunction(chashtable_t *table, unsigned int key) { - return ( key & (table->mask))>>1; //throw away low order bit +static INLINE unsigned int chashFunction(chashtable_t *table, unsigned int key, unsigned int i) { + return ((key+i*331) & table->mask)>>1; //throw away low order bit } //Store objects and their pointers into hash void chashInsert(chashtable_t *table, unsigned int key, void *val) { - unsigned int newsize; - unsigned int index; - struct chashentry *node; + struct chashentry *node = &table->table[(key & table->mask)>>1]; + unsigned int ne=table->numelements++; + unsigned int i; - if(table->numelements > table->capacity) { + if (node->key==0) { + node->ptr=val; + node->key=key; + return; + } + + if(ne > table->capacity) { //Resize - newsize = table->size << 1; + unsigned int newsize = table->size << 1; chashResize(table,newsize); + node = &table->table[(key & table->mask)>>1]; + if (node->key==0) { + node->ptr=val; + node->key=key; + return; + } } - index=(key &table->mask)>>1; - while(1) { - node = &table->table[index]; - if (node->ptr==NULL) { + + + for(i=1;1;i++) { + node = &table->table[((key+i*331) & table->mask)>>1]; + if (node->key==0) { node->ptr=val; node->key=key; return; } - index++; - if (index==table->size) - index=0; } } // Search for an address for a given oid INLINE void * chashSearch(chashtable_t *table, unsigned int key) { //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE - unsigned int tmp=(key &table->mask)>>1; - struct chashentry *node; - unsigned int ckey; - while(1) { - node = &table->table[tmp]; + struct chashentry *node=&table->table[(key & table->mask)>>1]; + unsigned int i,ckey; + + if (node->key==key) + return node->ptr; + if (node->key==0) + return NULL; + + for(i=1;1;i++) { + node = &table->table[((key+i*331) & table->mask)>>1]; ckey=node->key; if (ckey==key) return node->ptr; if (ckey==0) return NULL; - tmp++; - if (tmp==table->size) - tmp=0; } } @@ -91,29 +103,30 @@ void chashResize(chashtable_t *table, unsigned int newsize) { printf("Calloc error %s %d\n", __FILE__, __LINE__); return; } - table->table = node; //Update the global hashtable upon resize() table->size = newsize; - mask=table->mask = (newsize << 1)-1; - table->numelements = 0; + table->capacity=table->loadfactor*table->size; + mask=(table->mask = (newsize << 1)-1); for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table curr=&ptr[i]; key=curr->key; if (key != 0) { - bin=(key&mask)>>1; - while(1) { - newnode= &table->table[bin]; + newnode= &table->table[(key&mask)>>1]; + if (newnode->key==0) { + newnode->key=key; + newnode->ptr=curr->ptr; + continue; + } + + for(bin=1;1;bin++) { + newnode = &table->table[((key+bin*331) & mask)>>1]; if (newnode->key==0) { newnode->key=key; newnode->ptr=curr->ptr; break; } - bin++; - if (bin==newsize) - bin=0; } - } } free(ptr); //Free the memory of the old hash table diff --git a/Robust/src/Runtime/DSTM/interface/clookup2.h b/Robust/src/Runtime/DSTM/interface/clookup2.h index cafa0a72..70ae9617 100644 --- a/Robust/src/Runtime/DSTM/interface/clookup2.h +++ b/Robust/src/Runtime/DSTM/interface/clookup2.h @@ -23,7 +23,7 @@ typedef struct chashtable { /* Prototypes for hash*/ chashtable_t *chashCreate(unsigned int size, float loadfactor); -static unsigned int chashFunction(chashtable_t *table, unsigned int key); +static unsigned int chashFunction(chashtable_t *table, unsigned int key, unsigned int i); void chashInsert(chashtable_t *table, unsigned int key, void *val); void *chashSearch(chashtable_t *table, unsigned int key); //returns val, NULL if not found void chashResize(chashtable_t *table, unsigned int newsize); diff --git a/Robust/src/Runtime/DSTM/interface/trans.c b/Robust/src/Runtime/DSTM/interface/trans.c index 10360a60..27e61f7e 100644 --- a/Robust/src/Runtime/DSTM/interface/trans.c +++ b/Robust/src/Runtime/DSTM/interface/trans.c @@ -334,6 +334,24 @@ transrecord_t *transStart() { return tmp; } +// Search for an address for a given oid +/*#define INLINE inline __attribute__((always_inline)) + +INLINE void * chashSearchI(chashtable_t *table, unsigned int key) { + //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE + chashlistnode_t *node = &table->table[(key & table->mask)>>1]; + + do { + if(node->key == key) { + return node->val; + } + node = node->next; + } while(node != NULL); + + return NULL; + }*/ + + /* This function finds the location of the objects involved in a transaction * and returns the pointer to the object if found in a remote location */ objheader_t *transRead(transrecord_t *record, unsigned int oid) { @@ -342,22 +360,42 @@ objheader_t *transRead(transrecord_t *record, unsigned int oid) { objheader_t *objcopy; int size; void *buf; + chashlistnode_t *node; + chashtable_t *table=record->lookupTable; if(oid == 0) { return NULL; } + + node= &table->table[(oid & table->mask)>>1]; + do { + if(node->key == oid) { +#ifdef TRANSSTATS + nchashSearch++; +#endif +#ifdef COMPILER + return &((objheader_t*)node->val)[1]; +#else + return node->val; +#endif + } + node = node->next; + } while(node != NULL); + - if((objheader = chashSearch(record->lookupTable, oid)) != NULL) { + /* + if((objheader = chashSearchI(record->lookupTable, oid)) != NULL) { #ifdef TRANSSTATS nchashSearch++; #endif - /* Search local transaction cache */ #ifdef COMPILER return &objheader[1]; #else return objheader; #endif - } else if ((objheader = (objheader_t *) mhashSearch(oid)) != NULL) { + } else + */ + if ((objheader = (objheader_t *) mhashSearch(oid)) != NULL) { #ifdef TRANSSTATS nmhashSearch++; #endif @@ -434,6 +472,7 @@ objheader_t *transCreateObj(transrecord_t *record, unsigned int size) { #endif } +#if 1 /* This function creates machine piles based on all machines involved in a * transaction commit request */ plistnode_t *createPiles(transrecord_t *record) { @@ -452,11 +491,7 @@ plistnode_t *createPiles(transrecord_t *record) { //if the first bin in hash table is empty if(curr->key == 0) break; - - if ((headeraddr = (objheader_t *) chashSearch(record->lookupTable, curr->key)) == NULL) { - printf("Error: No such oid %s, %d\n", __FILE__, __LINE__); - return NULL; - } + headeraddr=(objheader_t *) curr->val; //Get machine location for object id (and whether local or not) if (STATUS(headeraddr) & NEW || (mhashSearch(curr->key) != NULL)) { @@ -473,6 +508,40 @@ plistnode_t *createPiles(transrecord_t *record) { } return pile; } +#else +/* This function creates machine piles based on all machines involved in a + * transaction commit request */ +plistnode_t *createPiles(transrecord_t *record) { + int i; + plistnode_t *pile = NULL; + unsigned int machinenum; + objheader_t *headeraddr; + struct chashentry * ptr = record->lookupTable->table; + /* Represents number of bins in the chash table */ + unsigned int size = record->lookupTable->size; + + for(i = 0; i < size ; i++) { + struct chashentry * curr = & ptr[i]; + /* Inner loop to traverse the linked list of the cache lookupTable */ + //if the first bin in hash table is empty + if(curr->key == 0) + continue; + headeraddr=(objheader_t *) curr->ptr; + + //Get machine location for object id (and whether local or not) + if (STATUS(headeraddr) & NEW || (mhashSearch(curr->key) != NULL)) { + machinenum = myIpAddr; + } else if ((machinenum = lhashSearch(curr->key)) == 0) { + printf("Error: No such machine %s, %d\n", __FILE__, __LINE__); + return NULL; + } + + //Make machine groups + pile = pInsert(pile, headeraddr, machinenum, record->lookupTable->numelements); + } + return pile; +} +#endif /* This function initiates the transaction commit process * Spawns threads for each of the new connections with Participants -- 2.34.1