Charm++: Charm Source Code Documentation

00001 /*
00002   This file defines various reducers for sparse contiguous 2D arrays. 
00003   It also defines some functions to parse the result of a reduction 
00004   on sparse contiguous 2D arrays.
00005 
00006                               Vikas Mehta, vmehta1@uiuc.edu, 06/03/03
00007 */
00008 
00009 #include "cksparsecontiguousreducer.h"
00010 
00011 /* 
00012    various reducers supported for sparse contiguous 2D arrays
00013 */
00014 CkReduction::reducerType sparse_sum_int;
00015 CkReduction::reducerType sparse_sum_float;
00016 CkReduction::reducerType sparse_sum_double;
00017 CkReduction::reducerType sparse_sum_TwoFloats;
00018 CkReduction::reducerType sparse_sum_TwoDoubles;
00019 
00020 CkReduction::reducerType sparse_product_int;
00021 CkReduction::reducerType sparse_product_float;
00022 CkReduction::reducerType sparse_product_double;
00023 
00024 CkReduction::reducerType sparse_max_int;
00025 CkReduction::reducerType sparse_max_float;
00026 CkReduction::reducerType sparse_max_double;
00027 
00028 CkReduction::reducerType sparse_min_int;
00029 CkReduction::reducerType sparse_min_float;
00030 CkReduction::reducerType sparse_min_double;
00031 
00032 /*
00033   This function returns the index of jth data segment header in the 
00034   array of headers pointed to by 'ptr'.
00035 */
00036 //int getIndex(CkDataSegHeader *r, const unsigned char *ptr, int j);
00037 
00038 /*
00039   macro defining various reducer functions
00040 */
00041 #define SIMPLE_SPARSE_CONTIGUOUS_REDUCTION(name,dataType,typeStr,loop) \
00042 static CkReductionMsg *name(int nMsg, CkReductionMsg ** msg){\
00043   if(nMsg==1){\
00044     CkReductionMsg *ret = msg[0];\
00045     msg[0] = NULL;\
00046     return ret;\
00047   }\
00048  \
00049   int               count          = 0;\
00050   CkDataSegHeader*  finalHeaderArr = NULL; /* size [count] */\
00051   CkDataSegHeader** msgHeaderArr   = NULL; /* size [nMsg] */\
00052   int*              size           = NULL; /* size [nMsg] */\
00053   int*              pos            = NULL; /* size [nMsg] */\
00054   int*              off            = NULL; /* size [nMsg] */\
00055   int*              arrPos         = NULL; /* size [count] */\
00056   int*              dataPos        = NULL; /* size [count] */\
00057   int*              flag           = NULL; /* size [count] */\
00058   int               i              = 0;\
00059 \
00060   /* find the total data segments in n input msgs */\
00061   for(i=0; i<nMsg; i++) {\
00062     count += numDataSegs((unsigned char*)(msg[i]->getData()));\
00063   }\
00064 \
00065   int nm  = ((nMsg*sizeof(int)) + \
00066             sizeof(CkDataSegHeader))/sizeof(CkDataSegHeader);\
00067   int nmp = ((nMsg*sizeof(CkDataSegHeader*)) + \
00068             sizeof(CkDataSegHeader))/sizeof(CkDataSegHeader);\
00069   int nc  = ((count*sizeof(int)) + \
00070             sizeof(CkDataSegHeader))/sizeof(CkDataSegHeader);\
00071   int numHeaderToAllocate = count + nmp + 3*nm + 3*nc;\
00072 \
00073   finalHeaderArr = new CkDataSegHeader[numHeaderToAllocate];\
00074 \
00075   msgHeaderArr   = (CkDataSegHeader**)(finalHeaderArr + count);\
00076   size           = (int*)(((CkDataSegHeader*)msgHeaderArr) + nmp);\
00077   pos            = (int*)(((CkDataSegHeader*)size) + nm);\
00078   off            = (int*)(((CkDataSegHeader*)pos) + nm);\
00079   arrPos         = (int*)(((CkDataSegHeader*)off) + nm);\
00080   dataPos        = (int*)(((CkDataSegHeader*)arrPos) + nc);\
00081   flag           = (int*)(((CkDataSegHeader*)dataPos) + nc);\
00082 \
00083   /* put all the unique data headers from input messages to the header-array */\
00084 \
00085   /* initialize temporary variables */\
00086   pos [0]          = 0;\
00087   size [0]         = numDataSegs((unsigned char*)(msg[0]->getData()));\
00088   off [0]          = 0;\
00089   msgHeaderArr [0] = getDataSegHeaderPtr((unsigned char*)(msg[0]->getData()));\
00090 \
00091   for(i=1; i<nMsg; i++){\
00092     unsigned char * data = (unsigned char*)(msg[i]->getData());\
00093     pos  [i]             = 0;\
00094     size [i]             = numDataSegs(data);\
00095     off [i]              = off [i-1] + size [i-1];\
00096     msgHeaderArr [i]     = getDataSegHeaderPtr(data);\
00097   }\
00098 \
00099   for(i=0; i<count; i++){\
00100     arrPos  [i]  = -1;\
00101     dataPos [i]  = -1;\
00102   }\
00103 \
00104   /* n-way merge */\
00105   int nScanned    = 0;\
00106   int currMsg     = 0;\
00107   /* number of unique merged headers */\
00108   int totalHeader = 0;\
00109 \
00110   /* find the first header */\
00111   int index = 0;\
00112   int currDataOff = 0;\
00113   CkDataSegHeader minHdr = msgHeaderArr [currMsg][pos[currMsg]];\
00114 \
00115   for (index=1; index < nMsg; index++) {\
00116     if (msgHeaderArr [index][pos[index]] < minHdr)  {\
00117       currMsg = index;\
00118       minHdr = msgHeaderArr [index][pos[index]];\
00119     }\
00120   }\
00121 \
00122   arrPos [off [currMsg] + pos [currMsg]] = totalHeader;\
00123   dataPos [off [currMsg] + pos [currMsg]] = currDataOff;\
00124   finalHeaderArr [totalHeader++] = msgHeaderArr [currMsg][pos[currMsg]++];\
00125   nScanned ++;\
00126 \
00127   while (nScanned != count) {\
00128     if (pos [currMsg] != size [currMsg]) {\
00129       minHdr = msgHeaderArr [currMsg][pos[currMsg]];\
00130     } else {\
00131       currMsg = (currMsg+1)%nMsg;\
00132       continue;\
00133     }\
00134     for (index=0; index < nMsg; index++) {\
00135       if ((pos [index] != size [index])&&\
00136           (msgHeaderArr [index][pos[index]] < minHdr))  {\
00137         currMsg = index;\
00138         minHdr = msgHeaderArr [index][pos[index]];\
00139       }\
00140     }\
00141 \
00142     if (!(finalHeaderArr [totalHeader-1] == msgHeaderArr [currMsg][pos[currMsg]])) {\
00143       currDataOff += sizeof(dataType)*finalHeaderArr [totalHeader-1].getNumElements();\
00144       arrPos [off [currMsg] + pos [currMsg]] = totalHeader;\
00145       dataPos [off [currMsg] + pos [currMsg]] = currDataOff;\
00146       finalHeaderArr [totalHeader++] = msgHeaderArr [currMsg][pos[currMsg]++];\
00147     }\
00148     else {\
00149       arrPos [off [currMsg] + pos [currMsg]] = totalHeader-1;\
00150       dataPos [off [currMsg] + pos [currMsg]] = currDataOff;\
00151       pos[currMsg]++;\
00152     }\
00153     nScanned ++;\
00154   }\
00155 \
00156  /* number of non-null data blocks and total number of elements in them is\
00157     known. Now pack the input data into one buffer resolving the overlap.*/\
00158 \
00159   int alignedHdrSize = 2*sizeof(int) + sizeof(CkDataSegHeader)*totalHeader;\
00160   if (alignedHdrSize%sizeof(double))\
00161     alignedHdrSize += sizeof(double) - (alignedHdrSize%sizeof(double));\
00162   int dataSize = alignedHdrSize + \
00163                  currDataOff + \
00164                  sizeof(dataType)*finalHeaderArr [totalHeader-1].getNumElements();\
00165 \
00166   CkReductionMsg* m = CkReductionMsg::buildNew(dataSize, NULL); \
00167   unsigned char *data = (unsigned char*)(m->getData ());\
00168   memset (flag, 0, totalHeader*sizeof(int));\
00169 \
00170   *(int*)data = totalHeader;\
00171   data += sizeof(int);\
00172   *(int*)data = alignedHdrSize;\
00173   data += sizeof(int);\
00174 \
00175   int dataOffset = alignedHdrSize - 2*sizeof (int);\
00176   int numElems;\
00177   CkDataSegHeader* hdrPtr = (CkDataSegHeader*)data;\
00178   dataType*        dataptr = (dataType*)(data + dataOffset);\
00179 \
00180   for (i=0; i<nMsg; i++) {\
00181     dataType* msgDataptr = (dataType*)getDataPtr((unsigned char*)(msg[i]->getData()));\
00182     for (index=0; index<size[i]; index++) {\
00183       numElems = msgHeaderArr [i][index].getNumElements();\
00184 \
00185       hdrPtr [arrPos [off [i] + index]] = msgHeaderArr [i][index];\
00186       dataptr = (dataType*)(data + dataOffset + dataPos [off [i] + index]);\
00187       if (!flag [arrPos [off [i] + index]]) {\
00188         flag [arrPos [off [i] + index]] = 1;\
00189         memcpy(dataptr, msgDataptr, sizeof(dataType)*numElems);\
00190         msgDataptr += numElems;\
00191       } else {\
00192         for (int k=0; k<numElems; k++) {\
00193           loop\
00194           msgDataptr++;\
00195         }\
00196       }\
00197     }\
00198   }\
00199 \
00200   delete[] finalHeaderArr;\
00201 \
00202   return m;\
00203 }
00204 
00205 //Use this macro for reductions that have the same type for all inputs
00206 #define SIMPLE_POLYMORPH_SPARSE_CONTIGUOUS_REDUCTION(nameBase,loop) \
00207   SIMPLE_SPARSE_CONTIGUOUS_REDUCTION(nameBase##_int,int,"%d",loop) \
00208   SIMPLE_SPARSE_CONTIGUOUS_REDUCTION(nameBase##_float,float,"%f",loop) \
00209   SIMPLE_SPARSE_CONTIGUOUS_REDUCTION(nameBase##_double,double,"%f",loop)
00210 
00211 //Use this macro for reductions that have the same type for all inputs
00212 #define POLYMORPH_SPARSE_CONTIGUOUS_REDUCTION(nameBase,loop) \
00213   SIMPLE_SPARSE_CONTIGUOUS_REDUCTION(nameBase##_TwoFloats,CkTwoFloats,"%d",loop) \
00214   SIMPLE_SPARSE_CONTIGUOUS_REDUCTION(nameBase##_TwoDoubles,CkTwoDoubles,"%f",loop) \
00215 
00216 // Merge the sparse arrays passed by elements, summing the elements with same
00217 // indices.
00218 POLYMORPH_SPARSE_CONTIGUOUS_REDUCTION(_sparse_sum, *(dataptr + k) +=
00219   *msgDataptr;)
00220 
00221 // Merge the sparse arrays passed by elements, summing the elements with same
00222 // indices.
00223 SIMPLE_POLYMORPH_SPARSE_CONTIGUOUS_REDUCTION(_sparse_sum, *(dataptr + k) +=
00224   *msgDataptr;)
00225 
00226 // Merge the sparse arrays passed by elements, multiplying the elements with
00227 // same indices.
00228 SIMPLE_POLYMORPH_SPARSE_CONTIGUOUS_REDUCTION(_sparse_product, *(dataptr + k) *=
00229   *msgDataptr;)
00230 
00231 // Merge the sparse arrays passed by elements, keeping the largest of the
00232 // elements with same indices.
00233 SIMPLE_POLYMORPH_SPARSE_CONTIGUOUS_REDUCTION(_sparse_max,
00234   if(*(dataptr+k)<*msgDataptr) *(dataptr+k)=*msgDataptr;)
00235 
00236 // Merge the sparse arrays passed by elements, keeping the smallest of the
00237 // elements with same indices.
00238 SIMPLE_POLYMORPH_SPARSE_CONTIGUOUS_REDUCTION(_sparse_min,
00239   if(*(dataptr+k)>*msgDataptr) *(dataptr+k)=*msgDataptr;)
00240 
00241 /*
00242    register supported reducers
00243 */
00244 void registerReducers(void)
00245 {
00246   sparse_sum_int = CkReduction::addReducer(_sparse_sum_int);
00247   sparse_sum_float = CkReduction::addReducer(_sparse_sum_float);
00248   sparse_sum_double = CkReduction::addReducer(_sparse_sum_double);
00249   sparse_sum_TwoFloats = CkReduction::addReducer(_sparse_sum_TwoFloats);
00250   sparse_sum_TwoDoubles = CkReduction::addReducer(_sparse_sum_TwoDoubles);
00251 
00252   sparse_product_int = CkReduction::addReducer(_sparse_product_int);
00253   sparse_product_float= CkReduction::addReducer(_sparse_product_float);
00254   sparse_product_double = CkReduction::addReducer(_sparse_product_double);
00255 
00256   sparse_max_int = CkReduction::addReducer(_sparse_max_int);
00257   sparse_max_float = CkReduction::addReducer(_sparse_max_float);
00258   sparse_max_double = CkReduction::addReducer(_sparse_max_double);
00259 
00260   sparse_min_int = CkReduction::addReducer(_sparse_min_int);
00261   sparse_min_float= CkReduction::addReducer(_sparse_min_float);
00262   sparse_min_double = CkReduction::addReducer(_sparse_min_double);
00263 }
00264 
00265 int numDataSegs(const unsigned char *data){
00266   return *(int*)data;
00267 }
00268 
00269 CkDataSegHeader getDataSegHeader(int index, const unsigned char *data){
00270   int size=numDataSegs(data);
00271   CkDataSegHeader r;
00272   if(index >= size)
00273     CkAbort("Error!!!\n");
00274 
00275   memcpy(&r, data+2*sizeof(int)+sizeof(CkDataSegHeader)*index, sizeof(CkDataSegHeader));
00276   return r;
00277 }
00278 
00279 /*int getIndex(CkDataSegHeader *r, const unsigned char *ptr, int j){
00280   int i=0;
00281   CkDataSegHeader header = getDataSegHeader(j, ptr);
00282   while(!(header == r[i]))
00283     i++;
00284   return i;
00285 }*/
00286 
00287 unsigned char * getDataPtr(unsigned char *ptr){
00288 /*
00289   int size;
00290   size = numDataSegs(ptr);
00291   return (unsigned char*)(ptr + sizeof(int) + size*sizeof(CkDataSegHeader));
00292 */
00293   return (ptr + *(((int*)ptr)+1));
00294 }
00295 
00296 CkDataSegHeader* getDataSegHeaderPtr(const unsigned char *ptr) {
00297   return (CkDataSegHeader*)(ptr + 2*sizeof(int));
00298 }
00299 
00300 CkDataSegHeader getDecompressedDataHdr(const unsigned char *msg){
00301   CkDataSegHeader retHead(0, 0, 0, 0);
00302   CkDataSegHeader h;
00303   int numSegs = numDataSegs(msg);
00304 
00305   for(int i=0; i<numSegs; i++){
00306     h = getDataSegHeader(i, msg);
00307     if(retHead.sx > h.sx)
00308       retHead.sx = h.sx;
00309     if(retHead.sy > h.sy)
00310       retHead.sy = h.sy;
00311     if(retHead.ex < h.ex)
00312       retHead.ex = h.ex;
00313     if(retHead.ey < h.ey)
00314       retHead.ey = h.ey;
00315   }
00316   return retHead;
00317 }
00318 
00319 #define SIMPLE_DECOMPRESSOR(dataType)\
00320 dataType *decompressMsg(CkReductionMsg *m, CkDataSegHeader &h, dataType nullVal){\
00321   unsigned char *msg = (unsigned char*)m->getData();\
00322   h = getDecompressedDataHdr(msg);\
00323   CkDataSegHeader head;\
00324   dataType *data;\
00325   int sizeX = h.ex - h.sx + 1;\
00326   int sizeY = h.ey - h.sy + 1;\
00327   int numSegs = numDataSegs(msg);\
00328 \
00329   data = new dataType[sizeX*sizeY];\
00330 \
00331   int i;    \
00332   for(i=0; i<sizeX*sizeY; i++)\
00333       data[i] = nullVal;\
00334 \
00335   dataType *msgDataptr = (dataType *)getDataPtr(msg);\
00336   for(i=0; i<numSegs; i++){\
00337     head = getDataSegHeader(i, msg);\
00338     int startY = head.sy - h.sy;\
00339     int endY   = head.ey - h.sy;\
00340     int startX = head.sx - h.sx;\
00341     int endX   = head.ex - h.sx;\
00342     for(int y=startY; y<=endY; y++){\
00343       int inc = y*sizeX;\
00344       for(int x=startX; x<=endX; x++)\
00345         data[x+inc] = *msgDataptr++;\
00346     }\
00347   }\
00348   return data;\
00349 }
00350 
00351 // define decompressor for 'int' data 
00352 SIMPLE_DECOMPRESSOR(int)
00353 
00354 // define decompressor for 'float' data
00355 SIMPLE_DECOMPRESSOR(float)
00356 
00357 // define decompressor for 'double' data
00358 SIMPLE_DECOMPRESSOR(double)
00359 
00360 // define decompressor for 'CkTwoFloats' data
00361 SIMPLE_DECOMPRESSOR(CkTwoFloats)
00362 
00363 // define decompressor for 'CkTwoDoubles' data
00364 SIMPLE_DECOMPRESSOR(CkTwoDoubles)
00365 #include "CkSparseContiguousReducer.def.h"
libs/ck-libs/sparseContiguousReducer/cksparsecontiguousreducer.C
