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