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