21682c950a7a9d3b10ab8bae1238be77f54427fe
[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  *  \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<std::string> names;
150     std::string line;
151   
152     while(getline(infile,line)){
153       if(line[0] != '#')
154         break;
155     }
156   
157     int numTimings = 0;
158     std::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     std::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       std::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<std::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<std::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<std::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<std::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<std::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<std::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 CPU utilization statistics
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   /// Inform the control point framework that a named control point affects the priorities of some array  
611   void controlPointManager::associatePriorityArray(const char *name, int groupIdx){
612     CkPrintf("Associating control point \"%s\" affects priority of array id=%d\n", name, groupIdx );
613     
614     if(affectsPrioritiesArray.count(std::string(name)) > 0 ) {
615       affectsPrioritiesArray[std::string(name)].insert(groupIdx);
616     } else {
617       std::set<int> s;
618       s.insert(groupIdx);
619       affectsPrioritiesArray[std::string(name)] = s;
620     }
621     
622 #if DEBUGPRINT   
623     std::map<std::string, std::set<int> >::iterator f;
624     for(f=affectsPrioritiesArray.begin(); f!=affectsPrioritiesArray.end();++f){
625       std::string name = f->first;
626       std::set<int> &vals = f->second;
627       cout << "Control point " << name << " affects arrays: ";
628       std::set<int>::iterator i;
629       for(i=vals.begin(); i!=vals.end();++i){
630         cout << *i << " ";
631       }
632       cout << endl;
633     }
634 #endif
635     
636   }
637   
638   /// Inform the control point framework that a named control point affects the priority of some entry method
639   void controlPointManager::associatePriorityEntry(const char *name, int idx){
640     CkPrintf("Associating control point \"%s\" with EP id=%d\n", name, idx);
641
642       if(affectsPrioritiesEP.count(std::string(name)) > 0 ) {
643       affectsPrioritiesEP[std::string(name)].insert(idx);
644     } else {
645       std::set<int> s;
646       s.insert(idx);
647       affectsPrioritiesEP[std::string(name)] = s;
648     }
649     
650 #if DEBUGPRINT
651     std::map<std::string, std::set<int> >::iterator f;
652     for(f=affectsPrioritiesEP.begin(); f!=affectsPrioritiesEP.end();++f){
653       std::string name = f->first;
654       std::set<int> &vals = f->second;
655       cout << "Control point " << name << " affects EP: ";
656       std::set<int>::iterator i;
657       for(i=vals.begin(); i!=vals.end();++i){
658         cout << *i << " ";
659       }
660       cout << endl;
661     }
662 #endif
663
664
665   }
666   
667
668
669 /// An interface callable by the application.
670 void gotoNextPhase(){
671   controlPointManagerProxy.ckLocalBranch()->gotoNextPhase();
672 }
673
674
675 /// A mainchare that is used just to create our controlPointManager group at startup
676 class controlPointMain : public CBase_controlPointMain {
677 public:
678   controlPointMain(CkArgMsg* args){
679 #if OLDRANDSEED
680     struct timeval tp;
681     gettimeofday(& tp, NULL);
682     random_seed = (int)tp.tv_usec ^ (int)tp.tv_sec;
683 #else
684     double time = CmiWallTimer();
685     int sec = (int)time;
686     int usec = (int)((time - (double)sec)*1000000.0);
687     random_seed =  sec ^ usec;
688 #endif
689
690
691     double period;
692     bool found = CmiGetArgDoubleDesc(args->argv,"+CPSamplePeriod", &period,"The time between Control Point Framework samples (in seconds)");
693     if(found){
694       CkPrintf("LBPERIOD = %ld sec\n", period);
695       controlPointSamplePeriod =  period * 1000;
696     } else {
697       controlPointSamplePeriod =  DEFAULT_CONTROL_POINT_SAMPLE_PERIOD;
698     }
699
700     controlPointManagerProxy = CProxy_controlPointManager::ckNew();
701   }
702   ~controlPointMain(){}
703 };
704
705 /// An interface callable by the application.
706 void registerGranularityChangeCallback(CkCallback cb, bool frameworkShouldAdvancePhase){
707   CkAssert(CkMyPe() == 0);
708   CkPrintf("registerGranularityChangeCallback\n");
709   controlPointManagerProxy.ckLocalBranch()->setGranularityCallback(cb, frameworkShouldAdvancePhase);
710 }
711
712 /// An interface callable by the application.
713 void registerControlPointTiming(double time){
714   CkAssert(CkMyPe() == 0);
715 #if DEBUGPRINT>0
716   CkPrintf("Program registering its own timing with registerControlPointTiming(time=%lf)\n", time);
717 #endif
718   controlPointManagerProxy.ckLocalBranch()->setTiming(time);
719 }
720
721 /// Shutdown the control point framework, writing data to disk if necessary
722 extern "C" void controlPointShutdown(){
723   CkAssert(CkMyPe() == 0);
724   CkPrintf("[%d] controlPointShutdown() at CkExit()\n", CkMyPe());
725   controlPointManagerProxy.ckLocalBranch()->writeDataFile();
726   CkExit();
727 }
728
729 /// A function called at startup on each node to register controlPointShutdown() to be called at CkExit()
730 void controlPointInitNode(){
731   CkPrintf("controlPointInitNode()\n");
732   registerExitFn(controlPointShutdown);
733 }
734
735 /// Called periodically to allow control point framework to do things periodically
736 static void periodicProcessControlPoints(void* ptr, double currWallTime){
737 #ifdef DEBUGPRINT
738   CkPrintf("[%d] periodicProcessControlPoints()\n", CkMyPe());
739 #endif
740   controlPointManagerProxy.ckLocalBranch()->processControlPoints();
741   CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, controlPointSamplePeriod, CkMyPe());
742 }
743
744
745
746
747
748 // Static point for life of program: randomly chosen, no optimizer
749 int staticPoint(const char *name, int lb, int ub){
750   instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
751   std::set<std::string> &staticControlPoints = controlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
752
753   int result = lb + randInt(ub-lb+1, name);
754   
755   controlPointManagerProxy.ckLocalBranch()->controlPointSpace.insert(std::make_pair(std::string(name),std::make_pair(lb,ub))); 
756   thisPhaseData.controlPoints.insert(std::make_pair(std::string(name),result)); 
757   staticControlPoints.insert(std::string(name));
758
759   return result;
760 }
761
762
763 /// Should an optimizer determine the control point values
764 bool valueShouldBeProvidedByOptimizer(){
765   
766   const int effective_phase = controlPointManagerProxy.ckLocalBranch()->allData.phases.size();
767   const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id; 
768   
769   std::map<std::string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace; 
770   
771   double spaceSize = 1.0;
772   std::map<std::string, pair<int,int> >::iterator iter;
773   for(iter = controlPointSpace.begin(); iter != controlPointSpace.end(); iter++){
774     spaceSize *= iter->second.second - iter->second.first + 1;
775   }
776
777   //  CkPrintf("Control Point Space:\n\t\tnumber of control points = %d\n\t\tnumber of possible configurations = %.0lf\n", controlPointSpace.size(), spaceSize);
778
779 #if 1
780   return false;
781 #elif 0
782   return effective_phase > 1 && phase_id > 1;
783 #else
784   return effective_phase >= OPTIMIZER_TRANSITION && phase_id > 3;
785 #endif
786 }
787
788
789
790
791
792 /// Determine a control point value using some optimization scheme (use max known, simmulated annealling, 
793 /// user observed characteristic to adapt specific control point values.
794 /// @note eventually there should be a plugin system where multiple schemes can be plugged in(similar to LB)
795 int valueProvidedByOptimizer(const char * name){
796   const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
797   const int effective_phase = controlPointManagerProxy.ckLocalBranch()->allData.phases.size();
798
799
800 #define OPTIMIZER_ADAPT_CRITICAL_PATHS 0
801 #define OPTIMIZER_USE_BEST_TIME 0
802 #define SIMULATED_ANNEALING 0
803 #define EXHAUSTIVE_SEARCH 1
804
805   // -----------------------------------------------------------
806 #if OPTIMIZER_ADAPT_CRITICAL_PATHS
807   // This scheme will return the median value for the range 
808   // early on, and then will transition over to the new control points
809   // determined by the critical path adapting code
810   if(controlPointManagerProxy.ckLocalBranch()->newControlPointsAvailable){
811     int result = controlPointManagerProxy.ckLocalBranch()->newControlPoints[std::string(name)];
812     CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d  from \"newControlPoints\" is: %d\n", name, phase_id, result);
813     return result;
814   } 
815   
816   std::map<std::string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;  
817
818   if(controlPointSpace.count(std::string(name))>0){
819     int minValue =  controlPointSpace[std::string(name)].first;
820     int maxValue =  controlPointSpace[std::string(name)].second;
821     return (minValue+maxValue)/2;
822   }
823   
824   // -----------------------------------------------------------
825 #elif OPTIMIZER_USE_BEST_TIME  
826   static bool firstTime = true;
827   if(firstTime){
828     firstTime = false;
829     CkPrintf("Finding best phase\n");
830     instrumentedPhase p = controlPointManagerProxy.ckLocalBranch()->allData.findBest(); 
831     CkPrintf("p=:\n");
832     p.print();
833     CkPrintf("\n");
834     controlPointManagerProxy.ckLocalBranch()->best_phase = p;
835   }
836   
837   
838   instrumentedPhase &p = controlPointManagerProxy.ckLocalBranch()->best_phase;
839   int result = p.controlPoints[std::string(name)];
840   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen out of best previous phase to be: %d\n", name, phase_id, result);
841   return result;
842
843   // -----------------------------------------------------------
844 #elsif SIMULATED_ANNEALING
845   
846   // Simulated Annealing style hill climbing method
847   //
848   // Find the best search space configuration, and try something
849   // nearby it, with a radius decreasing as phases increase
850   
851   std::map<std::string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;  
852   
853   CkPrintf("Finding best phase\n"); 
854   instrumentedPhase p = controlPointManagerProxy.ckLocalBranch()->allData.findBest();  
855   CkPrintf("best found:\n"); 
856   p.print(); 
857   CkPrintf("\n"); 
858   
859   int before = p.controlPoints[std::string(name)];   
860   
861   int minValue =  controlPointSpace[std::string(name)].first;
862   int maxValue =  controlPointSpace[std::string(name)].second;
863   
864   int convergeByPhase = 100;
865   
866   // Determine from 0.0 to 1.0 how far along we are
867   double progress = (double) min(effective_phase, convergeByPhase) / (double)convergeByPhase;
868   
869   int range = (maxValue-minValue+1)*(1.0-progress);
870
871   CkPrintf("========================== Hill climbing progress = %lf  range=%d\n", progress, range); 
872
873   int high = min(before+range, maxValue);
874   int low = max(before-range, minValue);
875   
876   int result = low;
877
878   if(high-low > 0){
879     result += randInt(high-low, name, phase_id); 
880   } 
881
882   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen by hill climbing to be: %d\n", name, phase_id, result); 
883   return result; 
884
885   // -----------------------------------------------------------
886 #elif EXHAUSTIVE_SEARCH
887   // Exhaustive search 
888
889   std::map<std::string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;
890   std::set<std::string> &staticControlPoints = controlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
891    
892   int numDimensions = controlPointSpace.size();
893   CkAssert(numDimensions > 0);
894   
895   vector<int> lowerBounds(numDimensions);
896   vector<int> upperBounds(numDimensions); 
897   
898   int d=0;
899   std::map<std::string, pair<int,int> >::iterator iter;
900   for(iter = controlPointSpace.begin(); iter != controlPointSpace.end(); iter++){
901     //    CkPrintf("Examining dimension %d\n", d);
902
903 #if DEBUGPRINT
904     std::string name = iter->first;
905     if(staticControlPoints.count(name) >0 ){
906       cout << " control point " << name << " is static " << endl;
907     } else{
908       cout << " control point " << name << " is not static " << endl;
909     }
910 #endif
911
912     lowerBounds[d] = iter->second.first;
913     upperBounds[d] = iter->second.second;
914     d++;
915   }
916    
917
918   vector<std::string> s(numDimensions);
919   d=0;
920   for(std::map<std::string, pair<int,int> >::iterator niter=controlPointSpace.begin(); niter!=controlPointSpace.end(); niter++){
921     s[d] = niter->first;
922     // cout << "s[" << d << "]=" << s[d] << endl;
923     d++;
924   }
925   
926   
927   // Create the first possible configuration
928   vector<int> config = lowerBounds;
929   config.push_back(0);
930   
931   // Increment until finding an unused configuration
932   controlPointManagerProxy.ckLocalBranch()->allData.cleanupNames(); // put -1 values in for any control points missing
933   std::vector<instrumentedPhase> &phases = controlPointManagerProxy.ckLocalBranch()->allData.phases;     
934
935   while(true){
936     
937     std::vector<instrumentedPhase>::iterator piter; 
938     bool testedConfiguration = false; 
939     for(piter = phases.begin(); piter != phases.end(); piter++){ 
940       
941       // Test if the configuration matches this phase
942       bool match = true;
943       for(int j=0;j<numDimensions;j++){
944         match &= piter->controlPoints[s[j]] == config[j];
945       }
946       
947       if(match){
948         testedConfiguration = true; 
949         break;
950       } 
951     } 
952     
953     if(testedConfiguration == false){ 
954       break;
955     } 
956     
957     // go to next configuration
958     config[0] ++;
959     // Propagate "carrys"
960     for(int i=0;i<numDimensions;i++){
961       if(config[i] > upperBounds[i]){
962         config[i+1]++;
963         config[i] = lowerBounds[i];
964       }
965     }
966     // check if we have exhausted all possible values
967     if(config[numDimensions] > 0){
968       break;
969     }
970        
971   }
972   
973   if(config[numDimensions] > 0){
974     for(int i=0;i<numDimensions;i++){ 
975       config[i]= (lowerBounds[i]+upperBounds[i]) / 2;
976     }
977   }
978   
979   
980   int result=-1;  
981
982   std::string name_s(name);
983   for(int i=0;i<numDimensions;i++){
984     //    cout << "Comparing " << name_s <<  " with s[" << i << "]=" << s[i] << endl;
985     if(name_s.compare(s[i]) == 0){
986       result = config[i];
987     }
988   }
989
990   CkAssert(result != -1);
991
992
993   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen by exhaustive search to be: %d\n", name, phase_id, result); 
994   return result; 
995 #else
996 #error You need to enable some scheme in valueProvidedByOptimizer()
997 #endif
998
999 CkAbort("valueProvidedByOptimizer(): ERROR: could not find a value for a control point.\n");
1000 return 0;
1001   
1002 }
1003
1004
1005
1006
1007
1008 #define isInRange(v,a,b) ( ((v)<=(a)&&(v)>=(b)) || ((v)<=(b)&&(v)>=(a)) )
1009
1010
1011 // Dynamic point varies throughout the life of program
1012 // The value it returns is based upon phase_id, a counter that changes for each phase of computation
1013 int controlPoint2Pow(const char *name, int fine_granularity, int coarse_granularity){
1014   instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
1015   const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
1016
1017   int result;
1018
1019   // Use best configuration after a certain point
1020   if(valueShouldBeProvidedByOptimizer()){
1021     result = valueProvidedByOptimizer(name);
1022   } 
1023   else {
1024
1025     int l1 = (int)CmiLog2(fine_granularity);
1026     int l2 = (int)CmiLog2(coarse_granularity);
1027   
1028     if (l1 > l2){
1029       int tmp;
1030       tmp = l2;
1031       l2 = l1; 
1032       l1 = tmp;
1033     }
1034     CkAssert(l1 <= l2);
1035     
1036     int l = l1 + randInt(l2-l1+1,name, phase_id);
1037
1038     result = 1 << l;
1039
1040     CkAssert(isInRange(result,fine_granularity,coarse_granularity));
1041     CkPrintf("Control Point \"%s\" for phase %d chosen randomly to be: %d\n", name, phase_id, result);
1042   }
1043
1044   thisPhaseData.controlPoints.insert(std::make_pair(std::string(name),result));
1045
1046   return result;
1047 }
1048
1049
1050 /// Get control point value from range of integers [lb,ub]
1051 int controlPoint(const char *name, int lb, int ub){
1052   instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
1053   const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
1054   std::map<std::string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;
1055
1056   int result;
1057
1058   // Use best configuration after a certain point
1059   if(valueShouldBeProvidedByOptimizer()){
1060     result = valueProvidedByOptimizer(name);
1061   } 
1062   else {
1063     result = lb + randInt(ub-lb+1, name, phase_id);
1064     CkPrintf("Control Point \"%s\" for phase %d chosen randomly to be: %d\n", name, phase_id, result); 
1065   } 
1066    
1067   CkAssert(isInRange(result,ub,lb));
1068   thisPhaseData.controlPoints.insert(std::make_pair(std::string(name),result)); 
1069   controlPointSpace.insert(std::make_pair(std::string(name),std::make_pair(lb,ub))); 
1070   //  CkPrintf("Inserting control point value to thisPhaseData.controlPoints with value %d; thisPhaseData.controlPoints.size=%d\n", result, thisPhaseData.controlPoints.size());
1071   return result;
1072 }
1073
1074 /// Get control point value from set of provided integers
1075 int controlPoint(const char *name, std::vector<int>& values){
1076   instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
1077   const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
1078
1079   int result;
1080   if(valueShouldBeProvidedByOptimizer()){
1081     result = valueProvidedByOptimizer(name);
1082   } 
1083   else { 
1084     result = values[randInt(values.size(), name, phase_id)];
1085   }
1086
1087   bool found = false;
1088   for(int i=0;i<values.size();i++){
1089     if(values[i] == result)
1090       found = true;
1091   }
1092   CkAssert(found);
1093
1094   thisPhaseData.controlPoints.insert(std::make_pair(std::string(name),result)); 
1095   return result;
1096 }
1097
1098
1099
1100
1101 /// Inform the control point framework that a named control point affects the priorities of some array  
1102 void controlPointPriorityArray(const char *name, CProxy_ArrayBase &arraybase){
1103   CkGroupID aid = arraybase.ckGetArrayID();
1104   int groupIdx = aid.idx;
1105   controlPointManagerProxy.ckLocalBranch()->associatePriorityArray(name, groupIdx);
1106   //  CkPrintf("Associating control point \"%s\" with array id=%d\n", name, groupIdx );
1107 }
1108
1109
1110 /// Inform the control point framework that a named control point affects the priorities of some entry method  
1111 void controlPointPriorityEntry(const char *name, int idx){
1112   controlPointManagerProxy.ckLocalBranch()->associatePriorityEntry(name, idx);
1113   //  CkPrintf("Associating control point \"%s\" with EP id=%d\n", name, idx);
1114 }
1115
1116
1117
1118 /*! @} */
1119
1120
1121 #include "ControlPoints.def.h"