a77a2b518bc001e16f5b1d0a4a10acfbc7c4821e
[charm.git] / src / ck-cp / controlPoints.C
1 #include <charm++.h>
2 #include "controlPoints.h"
3 #include "trace-controlPoints.h"
4 #include "LBDatabase.h"
5 #include "controlPoints.h"
6 #include "charm++.h"
7 #include "trace-projections.h"
8
9
10 /**
11  *  \addtogroup ControlPointFramework
12  *   @{
13  *
14  */
15
16
17
18
19 using namespace std;
20
21 #define DEFAULT_CONTROL_POINT_SAMPLE_PERIOD  10000000
22 #define NUM_SAMPLES_BEFORE_TRANSISTION 5
23 #define OPTIMIZER_TRANSITION 5
24
25 #define WRITEDATAFILE 1
26
27 //#undef DEBUGPRINT
28 //#define DEBUGPRINT 4
29
30 static void periodicProcessControlPoints(void* ptr, double currWallTime);
31
32
33
34 // A pointer to this PE's controlpoint manager Proxy
35 /* readonly */ CProxy_controlPointManager controlPointManagerProxy;
36 /* readonly */ int random_seed;
37 /* readonly */ long controlPointSamplePeriod;
38
39
40 /// A reduction type that combines idle time statistics (min/max/avg etc.)
41 CkReduction::reducerType idleTimeReductionType;
42 /// A reducer that combines idle time statistics (min/max/avg etc.)
43 CkReductionMsg *idleTimeReduction(int nMsg,CkReductionMsg **msgs){
44   double ret[3];
45   if(nMsg > 0){
46     CkAssert(msgs[0]->getSize()==3*sizeof(double));
47     double *m=(double *)msgs[0]->getData();
48     ret[0]=m[0];
49     ret[1]=m[1];
50     ret[2]=m[2];
51   }
52   for (int i=1;i<nMsg;i++) {
53     CkAssert(msgs[i]->getSize()==3*sizeof(double));
54     double *m=(double *)msgs[i]->getData();
55     ret[0]=min(ret[0],m[0]);
56     ret[1]+=m[1];
57     ret[2]=max(ret[2],m[2]);
58   }  
59   return CkReductionMsg::buildNew(3*sizeof(double),ret);   
60 }
61 /// An initcall that registers the idle time reducer idleTimeReduction()
62 /*initcall*/ void registerIdleTimeReduction(void) {
63   idleTimeReductionType=CkReduction::addReducer(idleTimeReduction);
64 }
65
66
67
68
69
70 /// Return an integer between 0 and num-1 inclusive
71 /// If different seed, name, and random_seed values are provided, the returned values are pseudo-random
72 unsigned int randInt(unsigned int num, const char* name, int seed=0){
73   CkAssert(num > 0);
74   CkAssert(num < 1000);
75
76   unsigned long hash = 0;
77   unsigned int c;
78   unsigned char * str = (unsigned char*)name;
79
80   while (c = *str++){
81     unsigned int c2 = (c+64)%128;
82     unsigned int c3 = (c2*5953)%127;
83     hash = c3 + (hash << 6) + (hash << 16) - hash;
84   }
85
86   unsigned long shuffled1 = (hash*2083)%7907;
87   unsigned long shuffled2 = (seed*4297)%2017;
88
89   unsigned long shuffled3 = (random_seed*4799)%7919;
90
91   unsigned int namehash = shuffled3 ^ shuffled1 ^ shuffled2;
92
93   unsigned int result = ((namehash * 6029) % 1117) % num;
94
95   CkAssert(result >=0 && result < num);
96   return result;
97 }
98
99
100
101 controlPointManager::controlPointManager(){
102 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
103     pathHistoryTableLastIdx = 0;
104 #endif
105
106     newControlPointsAvailable = false;
107     alreadyRequestedMemoryUsage = false;   
108     alreadyRequestedIdleTime = false;
109     
110     dataFilename = (char*)malloc(128);
111     sprintf(dataFilename, "controlPointData.txt");
112     
113     frameworkShouldAdvancePhase = false;
114     haveGranularityCallback = false;
115     CkPrintf("[%d] controlPointManager() Constructor Initializing control points, and loading data file\n", CkMyPe());
116     
117     phase_id = 0;
118     
119     controlPointManagerProxy = thisProxy;
120     
121     loadDataFile();
122     
123     if(allData.phases.size()>0){
124       allData.findBest();
125     }
126     
127     if(CkMyPe() == 0){
128       CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, controlPointSamplePeriod, CkMyPe());
129     }
130
131     traceRegisterUserEvent("No currently executing message", 5000);
132     traceRegisterUserEvent("Zero time along critical path", 5010);
133     traceRegisterUserEvent("Positive total time along critical path", 5020);
134     traceRegisterUserEvent("env->setPathHistory()", 6000);
135     traceRegisterUserEvent("Critical Path", 5900);
136     traceRegisterUserEvent("Table Entry", 5901);
137
138
139 #if USER_EVENT_FOR_REGISTERTERMINALPATH
140     traceRegisterUserEvent("registerTerminalPath", 100); 
141 #endif
142
143   }
144   
145
146  controlPointManager::~controlPointManager(){
147     CkPrintf("[%d] controlPointManager() Destructor\n", CkMyPe());
148   }
149
150
151   /// Loads the previous run data file
152   void controlPointManager::loadDataFile(){
153     ifstream infile(dataFilename);
154     vector<string> names;
155     string line;
156   
157     while(getline(infile,line)){
158       if(line[0] != '#')
159         break;
160     }
161   
162     int numTimings = 0;
163     istringstream n(line);
164     n >> numTimings;
165   
166     while(getline(infile,line)){ 
167       if(line[0] != '#') 
168         break; 
169     }
170
171     int numControlPointNames = 0;
172     istringstream n2(line);
173     n2 >> numControlPointNames;
174   
175     for(int i=0; i<numControlPointNames; i++){
176       getline(infile,line);
177       names.push_back(line);
178     }
179
180     for(int i=0;i<numTimings;i++){
181       getline(infile,line);
182       while(line[0] == '#')
183         getline(infile,line); 
184
185       instrumentedPhase ips;
186
187       istringstream iss(line);
188
189       // Read memory usage for phase
190       iss >> ips.memoryUsageMB;
191       //     CkPrintf("Memory usage loaded from file: %d\n", ips.memoryUsageMB);
192
193
194       // Read control point values
195       for(int cp=0;cp<numControlPointNames;cp++){
196         int cpvalue;
197         iss >> cpvalue;
198         ips.controlPoints.insert(make_pair(names[cp],cpvalue));
199       }
200
201       double time;
202
203       while(iss >> time){
204         ips.times.push_back(time);
205 #if DEBUGPRINT > 5
206         CkPrintf("read time %lf from file\n", time);
207 #endif
208       }
209
210       allData.phases.push_back(ips);
211
212     }
213
214     infile.close();
215   }
216
217
218
219   /// Add the current data to allData and output it to a file
220   void controlPointManager::writeDataFile(){
221 #if WRITEDATAFILE
222     CkPrintf("============= writeDataFile() ============\n");
223     ofstream outfile(dataFilename);
224     allData.phases.push_back(thisPhaseData);
225     allData.cleanupNames();
226     outfile << allData.toString();
227     outfile.close();
228 #else
229     CkPrintf("NOT WRITING OUTPUT FILE\n");
230 #endif
231   }
232
233   /// User can register a callback that is called when application should advance to next phase
234   void controlPointManager::setGranularityCallback(CkCallback cb, bool _frameworkShouldAdvancePhase){
235     frameworkShouldAdvancePhase = _frameworkShouldAdvancePhase;
236     granularityCallback = cb;
237     haveGranularityCallback = true;
238   }
239
240   /// Called periodically by the runtime to handle the control points
241   /// Currently called on each PE
242   void controlPointManager::processControlPoints(){
243
244     CkPrintf("[%d] processControlPoints() haveGranularityCallback=%d frameworkShouldAdvancePhase=%d\n", CkMyPe(), (int)haveGranularityCallback, (int)frameworkShouldAdvancePhase);
245
246         
247     if(CkMyPe() == 0 && !alreadyRequestedMemoryUsage){
248       alreadyRequestedMemoryUsage = true;
249       CkCallback *cb = new CkCallback(CkIndex_controlPointManager::gatherMemoryUsage(NULL), 0, thisProxy);
250       // thisProxy.requestMemoryUsage(*cb);
251       delete cb;
252     }
253     
254     if(CkMyPe() == 0 && !alreadyRequestedIdleTime){
255       alreadyRequestedIdleTime = true;
256       CkCallback *cb = new CkCallback(CkIndex_controlPointManager::gatherIdleTime(NULL), 0, thisProxy);
257       thisProxy.requestIdleTime(*cb);
258       delete cb;
259     }
260     
261
262     //==========================================================================================
263     // Print the data for each phase
264
265     const int s = allData.phases.size();
266
267 #if DEBUGPRINT
268     CkPrintf("\n\nExamining critical paths and priorities and idle times (num phases=%d)\n", s );
269     for(int p=0;p<s;++p){
270       const instrumentedPhase &phase = allData.phases[p];
271       const idleTimeContainer &idle = phase.idleTime;
272       //      vector<MergeablePathHistory> const &criticalPaths = phase.criticalPaths;
273       vector<double> const &times = phase.times;
274
275       CkPrintf("Phase %d:\n", p);
276       idle.print();
277      //   CkPrintf("critical paths: (* affected by control point)\n");
278         //   for(int i=0;i<criticalPaths.size(); i++){
279         // If affected by a control point
280         //      criticalPaths[i].print();
281
282       //        criticalPaths[i].print();
283       //        CkPrintf("\n");
284         
285
286       //   }
287       CkPrintf("Timings:\n");
288       for(int i=0;i<times.size(); i++){
289         CkPrintf("%lf ", times[i]);
290       }
291       CkPrintf("\n");
292
293     }
294     
295     CkPrintf("\n\n");
296
297
298 #endif
299
300
301
302     //==========================================================================================
303     // If this is a phase during which we try to adapt control point values based on critical path
304 #if 0
305
306     if( s%5 == 4) {
307
308       // Find the most recent phase with valid critical path data and idle time measurements      
309       int whichPhase=-1;
310       for(int p=0; p<s; ++p){
311         const instrumentedPhase &phase = allData.phases[p];
312         const idleTimeContainer &idle = phase.idleTime;
313         if(idle.isValid() && phase.criticalPaths.size()>0 ){
314           whichPhase = p;
315         }
316       }
317       
318       
319       CkPrintf("Examining phase %d which has a valid idle time and critical paths\n", whichPhase);
320       const instrumentedPhase &phase = allData.phases[whichPhase];
321       const idleTimeContainer &idle = phase.idleTime;
322       
323       if(idle.min > 0.1){
324         CkPrintf("Min PE idle is HIGH. %.2lf%% > 10%%\n", idle.min*100.0);
325         
326         // Determine the median critical path for this phase
327         int medianCriticalPathIdx = phase.medianCriticalPathIdx();
328         const PathHistory &path = phase.criticalPaths[medianCriticalPathIdx];
329         CkAssert(phase.criticalPaths.size() > 0);
330         CkAssert(phase.criticalPaths.size() > medianCriticalPathIdx); 
331         
332         CkPrintf("Median Critical Path has time %lf\n", path.getTotalTime());
333         
334         if(phase.times[medianCriticalPathIdx] > 1.2 * path.getTotalTime()){
335           CkPrintf("The application step(%lf) is taking significantly longer than the critical path(%lf). BAD\n",phase.times[medianCriticalPathIdx], path.getTotalTime() );
336
337
338           CkPrintf("Finding control points related to the critical path\n");
339           int cpcount = 0;
340           std::set<string> controlPointsAffectingCriticalPath;
341
342           
343           for(int e=0;e<path.getNumUsed();e++){
344             if(path.getUsedCount(e)>0){
345               int ep = path.getUsedEp(e);
346
347               std::map<string, std::set<int> >::iterator iter;
348               for(iter=affectsPrioritiesEP.begin(); iter!= affectsPrioritiesEP.end(); ++iter){
349                 if(iter->second.count(ep)>0){
350                   controlPointsAffectingCriticalPath.insert(iter->first);
351                   CkPrintf("Control Point \"%s\" affects the critical path\n", iter->first.c_str());
352                   cpcount++;
353                 }
354               }
355               
356             }
357           }
358           
359
360           if(cpcount==0){
361             CkPrintf("No control points are known to affect the critical path\n");
362           } else {
363             double beginTime = CmiWallTimer();
364
365             CkPrintf("Attempting to modify control point values for %d control points that affect the critical path\n", controlPointsAffectingCriticalPath.size());
366             
367             newControlPoints = phase.controlPoints;
368             
369             if(frameworkShouldAdvancePhase){
370               gotoNextPhase();  
371             }
372             
373             if(haveGranularityCallback){ 
374 #if DEBUGPRINT
375               CkPrintf("Calling granularity change callback\n");
376 #endif
377               controlPointMsg *msg = new(0) controlPointMsg;
378               granularityCallback.send(msg);
379             }
380             
381             
382             // adjust the control points that can affect the critical path
383
384             char textDescription[4096*2];
385             textDescription[0] = '\0';
386
387             std::map<string,int>::iterator newCP;
388             for(newCP = newControlPoints.begin(); newCP != newControlPoints.end(); ++ newCP){
389               if( controlPointsAffectingCriticalPath.count(newCP->first) > 0 ){
390                 // decrease the value (increase priority) if within range
391                 int lowerbound = controlPointSpace[newCP->first].first;
392                 if(newCP->second > lowerbound){
393                   newControlPointsAvailable = true;
394                   newCP->second --;
395                 }
396               }
397             }
398            
399             // Create a string for a projections user event
400             if(1){
401               std::map<string,int>::iterator newCP;
402               for(newCP = newControlPoints.begin(); newCP != newControlPoints.end(); ++ newCP){
403                 sprintf(textDescription+strlen(textDescription), "<br>\"%s\"=%d", newCP->first.c_str(), newCP->second);
404               }
405             }
406
407             char *userEventString = new char[4096*2];
408             sprintf(userEventString, "Adjusting control points affecting critical path: %s ***", textDescription);
409             
410             static int userEventCounter = 20000;
411             CkPrintf("USER EVENT: %s\n", userEventString);
412             
413             traceRegisterUserEvent(userEventString, userEventCounter); 
414             traceUserBracketEvent(userEventCounter, beginTime, CmiWallTimer());
415             userEventCounter++;
416             
417           }
418           
419         } else {
420           CkPrintf("The application step(%lf) is dominated mostly by the critical path(%lf). GOOD\n",phase.times[medianCriticalPathIdx], path.getTotalTime() );
421         }
422         
423         
424       }
425       
426     } else {
427       // This is a phase during which we should just advance to the
428       // next phase
429
430       if(frameworkShouldAdvancePhase){
431         gotoNextPhase();        
432       }
433       
434       if(haveGranularityCallback){ 
435 #if DEBUGPRINT
436         CkPrintf("Calling granularity change callback\n");
437 #endif
438         controlPointMsg *msg = new(0) controlPointMsg;
439         granularityCallback.send(msg);
440       }
441       
442       
443     }
444     
445
446 #endif
447
448
449     CkPrintf("\n");
450         
451   }
452   
453   /// Determine if any control point is known to affect an entry method
454   bool controlPointManager::controlPointAffectsThisEP(int ep){
455     std::map<string, std::set<int> >::iterator iter;
456     for(iter=affectsPrioritiesEP.begin(); iter!= affectsPrioritiesEP.end(); ++iter){
457       if(iter->second.count(ep)>0){
458         return true;
459       }
460     }
461     return false;    
462   }
463   
464   /// Determine if any control point is known to affect a chare array  
465   bool controlPointManager::controlPointAffectsThisArray(int array){
466     std::map<string, std::set<int> >::iterator iter;
467     for(iter=affectsPrioritiesArray.begin(); iter!= affectsPrioritiesArray.end(); ++iter){
468       if(iter->second.count(array)>0){
469         return true;
470       }
471     }
472     return false;   
473   }
474   
475   /// The data from the previous phase
476   instrumentedPhase * controlPointManager::previousPhaseData(){
477     int s = allData.phases.size();
478     if(s >= 1 && phase_id > 0) {
479       return &(allData.phases[s-1]);
480     } else {
481       return NULL;
482     }
483   }
484   
485
486   /// Called by either the application or the Control Point Framework to advance to the next phase  
487   void controlPointManager::gotoNextPhase(){
488
489     LBDatabase * myLBdatabase = LBDatabaseObj();
490
491 #if CMK_LBDB_ON && 0
492     LBDB * myLBDB = myLBdatabase->getLBDB();       // LBDB is Defined in LBDBManager.h
493     const CkVec<LBObj*> objs = myLBDB->getObjs();
494     const int objCount = myLBDB->getObjCount();
495     CkPrintf("LBDB info: objCount=%d objs contains %d LBObj* \n", objCount, objs.length());
496     
497     floatType maxObjWallTime = -1.0;
498     
499     for(int i=0;i<objs.length();i++){
500       LBObj* o = objs[i];
501       const LDObjData d = o->ObjData();
502       floatType cpuTime = d.cpuTime;
503       floatType wallTime = d.wallTime;
504       // can also get object handles from the LDObjData struct
505       CkPrintf("[%d] LBDB Object[%d]: cpuTime=%f wallTime=%f\n", CkMyPe(), i, cpuTime, wallTime);
506       if(wallTime > maxObjWallTime){
507
508       }
509       
510     }
511
512     myLBDB->ClearLoads(); // BUG: Probably very dangerous if we are actually using load balancing
513     
514 #endif    
515     
516     
517     // increment phase id
518     phase_id++;
519     
520     CkPrintf("Now in phase %d\n", phase_id);
521     
522     // save a copy of the timing information from this phase
523     allData.phases.push_back(thisPhaseData);
524     
525     // clear the timing information that will be used for the next phase
526     thisPhaseData.clear();
527     
528   }
529
530   /// An application uses this to register an instrumented timing for this phase
531   void controlPointManager::setTiming(double time){
532     thisPhaseData.times.push_back(time);
533 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
534        
535     // First we should register this currently executing message as a path, because it is likely an important one to consider.
536     //    registerTerminalEntryMethod();
537     
538     // save the critical path for this phase
539     //   thisPhaseData.criticalPaths.push_back(maxTerminalPathHistory);
540     //    maxTerminalPathHistory.reset();
541     
542     
543     // Reset the counts for the currently executing message
544     //resetThisEntryPath();
545         
546 #endif
547     
548   }
549   
550   /// Entry method called on all PEs to request memory usage
551   void controlPointManager::requestIdleTime(CkCallback cb){
552     double i = localControlPointTracingInstance()->idleRatio();
553     double idle[3];
554     idle[0] = i;
555     idle[1] = i;
556     idle[2] = i;
557     
558     localControlPointTracingInstance()->resetTimings();
559
560     contribute(3*sizeof(double),idle,idleTimeReductionType, cb);
561   }
562   
563   /// All processors reduce their memory usages in requestIdleTime() to this method
564   void controlPointManager::gatherIdleTime(CkReductionMsg *msg){
565     int size=msg->getSize() / sizeof(double);
566     CkAssert(size==3);
567     double *r=(double *) msg->getData();
568         
569     instrumentedPhase* prevPhase = previousPhaseData();
570     if(prevPhase != NULL){
571       CkPrintf("Storing idle time measurements\n");
572       prevPhase->idleTime.min = r[0];
573       prevPhase->idleTime.avg = r[1]/CkNumPes();
574       prevPhase->idleTime.max = r[2];
575       prevPhase->idleTime.print();
576       CkPrintf("Stored idle time min=%lf in prevPhase=%p\n", prevPhase->idleTime.min, prevPhase);
577     } else {
578       CkPrintf("There is no previous phase to store the idle time measurements\n");
579     }
580     
581     alreadyRequestedIdleTime = false;
582     delete msg;
583   }
584   
585
586
587   /// Entry method called on all PEs to request memory usage
588   void controlPointManager::requestMemoryUsage(CkCallback cb){
589     int m = CmiMaxMemoryUsage() / 1024 / 1024;
590     CmiResetMaxMemory();
591     CkPrintf("PE %d Memory Usage is %d MB\n",CkMyPe(), m);
592     contribute(sizeof(int),&m,CkReduction::max_int, cb);
593   }
594
595   /// All processors reduce their memory usages to this method
596   void controlPointManager::gatherMemoryUsage(CkReductionMsg *msg){
597     int size=msg->getSize() / sizeof(int);
598     CkAssert(size==1);
599     int *m=(int *) msg->getData();
600
601     CkPrintf("[%d] Max Memory Usage for all processors is %d MB\n", CkMyPe(), m[0]);
602     
603     instrumentedPhase* prevPhase = previousPhaseData();
604     if(prevPhase != NULL){
605       prevPhase->memoryUsageMB = m[0];
606     } else {
607       CkPrintf("No place to store memory usage");
608     }
609
610     alreadyRequestedMemoryUsage = false;
611     delete msg;
612   }
613
614
615   /** Trace perform a traversal backwards over the critical path specified as a 
616       table index for the processor upon which this is called.
617       
618       The callback cb will be called with the resulting msg after the path has 
619       been traversed to its origin.  
620   */
621  void controlPointManager::traceCriticalPathBack(pathInformationMsg *msg){
622 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
623    int count = pathHistoryTable.count(msg->table_idx);
624 #if DEBUGPRINT > 2
625    CkPrintf("Table entry %d on pe %d occurs %d times in table\n", msg->table_idx, CkMyPe(), count);
626 #endif
627    CkAssert(count==0 || count==1);
628
629     if(count > 0){ 
630       PathHistoryTableEntry & path = pathHistoryTable[msg->table_idx];
631       int idx = path.sender_history_table_idx;
632       int pe = path.sender_pe;
633
634 #if DEBUGPRINT > 2
635       CkPrintf("Table entry %d on pe %d points to pe=%d idx=%d\n", msg->table_idx, CkMyPe(), pe, idx);
636 #endif
637
638       // Make a copy of the message for broadcasting to all PEs
639       pathInformationMsg *newmsg = new(msg->historySize+1) pathInformationMsg;
640       for(int i=0;i<msg->historySize;i++){
641         newmsg->history[i] = msg->history[i];
642       }
643       newmsg->history[msg->historySize] = path;
644       newmsg->historySize = msg->historySize+1;
645       newmsg->cb = msg->cb;
646       newmsg->table_idx = idx;
647       
648       // Keep a message for returning to the user's callback
649       pathForUser = new(msg->historySize+1) pathInformationMsg;
650       for(int i=0;i<msg->historySize;i++){
651         pathForUser->history[i] = msg->history[i];
652       }
653       pathForUser->history[msg->historySize] = path;
654       pathForUser->historySize = msg->historySize+1;
655       pathForUser->cb = msg->cb;
656       pathForUser->table_idx = idx;
657       
658       
659       if(idx > -1 && pe > -1){
660         CkAssert(pe < CkNumPes() && pe >= 0);
661         thisProxy[pe].traceCriticalPathBack(newmsg);
662       } else {
663         CkPrintf("Traced critical path back to its origin.\n");
664         CkPrintf("Broadcasting it to all PE\n");
665         thisProxy.broadcastCriticalPathResult(newmsg);
666       }
667     } else {
668       CkAbort("ERROR: Traced critical path back to a nonexistent table entry.\n");
669     }
670
671     delete msg;
672 #else
673     CkAbort("Shouldn't call controlPointManager::traceCriticalPathBack when critical path detection is not enabled");
674 #endif
675   }
676
677
678 void controlPointManager::broadcastCriticalPathResult(pathInformationMsg *msg){
679
680 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
681   CkPrintf("[%d] Received broadcast of critical path\n", CkMyPe());
682   int me = CkMyPe();
683   int intersectsLocalPE = false;
684
685   // Create user events for critical path
686
687   for(int i=msg->historySize-1;i>=0;i--){
688     if(CkMyPe() == msg->history[i].local_pe){
689       // Part of critical path is local
690       // Create user event for it
691
692       //      CkPrintf("\t[%d] Path Step %d: local_path_time=%lf arr=%d ep=%d starttime=%lf preceding path time=%lf pe=%d\n",CkMyPe(), i, msg->history[i].get_local_path_time(), msg-> history[i].local_arr, msg->history[i].local_ep, msg->history[i].get_start_time(), msg->history[i].get_preceding_path_time(), msg->history[i].local_pe);
693       traceUserBracketEvent(5900, msg->history[i].get_start_time(), msg->history[i].get_start_time() + msg->history[i].get_local_path_time());
694       intersectsLocalPE = true;
695     }
696
697   }
698   
699
700 #if PRUNE_CRITICAL_PATH_LOGS
701   // Tell projections tracing to only output log entries if I contain part of the critical path
702   if(! intersectsLocalPE){
703     disableTraceLogOutput();
704     CkPrintf("PE %d doesn't intersect the critical path, so its log files won't be created\n", CkMyPe() );
705   }
706 #endif  
707   
708 #if TRACE_ALL_PATH_TABLE_ENTRIES
709   // Create user events for all table entries
710   std::map< int, PathHistoryTableEntry >::iterator iter;
711   for(iter=pathHistoryTable.begin(); iter != pathHistoryTable.end(); iter++){
712     double startTime = iter->second.get_start_time();
713     double endTime = iter->second.get_start_time() + iter->second.get_local_path_time();
714     traceUserBracketEvent(5901, startTime, endTime);
715   }
716 #endif
717
718   int data=1;
719   CkCallback cb(CkIndex_controlPointManager::criticalPathDone(NULL),thisProxy[0]); 
720   contribute(sizeof(int), &data, CkReduction::sum_int, cb);
721
722 #endif
723
724 }
725
726 void controlPointManager::criticalPathDone(CkReductionMsg *msg){
727 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
728   CkPrintf("[%d] All PEs have received the critical path information. Sending critical path to user supplied callback.\n", CkMyPe());
729   pathForUser->cb.send(pathForUser);
730   pathForUser = NULL;
731 #endif
732 }
733
734
735  
736   /// Inform the control point framework that a named control point affects the priorities of some array  
737   void controlPointManager::associatePriorityArray(const char *name, int groupIdx){
738     CkPrintf("Associating control point \"%s\" affects priority of array id=%d\n", name, groupIdx );
739     
740     if(affectsPrioritiesArray.count(std::string(name)) > 0 ) {
741       affectsPrioritiesArray[std::string(name)].insert(groupIdx);
742     } else {
743       std::set<int> s;
744       s.insert(groupIdx);
745       affectsPrioritiesArray[std::string(name)] = s;
746     }
747     
748 #if DEBUGPRINT   
749     std::map<string, std::set<int> >::iterator f;
750     for(f=affectsPrioritiesArray.begin(); f!=affectsPrioritiesArray.end();++f){
751       std::string name = f->first;
752       std::set<int> &vals = f->second;
753       cout << "Control point " << name << " affects arrays: ";
754       std::set<int>::iterator i;
755       for(i=vals.begin(); i!=vals.end();++i){
756         cout << *i << " ";
757       }
758       cout << endl;
759     }
760 #endif
761     
762   }
763   
764   /// Inform the control point framework that a named control point affects the priority of some entry method
765   void controlPointManager::associatePriorityEntry(const char *name, int idx){
766     CkPrintf("Associating control point \"%s\" with EP id=%d\n", name, idx);
767
768       if(affectsPrioritiesEP.count(std::string(name)) > 0 ) {
769       affectsPrioritiesEP[std::string(name)].insert(idx);
770     } else {
771       std::set<int> s;
772       s.insert(idx);
773       affectsPrioritiesEP[std::string(name)] = s;
774     }
775     
776 #if DEBUGPRINT
777     std::map<string, std::set<int> >::iterator f;
778     for(f=affectsPrioritiesEP.begin(); f!=affectsPrioritiesEP.end();++f){
779       std::string name = f->first;
780       std::set<int> &vals = f->second;
781       cout << "Control point " << name << " affects EP: ";
782       std::set<int>::iterator i;
783       for(i=vals.begin(); i!=vals.end();++i){
784         cout << *i << " ";
785       }
786       cout << endl;
787     }
788 #endif
789
790
791   }
792   
793
794
795 /// An interface callable by the application.
796 void gotoNextPhase(){
797   controlPointManagerProxy.ckLocalBranch()->gotoNextPhase();
798 }
799
800
801 /// A mainchare that is used just to create our controlPointManager group at startup
802 class controlPointMain : public CBase_controlPointMain {
803 public:
804   controlPointMain(CkArgMsg* args){
805 #if OLDRANDSEED
806     struct timeval tp;
807     gettimeofday(& tp, NULL);
808     random_seed = (int)tp.tv_usec ^ (int)tp.tv_sec;
809 #else
810     double time = CmiWallTimer();
811     int sec = (int)time;
812     int usec = (int)((time - (double)sec)*1000000.0);
813     random_seed =  sec ^ usec;
814 #endif
815
816
817     double period;
818     bool found = CmiGetArgDoubleDesc(args->argv,"+CPSamplePeriod", &period,"The time between Control Point Framework samples (in seconds)");
819     if(found){
820       CkPrintf("LBPERIOD = %ld sec\n", period);
821       controlPointSamplePeriod =  period * 1000;
822     } else {
823       controlPointSamplePeriod =  DEFAULT_CONTROL_POINT_SAMPLE_PERIOD;
824     }
825
826     controlPointManagerProxy = CProxy_controlPointManager::ckNew();
827   }
828   ~controlPointMain(){}
829 };
830
831 /// An interface callable by the application.
832 void registerGranularityChangeCallback(CkCallback cb, bool frameworkShouldAdvancePhase){
833   CkAssert(CkMyPe() == 0);
834   CkPrintf("registerGranularityChangeCallback\n");
835   controlPointManagerProxy.ckLocalBranch()->setGranularityCallback(cb, frameworkShouldAdvancePhase);
836 }
837
838 /// An interface callable by the application.
839 void registerControlPointTiming(double time){
840   CkAssert(CkMyPe() == 0);
841 #if DEBUGPRINT>0
842   CkPrintf("Program registering its own timing with registerControlPointTiming(time=%lf)\n", time);
843 #endif
844   controlPointManagerProxy.ckLocalBranch()->setTiming(time);
845 }
846
847 /// Shutdown the control point framework, writing data to disk if necessary
848 extern "C" void controlPointShutdown(){
849   CkAssert(CkMyPe() == 0);
850   CkPrintf("[%d] controlPointShutdown() at CkExit()\n", CkMyPe());
851   controlPointManagerProxy.ckLocalBranch()->writeDataFile();
852   CkExit();
853 }
854
855 /// A function called at startup on each node to register controlPointShutdown() to be called at CkExit()
856 void controlPointInitNode(){
857   CkPrintf("controlPointInitNode()\n");
858   registerExitFn(controlPointShutdown);
859 }
860
861 /// Called periodically to allow control point framework to do things periodically
862 static void periodicProcessControlPoints(void* ptr, double currWallTime){
863 #ifdef DEBUGPRINT
864   CkPrintf("[%d] periodicProcessControlPoints()\n", CkMyPe());
865 #endif
866   controlPointManagerProxy.ckLocalBranch()->processControlPoints();
867   CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, controlPointSamplePeriod, CkMyPe());
868 }
869
870
871
872
873
874 // Static point for life of program: randomly chosen, no optimizer
875 int staticPoint(const char *name, int lb, int ub){
876   instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
877   std::set<string> &staticControlPoints = controlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
878
879   int result = lb + randInt(ub-lb+1, name);
880   
881   controlPointManagerProxy.ckLocalBranch()->controlPointSpace.insert(std::make_pair(string(name),std::make_pair(lb,ub))); 
882   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result)); 
883   staticControlPoints.insert(string(name));
884
885   return result;
886 }
887
888
889 /// Should an optimizer determine the control point values
890 bool valueShouldBeProvidedByOptimizer(){
891   
892   const int effective_phase = controlPointManagerProxy.ckLocalBranch()->allData.phases.size();
893   const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id; 
894   
895   std::map<string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace; 
896   
897   double spaceSize = 1.0;
898   std::map<string, pair<int,int> >::iterator iter;
899   for(iter = controlPointSpace.begin(); iter != controlPointSpace.end(); iter++){
900     spaceSize *= iter->second.second - iter->second.first + 1;
901   }
902
903   //  CkPrintf("Control Point Space:\n\t\tnumber of control points = %d\n\t\tnumber of possible configurations = %.0lf\n", controlPointSpace.size(), spaceSize);
904
905 #if 1
906   return effective_phase > 1 && phase_id > 1;
907 #else
908   return effective_phase >= OPTIMIZER_TRANSITION && phase_id > 3;
909 #endif
910 }
911
912
913
914
915
916 /// Determine a control point value using some optimization scheme (use max known, simmulated annealling, 
917 /// user observed characteristic to adapt specific control point values.
918 /// @note eventually there should be a plugin system where multiple schemes can be plugged in(similar to LB)
919 int valueProvidedByOptimizer(const char * name){
920   const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
921   const int effective_phase = controlPointManagerProxy.ckLocalBranch()->allData.phases.size();
922
923
924 #define OPTIMIZER_ADAPT_CRITICAL_PATHS 0
925   
926   // -----------------------------------------------------------
927 #if OPTIMIZER_ADAPT_CRITICAL_PATHS
928   // This scheme will return the median value for the range 
929   // early on, and then will transition over to the new control points
930   // determined by the critical path adapting code
931   if(controlPointManagerProxy.ckLocalBranch()->newControlPointsAvailable){
932     int result = controlPointManagerProxy.ckLocalBranch()->newControlPoints[string(name)];
933     CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d  from \"newControlPoints\" is: %d\n", name, phase_id, result);
934     return result;
935   } 
936   
937   std::map<string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;  
938
939   if(controlPointSpace.count(std::string(name))>0){
940     int minValue =  controlPointSpace[std::string(name)].first;
941     int maxValue =  controlPointSpace[std::string(name)].second;
942     return (minValue+maxValue)/2;
943   }
944   
945   // -----------------------------------------------------------
946 #elif OPTIMIZER_USE_BEST_TIME  
947   static bool firstTime = true;
948   if(firstTime){
949     firstTime = false;
950     CkPrintf("Finding best phase\n");
951     instrumentedPhase p = controlPointManagerProxy.ckLocalBranch()->allData.findBest(); 
952     CkPrintf("p=:\n");
953     p.print();
954     CkPrintf("\n");
955     controlPointManagerProxy.ckLocalBranch()->best_phase = p;
956   }
957   
958   
959   instrumentedPhase &p = controlPointManagerProxy.ckLocalBranch()->best_phase;
960   int result = p.controlPoints[std::string(name)];
961   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen out of best previous phase to be: %d\n", name, phase_id, result);
962   return result;
963
964   // -----------------------------------------------------------
965 #elsif SIMULATED_ANNEALING
966   
967   // Simulated Annealing style hill climbing method
968   //
969   // Find the best search space configuration, and try something
970   // nearby it, with a radius decreasing as phases increase
971   
972   std::map<string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;  
973   
974   CkPrintf("Finding best phase\n"); 
975   instrumentedPhase p = controlPointManagerProxy.ckLocalBranch()->allData.findBest();  
976   CkPrintf("best found:\n"); 
977   p.print(); 
978   CkPrintf("\n"); 
979   
980   int before = p.controlPoints[std::string(name)];   
981   
982   int minValue =  controlPointSpace[std::string(name)].first;
983   int maxValue =  controlPointSpace[std::string(name)].second;
984   
985   int convergeByPhase = 100;
986   
987   // Determine from 0.0 to 1.0 how far along we are
988   double progress = (double) min(effective_phase, convergeByPhase) / (double)convergeByPhase;
989   
990   int range = (maxValue-minValue+1)*(1.0-progress);
991
992   CkPrintf("========================== Hill climbing progress = %lf  range=%d\n", progress, range); 
993
994   int high = min(before+range, maxValue);
995   int low = max(before-range, minValue);
996   
997   int result = low;
998
999   if(high-low > 0){
1000     result += randInt(high-low, name, phase_id); 
1001   } 
1002
1003   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen by hill climbing to be: %d\n", name, phase_id, result); 
1004   return result; 
1005
1006   // -----------------------------------------------------------
1007 #else
1008   // Exhaustive search
1009
1010   std::map<string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;
1011   std::set<string> &staticControlPoints = controlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
1012    
1013   int numDimensions = controlPointSpace.size();
1014   CkAssert(numDimensions > 0);
1015   
1016   vector<int> lowerBounds(numDimensions);
1017   vector<int> upperBounds(numDimensions); 
1018   
1019   int d=0;
1020   std::map<string, pair<int,int> >::iterator iter;
1021   for(iter = controlPointSpace.begin(); iter != controlPointSpace.end(); iter++){
1022     //    CkPrintf("Examining dimension %d\n", d);
1023
1024 #if DEBUGPRINT
1025     string name = iter->first;
1026     if(staticControlPoints.count(name) >0 ){
1027       cout << " control point " << name << " is static " << endl;
1028     } else{
1029       cout << " control point " << name << " is not static " << endl;
1030     }
1031 #endif
1032
1033     lowerBounds[d] = iter->second.first;
1034     upperBounds[d] = iter->second.second;
1035     d++;
1036   }
1037    
1038
1039   vector<std::string> s(numDimensions);
1040   d=0;
1041   for(std::map<string, pair<int,int> >::iterator niter=controlPointSpace.begin(); niter!=controlPointSpace.end(); niter++){
1042     s[d] = niter->first;
1043     // cout << "s[" << d << "]=" << s[d] << endl;
1044     d++;
1045   }
1046   
1047   
1048   // Create the first possible configuration
1049   vector<int> config = lowerBounds;
1050   config.push_back(0);
1051   
1052   // Increment until finding an unused configuration
1053   controlPointManagerProxy.ckLocalBranch()->allData.cleanupNames(); // put -1 values in for any control points missing
1054   std::vector<instrumentedPhase> &phases = controlPointManagerProxy.ckLocalBranch()->allData.phases;     
1055
1056   while(true){
1057     
1058     std::vector<instrumentedPhase>::iterator piter; 
1059     bool testedConfiguration = false; 
1060     for(piter = phases.begin(); piter != phases.end(); piter++){ 
1061       
1062       // Test if the configuration matches this phase
1063       bool match = true;
1064       for(int j=0;j<numDimensions;j++){
1065         match &= piter->controlPoints[s[j]] == config[j];
1066       }
1067       
1068       if(match){
1069         testedConfiguration = true; 
1070         break;
1071       } 
1072     } 
1073     
1074     if(testedConfiguration == false){ 
1075       break;
1076     } 
1077     
1078     // go to next configuration
1079     config[0] ++;
1080     // Propagate "carrys"
1081     for(int i=0;i<numDimensions;i++){
1082       if(config[i] > upperBounds[i]){
1083         config[i+1]++;
1084         config[i] = lowerBounds[i];
1085       }
1086     }
1087     // check if we have exhausted all possible values
1088     if(config[numDimensions] > 0){
1089       break;
1090     }
1091        
1092   }
1093   
1094   if(config[numDimensions] > 0){
1095     for(int i=0;i<numDimensions;i++){ 
1096       config[i]= (lowerBounds[i]+upperBounds[i]) / 2;
1097     }
1098   }
1099   
1100   
1101   int result=-1;  
1102
1103   std::string name_s(name);
1104   for(int i=0;i<numDimensions;i++){
1105     //    cout << "Comparing " << name_s <<  " with s[" << i << "]=" << s[i] << endl;
1106     if(name_s.compare(s[i]) == 0){
1107       result = config[i];
1108     }
1109   }
1110
1111   CkAssert(result != -1);
1112
1113
1114   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen by exhaustive search to be: %d\n", name, phase_id, result); 
1115   return result; 
1116
1117 #endif
1118
1119 CkAbort("valueProvidedByOptimizer(): ERROR: could not find a value for a control point.\n");
1120 return 0;
1121   
1122 }
1123
1124
1125
1126
1127
1128 #define isInRange(v,a,b) ( ((v)<=(a)&&(v)>=(b)) || ((v)<=(b)&&(v)>=(a)) )
1129
1130
1131 // Dynamic point varies throughout the life of program
1132 // The value it returns is based upon phase_id, a counter that changes for each phase of computation
1133 int controlPoint2Pow(const char *name, int fine_granularity, int coarse_granularity){
1134   instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
1135   const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
1136
1137   int result;
1138
1139   // Use best configuration after a certain point
1140   if(valueShouldBeProvidedByOptimizer()){
1141     result = valueProvidedByOptimizer(name);
1142   } 
1143   else {
1144
1145     int l1 = (int)CmiLog2(fine_granularity);
1146     int l2 = (int)CmiLog2(coarse_granularity);
1147   
1148     if (l1 > l2){
1149       int tmp;
1150       tmp = l2;
1151       l2 = l1; 
1152       l1 = tmp;
1153     }
1154     CkAssert(l1 <= l2);
1155     
1156     int l = l1 + randInt(l2-l1+1,name, phase_id);
1157
1158     result = 1 << l;
1159
1160     CkAssert(isInRange(result,fine_granularity,coarse_granularity));
1161     CkPrintf("Control Point \"%s\" for phase %d chosen randomly to be: %d\n", name, phase_id, result);
1162   }
1163
1164   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result));
1165
1166   return result;
1167 }
1168
1169
1170 /// Get control point value from range of integers [lb,ub]
1171 int controlPoint(const char *name, int lb, int ub){
1172   instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
1173   const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
1174   std::map<string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;
1175
1176   int result;
1177
1178   // Use best configuration after a certain point
1179   if(valueShouldBeProvidedByOptimizer()){
1180     result = valueProvidedByOptimizer(name);
1181   } 
1182   else {
1183     result = lb + randInt(ub-lb+1, name, phase_id);
1184     CkPrintf("Control Point \"%s\" for phase %d chosen randomly to be: %d\n", name, phase_id, result); 
1185   } 
1186    
1187   CkAssert(isInRange(result,ub,lb));
1188   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result)); 
1189   controlPointSpace.insert(std::make_pair(string(name),std::make_pair(lb,ub))); 
1190   //  CkPrintf("Inserting control point value to thisPhaseData.controlPoints with value %d; thisPhaseData.controlPoints.size=%d\n", result, thisPhaseData.controlPoints.size());
1191   return result;
1192 }
1193
1194 /// Get control point value from set of provided integers
1195 int controlPoint(const char *name, std::vector<int>& values){
1196   instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
1197   const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
1198
1199   int result;
1200   if(valueShouldBeProvidedByOptimizer()){
1201     result = valueProvidedByOptimizer(name);
1202   } 
1203   else { 
1204     result = values[randInt(values.size(), name, phase_id)];
1205   }
1206
1207   bool found = false;
1208   for(int i=0;i<values.size();i++){
1209     if(values[i] == result)
1210       found = true;
1211   }
1212   CkAssert(found);
1213
1214   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result)); 
1215   return result;
1216 }
1217
1218
1219
1220
1221 /// Inform the control point framework that a named control point affects the priorities of some array  
1222 void controlPointPriorityArray(const char *name, CProxy_ArrayBase &arraybase){
1223   CkGroupID aid = arraybase.ckGetArrayID();
1224   int groupIdx = aid.idx;
1225   controlPointManagerProxy.ckLocalBranch()->associatePriorityArray(name, groupIdx);
1226   //  CkPrintf("Associating control point \"%s\" with array id=%d\n", name, groupIdx );
1227 }
1228
1229
1230 /// Inform the control point framework that a named control point affects the priorities of some entry method  
1231 void controlPointPriorityEntry(const char *name, int idx){
1232   controlPointManagerProxy.ckLocalBranch()->associatePriorityEntry(name, idx);
1233   //  CkPrintf("Associating control point \"%s\" with EP id=%d\n", name, idx);
1234 }
1235
1236
1237
1238 /*! @} */
1239
1240
1241 #include "ControlPoints.def.h"