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