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