Adding new capability to automatically set message priorities based on critical path...
[charm.git] / src / ck-cp / pathHistory.h
1
2 /**     @defgroup CriticalPathFramework Critical Path Detection
3
4         Usable for determining the critical paths in Charm++, Charisma, and SDAG programs. 
5 */
6
7 /** 
8     A system for exposing application and runtime "control points" 
9     to the dynamic optimization framework.
10
11     @addtogroup CriticalPathFramework
12     @{
13
14 */
15 #ifndef __PATH_HISTORY_H__
16 #define __PATH_HISTORY_H__
17
18 #include <vector>
19 #include <map>
20 #include <utility>
21 #include <cmath>
22 #include "PathHistory.decl.h"
23 #include "envelope.h"
24
25 #include <pup_stl.h>
26
27
28
29 void initializeCriticalPath(void);
30
31 void useThisCriticalPathForPriorities();
32
33
34 class pathHistoryManager : public CBase_pathHistoryManager {
35  private:
36   std::map< std::pair<int,int>, int> criticalPathForPriorityCounts;
37   
38   pathInformationMsg *pathForUser; // A place to store the path while we perform a broadcast and reduction to save projections user events.
39
40  public:
41
42   pathHistoryManager();
43
44   pathHistoryManager(CkMigrateMessage *m){
45     CkAbort("pathHistoryManager does not have a working migration constructor."); 
46   }
47   
48   void pup(PUP::er &p) { 
49     CkAbort("pathHistoryManager cannot be pupped.");
50   } 
51
52
53
54  /** Trace perform a traversal backwards over the critical path specified as a 
55       table index for the processor upon which this is called.
56
57       If msg->saveAsProjectionsUserEvents is true then the resulting path will be 
58       broadcast to broadcastCriticalPathProjections() which will then call a 
59       reduction to criticalPathProjectionsDone() which will call the user supplied 
60       callback.
61       
62       Otherwise, the callback cb will be called with the resulting msg after the path has 
63       been traversed to its origin.  
64
65   */
66  void traceCriticalPathBackStepByStep(pathInformationMsg *msg);
67
68
69
70  void broadcastCriticalPathProjections(pathInformationMsg *msg);
71  void criticalPathProjectionsDone(CkReductionMsg *msg);
72
73  void saveCriticalPathForPriorities(pathInformationMsg *msg);
74
75
76  /// Traverse back and aquire the critical path to be used for automatic message prioritization
77  void useCriticalPathForPriories();
78
79  const std::map< std::pair<int,int>, int> & getCriticalPathForPriorityCounts() const { 
80    return criticalPathForPriorityCounts;
81  }
82   
83 };
84
85
86
87 /**
88    Augments the PathHistory in the envelope with the other necessary information
89    from the envelope. These should be derived from an incoming message.
90
91    These objects can then be used for storing of information about a path 
92    outside of the incoming message's header. 
93
94    These are used for:
95       1) information about the currently executing message
96       2) combining the maximum paths along a reduction
97       3) combining multiple paths in Charisma and SDAG programs
98
99    This can be constructed from an envelope.
100 */
101
102 class MergeablePathHistory {
103  public:
104   double timeEntryMethodStarted;
105
106   double preceding_path_time;
107
108   int sender_pe;  // for traversing back over the PAG
109   int sender_history_table_idx; // for traversing back over the PAG
110   
111   int local_ep;  // The locally executing EP
112   int local_arr; // The locally executing array
113
114 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
115  MergeablePathHistory(const envelope *env) 
116    : sender_pe(env->getSrcPe()), 
117     sender_history_table_idx(env->pathHistory.get_sender_history_table_idx()), 
118     local_ep(env->getEpIdx()),
119     local_arr(env->getArrayMgrIdx()),
120     preceding_path_time(env->pathHistory.getTime()),
121     timeEntryMethodStarted(0.0)
122       {
123         // No body
124       }
125 #else
126  MergeablePathHistory(const envelope *env) 
127    : sender_pe(env->getSrcPe()), 
128     local_ep(env->getEpIdx()),
129     local_arr(env->getArrayMgrIdx()),
130     timeEntryMethodStarted(0.0)
131       {
132         // No body
133       }
134 #endif
135
136   MergeablePathHistory() {
137     reset();
138   }
139   
140   void reset(){
141     sender_pe = -1; 
142     sender_history_table_idx = -1; 
143     local_ep = -1;
144     preceding_path_time = 0.0;
145     timeEntryMethodStarted = 0.0;
146   }
147   
148   void sanity_check(){
149     if(sender_history_table_idx > -1){ 
150       CkAssert(sender_pe < CkNumPes()); 
151       CkAssert(sender_pe >= -1);
152     }
153 /*     CkAssert(sender_history_table_idx < 100000); */
154 /*     CkAssert(sender_history_table_idx >= 0); */
155    
156 /*     CkAssert(local_ep < 500); */
157 /*     CkAssert(local_ep >= 0); */
158
159   }
160
161   void updateMax(const MergeablePathHistory& other){
162     if(preceding_path_time < other.preceding_path_time)
163       *this = other;
164   }
165
166
167   void updateMax(const envelope* env){
168     updateMax(MergeablePathHistory(env));
169   }
170   
171   double getTotalTime() const{
172     return preceding_path_time;
173   }
174
175   /// Write a description of the path into the beginning of the provided buffer. The buffer ought to be large enough.
176   void printHTMLToString(char* buf) const{
177 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
178     buf[0] = '\0';
179     sprintf(buf+strlen(buf), "MergeablePathHistory time=%lf send pe=%d idx=%d timeEntryStarted=%lf", (double)preceding_path_time, (int)sender_pe, (int)sender_history_table_idx, (double)timeEntryMethodStarted);
180 #endif
181   }
182
183   void setDebug100(){
184     preceding_path_time = 100.0;
185     CkPrintf("Setting path length to 100\n");
186   }
187
188 };
189
190
191 /** 
192     Stores information about the critical path in the table on each PE. 
193     The PAG can be constructed by merging these together.
194
195     These can be constructed from a MergeablePathHistory, and are assumed to refer to the local PE.
196 */
197 class PathHistoryTableEntry {
198 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
199
200  public:
201   int sender_pe;
202   int sender_history_table_idx;
203   int local_ep;
204   int local_arr;
205   int local_pe;
206
207  private:
208   double start_time;
209   double local_path_time;
210   double preceding_path_time;
211
212  public:
213   
214  PathHistoryTableEntry() 
215    : sender_pe(-1), 
216     sender_history_table_idx(-1), 
217     start_time(0.0),
218     local_path_time(0.0), 
219     preceding_path_time(0.0),     
220     local_ep(-1),
221     local_arr(-1),
222     local_pe(CkMyPe())
223       {
224         // No body
225       }
226   
227
228   /// Construct an entry for the table assuming the start time in input path is correct
229  PathHistoryTableEntry(const MergeablePathHistory& p, double localContribution = 0.0)
230     : sender_pe(p.sender_pe), 
231     sender_history_table_idx(p.sender_history_table_idx), 
232     local_path_time(localContribution), 
233     preceding_path_time(p.preceding_path_time),
234     start_time(p.timeEntryMethodStarted),
235     local_ep(p.local_ep),
236     local_arr(p.local_arr),
237     local_pe(CkMyPe())
238       {
239         // No body
240       }
241
242   /// Construct an entry with the actual start and end times for it.
243   PathHistoryTableEntry(const MergeablePathHistory& p, double start, double finish)
244     : sender_pe(p.sender_pe), 
245     sender_history_table_idx(p.sender_history_table_idx), 
246     local_path_time(finish-start), 
247     preceding_path_time(p.preceding_path_time),
248     start_time(start),
249     local_ep(p.local_ep),
250     local_arr(p.local_arr),
251     local_pe(CkMyPe())
252       {
253         // No body
254       }
255
256   void printInfo(char *prefix = ""){
257     CkPrintf("%s [sender pe=%d table idx=%d] [local path contribution=%lf ep=%d] [Time= %lf + %lf]\n", prefix,  
258              sender_pe, sender_history_table_idx, local_path_time, local_ep, preceding_path_time, local_path_time);  
259   }
260
261
262   /// Add an entry for this path history into the table, and write the corresponding information into the provided header
263   int addToTableAndEnvelope(envelope *env);
264   
265   /// Add an entry for this path history into the table. Returns the new index in the table.
266   int addToTable();
267   
268   /// Return the length of the path up to and including this entry
269   double getTotalTime(){
270     return local_path_time + preceding_path_time;
271   }
272
273   double get_start_time() const {return start_time;}
274   double get_local_path_time() const {return local_path_time;}
275   double get_preceding_path_time() const {return preceding_path_time;}
276 #endif
277
278 };
279
280
281
282 /// A debugging routine that outputs critical path info as Projections user events.
283 void  saveCurrentPathAsUserEvent(char* prefix="");
284
285 /// A debugging helper routine that sets the values in the currently executing message's path to 100
286 void setCurrentlyExecutingPathTo100(void);
287
288 /// A debugging routine that outputs critical path info as Projections user events.
289 void  printPathInMsg(void* msg);
290
291 /// A debugging routine that outputs critical path info as Projections user events.
292 void  printEPInfo();
293
294
295 /// Acquire the critical path and deliver it to the user supplied callback
296 void traceCriticalPathBack(CkCallback cb, bool saveToProjectionsTraces = false);
297
298
299 /// A message containing information about a path of entry method invocations. This contains an array of PathHistoryTableEntry objects
300 class pathInformationMsg : public CMessage_pathInformationMsg {
301  public:
302   PathHistoryTableEntry *history;
303   int historySize;
304   int saveAsProjectionsUserEvents;
305   CkCallback cb;
306   int table_idx;
307
308   void printme(){
309 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
310     CkPrintf("Path contains %d entries\n", historySize);
311     for(int i=historySize-1;i>=0;i--){
312       CkPrintf("\tPath Step %d: local_path_time=%lf arr=%d ep=%d starttime=%lf preceding path time=%lf pe=%d\n",i, history[i].get_local_path_time(),  history[i].local_arr, history[i].local_ep, history[i].get_start_time(), history[i].get_preceding_path_time(), history[i].local_pe);
313     }
314 #endif    
315   }
316   
317 };
318
319
320 CkpvExtern(MergeablePathHistory, currentlyExecutingPath); // The maximal incoming path for the node
321 CkpvExtern(double, timeEntryMethodStarted);
322
323
324 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
325 /** A table to store all the local nodes in the parallel dependency graph */
326 typedef std::map<int, PathHistoryTableEntry> PathHistoryTableType;
327 CkpvExtern(PathHistoryTableType, pathHistoryTable);
328 /** A counter that defines the new keys for the entries in the pathHistoryTable */
329 CkpvExtern(int, pathHistoryTableLastIdx);
330
331
332
333
334 // Reset the counts for the currently executing message. Cut the incoming path
335 extern void resetThisEntryPath();
336
337 extern void criticalPath_start(envelope * env); 
338 extern void criticalPath_send(envelope * sendingEnv);
339 extern void criticalPath_end();
340 extern void criticalPath_split(); 
341
342
343
344
345 /// Wrappers for Charm++ programs to use to annotate their program dependencies
346
347 /// Declare a MergeablePathHistory variable, whose name is mangled with the supplied parameter
348 #define MERGE_PATH_DECLARE(x) MergeablePathHistory merge_path_##x
349
350 /// Reset the merge_path variable
351 #define MERGE_PATH_RESET(x) merge_path_##x.reset()
352
353 /// Take the maximal path from the stored merge_path variable and the currently executing path. Put the result in currently executing path.
354 #define MERGE_PATH_MAX(x) merge_path_##x.updateMax(CkpvAccess(currentlyExecutingPath)); CkpvAccess(currentlyExecutingPath) = merge_path_##x; 
355
356
357
358 /// Declare a dynamic MergeablePathHistory variable. Each object can have many merge points stored in this single DECLARE.
359 #define MERGE_PATH_DECLARE_D(x) std::map<int,MergeablePathHistory> merge_path_D_##x
360
361 /// Reset the merge_path variable
362 #define MERGE_PATH_RESET_D(x,n) merge_path_D_##x[n].reset()
363
364 /// Delete the merge_path variable
365 #define MERGE_PATH_DELETE_D(x,n) merge_path_D_##x.erase(n)
366
367 /// Delete all entries in the merge_path variable
368 #define MERGE_PATH_DELETE_ALL_D(x) merge_path_D_##x.clear()
369
370 /// Take the maximal path from the stored merge_path variable and the currently executing path. Put the result in currently executing path.
371 #define MERGE_PATH_MAX_D(x,n) merge_path_D_##x[n].updateMax(CkpvAccess(currentlyExecutingPath)); CkpvAccess(currentlyExecutingPath) = merge_path_D_##x[n]; 
372
373
374
375 #else
376
377
378 /// Empty no-op version for when critical path history is not compiled in
379
380 #define MERGE_PATH_DECLARE(x) ;
381 #define MERGE_PATH_RESET(x) ;
382 #define MERGE_PATH_MAX(x) ;
383 #define MERGE_PATH_DECLARE_D(x) ;
384 #define MERGE_PATH_RESET_D(x,n) ;
385 #define MERGE_PATH_DELETE_D(x,n) ;
386 #define MERGE_PATH_DELETE_ALL_D(x) ;
387 #define MERGE_PATH_MAX_D(x,n) ;
388
389
390 #endif
391
392
393
394
395 /** @} */
396 #endif