Moving the "critical path" history code into its own module which is included in...
[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 "arrayRedistributor.h"
33 #include "pathHistory.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   /// The lower and upper bounds for each named control point
521   std::map<string, pair<int,int> > controlPointSpace;
522
523   /// A set of named control points whose values cannot change within a single run of an application
524   std::set<string> staticControlPoints;
525
526   /// Sets of entry point ids that are affected by some named control points
527   std::map<string, std::set<int> > affectsPrioritiesEP;
528   /// Sets of entry array ids that are affected by some named control points
529   std::map<string, std::set<int> > affectsPrioritiesArray;
530
531   
532   /// The control points to be used in the next phase. In gotoNextPhase(), these will be used
533   std::map<string,int> newControlPoints;
534   /// Whether to use newControlPoints in gotoNextPhase()
535   bool newControlPointsAvailable;
536   
537   /// A user supplied callback to call when control point values are to be changed
538   CkCallback granularityCallback;
539   bool haveGranularityCallback;
540   bool frameworkShouldAdvancePhase;
541   
542   int phase_id;
543
544   bool alreadyRequestedMemoryUsage;
545   bool alreadyRequestedIdleTime;
546
547   controlPointManager();
548      
549   ~controlPointManager();
550
551
552   /// Loads the previous run data file
553   void loadDataFile();
554
555   /// Add the current data to allData and output it to a file
556   void writeDataFile();
557
558   /// User can register a callback that is called when application should advance to next phase
559   void setGranularityCallback(CkCallback cb, bool _frameworkShouldAdvancePhase);
560
561   /// Called periodically by the runtime to handle the control points
562   /// Currently called on each PE
563   void processControlPoints();
564   
565   /// Determine if any control point is known to affect an entry method
566   bool controlPointAffectsThisEP(int ep);
567   
568   /// Determine if any control point is known to affect a chare array  
569   bool controlPointAffectsThisArray(int array);
570   
571   /// The data from the previous phase
572   instrumentedPhase *previousPhaseData();
573   
574
575   /// Called by either the application or the Control Point Framework to advance to the next phase  
576   void gotoNextPhase();
577
578   /// An application uses this to register an instrumented timing for this phase
579   void setTiming(double time);
580   
581   /// Entry method called on all PEs to request memory usage
582   void requestIdleTime(CkCallback cb);
583   
584   /// All processors reduce their memory usages in requestIdleTime() to this method
585   void gatherIdleTime(CkReductionMsg *msg);
586   
587
588
589   /// Entry method called on all PEs to request memory usage
590   void requestMemoryUsage(CkCallback cb);
591
592   /// All processors reduce their memory usages to this method
593   void gatherMemoryUsage(CkReductionMsg *msg);
594
595
596
597
598
599   /// Inform the control point framework that a named control point affects the priorities of some array  
600   void associatePriorityArray(const char *name, int groupIdx);
601   
602   /// Inform the control point framework that a named control point affects the priority of some entry method
603   void associatePriorityEntry(const char *name, int idx);
604   
605 };
606
607
608
609 /** @} */
610 #endif