Adding some new multicast strategies.
[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 /** Used to setup a multicast tree in SectionInfo and MulticastStrategies */
194 // TO BE MOVED TO MULTICAST SPECIFIC
195 class ComlibMulticastMsg : public CkMcastBaseMsg, 
196                public CMessage_ComlibMulticastMsg {
197     
198   public:
199     int nPes;
200     ComlibMulticastIndexCount *indicesCount;
201     CkArrayIndexMax *indices;
202     char *usrMsg;        
203 };
204
205
206 void ComlibAssociateProxy(ComlibInstanceHandle cinst, CProxy &proxy);
207 void ComlibAssociateProxy(Strategy *strat, CProxy &proxy); 
208
209 /// @deprecated
210 ComlibInstanceHandle ComlibRegister(Strategy *strat);
211
212 void ComlibBegin(CProxy &proxy, int iteration);    
213 void ComlibEnd(CProxy &proxy, int iteration);    
214
215 /** The behaviour has changed from the previous version:
216     while before this function was used to reset a proxy after a migration,
217     now it is used to reset a proxy before it is reassociated with another strategy. 
218  */
219 inline void ComlibResetSectionProxy(CProxySection_ArrayBase &sproxy) {
220   sproxy.ckGetSectionInfo().sInfo.cInfo.id = 0;
221 }
222
223
224 void ComlibInitSectionID(CkSectionID &sid);
225
226 class LBMigrateMsg;
227
228 /** The main group doing the management of all the charm system. It takes care
229     of calling the strategies when a message arrives, and modifying them when
230     needed by the learning framework. It relies on ConvComlibManager for the
231     processor operations involved. It installes itself as a delegated class from
232     CkDelegateMgr, overwriting the standard path of message sending in charm.
233  */
234 class ComlibManager: public CkDelegateMgr {
235   //friend class ComlibInstanceHandle;
236
237     int *bcast_pelist;  //Pelist passed to all broadcast operations
238
239     /// Used to register and record events into projection
240     int section_send_event;
241
242     CkArrayIndexMax dummyArrayIndex;
243
244     /// Pointer to the converse comlib object, for efficiency over calling CkpvAccess
245     ConvComlibManager *converseManager;
246
247
248     /// Lists of messages whose delivery will be postponed until the comlib strategy has been fully setup, and 
249     /// the strategy has exited an error state
250     /// The map key is a comlib instance handle
251     /// The map value is a set of messages
252     std::map<ComlibInstanceHandle, std::set<CharmMessageHolder*> > delayMessageSendBuffer;
253    
254  
255     /// Different than 0 once this group has been created on all processors
256     int setupComplete;
257   
258     int prioEndIterationFlag;
259
260     ComlibGlobalStats clib_gstats; 
261     int numStatsReceived;
262
263     int curComlibController;   //Processor where strategies are created
264     int clibIteration;         //Number of such learning iterations,
265                                //each of which is triggered by a
266                                //loadbalancing operation
267
268     void init(); ///Initialization function
269
270     //charm_message for multicast for a section of that group
271     void multicast(CharmMessageHolder *cmsg, int instid); //charm message holder here
272     //void multicast(void *charm_msg, int npes, int *pelist);
273
274     //The following funtions can be accessed only from the user provided hooks
275     friend void ComlibBegin(CProxy&, int iteration);
276     friend void ComlibEnd(CProxy&, int iteration);
277
278     ///Notify begining of a bracket with strategy identifier
279     void beginIteration(int instid, int iteration);
280     
281     ///Notify end, endIteration must be called if a beginIteration is called.
282     ///Otherwise end of the entry method is assumed to be the end of the
283     ///bracket.
284     void endIteration(int instid, int iteration);
285     
286     void printPeList(char* note, int *peList);
287
288     
289     bool shouldBufferMessagesNow(int instid);
290     void sendBufferedMessages(int instid);
291     void sendBufferedMessagesAllStrategies();
292
293  public:
294
295     ComlibLocalStats clib_stats;   //To store statistics of
296                                    //communication operations
297     
298     ComlibManager();  //Recommended constructor
299
300     ComlibManager(CkMigrateMessage *m) { }
301     int useDefCtor(void){ return 1; } //Use default constructor should
302     //be pupped and store all the strategies.
303
304     /* Initialization routines */
305     
306     void barrier(void);
307     void resumeFromSetupBarrier();
308    
309     /* The delegation framework reimplemented functions */
310
311     void ArraySend(CkDelegateData *pd,int ep, void *msg, 
312                    const CkArrayIndexMax &idx, CkArrayID a);
313     void GroupSend(CkDelegateData *pd, int ep, void *msg, int onpe, 
314                    CkGroupID gid);
315     void ArrayBroadcast(CkDelegateData *pd,int ep,void *m,CkArrayID a);
316     void GroupBroadcast(CkDelegateData *pd,int ep,void *m,CkGroupID g);
317     void ArraySectionSend(CkDelegateData *pd, int ep ,void *m, 
318                                   CkArrayID a, CkSectionID &s, int opts);
319     CkDelegateData* ckCopyDelegateData(CkDelegateData *data); 
320     CkDelegateData *DelegatePointerPup(PUP::er &p,CkDelegateData *pd);
321
322     inline Strategy *getStrategy(int instid)
323         {return converseManager->getStrategy(instid);}
324
325     inline StrategyTableEntry *getStrategyTableEntry(int instid)
326         {return converseManager->getStrategyTable(instid);}
327
328     // Entry methods used by bracketed strategies when there is some object
329     // migration. The comlib Manager realizes there is an error, it enters error
330     // mode by suspending the delivery of the strategy if it has already
331     // started, and it globally reduces the number of elements which already
332     // called endIteration. When this number matches the number of elements
333     // involved in the operation (or a multiple of it in case the user overlaps
334     // iterations), the system ri-deliver the doneInserting to the strategy.
335     //  void bracketedFinishSetup(int instid);
336     void bracketedCatchUpPE(int instid, int step);
337     void bracketedReceiveCount(int instid, int pe, int count, int isFirst, int step);
338     void bracketedStartErrorRecoveryProcess(int instid, int step);
339     void bracketedErrorDetected(int instid, int step);
340     void bracketedConfirmCount(int instid);
341     void bracketedCountConfirmed(int instid, int count, int step);
342     void bracketedReceiveNewCount(int instid);
343     void bracketedReceiveNewPeList(int instid, int *count);
344
345     void bracketedFinalBarrier(int instid);
346     void bracketedReleaseCount(int instid);
347     void bracketedReleaseBufferedMessages(int instid);
348
349     void bracketedStartDiscovery(int instid);
350     void bracketedDiscover(int instid, CkArrayID aid, CkArrayIndexMax &idx, int isSrc);
351     void bracketedContributeDiscovery(int instid, int pe, int nsrc, int ndest, int step);
352
353
354     // TODO: Delete the following two methods!!!!
355     void AtSync();           //User program called loadbalancer
356     void lbUpdate(LBMigrateMsg *); //loadbalancing updates
357
358     //Learning functions
359     //void learnPattern(int totalMessageCount, int totalBytes);
360     //void switchStrategy(int strat);
361
362     //void collectStats(ComlibLocalStats &s, int src,CkVec<ClibGlobalArrayIndex>&);
363     void collectStats(ComlibLocalStats &s, int src);
364  
365
366     /// Print information about the number of undelivered messages awaiting a specified strategy to be ready    
367     void printDiagnostics(int cinst);
368
369     /// Print information about the number of undelivered messages awaiting any strategy to be ready
370     void printDiagnostics();   
371        
372 }; 
373
374 /** This class is used by ComlibManager (the delegator manager) as its delegated
375     data. The only thing it contains is the position in the system of the
376     strategy it represents.
377  */
378 class ComlibDelegateData : public CkDelegateData {
379  private:
380   int _instid; ///< Position of this instance in the strategy table
381
382   friend void ComlibAssociateProxy(ComlibInstanceHandle, CProxy&);
383   friend CkDelegateData *ComlibManager::ckCopyDelegateData(CkDelegateData*);
384   ComlibDelegateData(int instid);
385
386  public:
387   ComlibDelegateData(CkMigrateMessage *) : CkDelegateData() { ref(); }
388   
389   void beginIteration();
390   void endIteration();
391
392   /// Get the position of this instance in the strategy table
393   inline int getID() {return _instid;}
394   
395   void pup(PUP::er &p) {
396     p | _instid;
397   }
398
399 };
400
401 void ComlibAtSync(void *msg);
402 void ComlibNotifyMigrationDoneHandler(void *msg);
403 void ComlibLBMigrationUpdate(LBMigrateMsg *);
404
405
406 #ifdef filippo
407 // The old interface
408 #define RECORD_SENDSTATS(sid, bytes, dest) {             \
409         CProxy_ComlibManager cgproxy(CkpvAccess(cmgrID));               \
410         cgproxy.ckLocalBranch()->clib_stats.recordSend(sid, bytes, dest); \
411 }\
412
413 #define RECORD_RECV_STATS(sid, bytes, src) { \
414         CProxy_ComlibManager cgproxy(CkpvAccess(cmgrID)); \
415         cgproxy.ckLocalBranch()->clib_stats.recordRecv(sid, bytes, src); \
416 }\
417
418 #define RECORD_SENDM_STATS(sid, bytes, dest_arr, ndest) {       \
419         CProxy_ComlibManager cgproxy(CkpvAccess(cmgrID)); \
420         cgproxy.ckLocalBranch()->clib_stats.recordSendM(sid, bytes, dest_arr, ndest); \
421 }\
422
423 #define RECORD_RECVM_STATS(sid, bytes, src_arr, nsrc) {        \
424         CProxy_ComlibManager cgproxy(CkpvAccess(cmgrID)); \
425         cgproxy.ckLocalBranch()->clib_stats.recordRecvM(sid, bytes, src_arr, nsrc); \
426 }\
427
428 #else
429 // the new version of comlib does not do anything with these yet
430 #define RECORD_SEND_STATS(sid, bytes, dest) /* empty */
431 #define RECORD_RECV_STATS(sid, bytes, src) /* empty */
432 #define RECORD_SENDM_STATS(sid, bytes, dest_arr, ndest) /* empty */
433 #define RECORD_RECVM_STATS(sid, bytes, src_arr, nsrc) /* empty */
434 #endif
435
436 /** @} */
437
438 #endif