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