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