355d22fcb6efc5624f927a86ba41258c00845e40
[charm.git] / src / ck-cp / controlPoints.h
1 /** 
2
3     A system for exposing application and runtime "control points" 
4     to the dynamic optimization framework.
5
6 */
7 #ifndef __CONTROLPOINTS_H__
8 #define __CONTROLPOINTS_H__
9
10 #include <vector>
11 #include <map>
12 #include <cmath>
13 #include "ControlPoints.decl.h"
14
15 #include <pup_stl.h>
16 #include <string>
17 #include <set>
18 #include <cmath>
19 #include <math.h>
20 #include <iostream>
21 #include <fstream>
22 #include <string>
23 #include <sstream>
24 #include <map>
25 #include <set>
26 #include <vector>
27 #include <utility>
28 #include <limits>
29 #include <float.h>
30
31 #include "LBDatabase.h"
32 #include "pathHistory.h"
33 #include "arrayRedistributor.h"
34
35 using namespace std;
36
37
38 /**
39  * \addtogroup ControlPointFramework
40  *   @{
41  */
42
43 #define DEBUG 0
44
45 /* readonly */ extern CProxy_controlPointManager controlPointManagerProxy;
46 /* readonly */ extern int random_seed;
47 /* readonly */ extern long controlPointSamplePeriod;
48
49
50
51 void registerGranularityChangeCallback(CkCallback cb, bool frameworkShouldAdvancePhase);
52 void registerControlPointTiming(double time);
53
54 /// The application specifies that it is ready to proceed to a new set of control point values.
55 /// This should be called after registerControlPointTiming()
56 /// This should be called before calling controlPoint()
57 void gotoNextPhase();
58
59 /// Return an integral power of 2 between c1 and c2
60 /// The value returned will likely change between subsequent invocations
61 int controlPoint2Pow(const char *name, int c1, int c2);
62
63 /// Return an integer between lb and ub inclusive
64 /// The value returned will likely change between subsequent invocations
65 int controlPoint(const char *name, int lb, int ub);
66
67 /// Return an integer from the provided vector of values
68 /// The value returned will likely change between subsequent invocations
69 int controlPoint(const char *name, std::vector<int>& values);
70
71 /// Return an integer between lb and ub inclusive
72 /// The value returned is static throughout the life of the program
73 int staticPoint(const char *name, int lb, int ub);
74
75
76 /// Associate a control point as affecting priorities for an array
77 void controlPointPriorityArray(const char *name, CProxy_ArrayBase &arraybase);
78
79 /// Associate a control point with an entry method, whose priorities are affected by the control point
80 void controlPointPriorityEntry(const char *name, int idx);
81
82
83
84
85 /// The application specifies that it is ready to proceed to a new set of control point values.
86 /// This should be called after registerControlPointTiming()
87 /// This should be called before calling controlPoint()
88 void gotoNextPhase();
89
90
91
92
93 /// A message used for signaling changes in control point values
94 class controlPointMsg : public CMessage_controlPointMsg {
95  public:
96   char *data;
97 };
98
99
100
101
102
103 /// A container that stores idle time statistics (min/max/avg etc.)
104 class idleTimeContainer {
105 public:
106   double min;
107   double avg;
108   double max;
109   
110   idleTimeContainer(){
111     min = -1.0;
112     max = -1.0;
113     avg = -1.0;
114   }
115   
116   bool isValid() const{
117     return (min >= 0.0 && avg >= min && max >= avg && max <= 1.0);
118   }
119   
120   void print() const{
121     if(isValid())
122       CkPrintf("[%d] Idle Time is Min=%.2lf%% Avg=%.2lf%% Max=%.2lf%%\n", CkMyPe(), min*100.0, avg*100.0, max*100.0);    
123     else
124       CkPrintf("[%d] Idle Time is invalid\n", CkMyPe(), min*100.0, avg*100.0, max*100.0);
125   }
126   
127 }; 
128
129
130
131
132 /// Stores data for a phase (a time range in which a single set of control point values is used).
133 /// The data stored includes the control point values, a set of timings registered by the application, 
134 /// The critical paths detected, the max memory usage, and the idle time.
135 class instrumentedPhase {
136 public:
137   std::map<string,int> controlPoints; // The control point values for this phase(don't vary within the phase)
138   std::vector<double> times;  // A list of times observed for iterations in this phase
139
140 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
141   std::vector<PathHistoryTableEntry> criticalPaths;
142 #endif
143   
144   int memoryUsageMB;
145
146   idleTimeContainer idleTime;
147
148   instrumentedPhase(){
149     memoryUsageMB = -1;
150   }
151   
152   void clear(){
153     controlPoints.clear();
154     times.clear();
155     //    criticalPaths.clear();
156   }
157
158   // Provide a previously computed value, or a value from a previous run
159   bool haveValueForName(const char* name){
160     string n(name);
161     return (controlPoints.count(n)>0);
162   }
163
164   void operator=(const instrumentedPhase& p){
165     controlPoints = p.controlPoints;
166     times = p.times;
167     memoryUsageMB = p.memoryUsageMB;
168   }
169
170
171
172   bool operator<(const instrumentedPhase& p){
173     CkAssert(hasSameKeysAs(p)); 
174     std::map<string,int>::iterator iter1 = controlPoints.begin();
175     std::map<string,int>::const_iterator iter2 = p.controlPoints.begin();
176     for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){
177       if(iter1->second < iter2->second){
178         return true;
179       }
180     }
181     return false;
182   }
183
184
185   // Determines if the control point values and other information exists
186   bool hasValidControlPointValues(){
187 #if 0
188     std::map<string,int>::iterator iter;
189     for(iter = controlPoints.begin();iter != controlPoints.end(); iter++){
190       if(iter->second == -1){ 
191         return false; 
192       }  
193     }
194 #endif
195     return true;
196   }
197
198   
199 //   int medianCriticalPathIdx() const{
200 //     // Bubble sort the critical path indices by Time
201 //     int numPaths = criticalPaths.size();
202 //     if(numPaths>0){
203 //       int *sortedPaths = new int[numPaths];
204 //       for(int i=0;i<numPaths;i++){
205 //      sortedPaths[i] = i;
206 //       }
207       
208 //       for(int j=0;j<numPaths;j++){
209 //      for(int i=0;i<numPaths-1;i++){
210 //        if(criticalPaths[sortedPaths[i]].getTotalTime() < criticalPaths[sortedPaths[i+1]].getTotalTime()){
211 //          // swap sortedPaths[i], sortedPaths[i+1]
212 //          int tmp = sortedPaths[i+1];
213 //          sortedPaths[i+1] = sortedPaths[i];
214 //          sortedPaths[i] = tmp;
215 //        }
216 //      }
217 //       }
218 //       int result = sortedPaths[numPaths/2];
219 //       delete[] sortedPaths;
220 //       return result;
221 //     } else {
222 //       return 0;
223 //     }
224 //   }
225
226
227
228   bool operator==(const instrumentedPhase& p){
229     CkAssert(hasSameKeysAs(p));
230     std::map<string,int>::iterator iter1 = controlPoints.begin();
231     std::map<string,int>::const_iterator iter2 = p.controlPoints.begin();
232     for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){ 
233       if(iter1->second != iter2->second){ 
234         return false; 
235       }  
236     }
237     return true;
238   }
239
240   /// Verify the names of the control points are consistent
241   /// note: std::map stores the pairs in a sorted order based on their first component 
242   bool hasSameKeysAs(const instrumentedPhase& p){
243     
244     if(controlPoints.size() != p.controlPoints.size())
245       return false;
246
247     std::map<string,int>::iterator iter1 = controlPoints.begin(); 
248     std::map<string,int>::const_iterator iter2 = p.controlPoints.begin(); 
249
250     for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){  
251       if(iter1->first != iter2->first)
252         return false;
253     } 
254
255     return true; 
256   }
257
258
259   void addAllNames(std::set<string> names_) {
260     
261     std::set<string> names = names_;
262     
263     // Remove all the names that we already have
264     std::map<std::string,int>::iterator iter;
265     
266     for(iter = controlPoints.begin(); iter != controlPoints.end(); iter++){
267       names.erase(iter->first);
268     }
269     
270     // Add -1 values for each name we didn't find
271     std::set<std::string>::iterator iter2;
272     for(iter2 = names.begin(); iter2 != names.end(); iter2++){
273       controlPoints.insert(make_pair(*iter2,-1));
274       CkPrintf("One of the datasets was missing a value for %s, so -1 was used\n", iter2->c_str());
275     }
276
277   }
278
279
280
281   void print() {
282     std::map<std::string,int>::iterator iter;
283
284     if(controlPoints.size() == 0){
285       CkPrintf("no control point values found\n");
286     }
287     
288     for(iter = controlPoints.begin(); iter != controlPoints.end(); iter++){
289       std::string name = iter->first;
290       int val = iter->second;
291       CkPrintf("%s ---> %d\n",  name.c_str(),  val);
292     } 
293     
294   }
295   
296   
297 };
298
299
300 /// Stores and manipulate all known instrumented phases. One instance of this exists on each PE in its local controlPointManager
301 class instrumentedData {
302 public:
303
304   /// Stores all known instrumented phases(loaded from file, or from this run)
305   std::vector<instrumentedPhase> phases;
306
307   /// get control point names for all phases
308   std::set<string> getNames(){
309     std::set<string> names;
310     
311     std::vector<instrumentedPhase>::iterator iter;
312     for(iter = phases.begin();iter!=phases.end();iter++) {
313       
314       std::map<string,int>::iterator iter2;
315       for(iter2 = iter->controlPoints.begin(); iter2 != iter->controlPoints.end(); iter2++){
316         names.insert(iter2->first);
317       }
318       
319     }  
320     return names;
321
322   } 
323
324
325   void cleanupNames(){
326     std::set<string> names = getNames();
327     
328     std::vector<instrumentedPhase>::iterator iter;
329     for(iter = phases.begin();iter!=phases.end();iter++) {
330       iter->addAllNames(names);
331     }
332   }
333
334
335   /// Remove one phase with invalid control point values if found
336   bool filterOutOnePhase(){
337 #if 0
338     // Note: calling erase on a vector will invalidate any iterators beyond the deletion point
339     std::vector<instrumentedPhase>::iterator iter;
340     for(iter = phases.begin(); iter != phases.end(); iter++) {
341       if(! iter->hasValidControlPointValues()  || iter->times.size()==0){
342         // CkPrintf("Filtered out a phase with incomplete control point values\n");
343         phases.erase(iter);
344         return true;
345       } else {
346         //      CkPrintf("Not filtering out some phase with good control point values\n");
347       }
348     }
349 #endif
350     return false;
351   }
352   
353   /// Drop any phases that do not contain timings or control point values
354   void filterOutIncompletePhases(){
355     bool done = false;
356     while(filterOutOnePhase()){
357       // do nothing
358     }
359   }
360
361
362   string toString(){
363     ostringstream s;
364
365     verify();
366
367     filterOutIncompletePhases();
368
369     // HEADER:
370     s << "# HEADER:\n";
371     s << "# Data for use with Isaac Dooley's Control Point Framework\n";
372     s << string("# Number of instrumented timings in this file:\n"); 
373     s << phases.size() << "\n" ;
374     
375     if(phases.size() > 0){
376       
377       std::map<string,int> &ps = phases[0].controlPoints; 
378       std::map<string,int>::iterator cpiter;
379
380       // SCHEMA:
381       s << "# SCHEMA:\n";
382       s << "# number of named control points:\n";
383       s << ps.size() << "\n";
384       
385       for(cpiter = ps.begin(); cpiter != ps.end(); cpiter++){
386         s << cpiter->first << "\n";
387       }
388       
389       // DATA:
390       s << "# DATA:\n";
391       s << "# first field is memory usage (MB). Then there are the " << ps.size()  << " control points values, followed by one or more timings" << "\n";
392       s << "# number of control point sets: " << phases.size() << "\n";
393       std::vector<instrumentedPhase>::iterator runiter;
394       for(runiter=phases.begin();runiter!=phases.end();runiter++){
395
396         // Print the memory usage
397          s << runiter->memoryUsageMB << "    "; 
398
399         // Print the control point values
400         for(cpiter = runiter->controlPoints.begin(); cpiter != runiter->controlPoints.end(); cpiter++){ 
401           s << cpiter->second << " "; 
402         }
403
404         s << "     ";
405
406         // Print the times
407         std::vector<double>::iterator titer;
408         for(titer = runiter->times.begin(); titer != runiter->times.end(); titer++){
409           s << *titer << " ";
410         }
411
412         s << "\n";
413         
414       }
415  
416     }
417
418     return s.str();
419     
420   }
421
422
423   /// Verify that all our phases of data have the same sets of control point names
424   void verify(){
425     if(phases.size() > 1){
426       instrumentedPhase & firstpoint = phases[0];
427       std::vector<instrumentedPhase>::iterator iter;
428       for(iter = phases.begin();iter!=phases.end();iter++){
429         CkAssert( firstpoint.hasSameKeysAs(*iter));
430       }  
431     } 
432   }
433
434
435   // Find the fastest time from previous runs
436   instrumentedPhase findBest(){
437     CkAssert(phases.size()>0);
438
439     double total_time = 0.0; // total for all times
440     int total_count = 0;
441
442     instrumentedPhase best_phase;
443 #if OLDMAXDOUBLE
444     double best_phase_avgtime = std::numeric_limits<double>::max();
445 #else
446     double best_phase_avgtime = DBL_MAX;
447 #endif
448
449     int valid_phase_count = 0;
450
451     std::vector<instrumentedPhase>::iterator iter;
452     for(iter = phases.begin();iter!=phases.end();iter++){
453       if(iter->hasValidControlPointValues()){
454         valid_phase_count++;
455
456         double total_for_phase = 0.0;
457         int phase_count = 0;
458
459         // iterate over all times for this control point configuration
460         std::vector<double>::iterator titer;
461         for(titer = iter->times.begin(); titer != iter->times.end(); titer++){
462           total_count++;
463           total_time += *titer;
464           total_for_phase += *titer;
465           phase_count ++;
466         }
467
468         double phase_average_time = total_for_phase / (double)phase_count;
469
470         if(phase_average_time  < best_phase_avgtime){
471           best_phase = *iter;
472           best_phase_avgtime = phase_average_time; 
473         }
474
475       }
476     }
477     
478     CkAssert(total_count > 0);
479
480     double avg = total_time / total_count;
481
482     if(CkMyPe() == 0){
483       CkPrintf("Best average time for a phase was %.1lf\n", best_phase_avgtime);
484       CkPrintf("Mean time for all %d times in the %d valid recorded phases was %.1lf\n", total_count, valid_phase_count, avg );
485     }
486
487     // Compute standard deviation
488     double sumx=0.0;
489     for(iter = phases.begin();iter!=phases.end();iter++){
490       if(iter->hasValidControlPointValues()){
491         std::vector<double>::iterator titer;
492         for(titer = iter->times.begin(); titer != iter->times.end(); titer++){
493           sumx += (avg - *titer)*(avg - *titer);
494         } 
495       }
496     }
497     
498     double std_dev = sqrt(sumx / total_count);
499
500     if(CkMyPe() == 0){
501       CkPrintf("Standard Deviation for previous runs was %.2lf   or %.1lf%% of mean\n", std_dev, std_dev/avg*100.0);
502       CkPrintf("The best phase average time was %.1lf%% faster than the mean\n", (avg-best_phase_avgtime)/avg*100.0);
503
504     }
505
506     return best_phase;
507   }
508   
509 };
510
511 class controlPointManager : public CBase_controlPointManager {
512 public:
513   
514   char * dataFilename;
515   
516   instrumentedData allData;
517   instrumentedPhase thisPhaseData;
518   instrumentedPhase best_phase;
519   
520   pathInformationMsg *pathForUser; // A place to store the path for the user while we go about doing other things.
521
522   /// The lower and upper bounds for each named control point
523   std::map<string, pair<int,int> > controlPointSpace;
524
525   /// A set of named control points whose values cannot change within a single run of an application
526   std::set<string> staticControlPoints;
527
528   /// Sets of entry point ids that are affected by some named control points
529   std::map<string, std::set<int> > affectsPrioritiesEP;
530   /// Sets of entry array ids that are affected by some named control points
531   std::map<string, std::set<int> > affectsPrioritiesArray;
532
533   
534   /// The control points to be used in the next phase. In gotoNextPhase(), these will be used
535   std::map<string,int> newControlPoints;
536   /// Whether to use newControlPoints in gotoNextPhase()
537   bool newControlPointsAvailable;
538   
539   /// A user supplied callback to call when control point values are to be changed
540   CkCallback granularityCallback;
541   bool haveGranularityCallback;
542   bool frameworkShouldAdvancePhase;
543   
544   int phase_id;
545
546   bool alreadyRequestedMemoryUsage;
547   bool alreadyRequestedIdleTime;
548
549
550 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
551   // A table of information about all the paths leading to executions of local entry methods.
552   std::map<int, PathHistoryTableEntry> pathHistoryTable;
553   int pathHistoryTableLastIdx;
554 #endif
555
556   controlPointManager();
557      
558   ~controlPointManager();
559
560
561   /// Loads the previous run data file
562   void loadDataFile();
563
564   /// Add the current data to allData and output it to a file
565   void writeDataFile();
566
567   /// User can register a callback that is called when application should advance to next phase
568   void setGranularityCallback(CkCallback cb, bool _frameworkShouldAdvancePhase);
569
570   /// Called periodically by the runtime to handle the control points
571   /// Currently called on each PE
572   void processControlPoints();
573   
574   /// Determine if any control point is known to affect an entry method
575   bool controlPointAffectsThisEP(int ep);
576   
577   /// Determine if any control point is known to affect a chare array  
578   bool controlPointAffectsThisArray(int array);
579   
580   /// The data from the previous phase
581   instrumentedPhase *previousPhaseData();
582   
583
584   /// Called by either the application or the Control Point Framework to advance to the next phase  
585   void gotoNextPhase();
586
587   /// An application uses this to register an instrumented timing for this phase
588   void setTiming(double time);
589   
590   /// Entry method called on all PEs to request memory usage
591   void requestIdleTime(CkCallback cb);
592   
593   /// All processors reduce their memory usages in requestIdleTime() to this method
594   void gatherIdleTime(CkReductionMsg *msg);
595   
596
597
598   /// Entry method called on all PEs to request memory usage
599   void requestMemoryUsage(CkCallback cb);
600
601   /// All processors reduce their memory usages to this method
602   void gatherMemoryUsage(CkReductionMsg *msg);
603
604
605   /** Trace perform a traversal backwards over the critical path specified as a 
606       table index for the processor upon which this is called.
607       
608       The callback cb will be called with the resulting msg after the path has 
609       been traversed to its origin.  
610   */
611  void traceCriticalPathBack(pathInformationMsg *msg);
612  void broadcastCriticalPathResult(pathInformationMsg *msg);
613  void criticalPathDone(CkReductionMsg *msg);
614   
615
616
617   /// Inform the control point framework that a named control point affects the priorities of some array  
618   void associatePriorityArray(const char *name, int groupIdx);
619   
620   /// Inform the control point framework that a named control point affects the priority of some entry method
621   void associatePriorityEntry(const char *name, int idx);
622   
623 };
624
625
626
627 /** @} */
628 #endif