4c85b792c9c9fb1fda7407a0e52051747a8608e8
[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 #include "cp_effects.h"
10
11
12 //  A framework for tuning "control points" exposed by an application. Tuning decisions are based upon observed performance measurements.
13  
14
15 /** @defgroup ControlPointFramework Automatic Performance Tuning and Steering Framework  */
16 /**  @{ */
17
18 using namespace std;
19
20 #define DEFAULT_CONTROL_POINT_SAMPLE_PERIOD  10000000
21 #define NUM_SAMPLES_BEFORE_TRANSISTION 5
22 #define OPTIMIZER_TRANSITION 5
23
24
25 //#undef DEBUGPRINT
26 //#define DEBUGPRINT 4
27
28 static void periodicProcessControlPoints(void* ptr, double currWallTime);
29
30
31 // A pointer to this PE's controlpoint manager Proxy
32 /* readonly */ CProxy_controlPointManager controlPointManagerProxy;
33 /* readonly */ int random_seed;
34 /* readonly */ long controlPointSamplePeriod;
35 /* readonly */ int whichTuningScheme;
36 /* readonly */ bool writeDataFileAtShutdown;
37 /* readonly */ bool loadDataFileAtStartup;
38 /* readonly */ bool shouldGatherMemoryUsage;
39 /* readonly */ bool shouldGatherUtilization;
40 /* readonly */ bool shouldGatherAll;
41
42
43
44 /// The control point values to be used for the first few phases if the strategy doesn't choose to do something else.
45 /// These probably come from the command line arguments, so are available only on PE 0
46 std::map<std::string, int> defaultControlPointValues;
47
48
49
50 typedef enum tuningSchemeEnum {RandomSelection, SimulatedAnnealing, ExhaustiveSearch, CriticalPathAutoPrioritization, UseBestKnownTiming, UseSteering, MemoryAware}  tuningScheme;
51
52
53
54 void printTuningScheme(){
55   switch(whichTuningScheme){
56   case RandomSelection:
57     CkPrintf("Tuning Scheme: RandomSelection\n");
58     break;
59   case SimulatedAnnealing:
60     CkPrintf("Tuning Scheme: SimulatedAnnealing\n");
61     break;
62   case ExhaustiveSearch:
63     CkPrintf("Tuning Scheme: ExhaustiveSearch\n");
64     break;
65   case CriticalPathAutoPrioritization:
66     CkPrintf("Tuning Scheme: CriticalPathAutoPrioritization\n");
67     break;
68   case UseBestKnownTiming:
69     CkPrintf("Tuning Scheme: UseBestKnownTiming\n");
70     break;
71   case UseSteering:
72     CkPrintf("Tuning Scheme: UseSteering\n");
73     break;
74   case MemoryAware:
75     CkPrintf("Tuning Scheme: MemoryAware\n");
76     break;
77   default:
78     CkPrintf("Unknown tuning scheme\n");
79     break;
80   }
81   fflush(stdout);
82 }
83
84
85
86 /// A reduction type that combines idle time measurements (min/sum/max etc.)
87 CkReduction::reducerType idleTimeReductionType;
88 /// A reducer that combines idle time measurements (min/sum/max etc.)
89 CkReductionMsg *idleTimeReduction(int nMsg,CkReductionMsg **msgs){
90   double ret[3];
91   if(nMsg > 0){
92     CkAssert(msgs[0]->getSize()==3*sizeof(double));
93     double *m=(double *)msgs[0]->getData();
94     ret[0]=m[0];
95     ret[1]=m[1];
96     ret[2]=m[2];
97   }
98   for (int i=1;i<nMsg;i++) {
99     CkAssert(msgs[i]->getSize()==3*sizeof(double));
100     double *m=(double *)msgs[i]->getData();
101     ret[0]=min(ret[0],m[0]);
102     ret[1]+=m[1];
103     ret[2]=max(ret[2],m[2]);
104   }  
105   return CkReductionMsg::buildNew(3*sizeof(double),ret);   
106 }
107
108
109
110 /// A reduction type that combines idle, overhead, and memory measurements
111 CkReduction::reducerType allMeasuresReductionType;
112 /// A reducer that combines idle, overhead, and memory measurements
113 CkReductionMsg *allMeasuresReduction(int nMsg,CkReductionMsg **msgs){
114   double ret[7];
115   if(nMsg > 0){
116     CkAssert(msgs[0]->getSize()==7*sizeof(double));
117     double *m=(double *)msgs[0]->getData();
118     ret[0]=m[0];
119     ret[1]=m[1];
120     ret[2]=m[2];
121     ret[3]=m[3];
122     ret[4]=m[4];
123     ret[5]=m[5];
124     ret[6]=m[6];
125   }
126   for (int i=1;i<nMsg;i++) {
127     CkAssert(msgs[i]->getSize()==7*sizeof(double));
128     double *m=(double *)msgs[i]->getData();
129     // idle time (min/sum/max)
130     ret[0]=min(ret[0],m[0]);
131     ret[1]+=m[1];
132     ret[2]=max(ret[2],m[2]);
133     // overhead time (min/sum/max)
134     ret[3]=min(ret[3],m[3]);
135     ret[4]+=m[4];
136     ret[5]=max(ret[5],m[5]);
137     // mem usage (max)
138     ret[6]=max(ret[6],m[6]);
139   }  
140   return CkReductionMsg::buildNew(7*sizeof(double),ret);   
141 }
142
143
144 /// Registers the control point framework's reduction handlers at startup on each PE
145 /*initproc*/ void registerCPReductions(void) {
146   idleTimeReductionType=CkReduction::addReducer(idleTimeReduction);
147   allMeasuresReductionType=CkReduction::addReducer(allMeasuresReduction);
148 }
149
150
151
152
153
154
155 /// Return an integer between 0 and num-1 inclusive
156 /// If different seed, name, and random_seed values are provided, the returned values are pseudo-random
157 unsigned int randInt(unsigned int num, const char* name, int seed=0){
158   CkAssert(num > 0);
159   CkAssert(num < 1000);
160
161   unsigned long hash = 0;
162   unsigned int c;
163   unsigned char * str = (unsigned char*)name;
164
165   while (c = *str++){
166     unsigned int c2 = (c+64)%128;
167     unsigned int c3 = (c2*5953)%127;
168     hash = c3 + (hash << 6) + (hash << 16) - hash;
169   }
170
171   unsigned long shuffled1 = (hash*2083)%7907;
172   unsigned long shuffled2 = (seed*4297)%2017;
173
174   unsigned long shuffled3 = (random_seed*4799)%7919;
175
176   unsigned int namehash = shuffled3 ^ shuffled1 ^ shuffled2;
177
178   unsigned int result = ((namehash * 6029) % 1117) % num;
179
180   CkAssert(result >=0 && result < num);
181   return result;
182 }
183
184
185
186 controlPointManager::controlPointManager(){
187   generatedPlanForStep = -1;
188
189     exitWhenReady = false;
190     alreadyRequestedMemoryUsage = false;   
191     alreadyRequestedIdleTime = false;
192     alreadyRequestedAll = false;
193     
194     instrumentedPhase * newPhase = new instrumentedPhase();
195     allData.phases.push_back(newPhase);   
196     
197     dataFilename = (char*)malloc(128);
198     sprintf(dataFilename, "controlPointData.txt");
199     
200     frameworkShouldAdvancePhase = false;
201     haveGranularityCallback = false;
202 //    CkPrintf("[%d] controlPointManager() Constructor Initializing control points, and loading data file\n", CkMyPe());
203     
204     ControlPoint::initControlPointEffects();
205
206     phase_id = 0;
207
208     if(loadDataFileAtStartup){    
209       loadDataFile();
210     }
211
212     
213     if(CkMyPe() == 0){
214       CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, controlPointSamplePeriod, CkMyPe());
215     }
216
217     traceRegisterUserEvent("No currently executing message", 5000);
218     traceRegisterUserEvent("Zero time along critical path", 5010);
219     traceRegisterUserEvent("Positive total time along critical path", 5020);
220     traceRegisterUserEvent("env->setPathHistory()", 6000);
221     traceRegisterUserEvent("Critical Path", 5900);
222     traceRegisterUserEvent("Table Entry", 5901);
223
224
225 #if USER_EVENT_FOR_REGISTERTERMINALPATH
226     traceRegisterUserEvent("registerTerminalPath", 100); 
227 #endif
228
229   }
230   
231
232  controlPointManager::~controlPointManager(){
233 //    CkPrintf("[%d] controlPointManager() Destructor\n", CkMyPe());
234   }
235
236
237   /// Loads the previous run data file
238   void controlPointManager::loadDataFile(){
239     ifstream infile(dataFilename);
240     vector<std::string> names;
241     std::string line;
242   
243     while(getline(infile,line)){
244       if(line[0] != '#')
245         break;
246     }
247   
248     int numTimings = 0;
249     std::istringstream n(line);
250     n >> numTimings;
251   
252     while(getline(infile,line)){ 
253       if(line[0] != '#') 
254         break; 
255     }
256
257     int numControlPointNames = 0;
258     std::istringstream n2(line);
259     n2 >> numControlPointNames;
260   
261     for(int i=0; i<numControlPointNames; i++){
262       getline(infile,line);
263       names.push_back(line);
264     }
265
266     for(int i=0;i<numTimings;i++){
267       getline(infile,line);
268       while(line[0] == '#')
269         getline(infile,line); 
270
271       instrumentedPhase * ips = new instrumentedPhase();
272
273       std::istringstream iss(line);
274
275       // Read memory usage for phase
276       iss >> ips->memoryUsageMB;
277       //     CkPrintf("Memory usage loaded from file: %d\n", ips.memoryUsageMB);
278
279       iss >> ips->idleTime.min;
280       iss >> ips->idleTime.avg;
281       iss >> ips->idleTime.max;
282
283       // Read control point values
284       for(int cp=0;cp<numControlPointNames;cp++){
285         int cpvalue;
286         iss >> cpvalue;
287         ips->controlPoints.insert(make_pair(names[cp],cpvalue));
288       }
289
290       double time;
291
292       while(iss >> time){
293         ips->times.push_back(time);
294 #if DEBUGPRINT > 5
295         CkPrintf("read time %lf from file\n", time);
296 #endif
297       }
298
299       allData.phases.push_back(ips);
300
301     }
302
303     infile.close();
304   }
305
306
307
308   /// Add the current data to allData and output it to a file
309   void controlPointManager::writeDataFile(){
310     CkPrintf("============= writeDataFile() ============\n");
311     ofstream outfile(dataFilename);
312     allData.cleanupNames();
313
314     //  string s = allData.toString();
315     //  CkPrintf("At end: \n %s\n", s.c_str());
316
317     allData.verify();
318     allData.filterOutIncompletePhases();
319
320     outfile << allData.toString();
321     outfile.close();
322   }
323
324   /// User can register a callback that is called when application should advance to next phase
325   void controlPointManager::setCPCallback(CkCallback cb, bool _frameworkShouldAdvancePhase){
326     frameworkShouldAdvancePhase = _frameworkShouldAdvancePhase;
327     granularityCallback = cb;
328     haveGranularityCallback = true;
329   }
330
331   /// Called periodically by the runtime to handle the control points
332   /// Currently called on each PE
333   void controlPointManager::processControlPoints(){
334
335     CkPrintf("[%d] processControlPoints() haveGranularityCallback=%d frameworkShouldAdvancePhase=%d\n", CkMyPe(), (int)haveGranularityCallback, (int)frameworkShouldAdvancePhase);
336
337
338     //==========================================================================================
339     // Print the data for each phase
340
341     const int s = allData.phases.size();
342
343 #if DEBUGPRINT
344     CkPrintf("\n\nExamining critical paths and priorities and idle times (num phases=%d)\n", s );
345     for(int p=0;p<s;++p){
346       const instrumentedPhase &phase = allData.phases[p];
347       const idleTimeContainer &idle = phase.idleTime;
348       //      vector<MergeablePathHistory> const &criticalPaths = phase.criticalPaths;
349       vector<double> const &times = phase.times;
350
351       CkPrintf("Phase %d:\n", p);
352       idle.print();
353      //   CkPrintf("critical paths: (* affected by control point)\n");
354         //   for(int i=0;i<criticalPaths.size(); i++){
355         // If affected by a control point
356         //      criticalPaths[i].print();
357
358       //        criticalPaths[i].print();
359       //        CkPrintf("\n");
360         
361
362       //   }
363       CkPrintf("Timings:\n");
364       for(int i=0;i<times.size(); i++){
365         CkPrintf("%lf ", times[i]);
366       }
367       CkPrintf("\n");
368
369     }
370     
371     CkPrintf("\n\n");
372
373
374 #endif
375
376
377
378     //==========================================================================================
379     // If this is a phase during which we try to adapt control point values based on critical path
380 #if 0
381
382     if( s%5 == 4) {
383
384       // Find the most recent phase with valid critical path data and idle time measurements      
385       int whichPhase=-1;
386       for(int p=0; p<s; ++p){
387         const instrumentedPhase &phase = allData.phases[p];
388         const idleTimeContainer &idle = phase.idleTime;
389         if(idle.isValid() && phase.criticalPaths.size()>0 ){
390           whichPhase = p;
391         }
392       }
393       
394       
395       CkPrintf("Examining phase %d which has a valid idle time and critical paths\n", whichPhase);
396       const instrumentedPhase &phase = allData.phases[whichPhase];
397       const idleTimeContainer &idle = phase.idleTime;
398       
399       if(idle.min > 0.1){
400         CkPrintf("Min PE idle is HIGH. %.2lf%% > 10%%\n", idle.min*100.0);
401         
402         // Determine the median critical path for this phase
403         int medianCriticalPathIdx = phase.medianCriticalPathIdx();
404         const PathHistory &path = phase.criticalPaths[medianCriticalPathIdx];
405         CkAssert(phase.criticalPaths.size() > 0);
406         CkAssert(phase.criticalPaths.size() > medianCriticalPathIdx); 
407         
408         CkPrintf("Median Critical Path has time %lf\n", path.getTotalTime());
409         
410         if(phase.times[medianCriticalPathIdx] > 1.2 * path.getTotalTime()){
411           CkPrintf("The application step(%lf) is taking significantly longer than the critical path(%lf). BAD\n",phase.times[medianCriticalPathIdx], path.getTotalTime() );
412
413
414           CkPrintf("Finding control points related to the critical path\n");
415           int cpcount = 0;
416           std::set<std::string> controlPointsAffectingCriticalPath;
417
418           
419           for(int e=0;e<path.getNumUsed();e++){
420             if(path.getUsedCount(e)>0){
421               int ep = path.getUsedEp(e);
422
423               std::map<std::string, std::set<int> >::iterator iter;
424               for(iter=affectsPrioritiesEP.begin(); iter!= affectsPrioritiesEP.end(); ++iter){
425                 if(iter->second.count(ep)>0){
426                   controlPointsAffectingCriticalPath.insert(iter->first);
427                   CkPrintf("Control Point \"%s\" affects the critical path\n", iter->first.c_str());
428                   cpcount++;
429                 }
430               }
431               
432             }
433           }
434           
435
436           if(cpcount==0){
437             CkPrintf("No control points are known to affect the critical path\n");
438           } else {
439             double beginTime = CmiWallTimer();
440
441             CkPrintf("Attempting to modify control point values for %d control points that affect the critical path\n", controlPointsAffectingCriticalPath.size());
442             
443             newControlPoints = phase.controlPoints;
444             
445             if(frameworkShouldAdvancePhase){
446               gotoNextPhase();  
447             }
448             
449             if(haveGranularityCallback){ 
450 #if DEBUGPRINT
451               CkPrintf("Calling granularity change callback\n");
452 #endif
453               controlPointMsg *msg = new(0) controlPointMsg;
454               granularityCallback.send(msg);
455             }
456             
457             
458             // adjust the control points that can affect the critical path
459
460             char textDescription[4096*2];
461             textDescription[0] = '\0';
462
463             std::map<std::string,int>::iterator newCP;
464             for(newCP = newControlPoints.begin(); newCP != newControlPoints.end(); ++ newCP){
465               if( controlPointsAffectingCriticalPath.count(newCP->first) > 0 ){
466                 // decrease the value (increase priority) if within range
467                 int lowerbound = controlPointSpace[newCP->first].first;
468                 if(newCP->second > lowerbound){
469                   newControlPointsAvailable = true;
470                   newCP->second --;
471                 }
472               }
473             }
474            
475             // Create a string for a projections user event
476             if(1){
477               std::map<std::string,int>::iterator newCP;
478               for(newCP = newControlPoints.begin(); newCP != newControlPoints.end(); ++ newCP){
479                 sprintf(textDescription+strlen(textDescription), "<br>\"%s\"=%d", newCP->first.c_str(), newCP->second);
480               }
481             }
482
483             char *userEventString = new char[4096*2];
484             sprintf(userEventString, "Adjusting control points affecting critical path: %s ***", textDescription);
485             
486             static int userEventCounter = 20000;
487             CkPrintf("USER EVENT: %s\n", userEventString);
488             
489             traceRegisterUserEvent(userEventString, userEventCounter); 
490             traceUserBracketEvent(userEventCounter, beginTime, CmiWallTimer());
491             userEventCounter++;
492             
493           }
494           
495         } else {
496           CkPrintf("The application step(%lf) is dominated mostly by the critical path(%lf). GOOD\n",phase.times[medianCriticalPathIdx], path.getTotalTime() );
497         }
498         
499         
500       }
501       
502     } else {
503       
504       
505     }
506     
507
508 #endif
509
510
511
512     if(frameworkShouldAdvancePhase){
513       gotoNextPhase();  
514     }
515     
516     if(haveGranularityCallback){ 
517       controlPointMsg *msg = new(0) controlPointMsg;
518       granularityCallback.send(msg);
519     }
520     
521     
522     
523   }
524   
525   /// Determine if any control point is known to affect an entry method
526   bool controlPointManager::controlPointAffectsThisEP(int ep){
527     std::map<std::string, std::set<int> >::iterator iter;
528     for(iter=affectsPrioritiesEP.begin(); iter!= affectsPrioritiesEP.end(); ++iter){
529       if(iter->second.count(ep)>0){
530         return true;
531       }
532     }
533     return false;    
534   }
535   
536   /// Determine if any control point is known to affect a chare array  
537   bool controlPointManager::controlPointAffectsThisArray(int array){
538     std::map<std::string, std::set<int> >::iterator iter;
539     for(iter=affectsPrioritiesArray.begin(); iter!= affectsPrioritiesArray.end(); ++iter){
540       if(iter->second.count(array)>0){
541         return true;
542       }
543     }
544     return false;   
545   }
546   
547
548   /// The data from the current phase
549   instrumentedPhase * controlPointManager::currentPhaseData(){
550     int s = allData.phases.size();
551     CkAssert(s>=1);
552     return allData.phases[s-1];
553   }
554  
555
556   /// The data from the previous phase
557   instrumentedPhase * controlPointManager::previousPhaseData(){
558     int s = allData.phases.size();
559     if(s >= 2 && phase_id > 0) {
560       return allData.phases[s-2];
561     } else {
562       return NULL;
563     }
564   }
565  
566   /// The data from two phases back
567   instrumentedPhase * controlPointManager::twoAgoPhaseData(){
568     int s = allData.phases.size();
569     if(s >= 3 && phase_id > 0) {
570       return allData.phases[s-3];
571     } else {
572       return NULL;
573     }
574   }
575   
576
577   /// Called by either the application or the Control Point Framework to advance to the next phase  
578   void controlPointManager::gotoNextPhase(){
579     
580     CkPrintf("gotoNextPhase shouldGatherAll=%d\n", (int)shouldGatherAll);
581     fflush(stdout);
582
583     if(shouldGatherAll && CkMyPe() == 0 && !alreadyRequestedAll){
584       alreadyRequestedAll = true;
585       CkCallback *cb = new CkCallback(CkIndex_controlPointManager::gatherAll(NULL), 0, thisProxy);
586       CkPrintf("Requesting all measurements\n");
587       thisProxy.requestAll(*cb);
588       delete cb;
589     
590     } else {
591       
592       if(shouldGatherMemoryUsage && CkMyPe() == 0 && !alreadyRequestedMemoryUsage){
593         alreadyRequestedMemoryUsage = true;
594         CkCallback *cb = new CkCallback(CkIndex_controlPointManager::gatherMemoryUsage(NULL), 0, thisProxy);
595         thisProxy.requestMemoryUsage(*cb);
596         delete cb;
597       }
598       
599       if(shouldGatherUtilization && CkMyPe() == 0 && !alreadyRequestedIdleTime){
600         alreadyRequestedIdleTime = true;
601         CkCallback *cb = new CkCallback(CkIndex_controlPointManager::gatherIdleTime(NULL), 0, thisProxy);
602         thisProxy.requestIdleTime(*cb);
603         delete cb;
604       }
605     }
606     
607
608
609
610
611     LBDatabase * myLBdatabase = LBDatabaseObj();
612
613 #if CMK_LBDB_ON && 0
614     LBDB * myLBDB = myLBdatabase->getLBDB();       // LBDB is Defined in LBDBManager.h
615     const CkVec<LBObj*> objs = myLBDB->getObjs();
616     const int objCount = myLBDB->getObjCount();
617     CkPrintf("LBDB info: objCount=%d objs contains %d LBObj* \n", objCount, objs.length());
618     
619     floatType maxObjWallTime = -1.0;
620     
621     for(int i=0;i<objs.length();i++){
622       LBObj* o = objs[i];
623       const LDObjData d = o->ObjData();
624       floatType cpuTime = d.cpuTime;
625       floatType wallTime = d.wallTime;
626       // can also get object handles from the LDObjData struct
627       CkPrintf("[%d] LBDB Object[%d]: cpuTime=%f wallTime=%f\n", CkMyPe(), i, cpuTime, wallTime);
628       if(wallTime > maxObjWallTime){
629
630       }
631       
632     }
633
634     myLBDB->ClearLoads(); // BUG: Probably very dangerous if we are actually using load balancing
635     
636 #endif    
637
638
639     
640     // increment phase id
641     phase_id++;
642     
643
644     // Create new entry for the phase we are starting now
645     instrumentedPhase * newPhase = new instrumentedPhase();
646     allData.phases.push_back(newPhase);
647     
648     CkPrintf("Now in phase %d allData.phases.size()=%d\n", phase_id, allData.phases.size());
649
650   }
651
652   /// An application uses this to register an instrumented timing for this phase
653   void controlPointManager::setTiming(double time){
654     currentPhaseData()->times.push_back(time);
655
656 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
657        
658     // First we should register this currently executing message as a path, because it is likely an important one to consider.
659     //    registerTerminalEntryMethod();
660     
661     // save the critical path for this phase
662     //   thisPhaseData.criticalPaths.push_back(maxTerminalPathHistory);
663     //    maxTerminalPathHistory.reset();
664     
665     
666     // Reset the counts for the currently executing message
667     //resetThisEntryPath();
668         
669 #endif
670     
671   }
672   
673   /// Entry method called on all PEs to request CPU utilization statistics
674   void controlPointManager::requestIdleTime(CkCallback cb){
675     double i = localControlPointTracingInstance()->idleRatio();
676     double idle[3];
677     idle[0] = i;
678     idle[1] = i;
679     idle[2] = i;
680     
681     //    CkPrintf("[%d] idleRatio=%f\n", CkMyPe(), i);
682     
683     localControlPointTracingInstance()->resetTimings();
684
685     contribute(3*sizeof(double),idle,idleTimeReductionType, cb);
686   }
687   
688   /// All processors reduce their memory usages in requestIdleTime() to this method
689   void controlPointManager::gatherIdleTime(CkReductionMsg *msg){
690     int size=msg->getSize() / sizeof(double);
691     CkAssert(size==3);
692     double *r=(double *) msg->getData();
693         
694     instrumentedPhase* prevPhase = previousPhaseData();
695     if(prevPhase != NULL){
696       prevPhase->idleTime.min = r[0];
697       prevPhase->idleTime.avg = r[1]/CkNumPes();
698       prevPhase->idleTime.max = r[2];
699       prevPhase->idleTime.print();
700       CkPrintf("Stored idle time min=%lf in prevPhase=%p\n", prevPhase->idleTime.min, prevPhase);
701     } else {
702       CkPrintf("There is no previous phase to store the idle time measurements\n");
703     }
704     
705     alreadyRequestedIdleTime = false;
706     checkForShutdown();
707     delete msg;
708   }
709
710
711
712
713
714
715   /// Entry method called on all PEs to request CPU utilization statistics and memory usage
716   void controlPointManager::requestAll(CkCallback cb){
717     const double i = localControlPointTracingInstance()->idleRatio();
718     const double o = localControlPointTracingInstance()->overheadRatio();
719     const double m = localControlPointTracingInstance()->memoryUsageMB();
720     
721     double data[3+3+1];
722
723     double *idle = data;
724     double *over = data+3;
725     double *mem = data+6;
726
727     idle[0] = i;
728     idle[1] = i;
729     idle[2] = i;
730
731     over[0] = o;
732     over[1] = o;
733     over[2] = o;
734
735     mem[0] = m;
736     
737     localControlPointTracingInstance()->resetAll();
738
739     contribute(7*sizeof(double),data,allMeasuresReductionType, cb);
740   }
741   
742   /// All processors reduce their memory usages in requestIdleTime() to this method
743   void controlPointManager::gatherAll(CkReductionMsg *msg){
744     int size=msg->getSize() / sizeof(double);
745     CkAssert(size==7);
746     double *data=(double *) msg->getData();
747         
748     double *idle = data;
749     double *over = data+3;
750     double *mem = data+6;
751
752     //    std::string b = allData.toString();
753
754     instrumentedPhase* prevPhase = previousPhaseData();
755     if(prevPhase != NULL){
756       prevPhase->idleTime.min = idle[0];
757       prevPhase->idleTime.avg = idle[1]/CkNumPes();
758       prevPhase->idleTime.max = idle[2];
759       
760       prevPhase->memoryUsageMB = mem[0];
761       
762       CkPrintf("Stored idle time min=%lf, mem=%lf in prevPhase=%p\n", (double)prevPhase->idleTime.min, (double)prevPhase->memoryUsageMB, prevPhase);
763
764       //      prevPhase->print();
765       // CkPrintf("prevPhase=%p number of timings=%d\n", prevPhase, prevPhase->times.size() );
766
767       //      std::string a = allData.toString();
768
769       //CkPrintf("Before:\n%s\nAfter:\n%s\n\n", b.c_str(), a.c_str());
770       
771     } else {
772       CkPrintf("There is no previous phase to store measurements\n");
773     }
774     
775     alreadyRequestedAll = false;
776     checkForShutdown();
777     delete msg;
778   }
779
780
781
782
783   void controlPointManager::checkForShutdown(){
784     if( exitWhenReady && !alreadyRequestedAll && !alreadyRequestedMemoryUsage && !alreadyRequestedIdleTime && CkMyPe()==0){
785       doExitNow();
786     }
787   }
788
789
790   void controlPointManager::exitIfReady(){
791      if( !alreadyRequestedMemoryUsage && !alreadyRequestedAll && !alreadyRequestedIdleTime && CkMyPe()==0){
792        CkPrintf("controlPointManager::exitIfReady exiting immediately\n");
793        doExitNow();
794      } else {
795        CkPrintf("controlPointManager::exitIfReady Delaying exiting\n");
796        exitWhenReady = true;
797      }
798   }
799
800
801
802   void controlPointManager::doExitNow(){
803     if(writeDataFileAtShutdown){
804       CkPrintf("[%d] controlPointShutdown() at CkExit()\n", CkMyPe());
805       controlPointManagerProxy.ckLocalBranch()->writeDataFile();
806     }
807     CkExit();
808   }
809
810
811   /// Entry method called on all PEs to request memory usage
812   void controlPointManager::requestMemoryUsage(CkCallback cb){
813     int m = CmiMaxMemoryUsage() / 1024 / 1024;
814     CmiResetMaxMemory();
815     //    CkPrintf("PE %d Memory Usage is %d MB\n",CkMyPe(), m);
816     contribute(sizeof(int),&m,CkReduction::max_int, cb);
817   }
818
819   /// All processors reduce their memory usages to this method
820   void controlPointManager::gatherMemoryUsage(CkReductionMsg *msg){
821     int size=msg->getSize() / sizeof(int);
822     CkAssert(size==1);
823     int *m=(int *) msg->getData();
824
825     CkPrintf("[%d] Max Memory Usage for all processors is %d MB\n", CkMyPe(), m[0]);
826     
827     instrumentedPhase* prevPhase = previousPhaseData();
828     if(prevPhase != NULL){
829       prevPhase->memoryUsageMB = m[0];
830     } else {
831       CkPrintf("No place to store memory usage");
832     }
833
834     alreadyRequestedMemoryUsage = false;
835     checkForShutdown();
836     delete msg;
837   }
838
839
840   /// Inform the control point framework that a named control point affects the priorities of some array  
841   void controlPointManager::associatePriorityArray(const char *name, int groupIdx){
842     CkPrintf("Associating control point \"%s\" affects priority of array id=%d\n", name, groupIdx );
843     
844     if(affectsPrioritiesArray.count(std::string(name)) > 0 ) {
845       affectsPrioritiesArray[std::string(name)].insert(groupIdx);
846     } else {
847       std::set<int> s;
848       s.insert(groupIdx);
849       affectsPrioritiesArray[std::string(name)] = s;
850     }
851     
852 #if DEBUGPRINT   
853     std::map<std::string, std::set<int> >::iterator f;
854     for(f=affectsPrioritiesArray.begin(); f!=affectsPrioritiesArray.end();++f){
855       std::string name = f->first;
856       std::set<int> &vals = f->second;
857       cout << "Control point " << name << " affects arrays: ";
858       std::set<int>::iterator i;
859       for(i=vals.begin(); i!=vals.end();++i){
860         cout << *i << " ";
861       }
862       cout << endl;
863     }
864 #endif
865     
866   }
867   
868   /// Inform the control point framework that a named control point affects the priority of some entry method
869   void controlPointManager::associatePriorityEntry(const char *name, int idx){
870     CkPrintf("Associating control point \"%s\" with EP id=%d\n", name, idx);
871
872       if(affectsPrioritiesEP.count(std::string(name)) > 0 ) {
873       affectsPrioritiesEP[std::string(name)].insert(idx);
874     } else {
875       std::set<int> s;
876       s.insert(idx);
877       affectsPrioritiesEP[std::string(name)] = s;
878     }
879     
880 #if DEBUGPRINT
881     std::map<std::string, std::set<int> >::iterator f;
882     for(f=affectsPrioritiesEP.begin(); f!=affectsPrioritiesEP.end();++f){
883       std::string name = f->first;
884       std::set<int> &vals = f->second;
885       cout << "Control point " << name << " affects EP: ";
886       std::set<int>::iterator i;
887       for(i=vals.begin(); i!=vals.end();++i){
888         cout << *i << " ";
889       }
890       cout << endl;
891     }
892 #endif
893
894
895   }
896   
897
898
899 /// An interface callable by the application.
900 void gotoNextPhase(){
901   controlPointManagerProxy.ckLocalBranch()->gotoNextPhase();
902 }
903
904
905 /// A mainchare that is used just to create our controlPointManager group at startup
906 class controlPointMain : public CBase_controlPointMain {
907 public:
908   controlPointMain(CkArgMsg* args){
909 #if OLDRANDSEED
910     struct timeval tp;
911     gettimeofday(& tp, NULL);
912     random_seed = (int)tp.tv_usec ^ (int)tp.tv_sec;
913 #else
914     double time = CmiWallTimer();
915     int sec = (int)time;
916     int usec = (int)((time - (double)sec)*1000000.0);
917     random_seed =  sec ^ usec;
918 #endif
919     
920     
921     double period;
922     bool haveSamplePeriod = CmiGetArgDoubleDesc(args->argv,"+CPSamplePeriod", &period,"The time between Control Point Framework samples (in seconds)");
923     if(haveSamplePeriod){
924       CkPrintf("LBPERIOD = %ld sec\n", period);
925       controlPointSamplePeriod =  period * 1000; /**< A readonly */
926     } else {
927       controlPointSamplePeriod =  DEFAULT_CONTROL_POINT_SAMPLE_PERIOD;
928     }
929     
930     
931     
932     whichTuningScheme = RandomSelection;
933
934
935     if( CmiGetArgFlagDesc(args->argv,"+CPSchemeRandom","Randomly Select Control Point Values") ){
936       whichTuningScheme = RandomSelection;
937     } else if ( CmiGetArgFlagDesc(args->argv,"+CPExhaustiveSearch","Exhaustive Search of Control Point Values") ){
938       whichTuningScheme = ExhaustiveSearch;
939     } else if ( CmiGetArgFlagDesc(args->argv,"+CPSimulAnneal","Simulated Annealing Search of Control Point Values") ){
940       whichTuningScheme = SimulatedAnnealing;
941     } else if ( CmiGetArgFlagDesc(args->argv,"+CPCriticalPathPrio","Use Critical Path to adapt Control Point Values") ){
942       whichTuningScheme = CriticalPathAutoPrioritization;
943     } else if ( CmiGetArgFlagDesc(args->argv,"+CPBestKnown","Use BestKnown Timing for Control Point Values") ){
944       whichTuningScheme = UseBestKnownTiming;
945     } else if ( CmiGetArgFlagDesc(args->argv,"+CPSteering","Use Steering to adjust Control Point Values") ){
946       whichTuningScheme = UseSteering;
947     } else if ( CmiGetArgFlagDesc(args->argv,"+CPMemoryAware", "Adjust control points to approach available memory") ){
948       whichTuningScheme = MemoryAware;
949     }
950
951     char *defValStr = NULL;
952     if( CmiGetArgStringDesc(args->argv, "+CPDefaultValues", &defValStr, "Specify the default control point values used for the first couple phases") ){
953       CkPrintf("You specified default value string: %s\n", defValStr);
954       
955       // Parse the string, looking for commas
956      
957
958       char *tok = strtok(defValStr, ",");
959       while (tok) {
960         // split on the equal sign
961         int len = strlen(tok);
962         char *eqsign = strchr(tok, '=');
963         if(eqsign != NULL && eqsign != tok){
964           *eqsign = '\0';
965           char *cpname = tok;
966           std::string cpName(tok);
967           char *cpDefVal = eqsign+1;      
968           int v=-1;
969           if(sscanf(cpDefVal, "%d", &v) == 1){
970             CkPrintf("Command Line Argument Specifies that Control Point \"%s\" defaults to %d\n", cpname, v);
971             CkAssert(CkMyPe() == 0); // can only access defaultControlPointValues on PE 0
972             defaultControlPointValues[cpName] = v;
973           }
974         }
975         tok = strtok(NULL, ",");
976       }
977
978     }
979
980     shouldGatherAll = false;
981     shouldGatherMemoryUsage = false;
982     shouldGatherUtilization = false;
983     
984     if ( CmiGetArgFlagDesc(args->argv,"+CPGatherAll","Gather all types of measurements for each phase") ){
985       shouldGatherAll = true;
986     } else {
987       if ( CmiGetArgFlagDesc(args->argv,"+CPGatherMemoryUsage","Gather memory usage after each phase") ){
988         shouldGatherMemoryUsage = true;
989       }
990       if ( CmiGetArgFlagDesc(args->argv,"+CPGatherUtilization","Gather utilization & Idle time after each phase") ){
991         shouldGatherUtilization = true;
992       }
993     }
994     
995     writeDataFileAtShutdown = false;   
996     if( CmiGetArgFlagDesc(args->argv,"+CPSaveData","Save Control Point timings & configurations at completion") ){
997       writeDataFileAtShutdown = true;
998     }
999
1000    loadDataFileAtStartup = false;   
1001     if( CmiGetArgFlagDesc(args->argv,"+CPLoadData","Load Control Point timings & configurations at startup") ){
1002       loadDataFileAtStartup = true;
1003     }
1004
1005
1006     controlPointManagerProxy = CProxy_controlPointManager::ckNew();
1007   }
1008   ~controlPointMain(){}
1009 };
1010
1011 /// An interface callable by the application.
1012 void registerCPChangeCallback(CkCallback cb, bool frameworkShouldAdvancePhase){
1013   CkAssert(CkMyPe() == 0);
1014   CkPrintf("Application has registered a control point change callback\n");
1015   controlPointManagerProxy.ckLocalBranch()->setCPCallback(cb, frameworkShouldAdvancePhase);
1016 }
1017
1018 /// An interface callable by the application.
1019 void registerControlPointTiming(double time){
1020   CkAssert(CkMyPe() == 0);
1021 #if DEBUGPRINT>0
1022   CkPrintf("Program registering its own timing with registerControlPointTiming(time=%lf)\n", time);
1023 #endif
1024   controlPointManagerProxy.ckLocalBranch()->setTiming(time);
1025 }
1026
1027 /// An interface callable by the application.
1028 void controlPointTimingStamp() {
1029   CkAssert(CkMyPe() == 0);
1030 #if DEBUGPRINT>0
1031   CkPrintf("Program registering its own timing with controlPointTimingStamp()\n", time);
1032 #endif
1033   
1034   static double prev_time = 0.0;
1035   double t = CmiWallTimer();
1036   double duration = t - prev_time;
1037   prev_time = t;
1038     
1039   controlPointManagerProxy.ckLocalBranch()->setTiming(duration);
1040 }
1041
1042 /// Shutdown the control point framework, writing data to disk if necessary
1043 extern "C" void controlPointShutdown(){
1044   if(CkMyPe() == 0){
1045
1046     // wait for gathering of idle time & memory usage to complete
1047     controlPointManagerProxy.ckLocalBranch()->exitIfReady();
1048
1049   }
1050 }
1051
1052 /// A function called at startup on each node to register controlPointShutdown() to be called at CkExit()
1053 void controlPointInitNode(){
1054 //  CkPrintf("controlPointInitNode()\n");
1055   registerExitFn(controlPointShutdown);
1056 }
1057
1058 /// Called periodically to allow control point framework to do things periodically
1059 static void periodicProcessControlPoints(void* ptr, double currWallTime){
1060 #ifdef DEBUGPRINT
1061   CkPrintf("[%d] periodicProcessControlPoints()\n", CkMyPe());
1062 #endif
1063   controlPointManagerProxy.ckLocalBranch()->processControlPoints();
1064   CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, controlPointSamplePeriod, CkMyPe());
1065 }
1066
1067
1068
1069
1070
1071 /// Determine a control point value using some optimization scheme (use max known, simmulated annealling, 
1072 /// user observed characteristic to adapt specific control point values.
1073 /// @note eventually there should be a plugin system where multiple schemes can be plugged in(similar to LB)
1074 void controlPointManager::generatePlan() {
1075   const int phase_id = this->phase_id;
1076   const int effective_phase = allData.phases.size();
1077
1078   // Only generate a plan once per phase
1079   if(generatedPlanForStep == phase_id) 
1080     return;
1081   generatedPlanForStep = phase_id;
1082  
1083   CkPrintf("Generating Plan for phase %d\n", phase_id); 
1084   printTuningScheme();
1085   
1086   if( whichTuningScheme == RandomSelection ){
1087     std::map<std::string, std::pair<int,int> >::const_iterator cpsIter;
1088     for(cpsIter=controlPointSpace.begin(); cpsIter != controlPointSpace.end(); ++cpsIter){
1089       const std::string &name = cpsIter->first;
1090       const std::pair<int,int> &bounds = cpsIter->second;
1091       const int lb = bounds.first;
1092       const int ub = bounds.second;
1093       newControlPoints[name] = lb + randInt(ub-lb+1, name.c_str(), phase_id);
1094     }
1095   } else if( whichTuningScheme == CriticalPathAutoPrioritization) {
1096     // -----------------------------------------------------------
1097     //  USE CRITICAL PATH TO ADJUST PRIORITIES
1098     //   
1099     // This scheme will return the median value for the range 
1100     // early on, and then will transition over to the new control points
1101     // determined by the critical path adapting code
1102
1103     // This won't work until the periodic function is fixed up a bit
1104
1105     std::map<std::string, std::pair<int,int> >::const_iterator cpsIter;
1106     for(cpsIter=controlPointSpace.begin(); cpsIter != controlPointSpace.end(); ++cpsIter){
1107       const std::string &name = cpsIter->first;
1108       const std::pair<int,int> &bounds = cpsIter->second;
1109       const int lb = bounds.first;
1110       const int ub = bounds.second;
1111       newControlPoints[name] =  (lb+ub)/2;
1112     }
1113
1114   } else if ( whichTuningScheme == MemoryAware ) {
1115
1116     // -----------------------------------------------------------
1117     //  STEERING BASED ON MEMORY USAGE
1118
1119     instrumentedPhase *twoAgoPhase = twoAgoPhaseData();
1120     instrumentedPhase *prevPhase = previousPhaseData();
1121  
1122     if(phase_id%4 == 0){
1123       CkPrintf("Steering (memory based) based on 2 phases ago:\n");
1124       twoAgoPhase->print();
1125       CkPrintf("\n");
1126       fflush(stdout);
1127       
1128       // See if memory usage is low:
1129       double memUsage = twoAgoPhase->memoryUsageMB;
1130       CkPrintf("Steering (memory based) encountered memory usage of (%f MB)\n", memUsage);
1131       fflush(stdout);
1132       if(memUsage < 1100.0 && memUsage > 0.0){ // Kraken has about 16GB and 12 cores per node
1133         CkPrintf("Steering (memory based) encountered low memory usage (%f) < 1200 \n", memUsage);
1134         CkPrintf("Steering (memory based) controlPointSpace.size()=\n", controlPointSpace.size());
1135         
1136         // Initialize plan to be the values from two phases ago (later we'll adjust this)
1137         std::map<std::string, std::pair<int,int> >::const_iterator cpsIter;
1138         for(cpsIter=controlPointSpace.begin(); cpsIter != controlPointSpace.end(); ++cpsIter){
1139           const std::string &name = cpsIter->first;
1140           const int& twoAgoValue =  twoAgoPhase->controlPoints[name];
1141           newControlPoints[name] = twoAgoValue;
1142         }
1143         CkPrintf("Steering (memory based) initialized plan\n");
1144         fflush(stdout);
1145
1146         // look for a possible control point knob to turn
1147         std::map<std::string, std::vector<std::pair<int, ControlPoint::ControlPointAssociation> > > &possibleCPsToTune = CkpvAccess(cp_effects)["MemoryConsumption"];
1148         
1149         // FIXME: assume for now that we just have one control point with the effect, and one direction to turn it
1150         bool found = false;
1151         std::string cpName;
1152         std::vector<std::pair<int, ControlPoint::ControlPointAssociation> > *info;
1153         std::map<std::string, std::vector<std::pair<int, ControlPoint::ControlPointAssociation> > >::iterator iter;
1154         for(iter = possibleCPsToTune.begin(); iter != possibleCPsToTune.end(); iter++){
1155           cpName = iter->first;
1156           info = &iter->second;
1157           found = true;
1158           break;
1159         }
1160
1161         // Adapt the control point value
1162         if(found){
1163           CkPrintf("Steering found knob to turn that should increase memory consumption\n");
1164           fflush(stdout);
1165           const int twoAgoValue =  twoAgoPhase->controlPoints[cpName];
1166           const int maxValue = controlPointSpace[cpName].second;
1167           
1168           if(twoAgoValue+1 <= maxValue){
1169             newControlPoints[cpName] = twoAgoValue+1; // increase from two phases back
1170           }
1171         }
1172         
1173       }
1174     }
1175
1176     CkPrintf("Steering (memory based) done for this phase\n");
1177     fflush(stdout);
1178
1179   } else if ( whichTuningScheme == UseBestKnownTiming ) {
1180
1181     // -----------------------------------------------------------
1182     //  USE BEST KNOWN TIME  
1183     static bool firstTime = true;
1184     if(firstTime){
1185       firstTime = false;
1186       instrumentedPhase *best = allData.findBest(); 
1187       CkPrintf("Best known phase is:\n");
1188       best->print();
1189       CkPrintf("\n");
1190       
1191       std::map<std::string, std::pair<int,int> >::const_iterator cpsIter;
1192       for(cpsIter=controlPointSpace.begin(); cpsIter != controlPointSpace.end(); ++cpsIter) {
1193         const std::string &name = cpsIter->first;
1194         newControlPoints[name] =  best->controlPoints[name];
1195       }
1196     }
1197
1198   } else if ( whichTuningScheme == UseSteering ) {
1199     // -----------------------------------------------------------
1200     //  STEERING BASED ON KNOWLEDGE
1201   
1202     // after 3 phases (and only on even steps), do steering performance. Otherwise, just use previous phase's configuration
1203     // plans are only generated after 3 phases
1204
1205     instrumentedPhase *twoAgoPhase = twoAgoPhaseData();
1206     instrumentedPhase *prevPhase = previousPhaseData();
1207  
1208     if(phase_id%4 == 0){
1209       CkPrintf("Steering based on 2 phases ago:\n");
1210       twoAgoPhase->print();
1211       CkPrintf("\n");
1212       fflush(stdout);
1213       
1214       // See if idle time is high:
1215       double idleTime = twoAgoPhase->idleTime.avg;
1216       CkPrintf("Steering encountered idle time (%f)\n", idleTime);
1217       fflush(stdout);
1218       if(idleTime > 0.10){
1219         CkPrintf("Steering encountered high idle time(%f) > 10%%\n", idleTime);
1220         CkPrintf("Steering controlPointSpace.size()=\n", controlPointSpace.size());
1221
1222         // Initialize plan to be the values from two phases ago (later we'll adjust this)
1223         std::map<std::string, std::pair<int,int> >::const_iterator cpsIter;
1224         for(cpsIter=controlPointSpace.begin(); cpsIter != controlPointSpace.end(); ++cpsIter){
1225           const std::string &name = cpsIter->first;
1226           const int& twoAgoValue =  twoAgoPhase->controlPoints[name];
1227           newControlPoints[name] = twoAgoValue;
1228         }
1229         CkPrintf("Steering initialized plan\n");
1230         fflush(stdout);
1231
1232         // look for a possible control point knob to turn
1233         std::map<std::string, std::vector<std::pair<int, ControlPoint::ControlPointAssociation> > > &possibleCPsToTune = CkpvAccess(cp_effects)["Concurrency"];
1234         
1235         // FIXME: assume for now that we just have one control point with the effect
1236         bool found = false;
1237         std::string cpName;
1238         std::vector<std::pair<int, ControlPoint::ControlPointAssociation> > *info;
1239         std::map<std::string, std::vector<std::pair<int, ControlPoint::ControlPointAssociation> > >::iterator iter;
1240         for(iter = possibleCPsToTune.begin(); iter != possibleCPsToTune.end(); iter++){
1241           cpName = iter->first;
1242           info = &iter->second;
1243           found = true;
1244           break;
1245         }
1246
1247         // Adapt the control point value
1248         if(found){
1249           CkPrintf("Steering found knob to turn\n");
1250           fflush(stdout);
1251           const int twoAgoValue =  twoAgoPhase->controlPoints[cpName];
1252           const int maxValue = controlPointSpace[cpName].second;
1253
1254           if(twoAgoValue+1 <= maxValue){
1255             newControlPoints[cpName] = twoAgoValue+1; // incrase from two phases back
1256           }
1257         }
1258         
1259       }
1260       
1261       CkPrintf("Steering done for this phase\n");
1262       fflush(stdout);
1263
1264     }  else {
1265       // This is not a phase to do steering, so stick with previously used values (one phase ago)
1266       CkPrintf("not a phase to do steering, so stick with previously planned values (one phase ago)\n");
1267       fflush(stdout);
1268     }
1269     
1270     
1271     
1272   } else if( whichTuningScheme == SimulatedAnnealing ) {
1273     
1274     // -----------------------------------------------------------
1275     //  SIMULATED ANNEALING
1276     //  Simulated Annealing style hill climbing method
1277     //
1278     //  Find the best search space configuration, and try something
1279     //  nearby it, with a radius decreasing as phases increase
1280
1281     CkPrintf("Finding best phase\n");
1282     instrumentedPhase *bestPhase = allData.findBest();  
1283     CkPrintf("best found:\n"); 
1284     bestPhase->print(); 
1285     CkPrintf("\n"); 
1286     
1287
1288     const int convergeByPhase = 100;
1289     // Determine from 0.0 to 1.0 how far along we are
1290     const double progress = (double) min(effective_phase, convergeByPhase) / (double)convergeByPhase;
1291
1292     std::map<std::string, std::pair<int,int> >::const_iterator cpsIter;
1293     for(cpsIter=controlPointSpace.begin(); cpsIter != controlPointSpace.end(); ++cpsIter){
1294       const std::string &name = cpsIter->first;
1295       const std::pair<int,int> &bounds = cpsIter->second;
1296       const int minValue = bounds.first;
1297       const int maxValue = bounds.second;
1298       
1299       const int before = bestPhase->controlPoints[name];   
1300   
1301       const int range = (maxValue-minValue+1)*(1.0-progress);
1302
1303       int high = min(before+range, maxValue);
1304       int low = max(before-range, minValue);
1305       
1306       newControlPoints[name] = low;
1307       if(high-low > 0){
1308         newControlPoints[name] += randInt(high-low, name.c_str(), phase_id); 
1309       } 
1310       
1311     }
1312
1313   } else if( whichTuningScheme == ExhaustiveSearch ) {
1314
1315     // -----------------------------------------------------------
1316     // EXHAUSTIVE SEARCH
1317    
1318     int numDimensions = controlPointSpace.size();
1319     CkAssert(numDimensions > 0);
1320   
1321     vector<int> lowerBounds(numDimensions);
1322     vector<int> upperBounds(numDimensions); 
1323   
1324     int d=0;
1325     std::map<std::string, pair<int,int> >::iterator iter;
1326     for(iter = controlPointSpace.begin(); iter != controlPointSpace.end(); iter++){
1327       //    CkPrintf("Examining dimension %d\n", d);
1328       lowerBounds[d] = iter->second.first;
1329       upperBounds[d] = iter->second.second;
1330       d++;
1331     }
1332    
1333     // get names for each dimension (control point)
1334     vector<std::string> names(numDimensions);
1335     d=0;
1336     for(std::map<std::string, pair<int,int> >::iterator niter=controlPointSpace.begin(); niter!=controlPointSpace.end(); niter++){
1337       names[d] = niter->first;
1338       d++;
1339     }
1340   
1341   
1342     // Create the first possible configuration
1343     vector<int> config = lowerBounds;
1344     config.push_back(0);
1345   
1346     // Increment until finding an unused configuration
1347     allData.cleanupNames(); // put -1 values in for any control points missing
1348     std::vector<instrumentedPhase*> &phases = allData.phases;     
1349
1350     while(true){
1351     
1352       std::vector<instrumentedPhase*>::iterator piter; 
1353       bool testedConfiguration = false; 
1354       for(piter = phases.begin(); piter != phases.end(); piter++){ 
1355       
1356         // Test if the configuration matches this phase
1357         bool match = true;
1358         for(int j=0;j<numDimensions;j++){
1359           match &= (*piter)->controlPoints[names[j]] == config[j];
1360         }
1361       
1362         if(match){
1363           testedConfiguration = true; 
1364           break;
1365         } 
1366       } 
1367     
1368       if(testedConfiguration == false){ 
1369         break;
1370       } 
1371     
1372       // go to next configuration
1373       config[0] ++;
1374       // Propagate "carrys"
1375       for(int i=0;i<numDimensions;i++){
1376         if(config[i] > upperBounds[i]){
1377           config[i+1]++;
1378           config[i] = lowerBounds[i];
1379         }
1380       }
1381       // check if we have exhausted all possible values
1382       if(config[numDimensions] > 0){
1383         break;
1384       }
1385        
1386     }
1387   
1388     if(config[numDimensions] > 0){
1389       for(int i=0;i<numDimensions;i++){ 
1390         config[i]= (lowerBounds[i]+upperBounds[i]) / 2;
1391       }
1392     }
1393
1394     // results are now in config[i]
1395     
1396     for(int i=0; i<numDimensions; i++){
1397       newControlPoints[names[i]] = config[i];
1398       CkPrintf("Exhaustive search chose:   %s   -> %d\n", names[i].c_str(), config[i]);
1399     }
1400
1401
1402   } else {
1403     CkAbort("Some Control Point tuning strategy must be enabled.\n");
1404   }
1405
1406 }
1407
1408
1409
1410
1411
1412 #define isInRange(v,a,b) ( ((v)<=(a)&&(v)>=(b)) || ((v)<=(b)&&(v)>=(a)) )
1413
1414
1415 /// Get control point value from range of integers [lb,ub]
1416 int controlPoint(const char *name, int lb, int ub){
1417   instrumentedPhase *thisPhaseData = controlPointManagerProxy.ckLocalBranch()->currentPhaseData();
1418   const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
1419   std::map<std::string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;
1420   int result;
1421
1422   // if we already have control point values for phase, return them
1423   if( thisPhaseData->controlPoints.count(std::string(name))>0 && thisPhaseData->controlPoints[std::string(name)]>=0 ){
1424     CkPrintf("Already have control point values for phase. %s -> %d\n", name, (int)(thisPhaseData->controlPoints[std::string(name)]) );
1425     return thisPhaseData->controlPoints[std::string(name)];
1426   }
1427   
1428
1429   if( phase_id < 4 ){
1430     // For the first few phases, just use the lower bound, or the default if one was provided 
1431     // This ensures that the ranges for all the control points are known before we do anything fancy
1432     result = lb;
1433
1434
1435     if(defaultControlPointValues.count(std::string(name)) > 0){
1436       int v = defaultControlPointValues[std::string(name)];
1437       CkPrintf("Startup phase using default value of %d for  \"%s\"\n", v, name);   
1438       result = v;
1439     }
1440
1441   } else if(controlPointSpace.count(std::string(name)) == 0){
1442     // if this is the first time we've seen the CP, then return the lower bound
1443     result = lb;
1444     
1445   }  else {
1446     // Generate a plan one time for each phase
1447     controlPointManagerProxy.ckLocalBranch()->generatePlan();
1448     
1449     // Use the planned value:
1450     result = controlPointManagerProxy.ckLocalBranch()->newControlPoints[std::string(name)];
1451     
1452   }
1453
1454   CkAssert(isInRange(result,ub,lb));
1455   thisPhaseData->controlPoints[std::string(name)] = result; // was insert() 
1456
1457   controlPointSpace.insert(std::make_pair(std::string(name),std::make_pair(lb,ub))); 
1458
1459   CkPrintf("Control Point \"%s\" for phase %d is: %d\n", name, phase_id, result);
1460   //  thisPhaseData->print();
1461   
1462   return result;
1463 }
1464
1465
1466
1467
1468 /// Inform the control point framework that a named control point affects the priorities of some array  
1469 void controlPointPriorityArray(const char *name, CProxy_ArrayBase &arraybase){
1470   CkGroupID aid = arraybase.ckGetArrayID();
1471   int groupIdx = aid.idx;
1472   controlPointManagerProxy.ckLocalBranch()->associatePriorityArray(name, groupIdx);
1473   //  CkPrintf("Associating control point \"%s\" with array id=%d\n", name, groupIdx );
1474 }
1475
1476
1477 /// Inform the control point framework that a named control point affects the priorities of some entry method  
1478 void controlPointPriorityEntry(const char *name, int idx){
1479   controlPointManagerProxy.ckLocalBranch()->associatePriorityEntry(name, idx);
1480   //  CkPrintf("Associating control point \"%s\" with EP id=%d\n", name, idx);
1481 }
1482
1483
1484
1485
1486 /*! @} */
1487
1488
1489 #include "ControlPoints.def.h"