use portable CmiLog2 instead of log2
[charm.git] / src / ck-cp / controlPoints.C
1 #include <charm++.h>
2 #include <cmath>
3 #include <math.h>
4 #include <iostream>
5 #include <fstream>
6 #include <string>
7 #include <sstream>
8 #include <map>
9 #include <set>
10 #include <vector>
11 #include <utility>
12 #include <sys/time.h>
13
14 #include "ControlPoints.decl.h"
15
16 #include "LBDatabase.h"
17 #include "controlPoints.h"
18
19 using namespace std;
20
21 #define CONTROL_POINT_PERIOD 8000
22 #define OPTIMIZER_TRANSITION 5
23
24 static void periodicProcessControlPoints(void* ptr, double currWallTime);
25
26
27 // A pointer to this PE's controlpoint manager Proxy
28 /* readonly */ CProxy_controlPointManager localControlPointManagerProxy;
29 /* readonly */ int random_seed;
30
31
32 class instrumentedPhase {
33 public:
34   std::map<string,int> controlPoints; // The control point values for this phase(don't vary within the phase)
35   std::multiset<double> times;  // A list of times observed for iterations in this phase
36   
37   int memoryUsageMB;
38   
39   instrumentedPhase(){
40     memoryUsageMB = -1;
41   }
42   
43   void clear(){
44     controlPoints.clear();
45     times.clear();
46   }
47
48   // Provide a previously computed value, or a value from a previous run
49   bool haveValueForName(const char* name){
50     string n(name);
51     return (controlPoints.count(n)>0);
52   }
53
54   void operator=(const instrumentedPhase& p){
55     controlPoints = p.controlPoints;
56     times = p.times;
57     memoryUsageMB = p.memoryUsageMB;
58   }
59
60
61
62   bool operator<(const instrumentedPhase& p){
63     CkAssert(hasSameKeysAs(p)); 
64     std::map<string,int>::iterator iter1 = controlPoints.begin();
65     std::map<string,int>::const_iterator iter2 = p.controlPoints.begin();
66     for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){
67       if(iter1->second < iter2->second){
68         return true;
69       }
70     }
71     return false;
72   }
73
74
75   // Determines if the control point values and other information exists
76   bool hasValidControlPointValues(){
77     std::map<string,int>::iterator iter;
78     for(iter = controlPoints.begin();iter != controlPoints.end(); iter++){
79       if(iter->second == -1){ 
80         return false; 
81       }  
82     }
83
84     return true;
85   }
86
87
88
89   bool operator==(const instrumentedPhase& p){
90     CkAssert(hasSameKeysAs(p));
91     std::map<string,int>::iterator iter1 = controlPoints.begin();
92     std::map<string,int>::const_iterator iter2 = p.controlPoints.begin();
93     for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){ 
94       if(iter1->second != iter2->second){ 
95         return false; 
96       }  
97     }
98     return true;
99   }
100
101   /// Verify the names of the control points are consistent
102   /// note: std::map stores the pairs in a sorted order based on their first component 
103   bool hasSameKeysAs(const instrumentedPhase& p){
104     
105     if(controlPoints.size() != p.controlPoints.size())
106       return false;
107
108     std::map<string,int>::iterator iter1 = controlPoints.begin(); 
109     std::map<string,int>::const_iterator iter2 = p.controlPoints.begin(); 
110
111     for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){  
112       if(iter1->first != iter2->first)
113         return false;
114     } 
115
116     return true; 
117   }
118
119
120   void addAllNames(std::set<string> names_) {
121     
122     std::set<string> names = names_;
123     
124     // Remove all the names that we already have
125     std::map<std::string,int>::iterator iter;
126     
127     for(iter = controlPoints.begin(); iter != controlPoints.end(); iter++){
128       names.erase(iter->first);
129     }
130     
131     // Add -1 values for each name we didn't find
132     std::set<std::string>::iterator iter2;
133     for(iter2 = names.begin(); iter2 != names.end(); iter2++){
134       controlPoints.insert(make_pair(*iter2,-1));
135       CkPrintf("One of the datasets was missing a value for %s, so -1 was used\n", iter2->c_str());
136     }
137
138   }
139
140
141
142   void print() {
143     std::map<std::string,int>::iterator iter;
144
145     if(controlPoints.size() == 0){
146       CkPrintf("no control point values found\n");
147     }
148     
149     for(iter = controlPoints.begin(); iter != controlPoints.end(); iter++){
150       std::string name = iter->first;
151       int val = iter->second;
152       CkPrintf("%s ---> %d\n",  name.c_str(),  val);
153     } 
154     
155   }
156   
157   
158 };
159
160
161
162 class instrumentedData {
163 public:
164   std::vector<instrumentedPhase> phases;
165
166   /// get control point names for all phases
167   std::set<string> getNames(){
168     std::set<string> names;
169     
170     std::vector<instrumentedPhase>::iterator iter;
171     for(iter = phases.begin();iter!=phases.end();iter++) {
172       
173       std::map<string,int>::iterator iter2;
174       for(iter2 = iter->controlPoints.begin(); iter2 != iter->controlPoints.end(); iter2++){
175         names.insert(iter2->first);
176       }
177       
178     }  
179     return names;
180
181   } 
182
183
184   void cleanupNames(){
185     std::set<string> names = getNames();
186     
187     std::vector<instrumentedPhase>::iterator iter;
188     for(iter = phases.begin();iter!=phases.end();iter++) {
189       iter->addAllNames(names);
190     }
191   }
192
193
194   /// Remove one phase with invalid control point values if found
195   bool filterOutOnePhase(){
196     // Note: calling erase on a vector will invalidate any iterators beyond the deletion point
197     std::vector<instrumentedPhase>::iterator iter;
198     for(iter = phases.begin(); iter != phases.end(); iter++) {
199       if(! iter->hasValidControlPointValues()  || iter->times.size()==0){
200         // CkPrintf("Filtered out a phase with incomplete control point values\n");
201         phases.erase(iter);
202         return true;
203       } else {
204         //      CkPrintf("Not filtering out some phase with good control point values\n");
205       }
206     }
207     return false;
208   }
209   
210   /// Drop any phases that do not contain timings or control point values
211   void filterOutIncompletePhases(){
212     bool done = false;
213     while(filterOutOnePhase()){
214       // do nothing
215     }
216   }
217
218
219   string toString(){
220     ostringstream s;
221
222     verify();
223
224     filterOutIncompletePhases();
225
226     // HEADER:
227     s << "# HEADER:\n";
228     s << "# Data for use with Isaac Dooley's Control Point Framework\n";
229     s << string("# Number of instrumented timings in this file:\n"); 
230     s << phases.size() << "\n" ;
231     
232     if(phases.size() > 0){
233       
234       std::map<string,int> &ps = phases[0].controlPoints; 
235       std::map<string,int>::iterator cpiter;
236
237       // SCHEMA:
238       s << "# SCHEMA:\n";
239       s << "# number of named control points:\n";
240       s << ps.size() << "\n";
241       
242       for(cpiter = ps.begin(); cpiter != ps.end(); cpiter++){
243         s << cpiter->first << "\n";
244       }
245       
246       // DATA:
247       s << "# DATA:\n";
248       s << "# first field is memory usage (MB). Then there are the " << ps.size()  << " control points values, followed by one or more timings" << "\n";
249       s << "# number of control point sets: " << phases.size() << "\n";
250       std::vector<instrumentedPhase>::iterator runiter;
251       for(runiter=phases.begin();runiter!=phases.end();runiter++){
252
253         // Print the memory usage
254          s << runiter->memoryUsageMB << "    "; 
255
256         // Print the control point values
257         for(cpiter = runiter->controlPoints.begin(); cpiter != runiter->controlPoints.end(); cpiter++){ 
258           s << cpiter->second << " "; 
259         }
260
261         s << "     ";
262
263         // Print the times
264         std::multiset<double>::iterator titer;
265         for(titer = runiter->times.begin(); titer != runiter->times.end(); titer++){
266           s << *titer << " ";
267         }
268
269         s << "\n";
270         
271       }
272  
273     }
274
275     return s.str();
276     
277   }
278
279
280   /// Verify that all our phases of data have the same sets of control point names
281   void verify(){
282     if(phases.size() > 1){
283       instrumentedPhase & firstpoint = phases[0];
284       std::vector<instrumentedPhase>::iterator iter;
285       for(iter = phases.begin();iter!=phases.end();iter++){
286         CkAssert( firstpoint.hasSameKeysAs(*iter));
287       }  
288     } 
289   }
290
291
292   // Find the fastest time from previous runs
293   instrumentedPhase findBest(){
294     CkAssert(phases.size()>0);
295
296     double total_time = 0.0; // total for all times
297     int total_count = 0;
298
299     instrumentedPhase best_phase;
300     double best_phase_avgtime = std::numeric_limits<double>::max();
301
302     int valid_phase_count = 0;
303
304     std::vector<instrumentedPhase>::iterator iter;
305     for(iter = phases.begin();iter!=phases.end();iter++){
306       if(iter->hasValidControlPointValues()){
307         valid_phase_count++;
308
309         double total_for_phase = 0.0;
310         int phase_count = 0;
311
312         // iterate over all times for this control point configuration
313         std::multiset<double>::iterator titer;
314         for(titer = iter->times.begin(); titer != iter->times.end(); titer++){
315           total_count++;
316           total_time += *titer;
317           total_for_phase += *titer;
318           phase_count ++;
319         }
320
321         double phase_average_time = total_for_phase / (double)phase_count;
322
323         if(phase_average_time  < best_phase_avgtime){
324           best_phase = *iter;
325           best_phase_avgtime = phase_average_time; 
326         }
327
328       }
329     }
330     
331     CkAssert(total_count > 0);
332
333     double avg = total_time / total_count;
334
335     if(CkMyPe() == 0){
336       CkPrintf("Best average time for a phase was %.1lf\n", best_phase_avgtime);
337       CkPrintf("Mean time for all %d times in the %d valid recorded phases was %.1lf\n", total_count, valid_phase_count, avg );
338     }
339
340     // Compute standard deviation
341     double sumx=0.0;
342     for(iter = phases.begin();iter!=phases.end();iter++){
343       if(iter->hasValidControlPointValues()){
344         std::multiset<double>::iterator titer;
345         for(titer = iter->times.begin(); titer != iter->times.end(); titer++){
346           sumx += (avg - *titer)*(avg - *titer);
347         } 
348       }
349     }
350     
351     double std_dev = sqrt(sumx / total_count);
352
353     if(CkMyPe() == 0){
354       CkPrintf("Standard Deviation for previous runs was %.2lf   or %.1lf%% of mean\n", std_dev, std_dev/avg*100.0);
355       CkPrintf("The best phase average time was %.1lf%% faster than the mean\n", (avg-best_phase_avgtime)/avg*100.0);
356
357     }
358
359     return best_phase;
360   }
361   
362 };
363
364
365
366 /// Return an integer between 0 and num-1 inclusive
367 /// If different seed, name, and random_seed values are provided, the returned values are pseudo-random
368 unsigned int randInt(unsigned int num, const char* name, int seed=0){
369   CkAssert(num > 0);
370   CkAssert(num < 1000);
371
372   unsigned long hash = 0;
373   unsigned int c;
374   unsigned char * str = (unsigned char*)name;
375
376   while (c = *str++){
377     unsigned int c2 = (c+64)%128;
378     unsigned int c3 = (c2*5953)%127;
379     hash = c3 + (hash << 6) + (hash << 16) - hash;
380   }
381
382   unsigned long shuffled1 = (hash*2083)%7907;
383   unsigned long shuffled2 = (seed*4297)%2017;
384
385   unsigned long shuffled3 = (random_seed*4799)%7919;
386
387   unsigned int namehash = shuffled3 ^ shuffled1 ^ shuffled2;
388
389   unsigned int result = ((namehash * 6029) % 1117) % num;
390
391   CkAssert(result >=0 && result < num);
392   return result;
393 }
394
395
396
397
398 //=============================================================================
399 // THE MODULE CODE IS HERE: 
400 //=============================================================================
401
402
403 // A group with representatives on all nodes
404 class controlPointManager : public CBase_controlPointManager {
405 public:
406   
407   char * dataFilename;
408   
409   instrumentedData allData;
410   instrumentedPhase thisPhaseData;
411   instrumentedPhase best_phase;
412   
413   std::map<string, pair<int,int> > controlPointSpace;
414
415   std::set<string> staticControlPoints;
416
417
418   CkCallback granularityCallback;
419   bool haveGranularityCallback;
420   bool frameworkShouldAdvancePhase;
421   
422   int phase_id;
423
424   bool alreadyRequestedMemoryUsage;
425
426   controlPointManager(){
427     alreadyRequestedMemoryUsage = false;
428     
429     dataFilename = (char*)malloc(128);
430     sprintf(dataFilename, "controlPointData.txt");
431     
432     frameworkShouldAdvancePhase = false;
433     haveGranularityCallback = false;
434     CkPrintf("[%d] controlPointManager() Constructor Initializing control points, and loading data file\n", CkMyPe());
435     
436     phase_id = 0;
437     
438     localControlPointManagerProxy = thisProxy;
439     
440     loadDataFile();
441     
442     if(allData.phases.size()>0){
443       allData.findBest();
444     }
445     
446     if(CkMyPe() == 0)
447       CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, CONTROL_POINT_PERIOD, CkMyPe());
448
449   }
450   
451   ~controlPointManager(){
452     CkPrintf("[%d] controlPointManager() Destructor\n", CkMyPe());
453   }
454
455
456   /// Loads the previous run data file
457   void loadDataFile(){
458     ifstream infile(dataFilename);
459     vector<string> names;
460     string line;
461   
462     while(getline(infile,line)){
463       if(line[0] != '#')
464         break;
465     }
466   
467     int numTimings = 0;
468     istringstream n(line);
469     n >> numTimings;
470   
471     while(getline(infile,line)){ 
472       if(line[0] != '#') 
473         break; 
474     }
475
476     int numControlPointNames = 0;
477     istringstream n2(line);
478     n2 >> numControlPointNames;
479   
480     for(int i=0; i<numControlPointNames; i++){
481       getline(infile,line);
482       names.push_back(line);
483     }
484
485     for(int i=0;i<numTimings;i++){
486       getline(infile,line);
487       while(line[0] == '#')
488         getline(infile,line); 
489
490       instrumentedPhase ips;
491
492       istringstream iss(line);
493
494       // Read memory usage for phase
495       iss >> ips.memoryUsageMB;
496       //     CkPrintf("Memory usage loaded from file: %d\n", ips.memoryUsageMB);
497
498
499       // Read control point values
500       for(int cp=0;cp<numControlPointNames;cp++){
501         int cpvalue;
502         iss >> cpvalue;
503         ips.controlPoints.insert(make_pair(names[cp],cpvalue));
504       }
505
506       double time;
507
508       while(iss >> time){
509         ips.times.insert(time);
510 #if DEBUG > 5
511         CkPrintf("read time %lf from file\n", time);
512 #endif
513       }
514
515       allData.phases.push_back(ips);
516
517     }
518
519     infile.close();
520   }
521
522
523
524   /// Add the current data to allData and output it to a file
525   void writeDataFile(){
526     CkPrintf("============= writeDataFile() ============\n");
527     ofstream outfile(dataFilename);
528     allData.phases.push_back(thisPhaseData);
529     allData.cleanupNames();
530     outfile << allData.toString();
531     outfile.close();
532   }
533
534
535   void setGranularityCallback(CkCallback cb, bool _frameworkShouldAdvancePhase){
536     frameworkShouldAdvancePhase = _frameworkShouldAdvancePhase;
537     granularityCallback = cb;
538     haveGranularityCallback = true;
539   }
540
541   /// Called periodically by the runtime to handle the control points
542   /// Currently called on each PE
543   void processControlPoints(){
544 #if DEBUG
545     CkPrintf("[%d] processControlPoints()\n", CkMyPe());
546 #endif
547     if(haveGranularityCallback){
548       if(frameworkShouldAdvancePhase){
549         gotoNextPhase();        
550       }
551       
552       controlPointMsg *msg = new(0) controlPointMsg;
553       granularityCallback.send(msg); 
554     }
555
556
557     if(CkMyPe() == 0 && !alreadyRequestedMemoryUsage){
558       alreadyRequestedMemoryUsage = true;
559       CkCallback *cb = new CkCallback(CkIndex_controlPointManager::gatherMemoryUsage(NULL), 0, thisProxy);
560       //      thisProxy.requestMemoryUsage(*cb);
561       delete cb;
562     }
563
564   }
565   
566   instrumentedPhase *previousPhaseData(){
567     int s = allData.phases.size();
568     if(s >= 1 && phase_id > 0) {
569       return &(allData.phases[s-1]);
570     } else {
571       return NULL;
572     }
573   }
574   
575   
576   void gotoNextPhase(){
577
578     LBDatabase * myLBdatabase = LBDatabaseObj();
579
580 #if CMK_LBDB_ON
581     LBDB * myLBDB = myLBdatabase->getLBDB();       // LBDB is Defined in LBDBManager.h
582     const CkVec<LBObj*> objs = myLBDB->getObjs();
583     const int objCount = myLBDB->getObjCount();
584     CkPrintf("LBDB info: objCount=%d objs contains %d LBObj* \n", objCount, objs.length());
585     
586     floatType maxObjWallTime = -1.0;
587     
588     for(int i=0;i<objs.length();i++){
589       LBObj* o = objs[i];
590       const LDObjData d = o->ObjData();
591       floatType cpuTime = d.cpuTime;
592       floatType wallTime = d.wallTime;
593       // can also get object handles from the LDObjData struct
594       CkPrintf("[%d] LBDB Object[%d]: cpuTime=%f wallTime=%f\n", CkMyPe(), i, cpuTime, wallTime);
595       if(wallTime > maxObjWallTime){
596
597       }
598       
599     }
600
601     myLBDB->ClearLoads(); // BUG: Probably very dangerous if we are actually using load balancing
602     
603 #endif    
604     
605     
606     // increment phase id
607     phase_id++;
608     
609     CkPrintf("Now in phase %d\n", phase_id);
610     
611     // save the timing information from this phase
612     allData.phases.push_back(thisPhaseData);
613         
614     // clear the timing information that will be used for the next phase
615     thisPhaseData.clear();
616     
617   }
618
619   // The application can set the instrumented time for this phase
620   void setTiming(double time){
621      thisPhaseData.times.insert(time);
622   }
623   
624
625
626   void requestMemoryUsage(CkCallback cb){
627     int m = CmiMaxMemoryUsage() / 1024 / 1024;
628     CmiResetMaxMemory();
629     CkPrintf("PE %d Memory Usage is %d MB\n",CkMyPe(), m);
630     contribute(sizeof(int),&m,CkReduction::max_int, cb);
631   }
632
633   void gatherMemoryUsage(CkReductionMsg *msg){
634     int size=msg->getSize() / sizeof(int);
635     CkAssert(size==1);
636     int *m=(int *) msg->getData();
637
638     CkPrintf("[%d] Max Memory Usage for all processors is %d MB\n", CkMyPe(), m[0]);
639     
640     instrumentedPhase* prevPhase = previousPhaseData();
641     if(prevPhase != NULL){
642       prevPhase->memoryUsageMB = m[0];
643     } else {
644       CkPrintf("No place to store memory usage");
645     }
646
647     alreadyRequestedMemoryUsage = false;
648     delete msg;
649   }
650
651
652
653 };
654
655
656
657 void gotoNextPhase(){
658   localControlPointManagerProxy.ckLocalBranch()->gotoNextPhase();
659 }
660
661
662 // A mainchare that is used just to create our controlPointManager group at startup
663 class controlPointMain : public CBase_controlPointMain {
664 public:
665   controlPointMain(CkArgMsg* args){
666     struct timeval tp;
667     gettimeofday(& tp, NULL);
668     random_seed = (int)tp.tv_usec ^ (int)tp.tv_sec;
669
670     localControlPointManagerProxy = CProxy_controlPointManager::ckNew();
671   }
672   ~controlPointMain(){}
673 };
674
675 void registerGranularityChangeCallback(CkCallback cb, bool frameworkShouldAdvancePhase){
676   CkAssert(CkMyPe() == 0);
677   CkPrintf("registerGranularityChangeCallback\n");
678   localControlPointManagerProxy.ckLocalBranch()->setGranularityCallback(cb, frameworkShouldAdvancePhase);
679 }
680
681
682 void registerControlPointTiming(double time){
683   CkAssert(CkMyPe() == 0);
684 #if DEBUG>0
685   CkPrintf("Program registering its own timing with registerControlPointTiming(time=%lf)\n", time);
686 #endif
687   localControlPointManagerProxy.ckLocalBranch()->setTiming(time);
688 }
689
690 extern "C" void controlPointShutdown(){
691   CkAssert(CkMyPe() == 0);
692   CkPrintf("[%d] controlPointShutdown() at CkExit()\n", CkMyPe());
693
694   localControlPointManagerProxy.ckLocalBranch()->writeDataFile();
695   CkExit();
696 }
697
698
699 void controlPointInitNode(){
700   CkPrintf("controlPointInitNode()\n");
701   registerExitFn(controlPointShutdown);
702 }
703
704 static void periodicProcessControlPoints(void* ptr, double currWallTime){
705 #ifdef DEBUG
706   CkPrintf("[%d] periodicProcessControlPoints()\n", CkMyPe());
707 #endif
708   localControlPointManagerProxy.ckLocalBranch()->processControlPoints();
709   CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, CONTROL_POINT_PERIOD, CkMyPe());
710 }
711
712
713
714
715
716 // Static point for life of program: randomly chosen, no optimizer
717 int staticPoint(const char *name, int lb, int ub){
718   instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
719   std::set<string> &staticControlPoints = localControlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
720
721   int result = lb + randInt(ub-lb+1, name);
722   
723   localControlPointManagerProxy.ckLocalBranch()->controlPointSpace.insert(std::make_pair(string(name),std::make_pair(lb,ub))); 
724   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result)); 
725   staticControlPoints.insert(string(name));
726
727   return result;
728 }
729
730
731
732 bool valueShouldBeProvidedByOptimizer(){
733   
734   const int effective_phase = localControlPointManagerProxy.ckLocalBranch()->allData.phases.size();
735   const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id; 
736   
737   std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace; 
738   
739   double spaceSize = 1.0;
740   std::map<string, pair<int,int> >::iterator iter;
741   for(iter = controlPointSpace.begin(); iter != controlPointSpace.end(); iter++){
742     spaceSize *= iter->second.second - iter->second.first + 1;
743   }
744
745   //  CkPrintf("Control Point Space:\n\t\tnumber of control points = %d\n\t\tnumber of possible configurations = %.0lf\n", controlPointSpace.size(), spaceSize);
746
747 #if 1
748   return effective_phase > 1 && phase_id > 1;
749 #else
750   return effective_phase >= OPTIMIZER_TRANSITION && phase_id > 3;
751 #endif
752 }
753
754
755
756
757
758
759
760
761
762 int valueProvidedByOptimizer(const char * name){
763   const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
764   const int effective_phase = localControlPointManagerProxy.ckLocalBranch()->allData.phases.size();
765
766   //#define OPTIMIZER_USE_BEST_TIME  
767 #if OPTIMIZER_USE_BEST_TIME  
768   static bool firstTime = true;
769   if(firstTime){
770     firstTime = false;
771     CkPrintf("Finding best phase\n");
772     instrumentedPhase p = localControlPointManagerProxy.ckLocalBranch()->allData.findBest(); 
773     CkPrintf("p=:\n");
774     p.print();
775     CkPrintf("\n");
776     localControlPointManagerProxy.ckLocalBranch()->best_phase = p;
777   }
778   
779   
780   instrumentedPhase &p = localControlPointManagerProxy.ckLocalBranch()->best_phase;
781   int result = p.controlPoints[std::string(name)];
782   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen out of best previous phase to be: %d\n", name, phase_id, result);
783   return result;
784 #elsif SIMULATED_ANNEALING
785   
786   // Simulated Annealing style hill climbing method
787   //
788   // Find the best search space configuration, and try something
789   // nearby it, with a radius decreasing as phases increase
790   
791   std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace;  
792   
793   CkPrintf("Finding best phase\n"); 
794   instrumentedPhase p = localControlPointManagerProxy.ckLocalBranch()->allData.findBest();  
795   CkPrintf("best found:\n"); 
796   p.print(); 
797   CkPrintf("\n"); 
798   
799   int before = p.controlPoints[std::string(name)];   
800   
801   int minValue =  controlPointSpace[std::string(name)].first;
802   int maxValue =  controlPointSpace[std::string(name)].second;
803   
804   int convergeByPhase = 100;
805   
806   // Determine from 0.0 to 1.0 how far along we are
807   double progress = (double) min(effective_phase, convergeByPhase) / (double)convergeByPhase;
808   
809   int range = (maxValue-minValue+1)*(1.0-progress);
810
811   CkPrintf("========================== Hill climbing progress = %lf  range=%d\n", progress, range); 
812
813   int high = min(before+range, maxValue);
814   int low = max(before-range, minValue);
815   
816   int result = low;
817
818   if(high-low > 0){
819     result += randInt(high-low, name, phase_id); 
820   } 
821
822   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen by hill climbing to be: %d\n", name, phase_id, result); 
823   return result; 
824
825 #else
826
827   std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace;
828   std::set<string> &staticControlPoints = localControlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
829    
830   int numDimensions = controlPointSpace.size();
831   CkAssert(numDimensions > 0);
832   
833   int lowerBounds[numDimensions];
834   int upperBounds[numDimensions]; 
835   
836   int d=0;
837   std::map<string, pair<int,int> >::iterator iter;
838   for(iter = controlPointSpace.begin(); iter != controlPointSpace.end(); iter++){
839     //    CkPrintf("Examining dimension %d\n", d);
840
841     string name = iter->first;
842     if(staticControlPoints.count(name) >0 ){
843       cout << " control point " << name << " is static " << endl;
844     } else{
845       cout << " control point " << name << " is not static " << endl;
846     }
847
848     lowerBounds[d] = iter->second.first;
849     upperBounds[d] = iter->second.second;
850     d++;
851   }
852    
853
854   std::string *s = new std::string[numDimensions];
855   d=0;
856   for(std::map<string, pair<int,int> >::iterator niter=controlPointSpace.begin(); niter!=controlPointSpace.end(); niter++){
857     s[d] = niter->first;
858     // cout << "s[" << d << "]=" << s[d] << endl;
859     d++;
860   }
861   
862   
863   // Create the first possible configuration
864   int config[numDimensions+1]; // one value for each dimension and a
865                                // final one to hold the carry
866                                // producing an invalid config
867   config[numDimensions] = 0;
868   for(int i=0;i<numDimensions;i++){
869     config[i] = lowerBounds[i];
870   }
871   
872   // Increment until finding an unused configuration
873   localControlPointManagerProxy.ckLocalBranch()->allData.cleanupNames(); // put -1 values in for any control points missing
874   std::vector<instrumentedPhase> &phases = localControlPointManagerProxy.ckLocalBranch()->allData.phases;     
875
876   while(true){
877     
878     std::vector<instrumentedPhase>::iterator piter; 
879     bool testedConfiguration = false; 
880     for(piter = phases.begin(); piter != phases.end(); piter++){ 
881       
882       // Test if the configuration matches this phase
883       bool match = true;
884       for(int j=0;j<numDimensions;j++){
885         match &= piter->controlPoints[s[j]] == config[j];
886       }
887       
888       if(match){
889         testedConfiguration = true; 
890         break;
891       } 
892     } 
893     
894     if(testedConfiguration == false){ 
895       break;
896     } 
897     
898     // go to next configuration
899     config[0] ++;
900     // Propagate "carrys"
901     for(int i=0;i<numDimensions;i++){
902       if(config[i] > upperBounds[i]){
903         config[i+1]++;
904         config[i] = lowerBounds[i];
905       }
906     }
907     // check if we have exhausted all possible values
908     if(config[numDimensions] > 0){
909       break;
910     }
911        
912   }
913   
914   if(config[numDimensions] > 0){
915     for(int i=0;i<numDimensions;i++){ 
916       config[i]= (lowerBounds[i]+upperBounds[i]) / 2;
917     }
918   }
919   
920   
921   int result=-1;  
922
923   std::string name_s(name);
924   for(int i=0;i<numDimensions;i++){
925     //    cout << "Comparing " << name_s <<  " with s[" << i << "]=" << s[i] << endl;
926     if(name_s.compare(s[i]) == 0){
927       result = config[i];
928     }
929   }
930
931   CkAssert(result != -1);
932
933
934   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen by exhaustive search to be: %d\n", name, phase_id, result); 
935   return result; 
936
937   delete [] s;
938
939 #endif
940   
941 }
942
943
944
945
946
947 #define isInRange(v,a,b) ( ((v)<=(a)&&(v)>=(b)) || ((v)<=(b)&&(v)>=(a)) )
948
949
950 // Dynamic point varies throughout the life of program
951 // The value it returns is based upon phase_id, a counter that changes for each phase of computation
952 int controlPoint2Pow(const char *name, int fine_granularity, int coarse_granularity){
953   instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
954   const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
955
956   int result;
957
958   // Use best configuration after a certain point
959   if(valueShouldBeProvidedByOptimizer()){
960     result = valueProvidedByOptimizer(name);
961   } 
962   else {
963
964     int l1 = CmiLog2(fine_granularity);
965     int l2 = CmiLog2(coarse_granularity);
966   
967     if (l1 > l2){
968       int tmp;
969       tmp = l2;
970       l2 = l1; 
971       l1 = tmp;
972     }
973     CkAssert(l1 <= l2);
974     
975     int l = l1 + randInt(l2-l1+1,name, phase_id);
976
977     result = 1 << l;
978
979     CkAssert(isInRange(result,fine_granularity,coarse_granularity));
980     CkPrintf("Control Point \"%s\" for phase %d chosen randomly to be: %d\n", name, phase_id, result);
981   }
982
983   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result));
984
985   return result;
986 }
987
988
989
990 int controlPoint(const char *name, int lb, int ub){
991   instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
992   const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
993   std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace;
994
995   int result;
996
997   // Use best configuration after a certain point
998   if(valueShouldBeProvidedByOptimizer()){
999     result = valueProvidedByOptimizer(name);
1000   } 
1001   else {
1002     result = lb + randInt(ub-lb+1, name, phase_id);
1003     CkPrintf("Control Point \"%s\" for phase %d chosen randomly to be: %d\n", name, phase_id, result); 
1004   } 
1005    
1006   CkAssert(isInRange(result,ub,lb));
1007   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result)); 
1008   controlPointSpace.insert(std::make_pair(string(name),std::make_pair(lb,ub))); 
1009   //  CkPrintf("Inserting control point value to thisPhaseData.controlPoints with value %d; thisPhaseData.controlPoints.size=%d\n", result, thisPhaseData.controlPoints.size());
1010   return result;
1011 }
1012
1013
1014 int controlPoint(const char *name, std::vector<int>& values){
1015   instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
1016   const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
1017
1018   int result;
1019   if(valueShouldBeProvidedByOptimizer()){
1020     result = valueProvidedByOptimizer(name);
1021   } 
1022   else { 
1023     result = values[randInt(values.size(), name, phase_id)];
1024   }
1025
1026   bool found = false;
1027   for(int i=0;i<values.size();i++){
1028     if(values[i] == result)
1029       found = true;
1030   }
1031   CkAssert(found);
1032
1033   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result)); 
1034   return result;
1035 }
1036
1037
1038
1039
1040 // The index in the global array for my top row  
1041 int redistributor2D::top_data_idx(){ 
1042   return (data_height * thisIndex.y) / y_chares; 
1043
1044  
1045 int redistributor2D::bottom_data_idx(){ 
1046   return ((data_height * (thisIndex.y+1)) / y_chares) - 1; 
1047
1048  
1049 int redistributor2D::left_data_idx(){ 
1050   return (data_width * thisIndex.x) / x_chares; 
1051
1052  
1053 int redistributor2D::right_data_idx(){ 
1054   return ((data_width * (thisIndex.x+1)) / x_chares) - 1; 
1055
1056  
1057 int redistributor2D::top_neighbor(){ 
1058   return (thisIndex.y + y_chares - 1) % y_chares; 
1059 }  
1060    
1061 int redistributor2D::bottom_neighbor(){ 
1062   return (thisIndex.y + 1) % y_chares; 
1063
1064    
1065 int redistributor2D::left_neighbor(){ 
1066   return (thisIndex.x + x_chares - 1) % x_chares; 
1067
1068  
1069 int redistributor2D::right_neighbor(){ 
1070   return (thisIndex.x + 1) % x_chares; 
1071
1072   
1073   
1074 /// the width of the non-ghost part of the local partition 
1075 int redistributor2D::mywidth(){ 
1076   return right_data_idx() - left_data_idx() + 1; 
1077
1078    
1079    
1080 // the height of the non-ghost part of the local partition 
1081 int redistributor2D::myheight(){ 
1082   return bottom_data_idx() - top_data_idx() + 1; 
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092 #include "ControlPoints.def.h"