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