Temporary fix of setting MaxActiveExperiments higher to allow Performance
[dyninst.git] / paradyn / src / PCthread / PCsearch.C
1 /*
2  * Copyright (c) 1996 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 /*
43  * PCsearch.C
44  * 
45  * class PCsearch
46  *
47  * $Log: PCsearch.C,v $
48  * Revision 1.26  1998/01/30 19:31:22  ssuen
49  * Temporary fix of setting MaxActiveExperiments higher to allow Performance
50  * Consultant to search "deeper" in program runs with lots of resources.
51  *
52  * Revision 1.25  1997/03/29 02:05:04  sec
53  * Adding some debugging stuff
54  *
55  * Revision 1.24  1997/03/16 23:17:46  lzheng
56  * Changes made for the value of observed cost
57  *
58  * Revision 1.23  1997/02/06 20:47:52  karavan
59  * changed MaxActiveExperiments constant to guard against deadlock.
60  *
61  * Revision 1.22  1996/08/16 21:03:41  tamches
62  * updated copyright for release 1.1
63  *
64  * Revision 1.21  1996/07/26 18:02:37  karavan
65  * added display of status if search throttled back.
66  *
67  * Revision 1.20  1996/07/24 20:10:37  karavan
68  * Fixed error in numActiveExperiments calculation; numActiveCurrentExperiments
69  * now zero'd at phase boundary.
70  *
71  * Revision 1.19  1996/07/23 20:28:05  karavan
72  * second part of two-part commit.
73  *
74  * implements new search strategy which retests false nodes under certain
75  * circumstances.
76  *
77  * change in handling of high-cost nodes blocking the ready queue.
78  *
79  * code cleanup.
80  *
81  * Revision 1.18  1996/07/22 18:55:44  karavan
82  * part one of two-part commit for new PC functionality of restarting searches.
83  *
84  * Revision 1.17  1996/05/16 06:58:37  karavan
85  * increased max num experiments and also min time to conclusion.
86  *
87  * Revision 1.16  1996/05/15 04:35:17  karavan
88  * bug fixes: changed pendingCost pendingSearches and numexperiments to
89  * break down by phase type, so starting a new current phase updates these
90  * totals correctly; fixed error in estimated cost propagation.
91  *
92  * Revision 1.15  1996/05/11 01:58:03  karavan
93  * fixed bug in PendingCost calculation.
94  *
95  * Revision 1.14  1996/05/08 07:35:26  karavan
96  * Changed enable data calls to be fully asynchronous within the performance consultant.
97  *
98  * some changes to cost handling, with additional limit on number of outstanding enable requests.
99  *
100  */
101
102 #include "PCintern.h"
103 #include "PCsearch.h"
104 #include "PCfilter.h"
105 #include "PCshg.h"
106 #include "PCmetric.h"
107
108 #include <iostream.h>
109 #include <fstream.h>
110
111 // for debugging purposes
112 #ifdef MYPCDEBUG
113 extern double TESTgetTime();
114 #endif
115
116 extern void initPChypos();
117 extern void initPCmetrics();
118 extern sampleValue DivideEval (focus, sampleValue *data, int dataSize);
119
120 unsigned int PCunhash (const unsigned &val) {return (val >> 3);} 
121
122 unsigned PCsearch::PCactiveCurrentPhase = 0;  // init to undefined
123 dictionary_hash<unsigned, PCsearch*> PCsearch::AllPCSearches(PCunhash);
124 PriorityQueue<SearchQKey, searchHistoryNode*> PCsearch::GlobalSearchQueue;
125 PriorityQueue<SearchQKey, searchHistoryNode*> PCsearch::CurrentSearchQueue;
126 PriorityQueue<SearchQKey, searchHistoryNode*> *PCsearch::q = &PCsearch::GlobalSearchQueue;
127 int PCsearch::numActiveGlobalExperiments = 0;
128 int PCsearch::numActiveCurrentExperiments = 0;
129 bool PCsearch::GlobalSearchPaused = false;
130 bool PCsearch::CurrentSearchPaused = false;
131 costModule *PCsearch::costTracker = NULL;
132 float PCsearch::PendingCurrentCost = 0.0;
133 float PCsearch::PendingGlobalCost = 0.0;
134 int PCsearch::PendingGlobalSearches = 0;
135 int PCsearch::PendingCurrentSearches = 0;
136 bool PCsearch::SearchThrottledBack = false;
137 searchHistoryNode *PCsearch::SearchThrottleNode = NULL;
138
139 //** this is currently being studied!! (klk)
140 const float costFudge = 0.1;
141 const int MaxPendingSearches = 30;
142 const int MaxActiveExperiments = 300;
143 //
144 // remove from search queues and start up as many experiments as we can 
145 // without exceeding our cost limit.  
146 //
147 void 
148 PCsearch::expandSearch (sampleValue estimatedCost)
149 {
150   bool costLimitReached = false;
151   searchHistoryNode *curr;
152   float candidateCost = 0.0;
153
154 #ifdef PCDEBUG
155   cout << "START OF EXPAND" << endl;
156   cout << "Global Qsize: " << GlobalSearchQueue.size() << 
157     " Current Qsize: " << CurrentSearchQueue.size() << endl;
158 #endif
159
160   // alternate between two queues for fairness
161   while (!costLimitReached 
162          && (PCsearch::getNumPendingSearches() < MaxPendingSearches)
163          && (PCsearch::getNumActiveExperiments() < MaxActiveExperiments)) {
164     // switch queues for fairness, if possible; never use q if empty or that 
165     // search is paused
166     if (q == &CurrentSearchQueue) {
167         if ( !(GlobalSearchQueue.empty() || GlobalSearchPaused))
168           q = &GlobalSearchQueue;
169         else
170           if (q->empty() || CurrentSearchPaused) 
171             // no queue is ready
172             break;
173     } else {
174       if ( !(CurrentSearchQueue.empty() || CurrentSearchPaused)) 
175         q = &CurrentSearchQueue;
176       else
177         if (q->empty() || GlobalSearchPaused) 
178           // no queue is ready 
179           break;
180     }
181     curr = q->peek_first_data();
182     candidateCost = curr->getEstimatedCost();
183 #ifdef PCDEBUG
184     cout << " considering node with cost: " << candidateCost
185          << " name = " << curr->getHypoName() << endl;
186 //    cout << " considering node with cost: " << candidateCost << endl;
187 #endif
188     sampleValue predMax = performanceConsultant::predictedCostLimit;
189     if (1/(1-candidateCost) > predMax) {
190       // **for now just get it out of the way
191       int dispToken = curr->getGuiToken();
192       q->delete_first();
193       string *ds = new string 
194         ("WARNING:  Predicted Node Search Code exceeds limit.  Skipped Node:\n\t");
195       *ds += curr->getShortName();
196       *ds += "||";
197       *ds += curr->getHypoName();
198       *ds += "\n";
199       uiMgr->updateStatusDisplay(dispToken, ds);
200     } else if ((1 / (1 - estimatedCost - candidateCost - 
201                      PCsearch::getPendingCost())) > predMax) {
202       costLimitReached = true;
203       // print status to display but just once per blockage
204       if ( !PCsearch::SearchThrottledBack && 
205           (curr != PCsearch::SearchThrottleNode)) {
206         int dispToken = curr->getGuiToken();
207         string *ds = new string ("Search Slowed:  Cost Limit Reached.\n");
208         uiMgr->updateStatusDisplay(dispToken, ds);
209         PCsearch::SearchThrottleNode = curr;
210         PCsearch::SearchThrottledBack = true;
211       }
212     } else {
213       curr->startExperiment();
214       if (PCsearch::SearchThrottledBack) {
215         int dispToken = curr->getGuiToken();
216         string *ds = new string ("Search Resumed.\n");
217         uiMgr->updateStatusDisplay(dispToken, ds);
218         PCsearch::SearchThrottledBack = false;
219         PCsearch::SearchThrottleNode = NULL;
220       }
221       if (q == &GlobalSearchQueue) {
222         PCsearch::PendingGlobalSearches += 1;
223         PCsearch::PendingGlobalCost += candidateCost;
224       } else {
225         PCsearch::PendingCurrentSearches += 1;
226         PCsearch::PendingCurrentCost += candidateCost;
227       }
228       q->delete_first();
229     }
230   }   
231   if ((PCsearch::getNumActiveExperiments() >=  MaxActiveExperiments) 
232       && (!PCsearch::SearchThrottledBack)) {
233     int dispToken = curr->getGuiToken();
234     string *ds = new string ("Search Slowed:  max active nodes reached.\n");
235     uiMgr->updateStatusDisplay(dispToken, ds);
236     PCsearch::SearchThrottledBack = true;
237   } else if ((PCsearch::getNumPendingSearches() >=  MaxPendingSearches)
238              && (!PCsearch::SearchThrottledBack)) {
239     int dispToken = curr->getGuiToken();
240     string *ds = new string ("Search Slowed:  max pending nodes.\n");
241     uiMgr->updateStatusDisplay(dispToken, ds);
242     PCsearch::SearchThrottledBack = true;
243   }
244 #ifdef PCDEBUG
245   cout << "END OF EXPAND" << endl;
246   cout << "cost limit: " << performanceConsultant::predictedCostLimit << endl;
247   cout << "total observed cost: " << estimatedCost << 
248     "/" << (1-costFudge)*performanceConsultant::predictedCostLimit << endl;
249   cout << "numActiveExperiments: " << PCsearch::getNumActiveExperiments() << endl;
250   cout << "pendingEnables: " << PCsearch::getNumPendingSearches() << endl;
251   cout << "pendingCost = " << PCsearch::getPendingCost() << endl;
252 #endif
253 }
254
255 PCsearch::PCsearch(unsigned phaseID, phaseType phase_type)
256 : searchStatus(schNeverRun),  phaseToken(phaseID), phType(phase_type)
257 {
258   if (phaseID == GlobalPhaseID)
259     database = performanceConsultant::globalPCMetricServer;
260   else 
261     database = new PCmetricInstServer(phaseID);  
262   shg = new searchHistoryGraph (this, phaseID);
263 }
264
265 PCsearch::~PCsearch()
266 {
267   delete database;
268   delete shg;
269 }
270
271 void 
272 PCsearch::initCostTracker () 
273 {
274   bool err = true;
275   PCmetric *pcm;
276   assert (PCmetric::AllPCmetrics.defines("normSmoothCost"));
277
278   pcm = PCmetric::AllPCmetrics ["normSmoothCost"];
279   PCsearch::costTracker = new costModule;
280   PCmetricInstServer *miserve = new PCmetricInstServer (GlobalPhase);
281   costTracker->costFilter = 
282     miserve->createPcmi(pcm, topLevelFocus, &err);
283   assert(costTracker->costFilter);
284   costTracker->costFilter->addSubscription(costTracker);
285 }
286
287 bool
288 PCsearch::addSearch(unsigned phaseID)
289 {
290   string *msg;
291   phaseType pType;
292   // we can't use the dm token really, cause there's no dm token for 
293   // global search, which throws our part of the universe into total 
294   // confusion.  So, internally and in communication with the UI, we always
295   // use dm's number plus one, and 0 for global phase.  
296   if (phaseID > 0) {
297     // non-global search
298     performanceConsultant::currentPhase = phaseID;
299     msg = new string ("Initializing Search for Current Phase ");
300     *msg += (phaseID-1);
301     *msg += string(".\n");
302     pType = CurrentPhase;
303   } else {
304     msg =  new string ("Initializing Search for Global Phase.\n");
305     pType = GlobalPhase;
306   }
307
308   // if this is first search, initialize all PC metrics and hypotheses
309   if (!performanceConsultant::PChyposDefined) {
310     initPCmetrics();
311     initPChypos();
312     performanceConsultant::PChyposDefined = true;
313     initCostTracker();
314   }
315
316   PCsearch *newkid = new PCsearch(phaseID , pType);
317   AllPCSearches[phaseID] = newkid;
318
319   // * initialize PC displays *
320   newkid->updateDisplayedStatus(msg);
321
322   // display root node with style 1 
323   uiMgr->DAGaddNode (phaseID, 0, searchHistoryGraph::InactiveUnknownNodeStyle, 
324                      "TopLevelHypothesis", 
325                      "TopLevelHypothesis", 1);
326   return true;
327 }
328   
329 //
330 // start instrumentation requests for the first time 
331 //
332 void
333 PCsearch::startSearching()
334 {
335   shg->initPersistentNodes();
336   searchStatus = schRunning;
337 }
338
339 //
340 // to pause a search we disable all instrumentation requests
341 //
342 void 
343 PCsearch::pause() 
344 {     
345   if (searchStatus == schRunning) {
346     searchStatus = schPaused;
347     if (phType == GlobalPhase) 
348       // no nodes will be started off the global search queue until false
349       GlobalSearchPaused = true;
350     else 
351       // no nodes will be started off the current search queue until false
352       CurrentSearchPaused = true;
353     shg->updateDisplayedStatus ("Search Paused by User.\n");
354     database->unsubscribeAllRawData();
355   }
356 }
357
358 void 
359 PCsearch::resume() 
360 {
361   if (searchStatus == schPaused) {
362     searchStatus = schRunning;
363     if (phType == GlobalPhase)
364       GlobalSearchPaused = false;
365     else
366       CurrentSearchPaused = false;
367     database->resubscribeAllRawData();
368     shg->updateDisplayedStatus ("Search Resumed.\n");
369   }
370 }
371
372 //
373 // this permanently ends a search, it can never be restarted
374 //
375 void 
376 PCsearch::terminate(timeStamp searchEndTime) {
377   searchStatus = schEnded;
378   // need to flush search nodes for this defunct search from the queue
379   if (phType == CurrentPhase) {
380     while (!PCsearch::CurrentSearchQueue.empty()) {
381       CurrentSearchQueue.delete_first();
382     }
383     PCsearch::PendingCurrentCost = 0;
384     PCsearch::PendingCurrentSearches = 0;
385     PCsearch::numActiveCurrentExperiments = 0;
386   } else {
387     while (!PCsearch::GlobalSearchQueue.empty()) {
388       GlobalSearchQueue.delete_first();
389     }
390     PCsearch::PendingGlobalCost = 0;
391     PCsearch::PendingGlobalSearches = 0;
392     PCsearch::numActiveGlobalExperiments = 0;
393   }
394   shg->finalizeSearch(searchEndTime);
395 }
396
397 void 
398 PCsearch::updateCurrentPhase (unsigned newPhaseID, timeStamp phaseEndTime) 
399 {
400   unsigned phaseID = performanceConsultant::currentPhase;
401   // the UI may be notified of the new phase, and the user select a 
402   // search for it, before the PC gets this callback from the DM.  So
403   // we must check here if we are already searching this "new" phase.
404   if (phaseID == newPhaseID) return;
405   // here if this is the first we're hearing of this phase.  If a search
406   // is in progress for the old current phase, we need to end it.
407   if (phaseID && AllPCSearches.defines(phaseID) ) {
408     // this one's done for good
409     AllPCSearches[phaseID]->terminate(phaseEndTime); 
410   }
411   // 0 indicates no current phase search in progress
412   performanceConsultant::currentPhase = 0;
413   PCsearch::numActiveCurrentExperiments = 0;
414 }
415
416 bool 
417 PCsearch::getNodeInfo(int nodeID, shg_node_info *theInfo)
418 {
419   searchHistoryNode *const currNode = shg->getNode(nodeID);
420   if (! currNode)
421     return false;
422
423   currNode->getInfo (theInfo);
424   return true;
425 }
426
427 PCsearch *
428 PCsearch::findSearch (phaseType pt)
429 {
430   if (pt == GlobalPhase) 
431     return PCsearch::AllPCSearches[0];
432   else {
433     if (performanceConsultant::currentPhase && 
434         PCsearch::AllPCSearches.defines(performanceConsultant::currentPhase))
435       return PCsearch::AllPCSearches[performanceConsultant::currentPhase];
436     else
437       return (PCsearch *)NULL;
438   }
439 }