TSP problem fixed
[charm.git] / examples / charm++ / state_space_searchengine / searchengineLib / searchEngine.C
1 /* searchEngine.C
2  *
3  *  Nov 3
4  *
5  * author: Yanhua Sun
6  */
7 #include <vector>
8 #include <stack>
9 #include <deque>
10
11 using namespace std;
12
13 #ifdef USING_CONTROLPOINTS
14 #include <controlPoints.h>
15 #endif
16
17 #include "searchEngine.h"
18
19 static SE_createInitialChildrenFn createInitialChildren = NULL;
20 static SE_createChildrenFn createChildren = NULL;
21 static SE_parallelLevelFn     parallelLevel = NULL;
22 static SE_searchDepthLimitFn   searchDepthLimit = NULL;
23 SE_lowerBoundFn   _lowerBoundFn = NULL;
24
25 //#include "searchEngine_impl.h"
26
27 void printPriority(SearchNodeMsg *pm){
28 #if defined(USEBITPRIORITY) || defined(USEINTPRIORITY)
29     UShort pw = UsrToEnv(pm)->getPrioWords();
30     unsigned int *pr = (unsigned int *)(CkPriorityPtr(pm));
31     CkPrintf("PE:%d ", CkMyPe());
32     for(int i = 0; i < pw; i++){
33         CkPrintf("[%d] 0x%x  ", i, pr[i]);
34     }
35     CkPrintf("\n");
36 #endif
37 }
38
39
40
41 #ifdef USING_CONTROLPOINTS
42 CProxy_BThreshold threshGroup;
43
44 int cp_grainsize;
45 int THRESH_MAX;
46 int THRESH_MIN;
47 void SearchConductor::controlChange(controlPointMsg* msg) {
48     controlPointTimingStamp();
49     cp_grainsize = controlPoint("grainsize", THRESH_MIN, THRESH_MAX);
50
51     ThreshMsg *msg1 = new ThreshMsg(cp_grainsize);
52     threshGroup.changeThreshold(msg1);
53 }
54 class BThreshold : public CBase_BThreshold {
55 public:
56     BThreshold() {}
57
58     void changeThreshold(ThreshMsg *msg) {
59         cp_grainsize = msg->threshold;
60     }
61 };
62
63 #endif
64
65
66 int se_statesize;     // readonly
67 CProxy_SearchConductor searchEngineProxy;
68 CProxy_SearchGroup groupProxy;
69
70
71 /****************************** search conductor  main chare */
72 SearchConductor::SearchConductor( CkArgMsg *m )
73 {
74         searchEngineProxy = thisProxy;
75         
76         groupProxy = CProxy_SearchGroup::ckNew();
77 }
78 void SearchConductor::start()
79 {
80
81     groupInitCount = 0;
82     groupProxy.init();
83 }
84
85 void SearchConductor::groupInitComplete()
86 {
87         groupInitCount ++;
88         if( groupInitCount == CkNumPes() )
89         {
90 #ifdef USING_CONTROLPOINTS
91         ControlPoint::EffectIncrease::Concurrency("grainsize");
92         cp_grainsize = controlPoint("grainsize", THRESH_MIN, THRESH_MAX);
93         threshGroup = CProxy_BThreshold::ckNew();
94         CkCallback cb(CkIndex_SearchConductor::controlChange(NULL), searchEngineProxy);
95         registerCPChangeCallback(cb, true);
96 #endif
97  
98         groupInitCount = 0;
99                 fire();
100         }
101 }
102
103 void SearchConductor::fire()
104 {
105         
106     int myStartDepth = 0;
107     int mySearchDepth = 3;
108         currentSearchDepth = 1;
109         startTime = CkWallTimer();
110   
111     ParallelSolver parSolver;
112     createInitialChildren(&parSolver);
113
114     //set the QD call back function
115     CkStartQD(CkIndex_SearchConductor::allSearchNodeDone((CkQdMsg *)0), &thishandle);
116 }
117
118 //QD call back function, it means all the searching is complete in current search depth
119 void SearchConductor::allSearchNodeDone( CkQdMsg *msg )
120 {
121
122     long long numSolutions = groupProxy.ckLocalBranch()->getTotalSolutions();
123     CkPrintf("All states are done in %lf sec \n",  CkWallTimer()-startTime);
124 #ifdef STATISTIC
125     groupProxy.ckLocalBranch()->printfStatistic();
126 #endif
127
128 #ifdef BRANCHBOUND
129     CkPrintf("Best solution is:%.4f\n Time cost:%lf on %d processors",groupProxy.ckLocalBranch()->getCost(), CkWallTimer()-startTime, CkNumPes());
130     CkExit();
131 #endif
132     if( numSolutions > 0 )
133     {
134         CkPrintf( "%lld solutions are found in %lf sec, with %d processors\n", numSolutions, CkWallTimer()-startTime, CkNumPes() );     
135         CkExit(); 
136     }
137     else
138     {
139         currentSearchDepth ++;
140         if( currentSearchDepth > searchDepthLimit() )
141         {
142             CkExit();
143             return;
144         }
145         groupProxy.searchDepthChange( currentSearchDepth );
146                 
147         //recreate the initail state, because the initial state may change as the search depth change
148         ParallelSolver parSolver;
149         createInitialChildren(&parSolver);
150
151         //set the QD call back function
152         CkStartQD(CkIndex_SearchConductor::allSearchNodeDone((CkQdMsg *)0), &thishandle);
153         //delete parSolver;
154     }
155
156     delete msg; 
157 }
158
159 void SearchConductor::foundSolution()
160 {
161     CkPrintf( "One solution is found in %lf sec, with %d processors\n",  CkWallTimer()-startTime, CkNumPes() ); 
162     CkExit(); 
163 }
164
165
166 /***************************************** Search Group   ***********************/
167
168 /* used to count the total number of solutions if all solutions are set */
169 SearchGroup::SearchGroup()
170
171     // initialize the local count;
172     mygrp = thisgroup;
173     myCount = totalCount = 0;
174 #ifdef STATISTIC
175     parallelnodes_generate = 0;
176     parallelnodes_generate_sum = 0;
177     parallelnodes_consume = 0;
178     parallelnodes_consume_sum = 0;
179     sequentialnodes_generate = 0;
180     sequentialnodes_generate_sum = 0;
181     sequentialnodes_consume = 0;
182     sequentialnodes_consume_sum = 0;
183 #endif
184     waitFor = CkNumPes(); // wait for all processors to report
185     threadId = NULL;
186
187 #ifdef BRANCHBOUND
188     minCost = 1000000;
189 #endif
190 }
191 #ifdef BRANCHBOUND
192 inline void SearchGroup::updateCost(double c)
193 {
194     if(c<minCost) 
195     {
196         minCost = c;
197     //   CkPrintf("min cost =%f\n", c);
198     //    void **copyqueue;
199     //    CqsEnumerateQueue((Queue)CpvAccess(CsdSchedQueue), &copyqueue);
200     //    for(int i=0; i<CqsLength((Queue)CpvAccess(CsdSchedQueue)); i++)
201     //    {
202     //        void* msgchare = copyqueue[i];
203     //        int prior = *(int*)CkPriorityPtr(msgchare);
204     //        if(prior > minCost)
205     //        {
206     //              CqsRemoveSpecific((Queue)CpvAccess(CsdSchedQueue), msgchare);
207     //              CkPrintf("node is removed, prior=%d, mincost=%f\n", prior, minCost);
208     //        }
209     //    }
210     //    //CmiFree(copyqueue);
211     }
212 }
213 #endif
214 // This method is invoked via a broadcast. Each branch then reports 
215 //  its count to the branch on 0 (or via a spanning tree.)
216 inline void SearchGroup::sendCounts()
217 {
218     CProxy_SearchGroup grp(mygrp);
219 #ifdef STATISTIC
220     grp[0].childCount(new countMsg(myCount, parallelnodes_generate, parallelnodes_consume, sequentialnodes_generate, sequentialnodes_consume));
221 #else
222     grp[0].childCount(new countMsg(myCount));
223 #endif
224 }
225
226 inline void SearchGroup::childCount(countMsg *m)
227 {
228     totalCount += m->count;
229 #ifdef STATISTIC
230     parallelnodes_generate_sum  += m->pg;
231     parallelnodes_consume_sum += m->pc;
232     sequentialnodes_generate_sum += m->sg;
233     sequentialnodes_consume_sum += m->sc;
234 #endif
235     waitFor--;
236     if (waitFor == 0) 
237         if (threadId) { CthAwaken(threadId);}
238     delete m;
239 }
240
241 long long  SearchGroup::getTotalSolutions() {
242     CProxy_SearchGroup grp(mygrp);
243     grp.sendCounts();//this is a broadcast, as no processor is mentioned
244     threadId = CthSelf();
245     while (waitFor != 0)  CthSuspend();
246     return totalCount;
247 }
248
249 SearchGroup::~SearchGroup()
250 {
251 }
252
253 void SearchGroup::init()
254 {
255     //get the factory from the user space
256     ////this function is the bridge to pass the pointer to the search engine
257     ////create new search core
258     parallelize_level = parallelLevel();
259
260 #ifdef USING_CONTROLPOINTS
261     THRESH_MIN = myCore->minimumLevel();
262     THRESH_MAX = myCore->maximumLevel();
263 #endif
264     //tell the mainchare that this branch is finished
265     starttimer = CkWallTimer();
266     searchEngineProxy.groupInitComplete();      
267 }
268
269
270 void SearchGroup::searchDepthChange( int depth) { /*searchDepthChangeNotify( depth );*/ }
271
272 void SearchGroup::killSearch()
273 {
274 #ifdef STATISTIC
275     groupProxy.ckLocalBranch()->printfStatistic();
276 #endif
277     CkExit();
278 }
279 //implementation of SearchNode
280 SearchNode::SearchNode( CkMigrateMessage *m ){}
281
282 SearchNode::~SearchNode() {}
283
284 #ifdef BRANCHBOUND
285 extern void createMultipleChildren(SearchGroup *s, StateBase *parent, SequentialSolver* solver, bool parallel);
286 #else
287 extern void createMultipleChildren(StateBase *parent, SequentialSolver* solver, bool parallel);
288 #endif
289
290 SearchNode::SearchNode( SearchNodeMsg *msg )
291 {
292
293 #ifdef STATISTIC
294     groupProxy.ckLocalBranch()->inc_parallel_consume();     
295 #endif
296     myGroup = groupProxy.ckLocalBranch();
297     mySearchClass = (StateBase*) (msg->objectDump);
298
299     myStartDepth = msg->startDepth;
300     mySearchDepth = msg->searchDepth;
301
302     if( mySearchDepth < myGroup->getParallelLevel() ){
303         ParallelSolver solver;
304 #ifdef DEBUG
305        CkPrintf("mySearchDepth: %d\n", mySearchDepth);
306        printPriority(msg);
307 #endif
308         solver.setParentInfo(msg, mySearchDepth);
309 #ifdef BRANCHBOUND
310         double minCost = myGroup->getCost();
311         double lb = _lowerBoundFn(mySearchClass);
312         //CkPrintf("best solution is %f\n", minCost);
313         if(lb<minCost)
314             createChildren(mySearchClass, &solver, true);
315         else
316             CkPrintf("Node is pruned with lower bound:%f, best solution:%f\n", lb, minCost); 
317 #else
318         createChildren(mySearchClass, &solver, true);
319 #endif
320     }
321     else
322     {
323         SequentialSolver solver;
324         solver.setParentInfo(msg, mySearchDepth);
325         StateBase *parent;// = mySearchClass;
326         int processed_nodes = 0;
327         if(msg->nodes == 1){
328             solver.initialize();
329             parent = mySearchClass;
330         }
331         else if(msg->nodes > 1){
332             solver.initialize(msg);
333             parent = solver.dequeue();
334         }
335 #ifdef BRANCHBOUND
336         createMultipleChildren(myGroup, parent, &solver, false);
337 #else
338         createMultipleChildren(parent, &solver, false);
339 #endif
340     }
341     delete msg;
342     delete this;
343 }
344
345 /* called in initproc */
346 void SE_register(SE_createInitialChildrenFn f1,
347                  SE_createChildrenFn f2,
348                  SE_parallelLevelFn f3,
349                  SE_searchDepthLimitFn f4,
350                  SE_lowerBoundFn f5
351                  )
352 {
353   createInitialChildren = f1;
354   createChildren = f2;
355   parallelLevel = f3;
356   searchDepthLimit = f4;
357   _lowerBoundFn = f5;
358
359   CmiPoolAllocInit(30);
360 }
361
362
363 #ifdef BRANCHBOUND
364 #include "searchEngine_bound.def.h"
365 #else
366 #include "searchEngine.def.h"
367 #endif