Adding optional support for critical path detection(currently disabled by default...
[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 #include "trace-controlPoints.h"
17 #include "LBDatabase.h"
18 #include "controlPoints.h"
19
20
21 using namespace std;
22
23 #define CONTROL_POINT_SAMPLE_PERIOD 4000
24 #define NUM_SAMPLES_BEFORE_TRANSISTION 5
25 #define OPTIMIZER_TRANSITION 5
26
27 static void periodicProcessControlPoints(void* ptr, double currWallTime);
28
29
30 // A pointer to this PE's controlpoint manager Proxy
31 /* readonly */ CProxy_controlPointManager localControlPointManagerProxy;
32 /* readonly */ int random_seed;
33
34
35 // A reduction to take min/sum/avg
36 CkReduction::reducerType idleTimeReductionType;
37 CkReductionMsg *idleTimeReduction(int nMsg,CkReductionMsg **msgs){
38   double ret[3];
39   if(nMsg > 0){
40     CkAssert(msgs[0]->getSize()==3*sizeof(double));
41     double *m=(double *)msgs[0]->getData();
42     ret[0]=m[0];
43     ret[1]=m[1];
44     ret[2]=m[2];
45   }
46   for (int i=1;i<nMsg;i++) {
47     CkAssert(msgs[i]->getSize()==3*sizeof(double));
48     double *m=(double *)msgs[i]->getData();
49     ret[0]=min(ret[0],m[0]);
50     ret[1]+=m[1];
51     ret[2]=max(ret[2],m[2]);
52   }  
53   return CkReductionMsg::buildNew(3*sizeof(double),ret);   
54 }
55 /*initcall*/ void registerIdleTimeReduction(void) {
56   idleTimeReductionType=CkReduction::addReducer(idleTimeReduction);
57 }
58
59
60
61
62 class idleTimeContainer {
63 public:
64   double min;
65   double avg;
66   double max;
67   
68   idleTimeContainer(){
69     min = -1.0;
70     max = -1.0;
71     avg = -1.0;
72   }
73   
74   bool isValid() const{
75     return (min >= 0.0 && avg >= min && max >= avg && max <= 1.0);
76   }
77   
78   void print() const{
79     if(isValid())
80       CkPrintf("[%d] Idle Time is Min=%.2lf%% Avg=%.2lf%% Max=%.2lf%%\n", CkMyPe(), min*100.0, avg*100.0, max*100.0);    
81     else
82       CkPrintf("[%d] Idle Time is invalid\n", CkMyPe(), min*100.0, avg*100.0, max*100.0);
83   }
84   
85 }; 
86
87
88
89
90 class instrumentedPhase {
91 public:
92   std::map<string,int> controlPoints; // The control point values for this phase(don't vary within the phase)
93   std::vector<double> times;  // A list of times observed for iterations in this phase
94
95   std::vector<PathHistory> criticalPaths;
96
97   
98   int memoryUsageMB;
99
100   idleTimeContainer idleTime;
101
102   instrumentedPhase(){
103     memoryUsageMB = -1;
104   }
105   
106   void clear(){
107     controlPoints.clear();
108     times.clear();
109     criticalPaths.clear();
110   }
111
112   // Provide a previously computed value, or a value from a previous run
113   bool haveValueForName(const char* name){
114     string n(name);
115     return (controlPoints.count(n)>0);
116   }
117
118   void operator=(const instrumentedPhase& p){
119     controlPoints = p.controlPoints;
120     times = p.times;
121     memoryUsageMB = p.memoryUsageMB;
122   }
123
124
125
126   bool operator<(const instrumentedPhase& p){
127     CkAssert(hasSameKeysAs(p)); 
128     std::map<string,int>::iterator iter1 = controlPoints.begin();
129     std::map<string,int>::const_iterator iter2 = p.controlPoints.begin();
130     for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){
131       if(iter1->second < iter2->second){
132         return true;
133       }
134     }
135     return false;
136   }
137
138
139   // Determines if the control point values and other information exists
140   bool hasValidControlPointValues(){
141     std::map<string,int>::iterator iter;
142     for(iter = controlPoints.begin();iter != controlPoints.end(); iter++){
143       if(iter->second == -1){ 
144         return false; 
145       }  
146     }
147
148     return true;
149   }
150
151
152
153   bool operator==(const instrumentedPhase& p){
154     CkAssert(hasSameKeysAs(p));
155     std::map<string,int>::iterator iter1 = controlPoints.begin();
156     std::map<string,int>::const_iterator iter2 = p.controlPoints.begin();
157     for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){ 
158       if(iter1->second != iter2->second){ 
159         return false; 
160       }  
161     }
162     return true;
163   }
164
165   /// Verify the names of the control points are consistent
166   /// note: std::map stores the pairs in a sorted order based on their first component 
167   bool hasSameKeysAs(const instrumentedPhase& p){
168     
169     if(controlPoints.size() != p.controlPoints.size())
170       return false;
171
172     std::map<string,int>::iterator iter1 = controlPoints.begin(); 
173     std::map<string,int>::const_iterator iter2 = p.controlPoints.begin(); 
174
175     for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){  
176       if(iter1->first != iter2->first)
177         return false;
178     } 
179
180     return true; 
181   }
182
183
184   void addAllNames(std::set<string> names_) {
185     
186     std::set<string> names = names_;
187     
188     // Remove all the names that we already have
189     std::map<std::string,int>::iterator iter;
190     
191     for(iter = controlPoints.begin(); iter != controlPoints.end(); iter++){
192       names.erase(iter->first);
193     }
194     
195     // Add -1 values for each name we didn't find
196     std::set<std::string>::iterator iter2;
197     for(iter2 = names.begin(); iter2 != names.end(); iter2++){
198       controlPoints.insert(make_pair(*iter2,-1));
199       CkPrintf("One of the datasets was missing a value for %s, so -1 was used\n", iter2->c_str());
200     }
201
202   }
203
204
205
206   void print() {
207     std::map<std::string,int>::iterator iter;
208
209     if(controlPoints.size() == 0){
210       CkPrintf("no control point values found\n");
211     }
212     
213     for(iter = controlPoints.begin(); iter != controlPoints.end(); iter++){
214       std::string name = iter->first;
215       int val = iter->second;
216       CkPrintf("%s ---> %d\n",  name.c_str(),  val);
217     } 
218     
219   }
220   
221   
222 };
223
224
225
226 class instrumentedData {
227 public:
228   std::vector<instrumentedPhase> phases;
229
230   /// get control point names for all phases
231   std::set<string> getNames(){
232     std::set<string> names;
233     
234     std::vector<instrumentedPhase>::iterator iter;
235     for(iter = phases.begin();iter!=phases.end();iter++) {
236       
237       std::map<string,int>::iterator iter2;
238       for(iter2 = iter->controlPoints.begin(); iter2 != iter->controlPoints.end(); iter2++){
239         names.insert(iter2->first);
240       }
241       
242     }  
243     return names;
244
245   } 
246
247
248   void cleanupNames(){
249     std::set<string> names = getNames();
250     
251     std::vector<instrumentedPhase>::iterator iter;
252     for(iter = phases.begin();iter!=phases.end();iter++) {
253       iter->addAllNames(names);
254     }
255   }
256
257
258   /// Remove one phase with invalid control point values if found
259   bool filterOutOnePhase(){
260     // Note: calling erase on a vector will invalidate any iterators beyond the deletion point
261     std::vector<instrumentedPhase>::iterator iter;
262     for(iter = phases.begin(); iter != phases.end(); iter++) {
263       if(! iter->hasValidControlPointValues()  || iter->times.size()==0){
264         // CkPrintf("Filtered out a phase with incomplete control point values\n");
265         phases.erase(iter);
266         return true;
267       } else {
268         //      CkPrintf("Not filtering out some phase with good control point values\n");
269       }
270     }
271     return false;
272   }
273   
274   /// Drop any phases that do not contain timings or control point values
275   void filterOutIncompletePhases(){
276     bool done = false;
277     while(filterOutOnePhase()){
278       // do nothing
279     }
280   }
281
282
283   string toString(){
284     ostringstream s;
285
286     verify();
287
288     filterOutIncompletePhases();
289
290     // HEADER:
291     s << "# HEADER:\n";
292     s << "# Data for use with Isaac Dooley's Control Point Framework\n";
293     s << string("# Number of instrumented timings in this file:\n"); 
294     s << phases.size() << "\n" ;
295     
296     if(phases.size() > 0){
297       
298       std::map<string,int> &ps = phases[0].controlPoints; 
299       std::map<string,int>::iterator cpiter;
300
301       // SCHEMA:
302       s << "# SCHEMA:\n";
303       s << "# number of named control points:\n";
304       s << ps.size() << "\n";
305       
306       for(cpiter = ps.begin(); cpiter != ps.end(); cpiter++){
307         s << cpiter->first << "\n";
308       }
309       
310       // DATA:
311       s << "# DATA:\n";
312       s << "# first field is memory usage (MB). Then there are the " << ps.size()  << " control points values, followed by one or more timings" << "\n";
313       s << "# number of control point sets: " << phases.size() << "\n";
314       std::vector<instrumentedPhase>::iterator runiter;
315       for(runiter=phases.begin();runiter!=phases.end();runiter++){
316
317         // Print the memory usage
318          s << runiter->memoryUsageMB << "    "; 
319
320         // Print the control point values
321         for(cpiter = runiter->controlPoints.begin(); cpiter != runiter->controlPoints.end(); cpiter++){ 
322           s << cpiter->second << " "; 
323         }
324
325         s << "     ";
326
327         // Print the times
328         std::vector<double>::iterator titer;
329         for(titer = runiter->times.begin(); titer != runiter->times.end(); titer++){
330           s << *titer << " ";
331         }
332
333         s << "\n";
334         
335       }
336  
337     }
338
339     return s.str();
340     
341   }
342
343
344   /// Verify that all our phases of data have the same sets of control point names
345   void verify(){
346     if(phases.size() > 1){
347       instrumentedPhase & firstpoint = phases[0];
348       std::vector<instrumentedPhase>::iterator iter;
349       for(iter = phases.begin();iter!=phases.end();iter++){
350         CkAssert( firstpoint.hasSameKeysAs(*iter));
351       }  
352     } 
353   }
354
355
356   // Find the fastest time from previous runs
357   instrumentedPhase findBest(){
358     CkAssert(phases.size()>0);
359
360     double total_time = 0.0; // total for all times
361     int total_count = 0;
362
363     instrumentedPhase best_phase;
364     double best_phase_avgtime = std::numeric_limits<double>::max();
365
366     int valid_phase_count = 0;
367
368     std::vector<instrumentedPhase>::iterator iter;
369     for(iter = phases.begin();iter!=phases.end();iter++){
370       if(iter->hasValidControlPointValues()){
371         valid_phase_count++;
372
373         double total_for_phase = 0.0;
374         int phase_count = 0;
375
376         // iterate over all times for this control point configuration
377         std::vector<double>::iterator titer;
378         for(titer = iter->times.begin(); titer != iter->times.end(); titer++){
379           total_count++;
380           total_time += *titer;
381           total_for_phase += *titer;
382           phase_count ++;
383         }
384
385         double phase_average_time = total_for_phase / (double)phase_count;
386
387         if(phase_average_time  < best_phase_avgtime){
388           best_phase = *iter;
389           best_phase_avgtime = phase_average_time; 
390         }
391
392       }
393     }
394     
395     CkAssert(total_count > 0);
396
397     double avg = total_time / total_count;
398
399     if(CkMyPe() == 0){
400       CkPrintf("Best average time for a phase was %.1lf\n", best_phase_avgtime);
401       CkPrintf("Mean time for all %d times in the %d valid recorded phases was %.1lf\n", total_count, valid_phase_count, avg );
402     }
403
404     // Compute standard deviation
405     double sumx=0.0;
406     for(iter = phases.begin();iter!=phases.end();iter++){
407       if(iter->hasValidControlPointValues()){
408         std::vector<double>::iterator titer;
409         for(titer = iter->times.begin(); titer != iter->times.end(); titer++){
410           sumx += (avg - *titer)*(avg - *titer);
411         } 
412       }
413     }
414     
415     double std_dev = sqrt(sumx / total_count);
416
417     if(CkMyPe() == 0){
418       CkPrintf("Standard Deviation for previous runs was %.2lf   or %.1lf%% of mean\n", std_dev, std_dev/avg*100.0);
419       CkPrintf("The best phase average time was %.1lf%% faster than the mean\n", (avg-best_phase_avgtime)/avg*100.0);
420
421     }
422
423     return best_phase;
424   }
425   
426 };
427
428
429
430 /// Return an integer between 0 and num-1 inclusive
431 /// If different seed, name, and random_seed values are provided, the returned values are pseudo-random
432 unsigned int randInt(unsigned int num, const char* name, int seed=0){
433   CkAssert(num > 0);
434   CkAssert(num < 1000);
435
436   unsigned long hash = 0;
437   unsigned int c;
438   unsigned char * str = (unsigned char*)name;
439
440   while (c = *str++){
441     unsigned int c2 = (c+64)%128;
442     unsigned int c3 = (c2*5953)%127;
443     hash = c3 + (hash << 6) + (hash << 16) - hash;
444   }
445
446   unsigned long shuffled1 = (hash*2083)%7907;
447   unsigned long shuffled2 = (seed*4297)%2017;
448
449   unsigned long shuffled3 = (random_seed*4799)%7919;
450
451   unsigned int namehash = shuffled3 ^ shuffled1 ^ shuffled2;
452
453   unsigned int result = ((namehash * 6029) % 1117) % num;
454
455   CkAssert(result >=0 && result < num);
456   return result;
457 }
458
459
460
461
462 //=============================================================================
463 // THE MODULE CODE IS HERE: 
464 //=============================================================================
465
466
467 // A group with representatives on all nodes
468 class controlPointManager : public CBase_controlPointManager {
469 public:
470   
471   char * dataFilename;
472   
473   instrumentedData allData;
474   instrumentedPhase thisPhaseData;
475   instrumentedPhase best_phase;
476   
477   std::map<string, pair<int,int> > controlPointSpace;
478
479   std::set<string> staticControlPoints;
480
481   std::map<string, std::set<int> > affectsPrioritiesEP;
482   std::map<string, std::set<int> > affectsPrioritiesArray;
483
484
485
486   CkCallback granularityCallback;
487   bool haveGranularityCallback;
488   bool frameworkShouldAdvancePhase;
489   
490   int phase_id;
491
492   bool alreadyRequestedMemoryUsage;
493   bool alreadyRequestedIdleTime;
494
495
496 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
497   PathHistory maxTerminalPathHistory;
498 #endif
499
500   controlPointManager(){
501
502     alreadyRequestedMemoryUsage = false;   
503     alreadyRequestedIdleTime = false;
504     
505     dataFilename = (char*)malloc(128);
506     sprintf(dataFilename, "controlPointData.txt");
507     
508     frameworkShouldAdvancePhase = false;
509     haveGranularityCallback = false;
510     CkPrintf("[%d] controlPointManager() Constructor Initializing control points, and loading data file\n", CkMyPe());
511     
512     phase_id = 0;
513     
514     localControlPointManagerProxy = thisProxy;
515     
516     loadDataFile();
517     
518     if(allData.phases.size()>0){
519       allData.findBest();
520     }
521     
522     if(CkMyPe() == 0)
523       CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, CONTROL_POINT_SAMPLE_PERIOD, CkMyPe());
524
525   }
526   
527   ~controlPointManager(){
528     CkPrintf("[%d] controlPointManager() Destructor\n", CkMyPe());
529   }
530
531
532   /// Loads the previous run data file
533   void loadDataFile(){
534     ifstream infile(dataFilename);
535     vector<string> names;
536     string line;
537   
538     while(getline(infile,line)){
539       if(line[0] != '#')
540         break;
541     }
542   
543     int numTimings = 0;
544     istringstream n(line);
545     n >> numTimings;
546   
547     while(getline(infile,line)){ 
548       if(line[0] != '#') 
549         break; 
550     }
551
552     int numControlPointNames = 0;
553     istringstream n2(line);
554     n2 >> numControlPointNames;
555   
556     for(int i=0; i<numControlPointNames; i++){
557       getline(infile,line);
558       names.push_back(line);
559     }
560
561     for(int i=0;i<numTimings;i++){
562       getline(infile,line);
563       while(line[0] == '#')
564         getline(infile,line); 
565
566       instrumentedPhase ips;
567
568       istringstream iss(line);
569
570       // Read memory usage for phase
571       iss >> ips.memoryUsageMB;
572       //     CkPrintf("Memory usage loaded from file: %d\n", ips.memoryUsageMB);
573
574
575       // Read control point values
576       for(int cp=0;cp<numControlPointNames;cp++){
577         int cpvalue;
578         iss >> cpvalue;
579         ips.controlPoints.insert(make_pair(names[cp],cpvalue));
580       }
581
582       double time;
583
584       while(iss >> time){
585         ips.times.push_back(time);
586 #if DEBUG > 5
587         CkPrintf("read time %lf from file\n", time);
588 #endif
589       }
590
591       allData.phases.push_back(ips);
592
593     }
594
595     infile.close();
596   }
597
598
599
600   /// Add the current data to allData and output it to a file
601   void writeDataFile(){
602     CkPrintf("============= writeDataFile() ============\n");
603     ofstream outfile(dataFilename);
604     allData.phases.push_back(thisPhaseData);
605     allData.cleanupNames();
606     outfile << allData.toString();
607     outfile.close();
608   }
609
610
611   void setGranularityCallback(CkCallback cb, bool _frameworkShouldAdvancePhase){
612     frameworkShouldAdvancePhase = _frameworkShouldAdvancePhase;
613     granularityCallback = cb;
614     haveGranularityCallback = true;
615   }
616
617   /// Called periodically by the runtime to handle the control points
618   /// Currently called on each PE
619   void processControlPoints(){
620
621     CkPrintf("[%d] processControlPoints() haveGranularityCallback=%d frameworkShouldAdvancePhase=%d\n", CkMyPe(), (int)haveGranularityCallback, (int)frameworkShouldAdvancePhase);
622
623     
624     if(haveGranularityCallback){
625       if(frameworkShouldAdvancePhase){
626         gotoNextPhase();        
627       }
628       
629       controlPointMsg *msg = new(0) controlPointMsg;
630       granularityCallback.send(msg); 
631     }
632     
633     
634     if(CkMyPe() == 0 && !alreadyRequestedMemoryUsage){
635       alreadyRequestedMemoryUsage = true;
636       CkCallback *cb = new CkCallback(CkIndex_controlPointManager::gatherMemoryUsage(NULL), 0, thisProxy);
637       // thisProxy.requestMemoryUsage(*cb);
638       delete cb;
639     }
640     
641     if(CkMyPe() == 0 && !alreadyRequestedIdleTime){
642       alreadyRequestedIdleTime = true;
643       CkCallback *cb = new CkCallback(CkIndex_controlPointManager::gatherIdleTime(NULL), 0, thisProxy);
644       thisProxy.requestIdleTime(*cb);
645       delete cb;
646     }
647     
648     
649     int s = allData.phases.size();
650     
651     CkPrintf("\n\nExamining critical paths and priorities and idle times (num phases=%d)\n", s );
652     
653     for(int p=0;p<s;++p){
654       const instrumentedPhase &phase = allData.phases[p];
655       const idleTimeContainer &idle = phase.idleTime;
656       vector<PathHistory> const &criticalPaths = phase.criticalPaths;
657       vector<double> const &times = phase.times;
658
659       CkPrintf("Phase %d:\n", p);
660       idle.print();
661       CkPrintf("critical paths: (* affected by control point)\n");
662       for(int i=0;i<criticalPaths.size(); i++){
663         // If affected by a control point
664         //      criticalPaths[i].print();
665
666
667         CkPrintf("Critical Path Time=%lf : ", (double)criticalPaths[i].getTotalTime());
668         for(int e=0;e<numEpIdxs;e++){
669
670           if(criticalPaths[i].getEpIdxCount(e)>0){
671             if(controlPointAffectsThisEP(e))
672               CkPrintf("* ");
673             CkPrintf("EP %d count=%d : ", e, (int)criticalPaths[i].getEpIdxCount(e));
674           }
675         }
676         for(int a=0;a<numArrayIds;a++){
677           if(criticalPaths[i].getArrayIdxCount(a)>0){
678             if(controlPointAffectsThisArray(a))
679               CkPrintf("* ");
680             CkPrintf("Array %d count=%d : ", a, (int)criticalPaths[i].getArrayIdxCount(a));
681           }
682         }
683         CkPrintf("\n");
684         
685
686       }
687       CkPrintf("Timings:\n");
688       for(int i=0;i<times.size(); i++){
689         CkPrintf("%lf ", times[i]);
690       }
691       CkPrintf("\n");
692
693     }
694  
695     
696     CkPrintf("\n\n");
697
698   }
699   
700   bool controlPointAffectsThisEP(int ep){
701     std::map<string, std::set<int> >::iterator iter;
702     for(iter=affectsPrioritiesEP.begin(); iter!= affectsPrioritiesEP.end(); ++iter){
703       if(iter->second.count(ep)>0){
704         return true;
705       }
706     }
707     return false;    
708   }
709   
710   
711   bool controlPointAffectsThisArray(int array){
712     std::map<string, std::set<int> >::iterator iter;
713     for(iter=affectsPrioritiesArray.begin(); iter!= affectsPrioritiesArray.end(); ++iter){
714       if(iter->second.count(array)>0){
715         return true;
716       }
717     }
718     return false;   
719   }
720   
721   instrumentedPhase *previousPhaseData(){
722     int s = allData.phases.size();
723     if(s >= 1 && phase_id > 0) {
724       return &(allData.phases[s-1]);
725     } else {
726       return NULL;
727     }
728   }
729   
730   
731   void gotoNextPhase(){
732
733     LBDatabase * myLBdatabase = LBDatabaseObj();
734
735 #if CMK_LBDB_ON
736     LBDB * myLBDB = myLBdatabase->getLBDB();       // LBDB is Defined in LBDBManager.h
737     const CkVec<LBObj*> objs = myLBDB->getObjs();
738     const int objCount = myLBDB->getObjCount();
739     CkPrintf("LBDB info: objCount=%d objs contains %d LBObj* \n", objCount, objs.length());
740     
741     floatType maxObjWallTime = -1.0;
742     
743     for(int i=0;i<objs.length();i++){
744       LBObj* o = objs[i];
745       const LDObjData d = o->ObjData();
746       floatType cpuTime = d.cpuTime;
747       floatType wallTime = d.wallTime;
748       // can also get object handles from the LDObjData struct
749       CkPrintf("[%d] LBDB Object[%d]: cpuTime=%f wallTime=%f\n", CkMyPe(), i, cpuTime, wallTime);
750       if(wallTime > maxObjWallTime){
751
752       }
753       
754     }
755
756     myLBDB->ClearLoads(); // BUG: Probably very dangerous if we are actually using load balancing
757     
758 #endif    
759     
760     
761     // increment phase id
762     phase_id++;
763     
764     CkPrintf("Now in phase %d\n", phase_id);
765     
766     // save a copy of the timing information from this phase
767     allData.phases.push_back(thisPhaseData);
768         
769     // clear the timing information that will be used for the next phase
770     thisPhaseData.clear();
771     
772   }
773
774   // The application can set the instrumented time for this phase
775   void setTiming(double time){
776     thisPhaseData.times.push_back(time);
777 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
778        
779     // First we should register this currently executing message as a path, because it is likely an important one to consider.
780     registerTerminalEntryMethod();
781     
782     // save the critical path for this phase
783     thisPhaseData.criticalPaths.push_back(maxTerminalPathHistory);
784     maxTerminalPathHistory.reset();
785     
786     
787     // Reset the counts for the currently executing message
788     resetThisEntryPath();
789     
790     
791 #endif
792     
793   }
794   
795   // Entry method called on all PEs to request memory usage
796   void requestIdleTime(CkCallback cb){
797     double i = localControlPointTracingInstance()->idleRatio();
798     double idle[3];
799     idle[0] = i;
800     idle[1] = i;
801     idle[2] = i;
802     
803     localControlPointTracingInstance()->resetTimings();
804
805     //   CkPrintf("PE %d Idle Time is %lf\n",CkMyPe(), idle);
806     contribute(3*sizeof(double),idle,idleTimeReductionType, cb);
807   }
808   
809   // All processors reduce their memory usages to this method
810   void gatherIdleTime(CkReductionMsg *msg){
811     int size=msg->getSize() / sizeof(double);
812     CkAssert(size==3);
813     double *r=(double *) msg->getData();
814         
815     instrumentedPhase* prevPhase = previousPhaseData();
816     if(prevPhase != NULL){
817       CkPrintf("Storing idle time measurements\n");
818       prevPhase->idleTime.min = r[0];
819       prevPhase->idleTime.avg = r[1]/CkNumPes();
820       prevPhase->idleTime.max = r[2];
821       prevPhase->idleTime.print();
822       CkPrintf("Stored idle time min=%lf in prevPhase=%p\n", prevPhase->idleTime.min, prevPhase);
823     } else {
824       CkPrintf("No place to store idle time measurements\n");
825     }
826     
827     alreadyRequestedIdleTime = false;
828     delete msg;
829   }
830   
831
832
833   // Entry method called on all PEs to request memory usage
834   void requestMemoryUsage(CkCallback cb){
835     int m = CmiMaxMemoryUsage() / 1024 / 1024;
836     CmiResetMaxMemory();
837     CkPrintf("PE %d Memory Usage is %d MB\n",CkMyPe(), m);
838     contribute(sizeof(int),&m,CkReduction::max_int, cb);
839   }
840
841   // All processors reduce their memory usages to this method
842   void gatherMemoryUsage(CkReductionMsg *msg){
843     int size=msg->getSize() / sizeof(int);
844     CkAssert(size==1);
845     int *m=(int *) msg->getData();
846
847     CkPrintf("[%d] Max Memory Usage for all processors is %d MB\n", CkMyPe(), m[0]);
848     
849     instrumentedPhase* prevPhase = previousPhaseData();
850     if(prevPhase != NULL){
851       prevPhase->memoryUsageMB = m[0];
852     } else {
853       CkPrintf("No place to store memory usage");
854     }
855
856     alreadyRequestedMemoryUsage = false;
857     delete msg;
858   }
859
860
861
862   void registerTerminalPath(PathHistory &path){
863 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
864   
865     double beginTime = CmiWallTimer();
866         
867     if(maxTerminalPathHistory.updateMax(path) ) {
868       // The new path is more critical than the previous one
869       // propogate it towards processor 0 in a binary tree
870       if(CkMyPe() > 0){
871         int dest = (CkMyPe() -1) / 2;
872         //      CkPrintf("Forwarding better critical path from PE %d to %d\n", CkMyPe(), dest);
873
874         // This is part of a reduction-like propagation of the maximum back to PE 0
875         resetThisEntryPath();
876
877         thisProxy[dest].registerTerminalPath(path);
878       }
879     }
880
881     traceRegisterUserEvent("registerTerminalPath", 100); 
882     traceUserBracketEvent(100, beginTime, CmiWallTimer());
883 #endif
884   }
885
886   void printTerminalPath(){
887 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
888     maxTerminalPathHistory.print();
889 #endif
890   }
891   
892   void resetTerminalPath(){
893 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
894     maxTerminalPathHistory.reset();
895 #endif
896   }
897   
898   void associatePriorityArray(const char *name, int groupIdx){
899     CkPrintf("Associating control point \"%s\" affects priority of array id=%d\n", name, groupIdx );
900     
901     if(affectsPrioritiesArray.count(std::string(name)) > 0 ) {
902       affectsPrioritiesArray[std::string(name)].insert(groupIdx);
903     } else {
904       std::set<int> s;
905       s.insert(groupIdx);
906       affectsPrioritiesArray[std::string(name)] = s;
907     }
908     
909 #if DEBUG   
910     std::map<string, std::set<int> >::iterator f;
911     for(f=affectsPrioritiesArray.begin(); f!=affectsPrioritiesArray.end();++f){
912       std::string name = f->first;
913       std::set<int> &vals = f->second;
914       cout << "Control point " << name << " affects arrays: ";
915       std::set<int>::iterator i;
916       for(i=vals.begin(); i!=vals.end();++i){
917         cout << *i << " ";
918       }
919       cout << endl;
920     }
921 #endif
922     
923   }
924   
925   void associatePriorityEntry(const char *name, int idx){
926     CkPrintf("Associating control point \"%s\" with EP id=%d\n", name, idx);
927
928       if(affectsPrioritiesEP.count(std::string(name)) > 0 ) {
929       affectsPrioritiesEP[std::string(name)].insert(idx);
930     } else {
931       std::set<int> s;
932       s.insert(idx);
933       affectsPrioritiesEP[std::string(name)] = s;
934     }
935     
936 #if DEBUG
937     std::map<string, std::set<int> >::iterator f;
938     for(f=affectsPrioritiesEP.begin(); f!=affectsPrioritiesEP.end();++f){
939       std::string name = f->first;
940       std::set<int> &vals = f->second;
941       cout << "Control point " << name << " affects EP: ";
942       std::set<int>::iterator i;
943       for(i=vals.begin(); i!=vals.end();++i){
944         cout << *i << " ";
945       }
946       cout << endl;
947     }
948 #endif
949
950
951   }
952   
953 };
954
955
956
957 void gotoNextPhase(){
958   localControlPointManagerProxy.ckLocalBranch()->gotoNextPhase();
959 }
960
961
962 // A mainchare that is used just to create our controlPointManager group at startup
963 class controlPointMain : public CBase_controlPointMain {
964 public:
965   controlPointMain(CkArgMsg* args){
966     struct timeval tp;
967     gettimeofday(& tp, NULL);
968     random_seed = (int)tp.tv_usec ^ (int)tp.tv_sec;
969
970     localControlPointManagerProxy = CProxy_controlPointManager::ckNew();
971   }
972   ~controlPointMain(){}
973 };
974
975 void registerGranularityChangeCallback(CkCallback cb, bool frameworkShouldAdvancePhase){
976   CkAssert(CkMyPe() == 0);
977   CkPrintf("registerGranularityChangeCallback\n");
978   localControlPointManagerProxy.ckLocalBranch()->setGranularityCallback(cb, frameworkShouldAdvancePhase);
979 }
980
981
982 void registerControlPointTiming(double time){
983   CkAssert(CkMyPe() == 0);
984 #if DEBUG>0
985   CkPrintf("Program registering its own timing with registerControlPointTiming(time=%lf)\n", time);
986 #endif
987   localControlPointManagerProxy.ckLocalBranch()->setTiming(time);
988 }
989
990 extern "C" void controlPointShutdown(){
991   CkAssert(CkMyPe() == 0);
992   CkPrintf("[%d] controlPointShutdown() at CkExit()\n", CkMyPe());
993
994   localControlPointManagerProxy.ckLocalBranch()->writeDataFile();
995   CkExit();
996 }
997
998
999 void controlPointInitNode(){
1000   CkPrintf("controlPointInitNode()\n");
1001   registerExitFn(controlPointShutdown);
1002 }
1003
1004 static void periodicProcessControlPoints(void* ptr, double currWallTime){
1005 #ifdef DEBUG
1006   CkPrintf("[%d] periodicProcessControlPoints()\n", CkMyPe());
1007 #endif
1008   localControlPointManagerProxy.ckLocalBranch()->processControlPoints();
1009   CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, CONTROL_POINT_SAMPLE_PERIOD, CkMyPe());
1010 }
1011
1012
1013
1014
1015
1016 // Static point for life of program: randomly chosen, no optimizer
1017 int staticPoint(const char *name, int lb, int ub){
1018   instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
1019   std::set<string> &staticControlPoints = localControlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
1020
1021   int result = lb + randInt(ub-lb+1, name);
1022   
1023   localControlPointManagerProxy.ckLocalBranch()->controlPointSpace.insert(std::make_pair(string(name),std::make_pair(lb,ub))); 
1024   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result)); 
1025   staticControlPoints.insert(string(name));
1026
1027   return result;
1028 }
1029
1030
1031
1032 bool valueShouldBeProvidedByOptimizer(){
1033   
1034   const int effective_phase = localControlPointManagerProxy.ckLocalBranch()->allData.phases.size();
1035   const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id; 
1036   
1037   std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace; 
1038   
1039   double spaceSize = 1.0;
1040   std::map<string, pair<int,int> >::iterator iter;
1041   for(iter = controlPointSpace.begin(); iter != controlPointSpace.end(); iter++){
1042     spaceSize *= iter->second.second - iter->second.first + 1;
1043   }
1044
1045   //  CkPrintf("Control Point Space:\n\t\tnumber of control points = %d\n\t\tnumber of possible configurations = %.0lf\n", controlPointSpace.size(), spaceSize);
1046
1047 #if 1
1048   return effective_phase > 1 && phase_id > 1;
1049 #else
1050   return effective_phase >= OPTIMIZER_TRANSITION && phase_id > 3;
1051 #endif
1052 }
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062 int valueProvidedByOptimizer(const char * name){
1063   const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
1064   const int effective_phase = localControlPointManagerProxy.ckLocalBranch()->allData.phases.size();
1065
1066   //#define OPTIMIZER_USE_BEST_TIME  
1067 #if OPTIMIZER_USE_BEST_TIME  
1068   static bool firstTime = true;
1069   if(firstTime){
1070     firstTime = false;
1071     CkPrintf("Finding best phase\n");
1072     instrumentedPhase p = localControlPointManagerProxy.ckLocalBranch()->allData.findBest(); 
1073     CkPrintf("p=:\n");
1074     p.print();
1075     CkPrintf("\n");
1076     localControlPointManagerProxy.ckLocalBranch()->best_phase = p;
1077   }
1078   
1079   
1080   instrumentedPhase &p = localControlPointManagerProxy.ckLocalBranch()->best_phase;
1081   int result = p.controlPoints[std::string(name)];
1082   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen out of best previous phase to be: %d\n", name, phase_id, result);
1083   return result;
1084 #elsif SIMULATED_ANNEALING
1085   
1086   // Simulated Annealing style hill climbing method
1087   //
1088   // Find the best search space configuration, and try something
1089   // nearby it, with a radius decreasing as phases increase
1090   
1091   std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace;  
1092   
1093   CkPrintf("Finding best phase\n"); 
1094   instrumentedPhase p = localControlPointManagerProxy.ckLocalBranch()->allData.findBest();  
1095   CkPrintf("best found:\n"); 
1096   p.print(); 
1097   CkPrintf("\n"); 
1098   
1099   int before = p.controlPoints[std::string(name)];   
1100   
1101   int minValue =  controlPointSpace[std::string(name)].first;
1102   int maxValue =  controlPointSpace[std::string(name)].second;
1103   
1104   int convergeByPhase = 100;
1105   
1106   // Determine from 0.0 to 1.0 how far along we are
1107   double progress = (double) min(effective_phase, convergeByPhase) / (double)convergeByPhase;
1108   
1109   int range = (maxValue-minValue+1)*(1.0-progress);
1110
1111   CkPrintf("========================== Hill climbing progress = %lf  range=%d\n", progress, range); 
1112
1113   int high = min(before+range, maxValue);
1114   int low = max(before-range, minValue);
1115   
1116   int result = low;
1117
1118   if(high-low > 0){
1119     result += randInt(high-low, name, phase_id); 
1120   } 
1121
1122   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen by hill climbing to be: %d\n", name, phase_id, result); 
1123   return result; 
1124
1125 #else
1126
1127   std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace;
1128   std::set<string> &staticControlPoints = localControlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
1129    
1130   int numDimensions = controlPointSpace.size();
1131   CkAssert(numDimensions > 0);
1132   
1133   vector<int> lowerBounds(numDimensions);
1134   vector<int> upperBounds(numDimensions); 
1135   
1136   int d=0;
1137   std::map<string, pair<int,int> >::iterator iter;
1138   for(iter = controlPointSpace.begin(); iter != controlPointSpace.end(); iter++){
1139     //    CkPrintf("Examining dimension %d\n", d);
1140
1141 #if DEBUG
1142     string name = iter->first;
1143     if(staticControlPoints.count(name) >0 ){
1144       cout << " control point " << name << " is static " << endl;
1145     } else{
1146       cout << " control point " << name << " is not static " << endl;
1147     }
1148 #endif
1149
1150     lowerBounds[d] = iter->second.first;
1151     upperBounds[d] = iter->second.second;
1152     d++;
1153   }
1154    
1155
1156   vector<std::string> s(numDimensions);
1157   d=0;
1158   for(std::map<string, pair<int,int> >::iterator niter=controlPointSpace.begin(); niter!=controlPointSpace.end(); niter++){
1159     s[d] = niter->first;
1160     // cout << "s[" << d << "]=" << s[d] << endl;
1161     d++;
1162   }
1163   
1164   
1165   // Create the first possible configuration
1166   vector<int> config = lowerBounds;
1167   config.push_back(0);
1168   
1169   // Increment until finding an unused configuration
1170   localControlPointManagerProxy.ckLocalBranch()->allData.cleanupNames(); // put -1 values in for any control points missing
1171   std::vector<instrumentedPhase> &phases = localControlPointManagerProxy.ckLocalBranch()->allData.phases;     
1172
1173   while(true){
1174     
1175     std::vector<instrumentedPhase>::iterator piter; 
1176     bool testedConfiguration = false; 
1177     for(piter = phases.begin(); piter != phases.end(); piter++){ 
1178       
1179       // Test if the configuration matches this phase
1180       bool match = true;
1181       for(int j=0;j<numDimensions;j++){
1182         match &= piter->controlPoints[s[j]] == config[j];
1183       }
1184       
1185       if(match){
1186         testedConfiguration = true; 
1187         break;
1188       } 
1189     } 
1190     
1191     if(testedConfiguration == false){ 
1192       break;
1193     } 
1194     
1195     // go to next configuration
1196     config[0] ++;
1197     // Propagate "carrys"
1198     for(int i=0;i<numDimensions;i++){
1199       if(config[i] > upperBounds[i]){
1200         config[i+1]++;
1201         config[i] = lowerBounds[i];
1202       }
1203     }
1204     // check if we have exhausted all possible values
1205     if(config[numDimensions] > 0){
1206       break;
1207     }
1208        
1209   }
1210   
1211   if(config[numDimensions] > 0){
1212     for(int i=0;i<numDimensions;i++){ 
1213       config[i]= (lowerBounds[i]+upperBounds[i]) / 2;
1214     }
1215   }
1216   
1217   
1218   int result=-1;  
1219
1220   std::string name_s(name);
1221   for(int i=0;i<numDimensions;i++){
1222     //    cout << "Comparing " << name_s <<  " with s[" << i << "]=" << s[i] << endl;
1223     if(name_s.compare(s[i]) == 0){
1224       result = config[i];
1225     }
1226   }
1227
1228   CkAssert(result != -1);
1229
1230
1231   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen by exhaustive search to be: %d\n", name, phase_id, result); 
1232   return result; 
1233
1234 #endif
1235   
1236 }
1237
1238
1239
1240
1241
1242 #define isInRange(v,a,b) ( ((v)<=(a)&&(v)>=(b)) || ((v)<=(b)&&(v)>=(a)) )
1243
1244
1245 // Dynamic point varies throughout the life of program
1246 // The value it returns is based upon phase_id, a counter that changes for each phase of computation
1247 int controlPoint2Pow(const char *name, int fine_granularity, int coarse_granularity){
1248   instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
1249   const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
1250
1251   int result;
1252
1253   // Use best configuration after a certain point
1254   if(valueShouldBeProvidedByOptimizer()){
1255     result = valueProvidedByOptimizer(name);
1256   } 
1257   else {
1258
1259     int l1 = CmiLog2(fine_granularity);
1260     int l2 = CmiLog2(coarse_granularity);
1261   
1262     if (l1 > l2){
1263       int tmp;
1264       tmp = l2;
1265       l2 = l1; 
1266       l1 = tmp;
1267     }
1268     CkAssert(l1 <= l2);
1269     
1270     int l = l1 + randInt(l2-l1+1,name, phase_id);
1271
1272     result = 1 << l;
1273
1274     CkAssert(isInRange(result,fine_granularity,coarse_granularity));
1275     CkPrintf("Control Point \"%s\" for phase %d chosen randomly to be: %d\n", name, phase_id, result);
1276   }
1277
1278   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result));
1279
1280   return result;
1281 }
1282
1283
1284
1285 int controlPoint(const char *name, int lb, int ub){
1286   instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
1287   const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
1288   std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace;
1289
1290   int result;
1291
1292   // Use best configuration after a certain point
1293   if(valueShouldBeProvidedByOptimizer()){
1294     result = valueProvidedByOptimizer(name);
1295   } 
1296   else {
1297     result = lb + randInt(ub-lb+1, name, phase_id);
1298     CkPrintf("Control Point \"%s\" for phase %d chosen randomly to be: %d\n", name, phase_id, result); 
1299   } 
1300    
1301   CkAssert(isInRange(result,ub,lb));
1302   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result)); 
1303   controlPointSpace.insert(std::make_pair(string(name),std::make_pair(lb,ub))); 
1304   //  CkPrintf("Inserting control point value to thisPhaseData.controlPoints with value %d; thisPhaseData.controlPoints.size=%d\n", result, thisPhaseData.controlPoints.size());
1305   return result;
1306 }
1307
1308
1309 int controlPoint(const char *name, std::vector<int>& values){
1310   instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
1311   const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
1312
1313   int result;
1314   if(valueShouldBeProvidedByOptimizer()){
1315     result = valueProvidedByOptimizer(name);
1316   } 
1317   else { 
1318     result = values[randInt(values.size(), name, phase_id)];
1319   }
1320
1321   bool found = false;
1322   for(int i=0;i<values.size();i++){
1323     if(values[i] == result)
1324       found = true;
1325   }
1326   CkAssert(found);
1327
1328   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result)); 
1329   return result;
1330 }
1331
1332
1333
1334
1335
1336 void controlPointPriorityArray(const char *name, CProxy_ArrayBase &arraybase){
1337   CkGroupID aid = arraybase.ckGetArrayID();
1338   int groupIdx = aid.idx;
1339   localControlPointManagerProxy.ckLocalBranch()->associatePriorityArray(name, groupIdx);
1340   //  CkPrintf("Associating control point \"%s\" with array id=%d\n", name, groupIdx );
1341 }
1342
1343
1344
1345 void controlPointPriorityEntry(const char *name, int idx){
1346   localControlPointManagerProxy.ckLocalBranch()->associatePriorityEntry(name, idx);
1347   //  CkPrintf("Associating control point \"%s\" with EP id=%d\n", name, idx);
1348 }
1349
1350
1351
1352
1353
1354
1355 // The index in the global array for my top row  
1356 int redistributor2D::top_data_idx(){ 
1357   return (data_height * thisIndex.y) / y_chares; 
1358
1359  
1360 int redistributor2D::bottom_data_idx(){ 
1361   return ((data_height * (thisIndex.y+1)) / y_chares) - 1; 
1362
1363  
1364 int redistributor2D::left_data_idx(){ 
1365   return (data_width * thisIndex.x) / x_chares; 
1366
1367  
1368 int redistributor2D::right_data_idx(){ 
1369   return ((data_width * (thisIndex.x+1)) / x_chares) - 1; 
1370
1371  
1372 int redistributor2D::top_neighbor(){ 
1373   return (thisIndex.y + y_chares - 1) % y_chares; 
1374 }  
1375    
1376 int redistributor2D::bottom_neighbor(){ 
1377   return (thisIndex.y + 1) % y_chares; 
1378
1379    
1380 int redistributor2D::left_neighbor(){ 
1381   return (thisIndex.x + x_chares - 1) % x_chares; 
1382
1383  
1384 int redistributor2D::right_neighbor(){ 
1385   return (thisIndex.x + 1) % x_chares; 
1386
1387   
1388   
1389 /// the width of the non-ghost part of the local partition 
1390 int redistributor2D::mywidth(){ 
1391   return right_data_idx() - left_data_idx() + 1; 
1392
1393    
1394    
1395 // the height of the non-ghost part of the local partition 
1396 int redistributor2D::myheight(){ 
1397   return bottom_data_idx() - top_data_idx() + 1; 
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
1412
1413
1414
1415 void registerTerminalEntryMethod(){
1416   localControlPointManagerProxy.ckLocalBranch()->registerTerminalPath(currentlyExecutingMsg->pathHistory);
1417 }
1418
1419 void printPECriticalPath(){
1420   localControlPointManagerProxy.ckLocalBranch()->printTerminalPath();
1421 }
1422
1423 void resetPECriticalPath(){
1424   localControlPointManagerProxy.ckLocalBranch()->resetTerminalPath();
1425 }
1426
1427 #endif
1428
1429
1430
1431
1432 #include "ControlPoints.def.h"