Charm++: Charm Source Code Documentation

00001 /* searchEngine_impl.h
00002  *
00003  *  Nov 3
00004  *
00005  * author: Yanhua Sun
00006  */
00007 #ifndef __SEARCHENGINE_IMPL_
00008 #define __SEARCHENGINE_IMPL_
00009 
00010 
00011 
00012 #ifdef BRANCHBOUND
00013 #include "searchEngine_bound.decl.h"
00014 #else
00015 #include "searchEngine.decl.h"
00016 #endif
00017 #include "cmipool.h"
00018 
00019 #define SIZEINT  sizeof(size_t)
00020 #define MAXSTACKSIZE 409600
00021 #define NODESINGROUP 50
00022 #define ENTRYTHRESHOLD 100
00023 extern CProxy_SearchConductor searchEngineProxy;
00024 extern CProxy_SearchGroup groupProxy;
00025 extern int se_statesize;
00026 
00027 #ifdef USEBITPRIORITY
00028 inline int __se_log(int n)
00029 {
00030     int _mylog = 0;
00031     for(n=n-1;n>0;n=n>>1)
00032     {
00033         _mylog++;
00034     }
00035     return _mylog;
00036 }
00037 
00038 inline void setMsgPriority(SearchNodeMsg *msg, UShort childbits, unsigned int childnum, UShort newpw, UShort parentBits,unsigned int* parentPtr ){
00039     unsigned int *newPriority = (unsigned int *)(CkPriorityPtr(msg));
00040     UShort prioWords = CkPriobitsToInts(parentBits);
00041     for(int i=0; i<prioWords; i++)
00042     {
00043         newPriority[i] = parentPtr[i];
00044     }
00045 
00046     int shiftbits = 0;
00047     // Two cases 1: with new bits, we do not have to append the number of integers
00048     if(newpw == prioWords)
00049     {
00050         if((childbits+parentBits) % (8*sizeof(unsigned int)) != 0)
00051             shiftbits = 8*sizeof(unsigned int) - (childbits+parentBits)%(8*sizeof(unsigned int));
00052         newPriority[prioWords-1] = parentPtr[prioWords-1] | (childnum << shiftbits);
00053     }else if(newpw>prioWords)
00054     {
00055         /* have to append a new integer */
00056         if(parentBits % (8*sizeof(unsigned int)) == 0)
00057         {
00058             shiftbits = sizeof(unsigned int)*8 - childbits;
00059             newPriority[prioWords] = (childnum << shiftbits);
00060         }else /*higher bits are appended to the last integer and then use anothe new integer */
00061         {
00062             int inusebits = parentBits % ( 8*sizeof(unsigned int));
00063             unsigned int higherbits =  childnum >> (childbits - inusebits);
00064             newPriority[prioWords-1] = parentPtr[prioWords-1] | higherbits;
00065             /* lower bits are stored in new integer */
00066             newPriority[prioWords] = childnum << (8*sizeof(unsigned int) - childbits + inusebits);
00067         }
00068     }
00069 
00070 }
00071  
00072 #endif
00073 
00074 class SearchNodeMsg : public CMessage_SearchNodeMsg
00075 {
00076 public:
00077     
00078     int startDepth, searchDepth;
00079 //    int data_offset;
00080     int top;
00081     int nodes;
00082     char *msgptr;   // pointer to this message, make sure it is pointer aligned 
00083     char *objectDump;
00084 
00085     SearchNodeMsg( int sdepth, int depth, int t, int n):
00086                  startDepth(sdepth), searchDepth(depth), top(t), nodes(n)
00087     {
00088     }
00089 
00090     SearchNodeMsg(){}
00091 };
00092 
00093 
00094 
00095 /****************************************** search engine */
00096 /* for count solutions */
00097 class countMsg : public CMessage_countMsg {
00098 public:
00099   long long count;
00100 #ifdef STATISTIC
00101   int pg, pc, sg, sc;
00102 
00103   countMsg(long long c, int c1, int c2, int c3, int c4) : count(c), pg(c1), pc(c2), sg(c3), sc(c4){};
00104 #endif
00105   countMsg(long long c) : count(c){};
00106 };
00107 
00108 class SearchConductor : public CBase_SearchConductor
00109 {
00110 public: 
00111     double startTime;
00112     
00113     int currentSearchDepth, mySearchLimit;
00114     int groupInitCount;
00115     int solutionFound;
00116     int parallelize_level;
00117     
00118     SearchConductor( CkArgMsg *m );
00119 
00120     void allSearchNodeDone( CkQdMsg *msg );
00121     void start();
00122     void groupInitComplete();
00123     void foundSolution();
00124 
00125     void fire();
00126 
00127 #ifdef USING_CONTROLPOINTS
00128     void controlChange(controlPointMsg* msg);
00129 #endif
00130 };
00131 
00132 class SearchGroup : public Group
00133 {
00134 private:
00135     CkGroupID mygrp;
00136     long long myCount;
00137     long long totalCount;
00138 
00139     double starttimer;
00140 #ifdef BRANCHBOUND
00141     double minCost;
00142 #endif
00143 #ifdef STATISTIC
00144     int parallelnodes_generate;
00145     int parallelnodes_generate_sum;
00146     int parallelnodes_consume;
00147     int parallelnodes_consume_sum;
00148     int sequentialnodes_generate;
00149     int sequentialnodes_generate_sum;
00150     int sequentialnodes_consume;
00151     int sequentialnodes_consume_sum;
00152 #endif
00153     int waitFor;
00154     CthThread threadId;
00155 public:
00156     int parallelize_level;
00157 
00158     SearchGroup(CkMigrateMessage *m) {}
00159     SearchGroup();
00160     
00161     void killSearch();
00162     ~SearchGroup();
00163     double getStartTimer() {return starttimer;} 
00164     void childCount(countMsg *);
00165     void increment() {myCount++;}
00166 #ifdef BRANCHBOUND
00167     double getCost() {return minCost;}
00168     //void  updateCostLocal(double c) { /*CkPrintf("before update best is:%f, new solution:%f\n", minCost, c); */if(c<minCost) minCost = c;}
00169     void  updateCost(double c);
00170 #endif
00171 #ifdef STATISTIC
00172     void inc_parallel_generate() {parallelnodes_generate++;}
00173     void inc_parallel_consume() {parallelnodes_consume++;}
00174 
00175     void inc_sequential_generate() {sequentialnodes_generate++;}
00176     void decrease_sequential_generate() {sequentialnodes_generate--;}
00177     void inc_sequential_consume() {sequentialnodes_consume++;}
00178 
00179     int printfStatistic()
00180     {
00181         CkPrintf(" Search Engine Statistic Information:\nParallel nodes produced:%d, processed:%d\n sequential nodes produced:%d, processed:%d\n", parallelnodes_generate_sum, parallelnodes_consume_sum, sequentialnodes_generate_sum, sequentialnodes_consume_sum);
00182     }
00183 #endif
00184     void sendCounts();
00185     long long  getTotalSolutions();
00186     
00187     void init();
00188     inline void setParallelLevel( int level ) { parallelize_level = level;}
00189     inline void searchDepthChange( int depth);
00190     
00191     inline int getParallelLevel() {return parallelize_level;}
00192 
00193 };
00194 
00195 class SearchNode : public CBase_SearchNode
00196 {
00197 public:
00198     int myStartDepth;
00199     int mySearchDepth;
00200 
00201     SearchGroup *myGroup;
00202     StateBase *mySearchClass;
00203     
00204     SearchNode( CkMigrateMessage *m );
00205     SearchNode( SearchNodeMsg *msg );
00206     ~SearchNode();
00207     
00208 };
00209 
00210 /**************************** parallel and sequential solver */
00211 
00212 inline void Solver::reportSolution()
00213 {
00214 #ifdef ONESOLUTION
00215     double startime = groupProxy.ckLocalBranch()->getStartTimer();
00216     CkPrintf("First solution found within time %f second\n", CkWallTimer()-startime);
00217     groupProxy.ckLocalBranch()->increment();
00218     groupProxy.killSearch();
00219     CkExit();
00220 #else
00221     groupProxy.ckLocalBranch()->increment();
00222 #endif
00223  
00224 }
00225 
00226 #ifdef BRANCHBOUND
00227 inline void Solver::updateCost(double c)
00228 {
00229     //CkPrintf("updating best solution:%.4f\n", c);
00230     groupProxy.updateCost(c);
00231 }
00232 #endif
00233 
00234 class ParallelSolver: public Solver {
00235 public:
00236     inline void setParentInfo(SearchNodeMsg *msg, int l)
00237     {
00238 #if defined(USEBITPRIORITY) || defined(USEINTPRIORITY)
00239         parentBits = UsrToEnv(msg)->getPriobits();
00240         parentPtr = (unsigned int *)(CkPriorityPtr(msg));
00241 #endif
00242         searchLevel = l+1;
00243     }
00244 
00245     inline void setPriority(StateBase *s, int p)
00246     {
00247         SearchNodeMsg *msg = *(SearchNodeMsg**)((char*)s - 2*sizeof(void*));
00248 #ifdef USEINTPRIORITY
00249         CkSetQueueing(msg, CK_QUEUEING_ILIFO);
00250         *(int*)CkPriorityPtr(msg) = p;
00251 #endif
00252     }
00253 
00254     inline StateBase *registerRootState(size_t size, unsigned int childnum, unsigned int totalNumChildren)
00255     {
00256 #ifdef STATISTIC
00257         groupProxy.ckLocalBranch()->inc_parallel_generate();     
00258 #endif
00259 
00260 #ifdef USEBITPRIORITY
00261         UShort rootBits = __se_log(totalNumChildren)+1;
00262         SearchNodeMsg *msg = new (size, rootBits) SearchNodeMsg(0, 0, size, 1);
00263         unsigned int *pbits = (unsigned int *)CkPriorityPtr(msg);
00264         *pbits = childnum << (SIZEINT*8 - rootBits);;
00265         CkSetQueueing(msg, CK_QUEUEING_BLIFO);
00266 #elif USEINTPRIORITY
00267         SearchNodeMsg *msg = new (size , 8*sizeof(int)) SearchNodeMsg(0, 0, size, 1);
00268         CkSetQueueing(msg, CK_QUEUEING_ILIFO);
00269         *(int*)CkPriorityPtr(msg) = childnum;
00270 #else
00271         SearchNodeMsg *msg = new (size , 0) SearchNodeMsg(0,0, size, 1);
00272 #endif
00273         msg->searchDepth =  0;
00274         msg->msgptr = (char*)msg;
00275         return (StateBase *) (msg->objectDump);
00276 
00277     }
00278 
00279     inline StateBase *registerState(size_t size, unsigned int childnum, unsigned int totalNumChildren) 
00280     {
00281 
00282 #ifdef STATISTIC
00283         groupProxy.ckLocalBranch()->inc_parallel_generate();     
00284 #endif
00285 #ifdef USEBITPRIORITY
00286         UShort extraBits = __se_log(totalNumChildren);
00287         CkAssert(extraBits <= CkIntbits);
00288         UShort newpbsize = extraBits + parentBits;
00289         SearchNodeMsg *msg = new (size, newpbsize) SearchNodeMsg(0, searchLevel, size, 1);
00290         CkSetQueueing(msg, CK_QUEUEING_BLIFO);
00291         setMsgPriority(msg, extraBits, childnum, CkPriobitsToInts(newpbsize), parentBits, parentPtr );
00292 #elif USEINTPRIORITY
00293         SearchNodeMsg *msg = new (size , 8*sizeof(int)) SearchNodeMsg(0, searchLevel, size, 1);
00294         CkSetQueueing(msg, CK_QUEUEING_ILIFO);
00295         *(int*)CkPriorityPtr(msg) = childnum;
00296 #else
00297         SearchNodeMsg *msg = new (size , 0) SearchNodeMsg(0, searchLevel, size, 1);
00298 #endif
00299         msg->msgptr = (char*)msg;
00300         return (StateBase *) (msg->objectDump);
00301     }
00302 
00303     inline void deleteState(StateBase* s)
00304     {
00305         //SearchNodeMsg *msg = *(SearchNodeMsg**)((char*)s - 2*sizeof(void*));
00306         SearchNodeMsg *msg = *((SearchNodeMsg**)s - 2);
00307         delete msg;
00308     }
00309 
00310     /* recover the message from the state */
00311     inline void process(StateBase* s)
00312     {
00313         //SearchNodeMsg *msg = *(SearchNodeMsg**)((char*)s - 2*sizeof(void*));
00314 #ifdef BRANCHBOUND
00315         if(_lowerBoundFn(s) >= groupProxy.ckLocalBranch()->getCost())
00316         {
00317             deleteState(s);
00318             return;
00319         }
00320 #endif
00321         SearchNodeMsg *msg = *((SearchNodeMsg**)s - 2);
00322         CProxy_SearchNode::ckNew(msg, NULL, -1);
00323 #ifdef STATISTIC
00324         groupProxy.ckLocalBranch()->inc_parallel_generate();     
00325 #endif
00326     }
00327 };
00328 
00329 #ifdef USE_CMIPOOL
00330 #define mymalloc  CmiPoolAlloc
00331 #define myfree    CmiPoolFree
00332 #else
00333 #define mymalloc  malloc
00334 #define myfree    free
00335 #endif
00336 
00337 #ifdef SE_FIXED_STATE
00338 class StateStack {
00339    char* mystack;
00340    char* cur;
00341    int maxsize;
00342    bool msgstack;
00343 
00344    void expand(int size) {
00345        while(cur - mystack + size >maxsize)
00346            maxsize *= 2;
00347        //CkPrintf("maxsize=%d, top=%d, top=%d\n", maxsize, cursize() + size + SIZEINT,  cursize());
00348        char* newstack = (char*)mymalloc(maxsize);
00349        memcpy(newstack, mystack, cursize());
00350        cur = newstack + cursize();
00351        free_stack();
00352        if(msgstack) msgstack = false;
00353        mystack = newstack;
00354    }
00355 public:
00356    StateStack(): mystack(NULL), cur(NULL), maxsize(0), msgstack(false) {}
00357    ~StateStack(){
00358        free_stack();
00359    }                        
00360    inline void set(int size) {
00361        maxsize = size;
00362        mystack = cur = (char*)mymalloc(maxsize);
00363    }
00364    inline void set(SearchNodeMsg *m) {
00365        mystack = m->objectDump;
00366        cur = mystack + m->top;
00367        maxsize = m->top;    // ?
00368        msgstack = true;
00369    }
00370    inline void freeMsg() {
00371        SearchNodeMsg *msg = *((SearchNodeMsg**)mystack - 2);
00372        delete msg;
00373    }
00374    inline void free_stack() {
00375        if(!msgstack) myfree(mystack);
00376    }
00377    inline int empty() const {  return cur == mystack; }
00378    inline char *top() const { return cur; }
00379    inline int cursize() const { return cur - mystack; }
00380    inline void clear() { cur = mystack; }
00381    inline char* push(int size)
00382    {
00383        if(cursize() + size >maxsize) expand(size);
00384        char * const oldcur = cur;
00385        cur += size;
00386        return oldcur;
00387    }
00388    inline StateBase *pop(){
00389         if(empty()) return NULL;
00390         cur -= se_statesize;
00391         return (StateBase*)cur;
00392     }
00393     inline int popN(int n) {
00394         int i;
00395         for( i=0; !empty() && i<n; i++)
00396         {
00397             cur -= se_statesize;
00398         }
00399         return i;
00400     }
00401 };
00402 #else
00403 class StateStack {
00404    char* mystack;
00405    char* cur;
00406    int maxsize;
00407    bool msgstack;
00408 
00409    void expand(int size) {
00410        while(cur - mystack + size + SIZEINT >maxsize)
00411            maxsize *= 2;
00412        //CkPrintf("State stack expand: maxsize=%d, top=%d, top=%d\n", maxsize, cursize() + size + SIZEINT,  cursize());
00413        char* newstack = (char*)mymalloc(maxsize);
00414        memcpy(newstack, mystack, cursize());
00415        cur = newstack + cursize();
00416        free_stack();
00417        if(msgstack) msgstack = false;
00418        mystack = newstack;
00419        //CkPrintf("maxsize=%d, top=%d, stack=%p %p\n", maxsize, cursize() + size + SIZEINT,  mystack, cur);
00420    }
00421 public:
00422    StateStack(): mystack(NULL), cur(NULL), maxsize(0), msgstack(false) {}
00423    ~StateStack(){
00424        free_stack();
00425     }                        
00426    inline void set(int size) {
00427      maxsize = size;
00428      mystack = cur = (char*)mymalloc(maxsize);
00429    }
00430    inline void set(SearchNodeMsg *m) {
00431      mystack = m->objectDump;
00432      cur = mystack + m->top;
00433      maxsize = m->top;    // ?
00434      msgstack = true;
00435    }
00436    inline void freeMsg() {
00437         SearchNodeMsg *msg = *((SearchNodeMsg**)mystack - 2);
00438         delete msg;
00439    }
00440    inline void free_stack() {
00441        if(!msgstack) myfree(mystack);
00442    }
00443    inline char* push(int size)
00444    {
00445         if(cursize() + size + SIZEINT >maxsize) expand(size);
00446         char * const oldcur = cur;
00447         *((size_t*)(cur+size)) = size;
00448         cur += (size + SIZEINT);
00449         return oldcur;
00450    }
00451    inline StateBase *pop(){
00452         if(empty()) return NULL;
00453         const size_t size = *((size_t*)(cur-SIZEINT));
00454         cur -= (SIZEINT + size);
00455         return (StateBase*)cur;
00456     }
00457     inline int popN(int n) {
00458         int i=0;
00459         for(i=0 ; !empty() && i<n; i++)
00460             {
00461                 size_t size = *((size_t*)(cur-SIZEINT));
00462                 cur -= (SIZEINT + size);
00463             }
00464          return i;
00465     }
00466     inline int empty() const {  return cur == mystack; }
00467     inline char *top() const { return cur; }
00468     inline int cursize() const { return cur - mystack; }
00469     inline void clear() { cur = mystack; }
00470 };
00471 #endif
00472 
00473 class SequentialSolver : public Solver { 
00474 
00475 private:
00476     int nodenum;
00477     StateStack stack;
00478 public:                                                            
00479     SequentialSolver() {}
00480     ~SequentialSolver() {}                        
00481     inline void initialize()
00482     {
00483         stack.set(MAXSTACKSIZE);
00484         nodenum = 0;
00485     }
00486 
00487     inline void initialize(SearchNodeMsg *m)
00488     {
00489         stack.set(m);
00490         nodenum = m->nodes;
00491     }
00492     
00493     inline StateBase *dequeue(){
00494         StateBase *state = stack.pop();
00495         if (state != NULL)  {
00496           nodenum--;
00497 #ifdef STATISTIC
00498           groupProxy.ckLocalBranch()->inc_sequential_consume();     
00499 #endif
00500         }
00501         return state;
00502     }
00503     
00504     inline void dequeue_multiple(double avgentrytime, int maxexecnodes)
00505     {
00506         int num_dequeued = 0;
00507         maxexecnodes = 1;
00508         int groups = nodenum/maxexecnodes;
00509         if(nodenum % maxexecnodes> 0)
00510             groups ++;
00511 #ifdef USEBITPRIORITY
00512         UShort extraBits = __se_log(groups);
00513 #endif        
00514         int groupIndex = 0;
00515         //CkPrintf("Fine grain decomposition\n");
00516         while(!stack.empty())
00517         {
00518             /* top ---------- top_top is a chunk */
00519             const char *old_top = stack.top();
00520             int c = stack.popN(maxexecnodes);
00521             const char *currenttop = stack.top(); 
00522             const int chunk_size = old_top - currenttop;
00523             //CkPrintf("[%d]fire new tasks with %d  nodes, chunksize=%d, old_top=%p, new top=%p\n", groupIndex, c, chunk_size, old_top, currenttop);
00524 #ifdef USEBITPRIORITY
00525             UShort newpbsize = extraBits + parentBits;
00526             SearchNodeMsg *msg = new (chunk_size, newpbsize)SearchNodeMsg(0, searchLevel, chunk_size, c);
00527             CkSetQueueing(msg, CK_QUEUEING_BLIFO);
00528             setMsgPriority(msg, extraBits, groupIndex, CkPriobitsToInts(newpbsize), parentBits, parentPtr);
00529 #elif USEINTPRIORITY
00530             SearchNodeMsg *msg = new (chunk_size, 8*sizeof(int)) SearchNodeMsg(0, searchLevel, chunk_size, c);
00531             CkSetQueueing(msg, CK_QUEUEING_ILIFO);
00532             *(int*)CkPriorityPtr(msg) = *parentPtr;
00533 #else
00534             SearchNodeMsg *msg = new (chunk_size, 0)SearchNodeMsg(0, searchLevel, chunk_size, c);
00535 #endif
00536             memcpy(msg->objectDump, stack.top(), chunk_size);
00537             nodenum-=c; 
00538             CProxy_SearchNode::ckNew(msg, NULL, -1);
00539             groupIndex++;
00540         }
00541     }
00542 
00543     inline void setParentInfo(SearchNodeMsg *msg, int l)
00544     {
00545 #if defined(USEBITPRIORITY) || defined(USEINTPRIORITY)
00546         parentBits = UsrToEnv(msg)->getPriobits();
00547         parentPtr = (unsigned int *)(CkPriorityPtr(msg));
00548 #endif
00549         searchLevel = l+1;
00550  
00551     }
00552 
00553     inline void setPriority(StateBase *s, int p){}
00554 
00555     inline StateBase *registerRootState(size_t size, unsigned int childnum, unsigned int totalNumChildren)
00556     {
00557 #ifdef STATISTIC
00558         groupProxy.ckLocalBranch()->inc_sequential_generate();     
00559 #endif
00560         nodenum++;
00561         return (StateBase*)stack.push(size);
00562     }
00563 
00564     inline StateBase *registerState(size_t size, unsigned int childnum, unsigned int totalNumChildren)
00565     {
00566 #ifdef STATISTIC
00567         groupProxy.ckLocalBranch()->inc_sequential_generate();     
00568 #endif
00569         nodenum++;
00570         return (StateBase *)stack.push(size);
00571     }
00572 
00573        /* pop up the top one since it is always a stack */
00574     inline void deleteState(StateBase* s)
00575     {
00576         StateBase *state = stack.pop();
00577         if (state) {
00578           nodenum--;
00579 #ifdef STATISTIC
00580           if (state)
00581             groupProxy.ckLocalBranch()->decrease_sequential_generate();
00582 #endif
00583         }
00584     }
00585     inline void process(StateBase *s)
00586     {
00587 #ifdef BRANCHBOUND
00588         if(_lowerBoundFn(s) >= groupProxy.ckLocalBranch()->getCost())
00589             deleteState(s);
00590         // sort again 
00591 #endif
00592     }
00593 
00594     inline void reportSolution()
00595     {
00596         Solver::reportSolution();
00597 #ifdef ONESOLUTION
00598         stack.clear();
00599 #endif
00600     }
00601 
00602 };
00603 #endif
libs/ck-libs/state_space_searchengine/searchEngine_impl.h
