Charm++: Charm Source Code Documentation

00001 /* searchEngine.C
00002  *
00003  *  Nov 3
00004  *
00005  * author: Yanhua Sun
00006  */
00007 #include <vector>
00008 #include <stack>
00009 #include <deque>
00010 
00011 using namespace std;
00012 
00013 #ifdef USING_CONTROLPOINTS
00014 #include <controlPoints.h>
00015 #endif
00016 
00017 #include "searchEngine.h"
00018 
00019 static SE_createInitialChildrenFn createInitialChildren = NULL;
00020 static SE_createChildrenFn createChildren = NULL;
00021 static SE_parallelLevelFn     parallelLevel = NULL;
00022 static SE_searchDepthLimitFn   searchDepthLimit = NULL;
00023 SE_lowerBoundFn   _lowerBoundFn = NULL;
00024 
00025 //#include "searchEngine_impl.h"
00026 
00027 void printPriority(SearchNodeMsg *pm){
00028 #if defined(USEBITPRIORITY) || defined(USEINTPRIORITY)
00029     UShort pw = UsrToEnv(pm)->getPrioWords();
00030     unsigned int *pr = (unsigned int *)(CkPriorityPtr(pm));
00031     CkPrintf("PE:%d ", CkMyPe());
00032     for(int i = 0; i < pw; i++){
00033         CkPrintf("[%d] 0x%x  ", i, pr[i]);
00034     }
00035     CkPrintf("\n");
00036 #endif
00037 }
00038 
00039 
00040 
00041 #ifdef USING_CONTROLPOINTS
00042 CProxy_BThreshold threshGroup;
00043 
00044 int cp_grainsize;
00045 int THRESH_MAX;
00046 int THRESH_MIN;
00047 void SearchConductor::controlChange(controlPointMsg* msg) {
00048     controlPointTimingStamp();
00049     cp_grainsize = controlPoint("grainsize", THRESH_MIN, THRESH_MAX);
00050 
00051     ThreshMsg *msg1 = new ThreshMsg(cp_grainsize);
00052     threshGroup.changeThreshold(msg1);
00053 }
00054 class BThreshold : public CBase_BThreshold {
00055 public:
00056     BThreshold() {}
00057 
00058     void changeThreshold(ThreshMsg *msg) {
00059         cp_grainsize = msg->threshold;
00060     }
00061 };
00062 
00063 #endif
00064 
00065 
00066 int se_statesize;     // readonly
00067 CProxy_SearchConductor searchEngineProxy;
00068 CProxy_SearchGroup groupProxy;
00069 
00070 
00071 /****************************** search conductor  main chare */
00072 SearchConductor::SearchConductor( CkArgMsg *m )
00073 {
00074     searchEngineProxy = thisProxy;
00075     
00076     groupProxy = CProxy_SearchGroup::ckNew();
00077 }
00078 void SearchConductor::start()
00079 {
00080 
00081     groupInitCount = 0;
00082     groupProxy.init();
00083 }
00084 
00085 void SearchConductor::groupInitComplete()
00086 {
00087     groupInitCount ++;
00088     if( groupInitCount == CkNumPes() )
00089     {
00090 #ifdef USING_CONTROLPOINTS
00091         ControlPoint::EffectIncrease::Concurrency("grainsize");
00092         cp_grainsize = controlPoint("grainsize", THRESH_MIN, THRESH_MAX);
00093         threshGroup = CProxy_BThreshold::ckNew();
00094         CkCallback cb(CkIndex_SearchConductor::controlChange(NULL), searchEngineProxy);
00095         registerCPChangeCallback(cb, true);
00096 #endif
00097  
00098         groupInitCount = 0;
00099         fire();
00100     }
00101 }
00102 
00103 void SearchConductor::fire()
00104 {
00105     
00106     int myStartDepth = 0;
00107     int mySearchDepth = 3;
00108     currentSearchDepth = 1;
00109     startTime = CkWallTimer();
00110   
00111     ParallelSolver parSolver;
00112     createInitialChildren(&parSolver);
00113 
00114     //set the QD call back function
00115     CkStartQD(CkIndex_SearchConductor::allSearchNodeDone((CkQdMsg *)0), &thishandle);
00116 }
00117 
00118 //QD call back function, it means all the searching is complete in current search depth
00119 void SearchConductor::allSearchNodeDone( CkQdMsg *msg )
00120 {
00121 
00122     long long numSolutions = groupProxy.ckLocalBranch()->getTotalSolutions();
00123     CkPrintf("All states are done in %lf sec \n",  CkWallTimer()-startTime);
00124 #ifdef STATISTIC
00125     groupProxy.ckLocalBranch()->printfStatistic();
00126 #endif
00127 
00128 #ifdef BRANCHBOUND
00129     CkPrintf("Best solution is:%.4f\n Time cost:%lf on %d processors",groupProxy.ckLocalBranch()->getCost(), CkWallTimer()-startTime, CkNumPes());
00130     CkExit();
00131 #endif
00132     if( numSolutions > 0 )
00133     {
00134         CkPrintf( "%lld solutions are found in %lf sec, with %d processors\n", numSolutions, CkWallTimer()-startTime, CkNumPes() ); 
00135         CkExit(); 
00136     }
00137     else
00138     {
00139         currentSearchDepth ++;
00140         if( currentSearchDepth > searchDepthLimit() )
00141         {
00142             CkExit();
00143             return;
00144         }
00145         groupProxy.searchDepthChange( currentSearchDepth );
00146         
00147         //recreate the initail state, because the initial state may change as the search depth change
00148         ParallelSolver parSolver;
00149         createInitialChildren(&parSolver);
00150 
00151         //set the QD call back function
00152         CkStartQD(CkIndex_SearchConductor::allSearchNodeDone((CkQdMsg *)0), &thishandle);
00153         //delete parSolver;
00154     }
00155 
00156     delete msg; 
00157 }
00158 
00159 void SearchConductor::foundSolution()
00160 {
00161     CkPrintf( "One solution is found in %lf sec, with %d processors\n",  CkWallTimer()-startTime, CkNumPes() ); 
00162     CkExit(); 
00163 }
00164 
00165 
00166 /***************************************** Search Group   ***********************/
00167 
00168 /* used to count the total number of solutions if all solutions are set */
00169 SearchGroup::SearchGroup()
00170 { 
00171     // initialize the local count;
00172     mygrp = thisgroup;
00173     myCount = totalCount = 0;
00174 #ifdef STATISTIC
00175     parallelnodes_generate = 0;
00176     parallelnodes_generate_sum = 0;
00177     parallelnodes_consume = 0;
00178     parallelnodes_consume_sum = 0;
00179     sequentialnodes_generate = 0;
00180     sequentialnodes_generate_sum = 0;
00181     sequentialnodes_consume = 0;
00182     sequentialnodes_consume_sum = 0;
00183 #endif
00184     waitFor = CkNumPes(); // wait for all processors to report
00185     threadId = NULL;
00186 
00187 #ifdef BRANCHBOUND
00188     minCost = 1000000;
00189 #endif
00190 }
00191 #ifdef BRANCHBOUND
00192 inline void SearchGroup::updateCost(double c)
00193 {
00194     if(c<minCost) 
00195     {
00196         minCost = c;
00197     //   CkPrintf("min cost =%f\n", c);
00198     //    void **copyqueue;
00199     //    CqsEnumerateQueue((Queue)CpvAccess(CsdSchedQueue), &copyqueue);
00200     //    for(int i=0; i<CqsLength((Queue)CpvAccess(CsdSchedQueue)); i++)
00201     //    {
00202     //        void* msgchare = copyqueue[i];
00203     //        int prior = *(int*)CkPriorityPtr(msgchare);
00204     //        if(prior > minCost)
00205     //        {
00206     //              CqsRemoveSpecific((Queue)CpvAccess(CsdSchedQueue), msgchare);
00207     //              CkPrintf("node is removed, prior=%d, mincost=%f\n", prior, minCost);
00208     //        }
00209     //    }
00210     //    //CmiFree(copyqueue);
00211     }
00212 }
00213 #endif
00214 // This method is invoked via a broadcast. Each branch then reports 
00215 //  its count to the branch on 0 (or via a spanning tree.)
00216 inline void SearchGroup::sendCounts()
00217 {
00218     CProxy_SearchGroup grp(mygrp);
00219 #ifdef STATISTIC
00220     grp[0].childCount(new countMsg(myCount, parallelnodes_generate, parallelnodes_consume, sequentialnodes_generate, sequentialnodes_consume));
00221 #else
00222     grp[0].childCount(new countMsg(myCount));
00223 #endif
00224 }
00225 
00226 inline void SearchGroup::childCount(countMsg *m)
00227 {
00228     totalCount += m->count;
00229 #ifdef STATISTIC
00230     parallelnodes_generate_sum  += m->pg;
00231     parallelnodes_consume_sum += m->pc;
00232     sequentialnodes_generate_sum += m->sg;
00233     sequentialnodes_consume_sum += m->sc;
00234 #endif
00235     waitFor--;
00236     if (waitFor == 0) 
00237         if (threadId) { CthAwaken(threadId);}
00238     delete m;
00239 }
00240 
00241 long long  SearchGroup::getTotalSolutions() {
00242     CProxy_SearchGroup grp(mygrp);
00243     grp.sendCounts();//this is a broadcast, as no processor is mentioned
00244     threadId = CthSelf();
00245     while (waitFor != 0)  CthSuspend();
00246     return totalCount;
00247 }
00248 
00249 SearchGroup::~SearchGroup()
00250 {
00251 }
00252 
00253 void SearchGroup::init()
00254 {
00255     //get the factory from the user space
00258     parallelize_level = parallelLevel();
00259 
00260 #ifdef USING_CONTROLPOINTS
00261     THRESH_MIN = myCore->minimumLevel();
00262     THRESH_MAX = myCore->maximumLevel();
00263 #endif
00264     //tell the mainchare that this branch is finished
00265     starttimer = CkWallTimer();
00266     searchEngineProxy.groupInitComplete();  
00267 }
00268 
00269 
00270 void SearchGroup::searchDepthChange( int depth) { /*searchDepthChangeNotify( depth );*/ }
00271 
00272 void SearchGroup::killSearch()
00273 {
00274 #ifdef STATISTIC
00275     groupProxy.ckLocalBranch()->printfStatistic();
00276 #endif
00277     CkExit();
00278 }
00279 //implementation of SearchNode
00280 SearchNode::SearchNode( CkMigrateMessage *m ){}
00281 
00282 SearchNode::~SearchNode() {}
00283 
00284 #ifdef BRANCHBOUND
00285 extern void createMultipleChildren(SearchGroup *s, StateBase *parent, SequentialSolver* solver, bool parallel);
00286 #else
00287 extern void createMultipleChildren(StateBase *parent, SequentialSolver* solver, bool parallel);
00288 #endif
00289 
00290 SearchNode::SearchNode( SearchNodeMsg *msg )
00291 {
00292 
00293 #ifdef STATISTIC
00294     groupProxy.ckLocalBranch()->inc_parallel_consume();     
00295 #endif
00296     myGroup = groupProxy.ckLocalBranch();
00297     mySearchClass = (StateBase*) (msg->objectDump);
00298 
00299     myStartDepth = msg->startDepth;
00300     mySearchDepth = msg->searchDepth;
00301 
00302     if( mySearchDepth < myGroup->getParallelLevel() ){
00303         ParallelSolver solver;
00304 #ifdef DEBUG
00305        CkPrintf("mySearchDepth: %d\n", mySearchDepth);
00306        printPriority(msg);
00307 #endif
00308         solver.setParentInfo(msg, mySearchDepth);
00309 #ifdef BRANCHBOUND
00310         double minCost = myGroup->getCost();
00311         double lb = _lowerBoundFn(mySearchClass);
00312         //CkPrintf("best solution is %f\n", minCost);
00313         if(lb<minCost)
00314             createChildren(mySearchClass, &solver, true);
00315         else
00316             CkPrintf("Node is pruned with lower bound:%f, best solution:%f\n", lb, minCost); 
00317 #else
00318         createChildren(mySearchClass, &solver, true);
00319 #endif
00320     }
00321     else
00322     {
00323         SequentialSolver solver;
00324         solver.setParentInfo(msg, mySearchDepth);
00325         StateBase *parent=NULL;// = mySearchClass;
00326         int processed_nodes = 0;
00327         if(msg->nodes == 1){
00328             solver.initialize();
00329             parent = mySearchClass;
00330         }
00331         else if(msg->nodes > 1){
00332             solver.initialize(msg);
00333             parent = solver.dequeue();
00334         }
00335 #ifdef BRANCHBOUND
00336         createMultipleChildren(myGroup, parent, &solver, false);
00337 #else
00338         createMultipleChildren(parent, &solver, false);
00339 #endif
00340     }
00341     delete msg;
00342     delete this;
00343 }
00344 
00345 /* called in initproc */
00346 void SE_register(SE_createInitialChildrenFn f1,
00347                  SE_createChildrenFn f2,
00348                  SE_parallelLevelFn f3,
00349                  SE_searchDepthLimitFn f4,
00350                  SE_lowerBoundFn f5
00351                  )
00352 {
00353   createInitialChildren = f1;
00354   createChildren = f2;
00355   parallelLevel = f3;
00356   searchDepthLimit = f4;
00357   _lowerBoundFn = f5;
00358 
00359   CmiPoolAllocInit(30);
00360 }
00361 
00362 
00363 #ifdef BRANCHBOUND
00364 #include "searchEngine_bound.def.h"
00365 #else
00366 #include "searchEngine.def.h"
00367 #endif
libs/ck-libs/state_space_searchengine/searchEngine.C
