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