re-worked cksection callback. Make cksectionInfo a struct so that it can be included...
[charm.git] / src / ck-com / ComlibManager.h
1 #ifndef COMLIBMANAGER_H
2 #define COMLIBMANAGER_H
3
4
5 /**
6    @{
7    
8    @file
9
10    @brief Charm ComlibManager
11    Contains the classes ComlibManager (charm++ delegated group) and
12    ComlibDelegateData (its delegated data). It also declares the user
13    interface to the framework, all beginning with the prefix "Comlib".
14
15
16    @defgroup Comlib  Communication Optimization Framework
17    @brief A communication optimization framework.
18
19    Comlib is a framework for delegating converse and charm++ level communications to optimizing strategies which can use appropriate topological routers.
20
21    The comlib framework underwent a large refactoring that was committed into CVS in February 2009. The framework was extricated from ck-core. Various files and classes were renamed, and many bugs were fixed. A new system for bracketed strategies was introduced. 
22
23    Bracketed communication strategies, such as those for all-to-all communication, now have knowledge that is updated on demand. If errors are detected in the knowledge base (eg. a chare array element is no longer located on some PE), the strategies enter an error mode. After the knowledge has been updated, the strategies will exit the error mode and send messages along the new optimized paths. While in the error states, the strategies send existing messages directly, and buffer new messages.
24
25
26 <h2>Usage Restrictions</h2>
27 Strategies should be created in a MainChare's Main method (hence on PE 0). Proxies can be created later and these can be delegated to the existing strategies. 
28
29   
30 <h2>Startup</h2>
31
32   The initilization of Comlib is done both asynchronously for parts and at startup for other parts. There is an initproc routine 
33   initConvComlibManager() that instantiates the Ckpv processor local conv_com_object. This needs to be created before the ComlibManagerMain method is called. Because we cannot guarantee the order for which the mainchares execute, we must do this in an initproc routine.
34
35
36    The startup of Comlib happens asynchronously. The <i>mainchare ComlibManagerMain</i> has a constructor that runs along with all other mainchares while charm++ messages are not activated at startup. This constructor simply sets a few variables from command line arguments, and then creates the <i>ComlibManager group </i>. After all mainchares have run (in no determinable order), then the charm++ system will release all charm++ messages. 
37
38    At this point the user program will continue asynchronously with the comlib startup.
39   
40    Then ComlibManager::ComlibManager() calls ComlibManager::init(), sets up a few variables, and then calls ComlibManager::barrier(). After barrier() has been called by all PEs, it calls ComlibManager::resumeFromSetupBarrier(). 
41
42    ComlibManager::resumeFromSetupBarrier() completes the initialization of the charm layer of comlib after all group branches are created. It is guaranteed that Main::Main has already run at this point, so all strategies created there can be broadcast.  This function calls ComlibDoneCreating() and then it sends all messages that were buffered (in unCompletedSetupBuffer).
43
44    ComlibDoneCreating() will do nothing on all PE != 0. On PE 0, it will call ConvComlibManager::doneCreating(). The strategy table will broadcast at this point.
45
46    The process for broadcasting the strategy table is as follows (see convcomlibmanager.C):
47  
48    <ol>
49    <li>the strategies are inserted on processor 0 (and possibly in other
50    processors with the same order. The strategies are marked as "new"
51    <li>when ConvComlibManager::doneCreating() is called, processor 0 broadcasts all the new
52    strategies to all the processors, and marks them as "inSync"  
53    <li>when a processor receives a table it updates its personal table with the
54    incoming, it marks all the strategies just arrived as "inSync", and it
55    sends an acknowledgement back to processor 0.   
56    <li>when an acknowledgement is received by processor 0, a counter is
57    decremented. When it reaches 0, all the "inSync" strategies are switched
58    to status "ready" and they can start working. All the messages in the
59    tmplist are delivered. The sync is broadcasted.   
60    <li>when an acknowledgement is received by a processor other than 0, all the
61    "inSync" strategies are switched to "ready" and the messages in tmplist
62    are delivered.   
63    <li>in order to prevent two consecutive table broadcasts to interfere with
64    each other, an additional acknowledgement is sent back by each processor
65    to processor 0 to allow a new table update to happen.
66    </ol>
67
68 <h2>Startup: Buffering of Messages</h2>
69
70    Because the startup of Comlib happens asynchronously. Thus, if a user program sends messages through a comlib strategy, and the strategy has not yet started up completely, then the messages may be delayed in one of two queues. 
71    
72 <ol>
73    <li>CkQ<MessageHolder*> tmplist; found in convcomlibstrategy.h buffers converse level messages when the converse strategies are not ready.
74    <li>std::map<ComlibInstanceHandle, std::set<CharmMessageHolder*> > ComlibManager::delayMessageSendBuffer in ComlibManager.h buffers charm level messages at startup before ComlibManager::resumeFromSetupBarrier() or while a strategy is in an error state. Messages are flushed from here once both the startup has finished and the strategy is not in an error state. The messages are flushed from one place: ComlibManager::sendBufferedMessages().
75 </ol>
76   
77
78
79
80 <h2>Bracketed Strategies</h2>
81 <h3>Usage of Bracketed Strategies</h3>
82 Bracketed strategies have the following usage pattern. For each iteration of the program: 
83 <ol>
84 <li>Each source object calls ComlibManager::beginIteration(int instid, int iteration)
85 <li>Each source object invokes one or more entry method(s) on the delegated proxy
86 <li>Each source object then calls ComlibManager::endIteration().
87 </ol>
88
89 <h3>Restrictions on Bracketed Strategies</h3>
90 <ol>
91 <li>The user application is not allowed to call beginIteration for iteration n until all messages from iteration n-1 have been received.
92 <li>Migrations of elements are not allowed between when they call ComlibManager::beginIteration and the associated ComlibManager::endIteration for the same iteration.
93 </ol>
94
95 <h3>Detecting migrations in Bracketed Strategies</h3>
96 The instance of each strategy on each PE maintains a list of the local array elements, and the last known iteration value. The current implementation only detects migrations when a PE gains a net positive number of migrated objects. All of the objects on that PE will call ComlibManager::beginIteration. Because the strategy knows how many elements were previously on the PE, it will detect more calls to ComlibManager::beginIteration than its previous element count. At this point, the future messages for the strategy will be enqueued in a buffer (ComlibManager::delayMessageSendBuffer). Once ComlibManager::endIteration() is called, the error recovery protocol will be started. All PEs will cause any objects that have migrated away to report back to PE 0, which updates a list of object locations. Once all PEs and migrated objects have reported back to PE 0, the updated PE list will be broadcast to all PEs, and the strategy will be enabled again. At this point any buffered messages will be released. The subsequent iteration of the application should then be optimized.
97
98 If two objects swap places between two PEs, the current implementation does not detect this change. In the future ComlibManager::beginIteration should compare the object to the list of known local objects, and start buffering messages and correcting this error condition.
99
100
101
102    
103    @defgroup ConvComlib  Converse Communication Optimization Framework 
104    @ingroup Comlib
105    @brief Framework for delegating converse level communication to Comlib.
106
107
108    @defgroup CharmComlib  Charm++ Communication Optimization Framework 
109    @ingroup Comlib
110    @brief Framework for delegating Charm++ level communication to Comlib. 
111
112
113    @defgroup ConvComlibRouter Converse level message Routers
114    @ingroup ConvComlib
115    @ingroup Comlib
116    @brief Routers used by converse strategies to route messages in certain topologies : grid, hypercube, etc.
117
118    Each router inherits from Router. 
119
120
121    @defgroup ComlibCharmStrategy Strategies for use in Charm++
122    @ingroup CharmComlib
123    @ingroup Comlib
124    @brief Communication optimizing strategies for use in Charm++ programs.
125
126    These strategies are used in Charm++ programs, by creating proxies that are then associated with a strategy. The future method invocations on the proxy are then handled by the strategy. 
127
128
129    @defgroup ComlibConverseStrategy Strategies for use in converse
130    @ingroup ConvComlib
131    @ingroup Comlib
132    @brief Communication optimizing strategies for use in converse programs or in other comlib strategies.
133
134 */
135
136
137
138 #include <math.h>
139 #include <map>
140 #include <set>
141
142 #include "convcomlibmanager.h"
143 #include "ComlibStrategy.h"
144 #include "ComlibArrayListener.h"
145 #include "cksection.h"
146
147 #define CHARM_MPI 0 
148 #define MAX_NSTRAT 1024
149 #define LEARNING_PERIOD 1000 //Number of iterations after which the
150                              //learning framework will discover 
151                              //the appropriate strategy, not completely 
152                              //implemented
153 #include "ComlibStats.h"
154
155 #include "comlib.decl.h"
156
157 CkpvExtern(CkGroupID, cmgrID);
158 ///Dummy message to be sent in case there are no messages to send. 
159 ///Used by only the EachToMany strategy!
160 class ComlibDummyMsg: public CMessage_ComlibDummyMsg {
161     int dummy;
162 };
163
164
165
166 /**
167  * Structure used to hold a count of the indeces associated to each pe in a
168  * multicast message.
169  */
170 // TO BE MOVED TO MULTICAST SPECIFIC
171 struct ComlibMulticastIndexCount {
172   int pe;
173   int count;
174 };
175
176 ///for use of qsort
177 inline int indexCountCompare(const void *a, const void *b) {
178   ComlibMulticastIndexCount a1 = *(ComlibMulticastIndexCount*) a;
179   ComlibMulticastIndexCount b1 = *(ComlibMulticastIndexCount*) b;
180
181   if(a1.pe < b1.pe)
182     return -1;
183   
184   if(a1.pe == b1.pe)
185     return 0;
186   
187   if(a1.pe > b1.pe)
188     return 1;
189   
190   return 0;
191 }
192
193
194 /** A class for multicast messages that contains the user message 
195     as well as a list of all destination indices and corresponding PEs 
196 */
197 class ComlibMulticastMsg : public CkMcastBaseMsg, 
198                public CMessage_ComlibMulticastMsg {
199   public:
200     int nPes;
201     ComlibMulticastIndexCount *indicesCount;
202     CkArrayIndex *indices;
203     char *usrMsg;        
204 };
205
206
207 void ComlibAssociateProxy(ComlibInstanceHandle cinst, CProxy &proxy);
208 void ComlibAssociateProxy(Strategy *strat, CProxy &proxy); 
209
210 /// @deprecated
211 ComlibInstanceHandle ComlibRegister(Strategy *strat);
212
213 void ComlibBegin(CProxy &proxy, int iteration);    
214 void ComlibEnd(CProxy &proxy, int iteration);    
215
216 /** The behaviour has changed from the previous version:
217     while before this function was used to reset a proxy after a migration,
218     now it is used to reset a proxy before it is reassociated with another strategy. 
219  */
220 inline void ComlibResetSectionProxy(CProxySection_ArrayBase &sproxy) {
221   sproxy.ckGetSectionInfo().info.sInfo.cInfo.id = 0;
222 }
223
224
225 void ComlibInitSectionID(CkSectionID &sid);
226
227 class LBMigrateMsg;
228
229 /** The main group doing the management of all the charm system. It takes care
230     of calling the strategies when a message arrives, and modifying them when
231     needed by the learning framework. It relies on ConvComlibManager for the
232     processor operations involved. It installes itself as a delegated class from
233     CkDelegateMgr, overwriting the standard path of message sending in charm.
234  */
235 class ComlibManager: public CkDelegateMgr {
236   //friend class ComlibInstanceHandle;
237
238     int *bcast_pelist;  //Pelist passed to all broadcast operations
239
240     /// Used to register and record events into projection
241     int section_send_event;
242
243     CkArrayIndex dummyArrayIndex;
244
245     /// Pointer to the converse comlib object, for efficiency over calling CkpvAccess
246     ConvComlibManager *converseManager;
247
248
249     /// Lists of messages whose delivery will be postponed until the comlib strategy has been fully setup, and 
250     /// the strategy has exited an error state
251     /// The map key is a comlib instance handle
252     /// The map value is a set of messages
253     std::map<ComlibInstanceHandle, std::set<CharmMessageHolder*> > delayMessageSendBuffer;
254    
255  
256     /// Different than 0 once this group has been created on all processors
257     int setupComplete;
258   
259     int prioEndIterationFlag;
260
261     ComlibGlobalStats clib_gstats; 
262     int numStatsReceived;
263
264     int curComlibController;   //Processor where strategies are created
265     int clibIteration;         //Number of such learning iterations,
266                                //each of which is triggered by a
267                                //loadbalancing operation
268
269     void init(); ///Initialization function
270
271     //charm_message for multicast for a section of that group
272     void multicast(CharmMessageHolder *cmsg, int instid); //charm message holder here
273     //void multicast(void *charm_msg, int npes, int *pelist);
274
275     //The following funtions can be accessed only from the user provided hooks
276     friend void ComlibBegin(CProxy&, int iteration);
277     friend void ComlibEnd(CProxy&, int iteration);
278
279     ///Notify begining of a bracket with strategy identifier
280     void beginIteration(int instid, int iteration);
281     
282     ///Notify end, endIteration must be called if a beginIteration is called.
283     ///Otherwise end of the entry method is assumed to be the end of the
284     ///bracket.
285     void endIteration(int instid, int iteration);
286     
287     void printPeList(const char* note, int *peList);
288
289     
290     bool shouldBufferMessagesNow(int instid);
291     void sendBufferedMessages(int instid, int step=-1);
292     void sendBufferedMessagesAllStrategies();
293
294  public:
295
296     ComlibLocalStats clib_stats;   //To store statistics of
297                                    //communication operations
298     
299     ComlibManager();  //Recommended constructor
300
301     ComlibManager(CkMigrateMessage *m) { }
302     int useDefCtor(void){ return 1; } //Use default constructor should
303     //be pupped and store all the strategies.
304
305     /* Initialization routines */
306     
307     void barrier(void);
308     void resumeFromSetupBarrier();
309    
310     /* The delegation framework reimplemented functions */
311
312     void ArraySend(CkDelegateData *pd,int ep, void *msg, 
313                    const CkArrayIndex &idx, CkArrayID a);
314     void GroupSend(CkDelegateData *pd, int ep, void *msg, int onpe, 
315                    CkGroupID gid);
316     void ArrayBroadcast(CkDelegateData *pd,int ep,void *m,CkArrayID a);
317     void GroupBroadcast(CkDelegateData *pd,int ep,void *m,CkGroupID g);
318     void ArraySectionSend(CkDelegateData *pd, int ep ,void *m, 
319                                   int nsid, CkSectionID *s, int opts);
320     CkDelegateData* ckCopyDelegateData(CkDelegateData *data); 
321     CkDelegateData *DelegatePointerPup(PUP::er &p,CkDelegateData *pd);
322
323     inline Strategy *getStrategy(int instid)
324         {return converseManager->getStrategy(instid);}
325
326     inline StrategyTableEntry *getStrategyTableEntry(int instid)
327         {return converseManager->getStrategyTable(instid);}
328
329     // Entry methods used by bracketed strategies when there is some object
330     // migration. The comlib Manager realizes there is an error, it enters error
331     // mode by suspending the delivery of the strategy if it has already
332     // started, and it globally reduces the number of elements which already
333     // called endIteration. When this number matches the number of elements
334     // involved in the operation (or a multiple of it in case the user overlaps
335     // iterations), the system ri-deliver the doneInserting to the strategy.
336     //  void bracketedFinishSetup(int instid);
337     void bracketedCatchUpPE(int instid, int step);
338     void bracketedReceiveCount(int instid, int pe, int count, int isFirst, int step);
339     void bracketedStartErrorRecoveryProcess(int instid, int step);
340     void bracketedErrorDetected(int instid, int step);
341     void bracketedConfirmCount(int instid, int step);
342     void bracketedCountConfirmed(int instid, int count, int step);
343     void bracketedReceiveNewCount(int instid, int step);
344     void bracketedReceiveNewPeList(int instid, int step, int *count);
345
346     void bracketedFinalBarrier(int instid, int step);
347     void bracketedReleaseCount(int instid, int step);
348     void bracketedReleaseBufferedMessages(int instid, int step);
349
350     void bracketedStartDiscovery(int instid);
351     void bracketedDiscover(int instid, CkArrayID aid, CkArrayIndex &idx, int isSrc);
352     void bracketedContributeDiscovery(int instid, int pe, int nsrc, int ndest, int step);
353
354
355     // TODO: Delete the following two methods!!!!
356     void AtSync();           //User program called loadbalancer
357     void lbUpdate(LBMigrateMsg *); //loadbalancing updates
358
359     //Learning functions
360     //void learnPattern(int totalMessageCount, int totalBytes);
361     //void switchStrategy(int strat);
362
363     //void collectStats(ComlibLocalStats &s, int src,CkVec<ClibGlobalArrayIndex>&);
364     void collectStats(ComlibLocalStats &s, int src);
365  
366
367     /// Print information about the number of undelivered messages awaiting a specified strategy to be ready    
368     void printDiagnostics(int cinst);
369
370     /// Print information about the number of undelivered messages awaiting any strategy to be ready
371     void printDiagnostics();   
372        
373 }; 
374
375 /** This class is used by ComlibManager (the delegator manager) as its delegated
376     data. The only thing it contains is the position in the system of the
377     strategy it represents.
378  */
379 class ComlibDelegateData : public CkDelegateData {
380  private:
381   int _instid; ///< Position of this instance in the strategy table
382
383   friend void ComlibAssociateProxy(ComlibInstanceHandle, CProxy&);
384   friend CkDelegateData *ComlibManager::ckCopyDelegateData(CkDelegateData*);
385   ComlibDelegateData(int instid);
386
387  public:
388   ComlibDelegateData(CkMigrateMessage *) : CkDelegateData() { ref(); }
389   
390   void beginIteration();
391   void endIteration();
392
393   /// Get the position of this instance in the strategy table
394   inline int getID() {return _instid;}
395   
396   void pup(PUP::er &p) {
397     p | _instid;
398   }
399
400 };
401
402 void ComlibAtSync(void *msg);
403 void ComlibNotifyMigrationDoneHandler(void *msg);
404 void ComlibLBMigrationUpdate(LBMigrateMsg *);
405
406
407 #ifdef filippo
408 // The old interface
409 #define RECORD_SENDSTATS(sid, bytes, dest) {             \
410         CProxy_ComlibManager cgproxy(CkpvAccess(cmgrID));               \
411         cgproxy.ckLocalBranch()->clib_stats.recordSend(sid, bytes, dest); \
412 }\
413
414 #define RECORD_RECV_STATS(sid, bytes, src) { \
415         CProxy_ComlibManager cgproxy(CkpvAccess(cmgrID)); \
416         cgproxy.ckLocalBranch()->clib_stats.recordRecv(sid, bytes, src); \
417 }\
418
419 #define RECORD_SENDM_STATS(sid, bytes, dest_arr, ndest) {       \
420         CProxy_ComlibManager cgproxy(CkpvAccess(cmgrID)); \
421         cgproxy.ckLocalBranch()->clib_stats.recordSendM(sid, bytes, dest_arr, ndest); \
422 }\
423
424 #define RECORD_RECVM_STATS(sid, bytes, src_arr, nsrc) {        \
425         CProxy_ComlibManager cgproxy(CkpvAccess(cmgrID)); \
426         cgproxy.ckLocalBranch()->clib_stats.recordRecvM(sid, bytes, src_arr, nsrc); \
427 }\
428
429 #else
430 // the new version of comlib does not do anything with these yet
431 #define RECORD_SEND_STATS(sid, bytes, dest) /* empty */
432 #define RECORD_RECV_STATS(sid, bytes, src) /* empty */
433 #define RECORD_SENDM_STATS(sid, bytes, dest_arr, ndest) /* empty */
434 #define RECORD_RECVM_STATS(sid, bytes, src_arr, nsrc) /* empty */
435 #endif
436
437 /** @} */
438
439 #endif