1 #include "BSprivate.h"
2
3 /* ******************************************************* */
4 /* routines for manipulating the bulletin board structures */
5 /* ******************************************************* */
6
7 /*+ BSinit_bb - initialize a bulletin board
8
9 Input Parameters:
10 . length - the length of the data in the BB
11 . map - pointer to the mapping to use
12
13 Returns:
14 the new BB
15
16 +*/
BSinit_bb(int length,BSmapping * map)17 BSbb *BSinit_bb(int length, BSmapping *map)
18 {
19 BSbb *bb;
20
21 MY_MALLOCN(bb,(BSbb *),sizeof(BSbb),1);
22 MY_MALLOCN(bb->info,(int *),sizeof(int)*length,2);
23 bb->length = length;
24 bb->map = map;
25 return(bb);
26 }
27
28 /*+ BSfree_bb - free a bulletin board
29
30 Input Parameters:
31 . bb - the BB to free
32
33 Returns:
34 void
35
36 +*/
BSfree_bb(BSbb * bb)37 void BSfree_bb(BSbb *bb)
38 {
39 MY_FREE(bb->info);
40 MY_FREE(bb);
41 }
42
43 /*+ BSpost_bb - post information with addresses into the BB
44
45 Input Parameters:
46 . bb - the BB
47 . length - the length of the data to be posted
48 . address - the address into the BB to post to
49 . info - the array of information to post
50
51 Returns:
52 void
53
54 +*/
BSpost_bb(BSbb * bb,int length,int * address,int * info)55 void BSpost_bb(BSbb *bb, int length, int *address, int *info)
56 {
57 int i;
58
59 for (i=0;i<length;i++) {
60 bb->info[address[i]] = info[i];
61 }
62 }
63
64 /*+ BSpost_noaddr_bb - post information w/o addresses into the BB
65
66 Input Parameters:
67 . bb - the BB
68 . length - the length of the data to be posted
69 . info - the array of information to post
70
71 Returns:
72 void
73
74 +*/
BSpost_noaddr_bb(BSbb * bb,int length,int * info)75 void BSpost_noaddr_bb(BSbb *bb, int length, int *info)
76 {
77 int i;
78
79 for (i=0;i<length;i++) {
80 bb->info[i] = info[i];
81 }
82 }
83
84 /*+ BSquery_match_bb - Mutual BB query
85
86 Input Parameters:
87 . bb - the BB
88 . length - the length of the query
89 . address - the array of global addresses to query
90 . procinfo - the usual processor info
91
92 Output Parameters:
93 . info - on exit, this array contains the query answers
94
95 Returns:
96 void
97
98 Notes:
99 The queries are symmetric in nature. If one processor queries
100 another, it assumed that that other processor will also be
101 querying the first processor.
102
103 +*/
BSquery_match_bb(BSbb * bb,int length,int * address,int * info,BSprocinfo * procinfo)104 void BSquery_match_bb(BSbb *bb, int length, int *address,
105 int *info, BSprocinfo *procinfo)
106 {
107 int i, j;
108 BSpermutation *perm;
109 int *proc_id;
110 int *p_address;
111 int *p_info;
112 int from, size;
113 int cur_len, cur_addr, cur_proc;
114 int num_msg_sent;
115 int *in_msg;
116 int *out_msg;
117 BSmsg_list *msg_list = NULL;
118 MPI_Status mpi_status;
119 void *msg_buf;
120
121 GSYNC(procinfo->procset);
122
123 if (length == 0) return;
124 /* build query list */
125 /* these NEED to be sorted by processor, such that each processor */
126 /* gets only ONE list */
127 MY_MALLOC(proc_id,(int *),sizeof(int)*length,1);
128 /* get processor numbers */
129 (*bb->map->fglobal2proc)(length,address,proc_id,
130 procinfo,bb->map); CHKERR(0);
131
132 /* allocate a permutation vector and copies of other vectors */
133 perm = BSalloc_permutation(length); CHKERR(0);
134 MY_MALLOC(p_address,(int *),sizeof(int)*length,2);
135 MY_MALLOC(p_info,(int *),sizeof(int)*length,3);
136
137 /* initialize the perm. to 1 thru length and copy vectors */
138 for (i=0;i<length;i++) {
139 perm->perm[i] = i;
140 p_address[i] = address[i];
141 }
142
143 /* sort vectors by address */
144 BSheap_sort2(length,proc_id,p_address,perm->perm); CHKERR(0);
145
146 /* send query lists */
147 cur_addr = 0;
148 cur_proc = proc_id[0];
149 cur_len = 0;
150 num_msg_sent = 0;
151 for (i=0;i<length;i++) {
152 if (cur_proc != proc_id[i]) {
153 MY_SEND_SYNC(msg_list,BB_SQ_MSG,&(p_address[cur_addr]),
154 cur_len,cur_proc,MPI_INT,procinfo);
155 /* after this we don't need the information in p_address */
156 /* or in proc_id. we will use this space to store */
157 /* information on where to receive the messages */
158 /* proc_id will store the processor number */
159 /* p_address will store the address of the message */
160 p_address[num_msg_sent] = cur_addr;
161 proc_id[num_msg_sent] = cur_proc;
162 /* end of reuse area */
163 num_msg_sent++;
164 cur_len = 0;
165 cur_proc = proc_id[i];
166 cur_addr = i;
167 }
168 cur_len++;
169 }
170 MY_SEND_SYNC(msg_list,BB_SQ_MSG,&(p_address[cur_addr]),
171 cur_len,cur_proc,MPI_INT,procinfo);
172 p_address[num_msg_sent] = cur_addr;
173 proc_id[num_msg_sent] = cur_proc;
174 num_msg_sent++;
175
176 /* receive queries and send answers */
177 for (i=0;i<num_msg_sent;i++) {
178 RECVSYNCUNSZ(BB_SQ_MSG,msg_buf,size,MPI_INT,procinfo,mpi_status);
179 CHKERR(0);
180 in_msg = (int *)msg_buf;
181 from = mpi_status.MPI_SOURCE;
182 CHECK_SEND_LIST(msg_list);
183 cur_proc = -1;
184 for (j=0;j<num_msg_sent;j++) {
185 if (proc_id[j] == from) {
186 cur_proc = proc_id[j];
187 break;
188 }
189 }
190 if (cur_proc == -1) {
191 MY_SETERRC(BB_ERROR,"Received message from unexpected source");
192 }
193 /* translate into local addrs */
194 MY_MALLOC(out_msg,(int *),sizeof(int)*size,4+i);
195 (*bb->map->fglobal2local)(size,in_msg,out_msg,procinfo,bb->map);
196 CHKERR(0);
197 /* free up message */
198 MSGFREERECV(msg_buf);CHKERR(0);
199 /* get requested info at local addresses */
200 for (j=0;j<size;j++) {
201 if (out_msg[j] < 0) {
202 MY_SETERRC(BB_ERROR,"Processor does not own information");
203 }
204 out_msg[j] = bb->info[out_msg[j]];
205 }
206 /* send back info */
207 MY_SEND_SYNC(msg_list,BB_SA_MSG,out_msg,size,from,MPI_INT,procinfo);
208 /* free up message */
209 MY_FREE(out_msg);
210 }
211
212 /* receive answers */
213 for (i=0;i<num_msg_sent;i++) {
214 RECVSYNCUNSZ(BB_SA_MSG,msg_buf,size,MPI_INT,procinfo,mpi_status);
215 CHKERR(0);
216 in_msg = (int *)msg_buf;
217 from = mpi_status.MPI_SOURCE;
218 CHECK_SEND_LIST(msg_list);
219 /* find place to receive in */
220 cur_addr = -1;
221 for (j=0;j<num_msg_sent;j++) {
222 if (from == proc_id[j]) {
223 cur_addr = p_address[j];
224 break;
225 }
226 }
227 if (cur_addr == -1) {
228 MY_SETERRC(BB_ERROR,"Not expecting message from processor");
229 }
230 for (j=0;j<size;j++) {
231 p_info[cur_addr+j] = in_msg[j];
232 }
233 MSGFREERECV(msg_buf);CHKERR(0);
234 }
235
236 /* now sort the information according to the permutation */
237 BSperm_ivec(p_info,info,perm); CHKERR(0);
238
239 MY_FREE(p_info);
240 MY_FREE(p_address);
241 MY_FREE(proc_id);
242 BSfree_permutation(perm); CHKERR(0);
243 FINISH_SEND_LIST(msg_list);
244 }
245
246 /*+ BSquery_nomatch_bb - BB query
247
248 Input Parameters:
249 . bb - the BB
250 . length - the length of the query
251 . address - the array of global addresses to query
252 . procinfo - the usual processor info
253
254 Output Parameters:
255 . info - on exit, this array contains the query answers
256
257 Returns:
258 void
259
260 Notes:
261 Unlike BSquery_match_bb, no assumptions are made about other
262 processors queries (other than that everyone will call this routine).
263 This routine is not currently used in the package and hence is
264 not well-tested (use at your own risk).
265
266 +*/
BSquery_nomatch_bb(BSbb * bb,int length,int * address,int * info,BSprocinfo * procinfo)267 void BSquery_nomatch_bb(BSbb *bb, int length, int *address,
268 int *info, BSprocinfo *procinfo)
269 {
270 int i, j;
271 BSpermutation *perm;
272 int *proc_id;
273 int *p_address;
274 int *p_info;
275 int from, size;
276 int cur_len, cur_addr, cur_proc;
277 int num_msg_sent;
278 int *in_msg;
279 int *out_msg;
280 int parent, l_child, r_child, num_children;
281 int dummy;
282 int num_real_msg, num_term_msg, sent_parent_term, done, msg_avail;
283 int type;
284 BSmsg_list *msg_list = NULL;
285 MPI_Status mpi_status;
286 void *msg_buf;
287
288 GSYNC(procinfo->procset);
289
290 /* build query list */
291 /* these NEED to be sorted by processor, such that each processor */
292 /* gets only ONE list */
293 if (length > 0) {
294 MY_MALLOC(proc_id,(int *),sizeof(int)*length,1);
295 /* get processor numbers */
296 (*bb->map->fglobal2proc)(length,address,proc_id,
297 procinfo,bb->map); CHKERR(0);
298
299 /* allocate a permutation vector and copies of other vectors */
300 perm = BSalloc_permutation(length); CHKERR(0);
301 MY_MALLOC(p_address,(int *),sizeof(int)*length,2);
302 MY_MALLOC(p_info,(int *),sizeof(int)*length,3);
303
304 /* initialize the perm. to 1 thru length and copy vectors */
305 for (i=0;i<length;i++) {
306 perm->perm[i] = i;
307 p_address[i] = address[i];
308 }
309
310 /* sort vectors by address */
311 BSheap_sort2(length,proc_id,p_address,perm->perm); CHKERR(0);
312
313 /* send query lists */
314 cur_addr = 0;
315 cur_proc = proc_id[0];
316 cur_len = 0;
317 num_msg_sent = 0;
318 for (i=0;i<length;i++) {
319 if (cur_proc != proc_id[i]) {
320 MY_SEND_SYNC(msg_list,BB_SQ_MSG,&(p_address[cur_addr]),
321 cur_len,cur_proc,MPI_INT,procinfo);
322 /* after this we don't need the information in p_address */
323 /* or in proc_id. we will use this space to store */
324 /* information on where to receive the messages */
325 /* proc_id will store the processor number */
326 /* p_address will store the address of the message */
327 p_address[num_msg_sent] = cur_addr;
328 proc_id[num_msg_sent] = cur_proc;
329 /* end of reuse area */
330 num_msg_sent++;
331 cur_len = 0;
332 cur_proc = proc_id[i];
333 cur_addr = i;
334 }
335 cur_len++;
336 }
337 MY_SEND_SYNC(msg_list,BB_SQ_MSG,&(p_address[cur_addr]),
338 cur_len,cur_proc,MPI_INT,procinfo);
339 p_address[num_msg_sent] = cur_addr;
340 proc_id[num_msg_sent] = cur_proc;
341 num_msg_sent++;
342 } else {
343 num_msg_sent = 0;
344 }
345
346 /* receive queries and send answers */
347 /* do this until the terminating message has been received from parent */
348 /* find my place in the termination tree */
349 PSNbrTree(PS_PARENT,parent,procinfo->procset);
350 PSNbrTree(PS_LCHILD,l_child,procinfo->procset);
351 PSNbrTree(PS_RCHILD,r_child,procinfo->procset);
352 num_children = 0;
353 if (l_child >= 0) num_children++;
354 if (r_child >= 0) num_children++;
355 num_term_msg = 0;
356 num_real_msg = 0;
357 sent_parent_term = FALSE;
358 done = FALSE;
359 while (! done ) {
360 /* if we have all our answers and we haven't done so, tell everyone */
361 if ((num_real_msg == num_msg_sent) && (num_children == num_term_msg)
362 && (sent_parent_term == FALSE)) {
363 if (PSISROOT(procinfo)) {
364 /* tell children */
365 if (l_child >= 0) {
366 MY_SEND_SYNC(msg_list,BB_SQ_MSG,&dummy,0,l_child,MPI_INT,
367 procinfo);
368 }
369 if (r_child >= 0) {
370 MY_SEND_SYNC(msg_list,BB_SQ_MSG,&dummy,0,r_child,MPI_INT,
371 procinfo);
372 }
373 done = TRUE;
374 break;
375 } else {
376 /* tell parent */
377 MY_SEND_SYNC(msg_list,BB_SQ_MSG,&dummy,0,parent,MPI_INT,
378 procinfo);
379 }
380 sent_parent_term = TRUE;
381 }
382
383 /* get either a request or an answer */
384 msg_avail = FALSE;
385 while (TRUE) {
386 type = BB_SQ_MSG;
387 MPI_Iprobe(MPI_ANY_SOURCE,type,procinfo->procset,
388 &msg_avail,&mpi_status);
389 if (msg_avail) break;
390 type = BB_SA_MSG;
391 MPI_Iprobe(MPI_ANY_SOURCE,type,procinfo->procset,
392 &msg_avail,&mpi_status);
393 if (msg_avail) break;
394 CHECK_SEND_LIST(msg_list);
395 }
396 if (type == BB_SQ_MSG) {
397 /* receive a request */
398 RECVSYNCUNSZ(BB_SQ_MSG,msg_buf,size,MPI_INT,procinfo,mpi_status);
399 CHKERR(0);
400 in_msg = (int *)msg_buf;
401 from = mpi_status.MPI_SOURCE;
402 CHECK_SEND_LIST(msg_list);
403 /* if empty message, then it is a termination message */
404 if (size == 0) {
405 if (from == l_child) {
406 num_term_msg++;
407 } else if (from == r_child) {
408 num_term_msg++;
409 } else {
410 /* tell children */
411 if (l_child >= 0) {
412 MY_SEND_SYNC(msg_list,BB_SQ_MSG,&dummy,0,l_child,
413 MPI_INT,procinfo);
414 }
415 if (r_child >= 0) {
416 MY_SEND_SYNC(msg_list,BB_SQ_MSG,&dummy,0,r_child,
417 MPI_INT,procinfo);
418 }
419 done = TRUE;
420 }
421 MSGFREERECV(msg_buf);CHKERR(0);
422 } else {
423 /* translate into local addrs */
424 MY_MALLOC(out_msg,(int *),sizeof(int)*size,4+i);
425 (*bb->map->fglobal2local)(size,in_msg,out_msg,procinfo,bb->map);
426 CHKERR(0);
427 /* free up message */
428 MSGFREERECV(msg_buf);CHKERR(0);
429 /* get requested info at local addresses */
430 for (j=0;j<size;j++) {
431 if (out_msg[j] < 0) {
432 MY_SETERRC(BB_ERROR,
433 "Processor does not own information");
434 }
435 out_msg[j] = bb->info[out_msg[j]];
436 }
437 /* send back info */
438 MY_SEND_SYNC(msg_list,BB_SA_MSG,out_msg,size,from,
439 MPI_INT,procinfo);
440 /* free up message */
441 MY_FREE(out_msg);
442 }
443 } else {
444 /* receive an answer */
445 RECVSYNCUNSZ(BB_SA_MSG,msg_buf,size,MPI_INT,procinfo,mpi_status);
446 CHKERR(0);
447 in_msg = (int *)msg_buf;
448 from = mpi_status.MPI_SOURCE;
449 CHECK_SEND_LIST(msg_list);
450 /* find place to receive in */
451 for (j=0;j<num_msg_sent;j++) {
452 if (from == proc_id[j]) {
453 cur_addr = p_address[j];
454 break;
455 }
456 }
457 for (j=0;j<size;j++) p_info[cur_addr+j] = in_msg[j];
458 MSGFREERECV(msg_buf);CHKERR(0);
459 num_real_msg++;
460 }
461 }
462
463 if (length > 0) {
464 /* now sort the information according to the permutation */
465 BSperm_ivec(p_info,info,perm); CHKERR(0);
466
467 /* free up work vectors */
468 MY_FREE(p_info);
469 MY_FREE(p_address);
470 MY_FREE(proc_id);
471 BSfree_permutation(perm); CHKERR(0);
472 }
473 FINISH_SEND_LIST(msg_list);
474 GSYNC(procinfo->procset);
475 GSYNC(procinfo->procset);
476 }
477