00001 #ifndef __CACHEMANAGER_H__
00002 #define __CACHEMANAGER_H__
00003
00004 #include <sys/types.h>
00005 #include <vector>
00006 #include <map>
00007 #include <set>
00008 #include "charm++.h"
00009 #include "envelope.h"
00010
00011 #if COSMO_STATS > 0
00012 #include <fstream>
00013 #endif
00014
00022
00023
00024
00025 typedef struct _CkCacheUserData {
00026 CmiUInt8 d0;
00027 CmiUInt8 d1;
00028 } CkCacheUserData;
00029
00030
00031 template<class CkCacheKey> class CkCacheEntryType;
00032 template<class CkCacheKey> class CkCacheRequestorData;
00033 template<class CkCacheKey> class CkCacheEntry;
00034
00035 #include "CkCache.decl.h"
00036
00037 class CkCacheStatistics {
00038 CmiUInt8 dataArrived;
00039 CmiUInt8 dataTotalArrived;
00040 CmiUInt8 dataMisses;
00041 CmiUInt8 dataLocal;
00042 CmiUInt8 dataError;
00043 CmiUInt8 totalDataRequested;
00044 CmiUInt8 maxData;
00045 int index;
00046
00047 CkCacheStatistics() : dataArrived(0), dataTotalArrived(0),
00048 dataMisses(0), dataLocal(0), dataError(0),
00049 totalDataRequested(0), maxData(0), index(-1) { }
00050
00051 public:
00052 CkCacheStatistics(CmiUInt8 pa, CmiUInt8 pta, CmiUInt8 pm,
00053 CmiUInt8 pl, CmiUInt8 pe, CmiUInt8 tpr,
00054 CmiUInt8 mp, int i) :
00055 dataArrived(pa), dataTotalArrived(pta), dataMisses(pm),
00056 dataLocal(pl), dataError(pe), totalDataRequested(tpr),
00057 maxData(mp), index(i) { }
00058
00059 void printTo(CkOStream &os) {
00060 os << " Cache: " << dataTotalArrived << " data arrived (corresponding to ";
00061 os << dataArrived << " messages), " << dataLocal << " from local Chares" << endl;
00062 if (dataError > 0) {
00063 os << "Cache: ======>>>> ERROR: " << dataError << " data messages arrived without being requested!! <<<<======" << endl;
00064 }
00065 os << " Cache: " << dataMisses << " misses during computation" << endl;
00066 os << " Cache: Maximum of " << maxData << " data stored at a time in processor " << index << endl;
00067 os << " Cache: local Chares made " << totalDataRequested << " requests" << endl;
00068 }
00069
00070 static CkReduction::reducerType sum;
00071
00072 static CkReductionMsg *sumFn(int nMsg, CkReductionMsg **msgs) {
00073 CkCacheStatistics ret;
00074 ret.maxData = 0;
00075 for (int i=0; i<nMsg; ++i) {
00076 CkAssert(msgs[i]->getSize() == sizeof(CkCacheStatistics));
00077 CkCacheStatistics *data = (CkCacheStatistics *)msgs[i]->getData();
00078 ret.dataArrived += data->dataArrived;
00079 ret.dataTotalArrived += data->dataTotalArrived;
00080 ret.dataMisses += data->dataMisses;
00081 ret.dataLocal += data->dataLocal;
00082 ret.totalDataRequested += data->totalDataRequested;
00083 if (data->maxData > ret.maxData) {
00084 ret.maxData = data->maxData;
00085 ret.index = data->index;
00086 }
00087 }
00088 return CkReductionMsg::buildNew(sizeof(CkCacheStatistics), &ret);
00089 }
00090 };
00091
00092 template<class CkCacheKey>
00093 class CkCacheRequestMsg : public CMessage_CkCacheRequestMsg<CkCacheKey> {
00094 public:
00095 CkCacheKey key;
00096 int replyTo;
00097 CkCacheRequestMsg(CkCacheKey k, int reply) : key(k), replyTo(reply) { }
00098 };
00099
00100 template<class CkCacheKey>
00101 class CkCacheFillMsg : public CMessage_CkCacheFillMsg<CkCacheKey> {
00102 public:
00103 CkCacheKey key;
00104 char *data;
00105 CkCacheFillMsg (CkCacheKey k) : key(k) {}
00106 };
00107
00108
00109 template<class CkCacheKey>
00110 class CkCacheRequestorData {
00111 public:
00112 CkCacheUserData userData;
00113 typedef void (*CkCacheCallback)(CkArrayID, CkArrayIndex&, CkCacheKey, CkCacheUserData &, void*, int);
00114 CkCacheCallback fn;
00115 CkArrayID requestorID;
00116 CkArrayIndex requestorIdx;
00117
00118 CkCacheRequestorData(CProxyElement_ArrayElement &el, CkCacheCallback f, CkCacheUserData &data) {
00119 userData = data;
00120 requestorID = el.ckGetArrayID();
00121 requestorIdx = el.ckGetIndex();
00122 fn = f;
00123 }
00124
00125 void deliver(CkCacheKey key, void *data, int chunk) {
00126 fn(requestorID, requestorIdx, key, userData, data, chunk);
00127 }
00128 };
00129
00130 template<class CkCacheKey>
00131 class CkCacheEntryType {
00132 public:
00133 virtual void * request(CkArrayIndex&, CkCacheKey) = 0;
00134 virtual void * unpack(CkCacheFillMsg<CkCacheKey> *, int, CkArrayIndex &) = 0;
00135 virtual void writeback(CkArrayIndex&, CkCacheKey, void *) = 0;
00136 virtual void free(void *) = 0;
00137 virtual int size(void *) = 0;
00138 };
00139
00140 template<class CkCacheKey>
00141 class CkCacheEntry {
00142 public:
00143 CkCacheKey key;
00144 CkArrayIndex home;
00145 CkCacheEntryType<CkCacheKey> *type;
00146 std::vector< CkCacheRequestorData<CkCacheKey> > requestorVec;
00147
00148 void *data;
00149
00150 bool requestSent;
00151 bool replyRecvd;
00152 bool writtenBack;
00153 #if COSMO_STATS > 1
00155 int totalRequests;
00158 int misses;
00159 #endif
00160 CkCacheEntry(CkCacheKey key, CkArrayIndex &home, CkCacheEntryType<CkCacheKey> *type) {
00161 replyRecvd = false;
00162 requestSent = false;
00163 writtenBack = false;
00164 data = NULL;
00165 this->key = key;
00166 this->home = home;
00167 this->type = type;
00168 #if COSMO_STATS > 1
00169 totalRequests=0;
00170 misses=0;
00171 #endif
00172 }
00173
00174 ~CkCacheEntry() {
00175 CkAssert(requestorVec.empty());
00176 if (!writtenBack) writeback();
00177 type->free(data);
00178 }
00179
00180 inline void writeback() {
00181 type->writeback(home, key, data);
00182 writtenBack = true;
00183 }
00184 };
00185
00186 class CkCacheArrayCounter : public CkLocIterator {
00187 public:
00188 int count;
00189 CkHashtableT<CkArrayIndex, int> registered;
00190 CkCacheArrayCounter() : count(0) { }
00191 void addLocation(CkLocation &loc) {
00192 registered.put(loc.getIndex()) = ++count;
00193 }
00194 void reset() {
00195 count = 0;
00196 registered.empty();
00197 }
00198 };
00199
00200 template<class CkCacheKey>
00201 class CkCacheManager : public CBase_CkCacheManager<CkCacheKey> {
00202
00203
00204
00205
00206
00208 int numChunks;
00210 int finishedChunks;
00211
00214 CkCacheArrayCounter localChares;
00217 CkCacheArrayCounter localCharesWB;
00219 int syncdChares;
00220
00222 int numLocMgr;
00225 CkGroupID *locMgr;
00227 int numLocMgrWB;
00230 CkGroupID *locMgrWB;
00231
00232 #if COSMO_STATS > 0
00234 CmiUInt8 dataArrived;
00237 CmiUInt8 dataTotalArrived;
00239 CmiUInt8 dataMisses;
00241 CmiUInt8 dataLocal;
00243 CmiUInt8 dataError;
00244
00246 CmiUInt8 totalDataRequested;
00248 CmiUInt8 maxData;
00249 #endif
00250
00253 CmiUInt8 *chunkWeight;
00254
00256 CmiUInt8 maxSize;
00257
00259 int *chunkAck;
00261 int *chunkAckWB;
00262
00264 std::map<CkCacheKey,CkCacheEntry<CkCacheKey>*> *cacheTable;
00265 int storedData;
00266
00269 std::map<CkCacheKey,int> outStandingRequests;
00270
00271
00272
00273
00274
00275 public:
00276
00277 CkCacheManager(int size, CkGroupID gid);
00278 CkCacheManager(int size, int n, CkGroupID *gid);
00279 CkCacheManager(int size, int n, CkGroupID *gid, int nWB, CkGroupID *gidWB);
00280 CkCacheManager(CkMigrateMessage *m): CBase_CkCacheManager<CkCacheKey>(m) { init(); }
00281 ~CkCacheManager() {}
00282 void pup(PUP::er &p);
00283 private:
00284 void init();
00285 public:
00286
00287 void * requestData(CkCacheKey what, CkArrayIndex &toWhom, int chunk, CkCacheEntryType<CkCacheKey> *type, CkCacheRequestorData<CkCacheKey> &req);
00288 void * requestDataNoFetch(CkCacheKey key, int chunk);
00289 CkCacheEntry<CkCacheKey> * requestCacheEntryNoFetch(CkCacheKey key, int chunk);
00290 void recvData(CkCacheKey key, void *data,
00291 CkCacheFillMsg<CkCacheKey> *msg = NULL);
00292 void recvData(CkCacheFillMsg<CkCacheKey> *msg);
00293 void recvData(CkCacheKey key, CkArrayIndex &from, CkCacheEntryType<CkCacheKey> *type, int chunk, void *data);
00294
00295 void cacheSync(int &numChunks, CkArrayIndex &chareIdx, int &localIdx);
00296
00299 void writebackChunk(int num);
00302 void finishedChunk(int num, CmiUInt8 weight);
00307 void collectStatistics(CkCallback cb);
00308 std::map<CkCacheKey,CkCacheEntry<CkCacheKey>*> *getCache();
00309
00310 };
00311
00312
00313
00314 template<class CkCacheKey>
00315 CkCacheManager<CkCacheKey>::CkCacheManager(int size, CkGroupID gid) {
00316 init();
00317 numLocMgr = 1;
00318 numLocMgrWB = 0;
00319 locMgr = new CkGroupID[1];
00320 locMgr[0] = gid;
00321 maxSize = (CmiUInt8)size * 1024 * 1024;
00322 }
00323
00324 template<class CkCacheKey>
00325 CkCacheManager<CkCacheKey>::CkCacheManager(int size, int n, CkGroupID *gid) {
00326 init();
00327 numLocMgr = n;
00328 numLocMgrWB = 0;
00329 locMgr = new CkGroupID[n];
00330 for (int i=0; i<n; ++i) locMgr[i] = gid[i];
00331 maxSize = (CmiUInt8)size * 1024 * 1024;
00332 }
00333
00334 template<class CkCacheKey>
00335 CkCacheManager<CkCacheKey>::CkCacheManager(int size, int n, CkGroupID *gid, int nWB, CkGroupID *gidWB) {
00336 init();
00337 numLocMgr = n;
00338 locMgr = new CkGroupID[n];
00339 for (int i=0; i<n; ++i) locMgr[i] = gid[i];
00340 numLocMgrWB = nWB;
00341 locMgrWB = new CkGroupID[nWB];
00342 for (int i=0; i<nWB; ++i) locMgrWB[i] = gidWB[i];
00343 maxSize = (CmiUInt8)size * 1024 * 1024;
00344 }
00345
00346 template<class CkCacheKey>
00347 void CkCacheManager<CkCacheKey>::init() {
00348 numChunks = 0;
00349 numLocMgr = 0;
00350 locMgr = NULL;
00351 maxSize = 0;
00352 syncdChares = 0;
00353 cacheTable = NULL;
00354 chunkAck = NULL;
00355 chunkWeight = NULL;
00356 storedData = 0;
00357 #if COSMO_STATS > 0
00358 dataArrived = 0;
00359 dataTotalArrived = 0;
00360 dataMisses = 0;
00361 dataLocal = 0;
00362 totalDataRequested = 0;
00363 #endif
00364 }
00365
00366 template<class CkCacheKey>
00367 void CkCacheManager<CkCacheKey>::pup(PUP::er &p) {
00368 p | numLocMgr;
00369 if (p.isUnpacking()) locMgr = new CkGroupID[numLocMgr];
00370 PUP::PUParray(p,locMgr,numLocMgr);
00371 p | numLocMgrWB;
00372 if (p.isUnpacking()) locMgrWB = new CkGroupID[numLocMgrWB];
00373 PUP::PUParray(p,locMgrWB,numLocMgrWB);
00374 p | maxSize;
00375 }
00376
00377 template<class CkCacheKey>
00378 void * CkCacheManager<CkCacheKey>::requestData(CkCacheKey what, CkArrayIndex &_toWhom, int chunk, CkCacheEntryType<CkCacheKey> *type, CkCacheRequestorData<CkCacheKey> &req)
00379 {
00380 typename std::map<CkCacheKey, CkCacheEntry<CkCacheKey>* >::iterator p;
00381 CkArrayIndex toWhom(_toWhom);
00382 CkAssert(chunkAck[chunk] > 0);
00383 p = cacheTable[chunk].find(what);
00384 CkCacheEntry<CkCacheKey> *e;
00385 #if COSMO_STATS > 0
00386 totalDataRequested++;
00387 #endif
00388 if (p != cacheTable[chunk].end()) {
00389 e = p->second;
00390 CkAssert(e->home == toWhom);
00391
00392
00393 #if COSMO_STATS > 1
00394 e->totalRequests++;
00395 #endif
00396 if (e->data != NULL) {
00397 return e->data;
00398 }
00399 if (!e->requestSent) {
00400 e->requestSent = true;
00401 if ((e->data = type->request(toWhom, what)) != NULL) {
00402 e->replyRecvd = true;
00403 return e->data;
00404 }
00405 }
00406 } else {
00407 e = new CkCacheEntry<CkCacheKey>(what, toWhom, type);
00408 #if COSMO_STATS > 1
00409 e->totalRequests++;
00410 #endif
00411 cacheTable[chunk][what] = e;
00412 e->requestSent = true;
00413 if ((e->data = type->request(toWhom, what)) != NULL) {
00414 e->replyRecvd = true;
00415 return e->data;
00416 }
00417 }
00418
00419 e->requestorVec.push_back(req);
00420 outStandingRequests[what] = chunk;
00421 #if COSMO_STATS > 1
00422 e->misses++;
00423 #endif
00424 return NULL;
00425 }
00426
00427 template<class CkCacheKey>
00428 void * CkCacheManager<CkCacheKey>::requestDataNoFetch(CkCacheKey key, int chunk) {
00429 typename std::map<CkCacheKey,CkCacheEntry<CkCacheKey> *>::iterator p = cacheTable[chunk].find(key);
00430 if (p != cacheTable[chunk].end()) {
00431 return p->second->data;
00432 }
00433 return NULL;
00434 }
00435
00436 template<class CkCacheKey>
00437 CkCacheEntry<CkCacheKey> * CkCacheManager<CkCacheKey>::requestCacheEntryNoFetch(CkCacheKey key, int chunk) {
00438 typename std::map<CkCacheKey,CkCacheEntry<CkCacheKey> *>::iterator p = cacheTable[chunk].find(key);
00439 if (p != cacheTable[chunk].end()) {
00440 return p->second;
00441 }
00442 return NULL;
00443 }
00444
00445 template<class CkCacheKey>
00446 std::map<CkCacheKey,CkCacheEntry<CkCacheKey>*> *CkCacheManager<CkCacheKey>::getCache(){
00447 return cacheTable;
00448 }
00449
00450 template <class CkCacheKey>
00451 inline void CkCacheManager<CkCacheKey>::recvData(CkCacheKey key, void *data, CkCacheFillMsg<CkCacheKey> *msg) {
00452
00453 typename std::map<CkCacheKey,int>::iterator pchunk = outStandingRequests.find(key);
00454 CkAssert(pchunk != outStandingRequests.end());
00455 int chunk = pchunk->second;
00456 CkAssert(chunk >= 0 && chunk < numChunks);
00457 CkAssert(chunkAck[chunk] > 0);
00458 outStandingRequests.erase(pchunk);
00459
00460 typename std::map<CkCacheKey,CkCacheEntry<CkCacheKey>*>::iterator p;
00461 p = cacheTable[chunk].find(key);
00462 CkAssert(p != cacheTable[chunk].end());
00463 CkCacheEntry<CkCacheKey> *e = p->second;
00464 if (msg != NULL) {
00465 e->data = e->type->unpack(msg, chunk, e->home);
00466 }
00467 else {
00468 e->data = data;
00469 }
00470 storedData += e->type->size(e->data);
00471
00472 typename std::vector<CkCacheRequestorData<CkCacheKey> >::iterator caller;
00473 for (caller = e->requestorVec.begin(); caller != e->requestorVec.end(); caller++) {
00474 caller->deliver(key, e->data, chunk);
00475 }
00476 e->requestorVec.clear();
00477
00478 }
00479
00480 template<class CkCacheKey>
00481 void CkCacheManager<CkCacheKey>::recvData(CkCacheFillMsg<CkCacheKey> *msg) {
00482 CkCacheKey key = msg->key;
00483 recvData(key, NULL, msg);
00484 }
00485
00486 template<class CkCacheKey>
00487 void CkCacheManager<CkCacheKey>::recvData(CkCacheKey key, CkArrayIndex &from, CkCacheEntryType<CkCacheKey> *type, int chunk, void *data) {
00488 typename std::map<CkCacheKey,CkCacheEntry<CkCacheKey>*>::iterator p = cacheTable[chunk].find(key);
00489 CkCacheEntry<CkCacheKey> *e;
00490 if (p == cacheTable[chunk].end()) {
00491 e = new CkCacheEntry<CkCacheKey>(key, from, type);
00492 cacheTable[chunk][key] = e;
00493 } else {
00494 e = p->second;
00495 storedData -= e->type->size(e->data);
00496 e->type->writeback(e->home, e->key, e->data);
00497 }
00498 e->replyRecvd = true;
00499 e->data = data;
00500 storedData += e->type->size(data);
00501
00502 typename std::vector<CkCacheRequestorData<CkCacheKey> >::iterator caller;
00503 for (caller = e->requestorVec.begin(); caller != e->requestorVec.end(); caller++) {
00504 caller->deliver(key, e->data, chunk);
00505 }
00506 e->requestorVec.clear();
00507 }
00508
00509 template<class CkCacheKey>
00510 void CkCacheManager<CkCacheKey>::cacheSync(int &_numChunks, CkArrayIndex &chareIdx, int &localIdx) {
00511 finishedChunks = 0;
00512 if (syncdChares > 0) {
00513 _numChunks = numChunks;
00514
00515 } else {
00516 syncdChares = 1;
00517
00518
00519 localChares.reset();
00520 localCharesWB.reset();
00521 for (int i=0; i<numLocMgr; ++i) {
00522 CkLocMgr *mgr = (CkLocMgr *)CkLocalBranch(locMgr[i]);
00523 mgr->iterate(localChares);
00524 }
00525 for (int i=0; i<numLocMgrWB; ++i) {
00526 CkLocMgr *mgr = (CkLocMgr *)CkLocalBranch(locMgrWB[i]);
00527 mgr->iterate(localChares);
00528 mgr->iterate(localCharesWB);
00529 }
00530
00531 #if COSMO_STATS > 0
00532 dataArrived = 0;
00533 dataTotalArrived = 0;
00534 dataMisses = 0;
00535 dataLocal = 0;
00536 totalDataRequested = 0;
00537 maxData = 0;
00538 #endif
00539
00540 for (int chunk=0; chunk<numChunks; ++chunk) {
00541 CkAssert(cacheTable[chunk].empty());
00542 CkAssert(chunkAck[chunk]==0);
00543 CkAssert(chunkAckWB[chunk]==0);
00544 }
00545 CkAssert(outStandingRequests.empty());
00546 storedData = 0;
00547
00548 if (numChunks != _numChunks) {
00549 if(numChunks != 0) {
00550 delete []cacheTable;
00551 delete []chunkAck;
00552 delete []chunkAckWB;
00553 delete []chunkWeight;
00554 }
00555
00556 numChunks = _numChunks;
00557 cacheTable = new std::map<CkCacheKey,CkCacheEntry<CkCacheKey>*>[numChunks];
00558 chunkAck = new int[numChunks];
00559 chunkAckWB = new int[numChunks];
00560 chunkWeight = new CmiUInt8[numChunks];
00561 }
00562 for (int i=0; i<numChunks; ++i) {
00563 chunkAck[i] = localChares.count;
00564 chunkAckWB[i] = localCharesWB.count;
00565 chunkWeight[i] = 0;
00566
00567 }
00568
00569 #if COSMO_STATS > 0
00570 CmiResetMaxMemory();
00571 #endif
00572 }
00573
00574 localIdx = localChares.registered.get(chareIdx);
00575 CkAssert(localIdx != 0);
00576 }
00577
00578 template<class CkCacheKey>
00579 void CkCacheManager<CkCacheKey>::writebackChunk(int chunk) {
00580
00581 CkAssert(chunkAckWB[chunk] > 0);
00582 if (--chunkAckWB[chunk] == 0) {
00583
00584
00585
00586 typename std::map<CkCacheKey,CkCacheEntry<CkCacheKey>*>::iterator iter;
00587 for (iter = cacheTable[chunk].begin(); iter != cacheTable[chunk].end(); iter++) {
00588 CkCacheEntry<CkCacheKey> *e = iter->second;
00589 e->writeback();
00590 }
00591
00592 }
00593 }
00594
00595 template<class CkCacheKey>
00596 void CkCacheManager<CkCacheKey>::finishedChunk(int chunk, CmiUInt8 weight) {
00597
00598 CkAssert(chunkAck[chunk] > 0);
00599 chunkWeight[chunk] += weight;
00600
00601 if (--chunkAck[chunk] == 0) {
00602
00603
00604
00605
00606
00607 #if COSMO_STATS > 0
00608 if (maxData < storedData) maxData = storedData;
00609 #endif
00610
00611 typename std::map<CkCacheKey,CkCacheEntry<CkCacheKey>*>::iterator iter;
00612 for (iter = cacheTable[chunk].begin(); iter != cacheTable[chunk].end(); iter++) {
00613 CkCacheEntry<CkCacheKey> *e = iter->second;
00614 storedData -= e->type->size(e->data);
00615
00616
00617
00618 delete e;
00619 }
00620 cacheTable[chunk].clear();
00621 if (++finishedChunks == numChunks) {
00622 finishedChunks = 0;
00623 syncdChares = 0;
00624 }
00625 }
00626 }
00627
00628 template<class CkCacheKey>
00629 void CkCacheManager<CkCacheKey>::collectStatistics(CkCallback cb) {
00630 #if COSMO_STATS > 0
00631 CkCacheStatistics cs(dataArrived, dataTotalArrived,
00632 dataMisses, dataLocal, dataError, totalDataRequested,
00633 maxData, CkMyPe());
00634 contribute(sizeof(CkCacheStatistics), &cs, CkCacheStatistics::sum, cb);
00635 #else
00636 CkAbort("Invalid call, only valid if COSMO_STATS is defined");
00637 #endif
00638 }
00639
00640 #define CK_TEMPLATES_ONLY
00641 #include "CkCache.def.h"
00642 #undef CK_TEMPLATES_ONLY
00643
00644 #endif
1.5.5