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 }