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