Checking in a new broadcast strategy which broadcasts to arrays along a load-balanced...
[charm.git] / src / ck-com / BroadcastStrategy.C
1
2 //Broadcast strategy for charm++ programs using the net version
3 //This strategy implements a tree based broadcast
4 //Developed by Sameer Kumar 04/10/04
5
6 //Extend for array sections later
7
8 #include "BroadcastStrategy.h"
9 #include "ComlibManager.h"
10
11 CkpvExtern(CkGroupID, cmgrID);
12 extern int sfactor;
13
14 static void recv_bcast_handler(void *msg) {
15     CmiMsgHeaderExt *conv_header = (CmiMsgHeaderExt *) msg;
16     int instid = conv_header->stratid;
17
18     BroadcastStrategy *bstrat = (BroadcastStrategy *)
19         CProxy_ComlibManager(CkpvAccess(cmgrID)).ckLocalBranch()->getStrategy(instid);
20     
21     bstrat->handleMessage((char *)msg);    
22 }
23
24
25 //Initialize the hypercube variables
26 void BroadcastStrategy::initHypercube() {
27     logp = log((double) CkNumPes())/log(2.0);
28     logp = ceil(logp);
29 }
30
31
32 //Constructor, 
33 //Can read spanning factor from command line
34 BroadcastStrategy::BroadcastStrategy(int topology) : 
35     CharmStrategy(), _topology(topology) {
36     spanning_factor = DEFAULT_BROADCAST_SPANNING_FACTOR;
37     if(sfactor > 0)
38         spanning_factor = sfactor;
39     
40     setType(GROUP_STRATEGY);
41     initHypercube();
42 }
43
44 //Array Constructor
45 //Can read spanning factor from command line
46 BroadcastStrategy::BroadcastStrategy(CkArrayID aid, int topology) : 
47     CharmStrategy(), _topology(topology) {
48         
49     setType(ARRAY_STRATEGY);
50     ainfo.setDestinationArray(aid);
51     
52     spanning_factor = DEFAULT_BROADCAST_SPANNING_FACTOR;
53     if(sfactor > 0)
54         spanning_factor = sfactor;    
55
56     initHypercube();
57     //if(topology == USE_HYPERCUBE)
58     //  CkPrintf("Warning: hypercube only works on powers of two PES\n");
59 }
60
61
62 //Receives the message and sends it along the spanning tree.
63 void BroadcastStrategy::insertMessage(CharmMessageHolder *cmsg){
64     //CkPrintf("[%d] BROADCASTING\n", CkMyPe());
65
66     char *msg = cmsg->getCharmMessage();
67
68     envelope *env = UsrToEnv(msg);
69     CmiMsgHeaderExt *conv_header = (CmiMsgHeaderExt *) env;
70
71     conv_header->root = 0;        //Use root later
72     if(_topology == USE_HYPERCUBE) 
73         conv_header->xhdl = 0;
74     else
75         //conv_header->root = CkMyPe();
76         conv_header->xhdl = CkMyPe();
77     
78     handleMessage((char *)UsrToEnv(msg));
79     
80     delete cmsg;
81 }
82
83 //not implemented here because no bracketing is required for this strategy
84 void BroadcastStrategy::doneInserting(){
85 }
86
87
88 //register the converse handler to recieve the broadcast message
89 void BroadcastStrategy::beginProcessing(int nelements) {
90     handlerId = CkRegisterHandler((CmiHandler)recv_bcast_handler);
91 }
92
93 void BroadcastStrategy::handleMessage(char *msg) {
94     if(_topology == USE_TREE)
95         handleTree(msg);
96     else if(_topology == USE_HYPERCUBE) 
97         handleHypercube(msg);
98     else CkAbort("Unknown Topology");
99 }
100
101 void BroadcastStrategy::handleTree(char *msg){
102     
103     envelope *env = (envelope *)msg;
104     CmiMsgHeaderExt *conv_header = (CmiMsgHeaderExt *) msg;
105
106     int startpe = conv_header->xhdl;
107     int size = env->getTotalsize();
108     
109     CkAssert(startpe>=0 && startpe < CkNumPes());
110     
111     CmiSetHandler(msg, handlerId);
112     
113     conv_header->stratid = getInstance();
114     
115     //Sending along the spanning tree
116     //Gengbins tree building code stolen from the MPI machine layer    
117     int i;
118     for (i=1; i<=spanning_factor; i++) {
119         
120         int p = CkMyPe() - startpe;
121         if (p<0) 
122             p += CkNumPes();
123
124         p = spanning_factor*p + i;
125
126         if (p > CkNumPes() - 1) break;
127
128         p += startpe;
129         p = p % CkNumPes();
130
131         CkAssert(p>=0 && p < CkNumPes() && p != CkMyPe());
132
133         CmiSyncSend(p, size, msg);
134     }
135
136     if(getType() == GROUP_STRATEGY)
137         CkSendMsgBranch(env->getEpIdx(), EnvToUsr(env), CkMyPe(), 
138                         env->getGroupNum());
139     else if(getType() == ARRAY_STRATEGY)
140         ainfo.localBroadcast(env);        
141 }
142
143
144 void BroadcastStrategy::handleHypercube(char *msg){
145     envelope *env = (envelope *)msg;
146
147     CmiMsgHeaderExt *conv_header = (CmiMsgHeaderExt *) msg;
148     //int curcycle = conv_header->root;
149     int curcycle = conv_header->xhdl;
150
151     int i;
152     int size = env->getTotalsize();
153         
154     //CkPrintf("In hypercube %d, %d\n", (int)logp, curcycle); 
155     
156     /* assert(startpe>=0 && startpe<_Cmi_numpes); */
157     CmiSetHandler(msg, handlerId);
158
159     conv_header->stratid = getInstance();
160
161     //Copied from system hypercube message passing
162
163     for (i = logp - curcycle - 1; i >= 0; i--) {
164         int p = CkMyPe() ^ (1 << i);
165
166         int newcycle = ++curcycle;
167         //CkPrintf("%d --> %d, %d\n", CkMyPe(), p, newcycle); 
168         
169         //conv_header->root = newcycle;
170         conv_header->xhdl = newcycle;
171
172         if(p >= CkNumPes()) {
173             p &= (-1) << i;
174             
175             //loadbalancing
176             if (p < CkNumPes())
177                 p += (CkMyPe() - 
178                       (CkMyPe() & ((-1) << i))) % (CkNumPes() - p);
179         }     
180         
181         if(p < CkNumPes())
182             CmiSyncSendFn(p, size, msg);                    
183     }
184     
185     if(getType() == GROUP_STRATEGY)
186         CkSendMsgBranch(env->getEpIdx(), EnvToUsr(env), CkMyPe(), 
187                         env->getGroupNum());
188     else if(getType() == ARRAY_STRATEGY)
189         ainfo.localBroadcast(env);        
190 }
191
192
193 //Pack the group id and the entry point of the user message
194 void BroadcastStrategy::pup(PUP::er &p){
195     CharmStrategy::pup(p);    
196
197     p | spanning_factor;
198     p | _topology;
199     p | logp;
200 }