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