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