YAP 7.1.0
or.scheduler.c
1/************************************************************************
2** **
3** The YapTab/YapOr/OPTYap systems **
4** **
5** YapTab extends the Yap Prolog engine to support sequential tabling **
6** YapOr extends the Yap Prolog engine to support or-parallelism **
7** OPTYap extends the Yap Prolog engine to support or-parallel tabling **
8** **
9** **
10** Yap Prolog was developed at University of Porto, Portugal **
11** **
12************************************************************************/
13
14/* ------------------ **
15** Includes **
16** ------------------ */
17
18#include "Yap.h"
19#ifdef YAPOR
20#include "Yatom.h"
21#include "YapHeap.h"
22#include "or.macros.h"
23#ifdef TABLING
24#include "tab.macros.h"
25#endif /* TABLING */
26
27#include "amiops.h"
28
29
30
31/* ------------------------------------- **
32** Local functions declaration **
33** ------------------------------------- */
34
35static int move_up_one_node(or_fr_ptr nearest_livenode);
36static int get_work_below(void);
37static int get_work_above(void);
38static int find_a_better_position(void);
39static int search_for_hidden_shared_work(bitmap stable_busy);
40
41
42
43/* ----------------------- **
44** Local inlines **
45** ----------------------- */
46
47static inline void PUT_NO_WORK_IN_UPPER_NODES(void);
48static inline void PUT_IDLE(int);
49static inline void PUT_BUSY(int);
50static inline void move_up_to_prune_request(void);
51
52
53static inline
54void PUT_NO_WORK_IN_UPPER_NODES(void) {
55 CACHE_REGS
56 or_fr_ptr current_node, nearest_livenode;
57 current_node = LOCAL_top_or_fr;
58 while ((nearest_livenode = OrFr_nearest_livenode(current_node))) {
59 OrFr_nearest_livenode(current_node) = NULL;
60 current_node = nearest_livenode;
61 }
62 return;
63}
64
65
66static inline
67void PUT_IDLE(int worker_num) {
68 LOCK(GLOBAL_locks_bm_idle_workers);
69 BITMAP_insert(GLOBAL_bm_idle_workers, worker_num);
70 UNLOCK(GLOBAL_locks_bm_idle_workers);
71 return;
72}
73
74
75static inline
76void PUT_BUSY(int worker_num) {
77 LOCK(GLOBAL_locks_bm_idle_workers);
78 BITMAP_delete(GLOBAL_bm_idle_workers, worker_num);
79 UNLOCK(GLOBAL_locks_bm_idle_workers);
80 return;
81}
82
83
84static inline
85void move_up_to_prune_request(void) {
86 CACHE_REGS
87 YAPOR_ERROR_CHECKING(move_up_to_prune_request, EQUAL_OR_YOUNGER_CP(Get_LOCAL_prune_request(), Get_LOCAL_top_cp()));
88
89 do {
90 LOCK_OR_FRAME(LOCAL_top_or_fr);
91 if (BITMAP_alone(OrFr_members(LOCAL_top_or_fr), worker_id)) {
92#ifdef TABLING
93 if (OrFr_suspensions(LOCAL_top_or_fr) || OrFr_owners(LOCAL_top_or_fr) != 1)
94 pruning_over_tabling_data_structures();
95#endif /* TABLING */
96 CUT_free_solution_frames(OrFr_qg_solutions(LOCAL_top_or_fr));
97#ifdef TABLING_INNER_CUTS
98 CUT_free_tg_solution_frames(OrFr_tg_solutions(LOCAL_top_or_fr));
99#endif /* TABLING_INNER_CUTS */
100 FREE_OR_FRAME(LOCAL_top_or_fr);
101 } else {
102 BITMAP_delete(OrFr_members(LOCAL_top_or_fr), worker_id);
103#ifdef TABLING
104 OrFr_owners(LOCAL_top_or_fr)--;
105#endif /* TABLING */
106 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
107 }
108 SCH_update_local_or_tops();
109 } while (Get_LOCAL_top_cp() != Get_LOCAL_prune_request());
110
111 CUT_reset_prune_request();
112#ifdef TABLING
113 Set_LOCAL_top_cp_on_stack( Get_LOCAL_top_cp());
114 abolish_incomplete_subgoals(Get_LOCAL_top_cp() - 1); /* do not include LOCAL_top_cp */
115#endif /* TABLIG */
116
117 return;
118}
119
120
121
122/* -------------------------- **
123** Global functions **
124** -------------------------- */
125
126int get_work(void) {
127 CACHE_REGS
128 int counter;
129 bitmap stable_busy;
130 yamop *alt_with_work;
131 or_fr_ptr or_fr_with_work, or_fr_to_move_to;
132#ifdef TABLING
133 choiceptr leader_node = DepFr_leader_cp(LOCAL_top_dep_fr);
134#endif /* TABLING */
135
136 /* reset local load */
137 LOCAL_load = 0;
138
139 /* check for prune request */
140 if (Get_LOCAL_prune_request())
141 move_up_to_prune_request();
142
143 /* find nearest node with available work */
144 or_fr_with_work = LOCAL_top_or_fr;
145 do {
146 or_fr_with_work = OrFr_nearest_livenode(or_fr_with_work);
147 if (or_fr_with_work == NULL)
148 break;
149 alt_with_work = OrFr_alternative(or_fr_with_work);
150 } while (alt_with_work == NULL || YAMOP_SEQ(alt_with_work));
151
152#ifndef TABLING
153 /* wait for incomplete installations */
154 while (LOCAL_reply_signal != worker_ready);
155#endif /* TABLING */
156
157 if (or_fr_with_work) {
158 /* move up to the nearest node with available work */
159#ifdef TABLING
160 if (leader_node && YOUNGER_CP(leader_node, GetOrFr_node(or_fr_with_work)))
161 /* there is a leader node before the nearest node with work */
162 or_fr_to_move_to = leader_node->cp_or_fr;
163 else
164#endif /* TABLING */
165 or_fr_to_move_to = or_fr_with_work;
166 do {
167 if (! move_up_one_node(or_fr_with_work))
168 break;
169 } while (LOCAL_top_or_fr != or_fr_to_move_to);
170 return TRUE;
171 }
172
173 /* no nodes with available work */
174 PUT_NO_WORK_IN_UPPER_NODES();
175#ifdef TABLING
176 if (leader_node) {
177 /* there is a leader node */
178 or_fr_to_move_to = leader_node->cp_or_fr;;
179 do {
180 if (! move_up_one_node(NULL))
181 break;
182 } while (LOCAL_top_or_fr != or_fr_to_move_to);
183 return TRUE;
184 }
185#endif /* TABLING */
186
187#ifdef TABLING_INNER_CUTS
188 if (LOCAL_pruning_scope) {
189 PUT_OUT_PRUNING(worker_id);
190 LOCAL_pruning_scope = NULL;
191 }
192#endif /* TABLING_INNER_CUTS */
193 PUT_OUT_ROOT_NODE(worker_id);
194 LOCK_WORKER(worker_id);
195 PUT_IDLE(worker_id);
196 UNLOCK_WORKER(worker_id);
197 SCH_refuse_share_request_if_any();
198
199 counter = 0;
200 BITMAP_difference(stable_busy, OrFr_members(LOCAL_top_or_fr), GLOBAL_bm_idle_workers);
201 while (1) {
202 while (BITMAP_subset(GLOBAL_bm_idle_workers, OrFr_members(LOCAL_top_or_fr)) &&
203 Get_LOCAL_top_cp() != Get_GLOBAL_root_cp()) {
204 /* no busy workers here and below */
205 if (! move_up_one_node(NULL)) {
206 PUT_BUSY(worker_id);
207 return TRUE;
208 }
209 }
210 if (Get_LOCAL_top_cp() == Get_GLOBAL_root_cp()) {
211 if (! BITMAP_member(GLOBAL_bm_root_cp_workers, worker_id))
212 /* We need this extra bitmap because the GLOBAL_bm_idle_workers bitmap
213 is not enough to deal with sequential predicates. The condition of
214 all workers being idle is not sufficient to ensure that there is no
215 available computation since a sequential predicate can still be resumed.
216 Only when all workers are idle and in the root choicepoint it is safe to
217 finish execution. */
218 PUT_IN_ROOT_NODE(worker_id);
219 if (BITMAP_same(GLOBAL_bm_root_cp_workers, GLOBAL_bm_present_workers))
220 /* All workers are idle in the root choicepoint. Execution
221 must finish as there is no available computation. */
222 return FALSE;
223 }
224 if (get_work_below()) {
225 PUT_BUSY(worker_id);
226 return TRUE;
227 }
228 if (get_work_above()) {
229 PUT_BUSY(worker_id);
230 return TRUE;
231 }
232 if (find_a_better_position()) {
233 PUT_BUSY(worker_id);
234 return TRUE;
235 }
236 if (++counter == GLOBAL_scheduler_loop) {
237 if (search_for_hidden_shared_work(stable_busy)) {
238 PUT_BUSY(worker_id);
239 return TRUE;
240 }
241 counter = 0;
242 BITMAP_difference(stable_busy, OrFr_members(LOCAL_top_or_fr), GLOBAL_bm_idle_workers);
243 } else {
244 BITMAP_minus(stable_busy, GLOBAL_bm_idle_workers);
245 }
246 }
247}
248
249
250
251/* ------------------------- **
252** Local functions **
253** ------------------------- */
254
255static
256int move_up_one_node(or_fr_ptr nearest_livenode) {
257 CACHE_REGS
258 YAPOR_ERROR_CHECKING(move_up_one_node, Get_LOCAL_prune_request() && EQUAL_OR_YOUNGER_CP(Get_LOCAL_prune_request(), Get_LOCAL_top_cp()));
259
260 LOCK_OR_FRAME(LOCAL_top_or_fr);
261 /* last worker in a sequential choicepoint ? */
262 if (OrFr_alternative(LOCAL_top_or_fr)
263 && YAMOP_SEQ(OrFr_alternative(LOCAL_top_or_fr))
264 && BITMAP_alone(OrFr_members(LOCAL_top_or_fr), worker_id)) {
265 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
266 return FALSE;
267 }
268
269 /* pending prune ? */
270 if (Get_OrFr_pend_prune_cp(LOCAL_top_or_fr)
271 && ! Get_LOCAL_prune_request()
272 && CUT_last_worker_left_pending_prune(LOCAL_top_or_fr)) {
273#ifdef TABLING
274 choiceptr aux_cp = Get_LOCAL_top_cp();
275#endif /* TABLIG */
276 choiceptr prune_cp = Get_OrFr_pend_prune_cp(LOCAL_top_or_fr);
277 Set_OrFr_pend_prune_cp(LOCAL_top_or_fr, NULL);
278 BRANCH(worker_id, OrFr_depth(LOCAL_top_or_fr)) = OrFr_pend_prune_ltt(LOCAL_top_or_fr);
279 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
280 prune_shared_branch(prune_cp, &OrFr_pend_prune_ltt(LOCAL_top_or_fr));
281#ifdef TABLING
282 while (YOUNGER_CP(aux_cp->cp_b, Get_LOCAL_top_cp()))
283 aux_cp = aux_cp->cp_b;
284 abolish_incomplete_subgoals(aux_cp);
285#endif /* TABLIG */
286 return FALSE;
287 }
288
289 OPTYAP_ERROR_CHECKING(move_up_one_node, B_FZ != DepFr_cons_cp(LOCAL_top_dep_fr));
290 OPTYAP_ERROR_CHECKING(move_up_one_node, LOCAL_top_susp_or_fr && EQUAL_OR_YOUNGER_CP(Get_LOCAL_top_cp(), B_FZ) && YOUNGER_CP(GetOrFr_node(LOCAL_top_susp_or_fr), Get_LOCAL_top_cp()));
291 OPTYAP_ERROR_CHECKING(move_up_one_node, LOCAL_top_susp_or_fr && YOUNGER_CP(B_FZ, Get_LOCAL_top_cp()) && YOUNGER_CP(GetOrFr_node(LOCAL_top_susp_or_fr), B_FZ));
292
293#ifdef TABLING
294 /* frozen stacks on branch ? */
295 if (YOUNGER_CP(B_FZ, Get_LOCAL_top_cp())) {
296 if (nearest_livenode)
297 OrFr_nearest_livenode(LOCAL_top_or_fr) = nearest_livenode;
298 BITMAP_delete(OrFr_members(LOCAL_top_or_fr), worker_id);
299 if (BITMAP_empty(OrFr_members(LOCAL_top_or_fr))) {
300 if (frame_with_suspensions_not_collected(LOCAL_top_or_fr)) {
301 collect_suspension_frames(LOCAL_top_or_fr);
302 }
303#ifdef TABLING_INNER_CUTS
304 if (OrFr_tg_solutions(LOCAL_top_or_fr)) {
305 tg_sol_fr_ptr tg_solutions;
306 or_fr_ptr leftmost_until;
307 tg_solutions = OrFr_tg_solutions(LOCAL_top_or_fr);
308 leftmost_until = CUT_leftmost_until(LOCAL_top_or_fr, OrFr_depth(TgSolFr_gen_cp(tg_solutions)->cp_or_fr));
309 OrFr_tg_solutions(LOCAL_top_or_fr) = NULL;
310 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
311 if (leftmost_until) {
312 LOCK_OR_FRAME(leftmost_until);
313 tg_solutions = CUT_store_tg_answers(leftmost_until, tg_solutions,
314 BRANCH_LTT(worker_id, OrFr_depth(leftmost_until)));
315 UNLOCK_OR_FRAME(leftmost_until);
316 }
317 CUT_validate_tg_answers(tg_solutions);
318 goto update_local_tops1;
319 }
320#endif /* TABLING_INNER_CUTS */
321 }
322 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
323#ifdef TABLING_INNER_CUTS
324 update_local_tops1:
325#endif /* TABLING_INNER_CUTS */
326 SCH_update_local_or_tops();
327 if (Get_LOCAL_prune_request())
328 pruning_over_tabling_data_structures();
329 return TRUE;
330 }
331
332 /* suspension frames to resume ? */
333 if (OrFr_suspensions(LOCAL_top_or_fr)) {
334 susp_fr_ptr resume_fr;
335#ifdef TIMESTAMP_CHECK
336 resume_fr = suspension_frame_to_resume(LOCAL_top_or_fr, ++GLOBAL_timestamp);
337#else
338 resume_fr = suspension_frame_to_resume(LOCAL_top_or_fr);
339#endif /* TIMESTAMP_CHECK */
340 if (resume_fr) {
341 if (LOCAL_top_susp_or_fr == LOCAL_top_or_fr && OrFr_suspensions(LOCAL_top_or_fr) == NULL) {
342 LOCAL_top_susp_or_fr = OrFr_nearest_suspnode(LOCAL_top_or_fr);
343 OrFr_nearest_suspnode(LOCAL_top_or_fr) = LOCAL_top_or_fr;
344 }
345 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
346 unbind_variables(TR, Get_LOCAL_top_cp()->cp_tr);
347 resume_suspension_frame(resume_fr, LOCAL_top_or_fr);
348 return FALSE;
349 }
350 if (LOCAL_top_susp_or_fr == LOCAL_top_or_fr) {
351 LOCAL_top_susp_or_fr = OrFr_nearest_suspnode(LOCAL_top_or_fr);
352 OrFr_nearest_suspnode(LOCAL_top_or_fr) = NULL;
353 }
354 } else if (LOCAL_top_susp_or_fr == LOCAL_top_or_fr) {
355 LOCAL_top_susp_or_fr = OrFr_nearest_suspnode(LOCAL_top_or_fr);
356 OrFr_nearest_suspnode(LOCAL_top_or_fr) = LOCAL_top_or_fr;
357 }
358
359 /* top node frozen ? */
360 if (B_FZ == Get_LOCAL_top_cp()) {
361 if (nearest_livenode)
362 OrFr_nearest_livenode(LOCAL_top_or_fr) = nearest_livenode;
363 BITMAP_delete(OrFr_members(LOCAL_top_or_fr), worker_id);
364#ifdef TABLING_INNER_CUTS
365 if (BITMAP_empty(OrFr_members(LOCAL_top_or_fr))) {
366#endif /* TABLING_INNER_CUTS */
367 if (OrFr_suspensions(LOCAL_top_or_fr) && OrFr_owners(LOCAL_top_or_fr) == 1) {
368 complete_suspension_frames(LOCAL_top_or_fr);
369 }
370#ifdef TABLING_INNER_CUTS
371 if (OrFr_tg_solutions(LOCAL_top_or_fr)) {
372 tg_sol_fr_ptr tg_solutions;
373 or_fr_ptr leftmost_until;
374 tg_solutions = OrFr_tg_solutions(LOCAL_top_or_fr);
375 leftmost_until = CUT_leftmost_until(LOCAL_top_or_fr, OrFr_depth(TgSolFr_gen_cp(tg_solutions)->cp_or_fr));
376 OrFr_tg_solutions(LOCAL_top_or_fr) = NULL;
377 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
378 if (leftmost_until) {
379 LOCK_OR_FRAME(leftmost_until);
380 tg_solutions = CUT_store_tg_answers(leftmost_until, tg_solutions,
381 BRANCH_LTT(worker_id, OrFr_depth(leftmost_until)));
382 UNLOCK_OR_FRAME(leftmost_until);
383 }
384 CUT_validate_tg_answers(tg_solutions);
385 goto update_local_tops2;
386 }
387 }
388#endif /* TABLING_INNER_CUTS */
389 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
390#ifdef TABLING_INNER_CUTS
391 update_local_tops2:
392#endif /* TABLING_INNER_CUTS */
393 SCH_update_local_or_tops();
394 if (Get_LOCAL_prune_request())
395 pruning_over_tabling_data_structures();
396 return TRUE;
397 }
398
399 OPTYAP_ERROR_CHECKING(move_up_one_node, OrFr_alternative(LOCAL_top_or_fr) && ! YAMOP_SEQ(OrFr_alternative(LOCAL_top_or_fr)));
400 OPTYAP_ERROR_CHECKING(move_up_one_node, Get_LOCAL_top_cp() == DepFr_cons_cp(LOCAL_top_dep_fr));
401 OPTYAP_ERROR_CHECKING(move_up_one_node, Get_LOCAL_top_cp() != Get_LOCAL_top_cp_on_stack());
402
403 /* no frozen nodes */
404 Set_LOCAL_top_cp_on_stack(GetOrFr_node(OrFr_next_on_stack(LOCAL_top_or_fr)));
405
406 /* no more owners ? */
407 if (OrFr_owners(LOCAL_top_or_fr) == 1) {
408 if (OrFr_suspensions(LOCAL_top_or_fr)) {
409 complete_suspension_frames(LOCAL_top_or_fr);
410 }
411 if (LOCAL_top_sg_fr && Get_LOCAL_top_cp() == SgFr_gen_cp(LOCAL_top_sg_fr)) {
412 mark_as_completed(LOCAL_top_sg_fr);
413 LOCAL_top_sg_fr = SgFr_next(LOCAL_top_sg_fr);
414 }
415#else
416 /* last member worker in node ? */
417 if (BITMAP_alone(OrFr_members(LOCAL_top_or_fr), worker_id)) {
418#endif /* TABLING */
419 if (Get_LOCAL_prune_request()) {
420 CUT_free_solution_frames(OrFr_qg_solutions(LOCAL_top_or_fr));
421#ifdef TABLING_INNER_CUTS
422 CUT_free_tg_solution_frames(OrFr_tg_solutions(LOCAL_top_or_fr));
423#endif /* TABLING_INNER_CUTS */
424 FREE_OR_FRAME(LOCAL_top_or_fr);
425 SCH_update_local_or_tops();
426 CUT_reset_prune_request();
427 } else {
428 qg_sol_fr_ptr qg_solutions = OrFr_qg_solutions(LOCAL_top_or_fr);
429#ifdef TABLING_INNER_CUTS
430 tg_sol_fr_ptr tg_solutions = OrFr_tg_solutions(LOCAL_top_or_fr);
431#endif /* TABLING_INNER_CUTS */
432 FREE_OR_FRAME(LOCAL_top_or_fr);
433 SCH_update_local_or_tops();
434 CUT_reset_prune_request();
435#ifdef TABLING_INNER_CUTS
436 if (qg_solutions || tg_solutions) {
437 or_fr_ptr leftmost_or_fr;
438 if (qg_solutions)
439 CUT_join_answers_in_an_unique_frame(qg_solutions);
440 leftmost_or_fr = CUT_leftmost_or_frame();
441 LOCK_OR_FRAME(leftmost_or_fr);
442 if (qg_solutions)
443 CUT_store_answers(leftmost_or_fr, qg_solutions);
444 if (tg_solutions)
445 tg_solutions = CUT_store_tg_answers(leftmost_or_fr, tg_solutions,
446 BRANCH_LTT(worker_id, OrFr_depth(leftmost_or_fr)));
447 UNLOCK_OR_FRAME(leftmost_or_fr);
448 CUT_validate_tg_answers(tg_solutions);
449 }
450#else
451 if (qg_solutions) {
452 or_fr_ptr leftmost_or_fr;
453 CUT_join_answers_in_an_unique_frame(qg_solutions);
454 leftmost_or_fr = CUT_leftmost_or_frame();
455 LOCK_OR_FRAME(leftmost_or_fr);
456 CUT_store_answers(leftmost_or_fr, qg_solutions);
457 UNLOCK_OR_FRAME(leftmost_or_fr);
458 }
459#endif /* TABLING_INNER_CUTS */
460 }
461 return TRUE;
462 }
463
464 /* more owners */
465 if (nearest_livenode)
466 OrFr_nearest_livenode(LOCAL_top_or_fr) = nearest_livenode;
467 BITMAP_delete(OrFr_members(LOCAL_top_or_fr), worker_id);
468#ifdef TABLING
469 OrFr_owners(LOCAL_top_or_fr)--;
470 if (BITMAP_empty(OrFr_members(LOCAL_top_or_fr))) {
471#ifdef TABLING_INNER_CUTS
472 if (OrFr_tg_solutions(LOCAL_top_or_fr)) {
473 tg_sol_fr_ptr tg_solutions;
474 or_fr_ptr leftmost_until;
475 tg_solutions = OrFr_tg_solutions(LOCAL_top_or_fr);
476 leftmost_until = CUT_leftmost_until(LOCAL_top_or_fr, OrFr_depth(TgSolFr_gen_cp(tg_solutions)->cp_or_fr));
477 if (Get_LOCAL_prune_request())
478 pruning_over_tabling_data_structures();
479 OrFr_tg_solutions(LOCAL_top_or_fr) = NULL;
480 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
481 if (leftmost_until) {
482 LOCK_OR_FRAME(leftmost_until);
483 tg_solutions = CUT_store_tg_answers(leftmost_until, tg_solutions,
484 BRANCH_LTT(worker_id, OrFr_depth(leftmost_until)));
485 UNLOCK_OR_FRAME(leftmost_until);
486 }
487 CUT_validate_tg_answers(tg_solutions);
488 goto update_local_tops3;
489 }
490#endif /* TABLING_INNER_CUTS */
491 if (Get_LOCAL_prune_request())
492 pruning_over_tabling_data_structures();
493 }
494#endif /* TABLING */
495 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
496#ifdef TABLING
497#ifdef TABLING_INNER_CUTS
498 update_local_tops3:
499#endif /* TABLING_INNER_CUTS */
500 if (LOCAL_top_sg_fr && Get_LOCAL_top_cp() == SgFr_gen_cp(LOCAL_top_sg_fr)) {
501 LOCAL_top_sg_fr = SgFr_next(LOCAL_top_sg_fr);
502 }
503#endif /* TABLING */
504 SCH_update_local_or_tops();
505 CUT_reset_prune_request();
506 return TRUE;
507}
508
509
510static
511int get_work_below(void){
512 CACHE_REGS
513 int i, worker_p, big_load;
514 bitmap busy_below, idle_below;
515
516 worker_p = -1;
517 big_load = GLOBAL_delayed_release_load ;
518 BITMAP_difference(busy_below, OrFr_members(LOCAL_top_or_fr), GLOBAL_bm_idle_workers);
519 BITMAP_difference(idle_below, OrFr_members(LOCAL_top_or_fr), busy_below);
520 BITMAP_delete(idle_below, worker_id);
521 for (i = 0; i < GLOBAL_number_workers; i++) {
522 if (BITMAP_member(idle_below ,i) && YOUNGER_CP(REMOTE_top_cp(i), Get_LOCAL_top_cp()))
523 BITMAP_minus(busy_below, OrFr_members(REMOTE_top_or_fr(i)));
524 }
525 if (BITMAP_empty(busy_below))
526 return FALSE;
527 /* choose the worker with highest load */
528 for (i = 0 ; i < GLOBAL_number_workers; i++) {
529 if (BITMAP_member(busy_below ,i) && REMOTE_load(i) > big_load) {
530 worker_p = i;
531 big_load = REMOTE_load(i);
532 }
533 }
534 if (worker_p == -1)
535 return FALSE;
536 return (q_share_work(worker_p));
537}
538
539
540static
541int get_work_above(void){
542 CACHE_REGS
543 int i, worker_p, big_load;
544 bitmap visible_busy_above, visible_idle_above;
545
546 worker_p = -1;
547 big_load = GLOBAL_delayed_release_load ;
548 BITMAP_difference(visible_busy_above, GLOBAL_bm_present_workers, OrFr_members(LOCAL_top_or_fr));
549 BITMAP_minus(visible_busy_above, GLOBAL_bm_invisible_workers);
550 BITMAP_copy(visible_idle_above, visible_busy_above);
551 BITMAP_minus(visible_busy_above, GLOBAL_bm_idle_workers);
552 BITMAP_and(visible_idle_above, GLOBAL_bm_idle_workers);
553 BITMAP_insert(visible_busy_above, worker_id);
554 for (i = 0 ; i < GLOBAL_number_workers; i++) {
555 if (BITMAP_member(visible_idle_above, i))
556 BITMAP_minus(visible_busy_above, OrFr_members(REMOTE_top_or_fr(i)));
557 }
558 if (!BITMAP_member(visible_busy_above, worker_id) || BITMAP_alone(visible_busy_above, worker_id))
559 return FALSE;
560 BITMAP_delete(visible_busy_above, worker_id);
561 /* choose the worker with higher load */
562 for (i = 0; i < GLOBAL_number_workers; i++) {
563 if (BITMAP_member(visible_busy_above ,i) && REMOTE_load(i) > big_load) {
564 worker_p = i;
565 big_load = REMOTE_load(i);
566 }
567 }
568 if (worker_p == -1)
569 return FALSE;
570 /* put workers invisibles */
571 LOCK(GLOBAL_locks_bm_invisible_workers);
572 if (BITMAP_member(GLOBAL_bm_invisible_workers, worker_p)) {
573 UNLOCK(GLOBAL_locks_bm_invisible_workers);
574 return FALSE;
575 }
576 BITMAP_insert(GLOBAL_bm_invisible_workers, worker_id);
577 BITMAP_insert(GLOBAL_bm_invisible_workers, worker_p);
578 UNLOCK(GLOBAL_locks_bm_invisible_workers);
579 /* move up to cp with worker_p */
580 do {
581 if (! move_up_one_node(NULL)) {
582 return TRUE;
583 }
584 } while (! BITMAP_member(OrFr_members(LOCAL_top_or_fr), worker_p));
585 /* put workers visibles */
586 LOCK(GLOBAL_locks_bm_invisible_workers);
587 BITMAP_delete(GLOBAL_bm_invisible_workers, worker_id);
588 BITMAP_delete(GLOBAL_bm_invisible_workers, worker_p);
589 UNLOCK(GLOBAL_locks_bm_invisible_workers);
590 return (q_share_work(worker_p));
591}
592
593
594static
595int find_a_better_position(void){
596 CACHE_REGS
597 int i;
598 bitmap busy_above, idle_above;
599 BITMAP_difference(busy_above, GLOBAL_bm_present_workers, OrFr_members(LOCAL_top_or_fr));
600 BITMAP_copy(idle_above, busy_above);
601 BITMAP_minus(busy_above, GLOBAL_bm_idle_workers);
602 BITMAP_and(idle_above, GLOBAL_bm_idle_workers);
603 for (i = 0; i < GLOBAL_number_workers; i++) {
604 if (BITMAP_member(idle_above, i)) {
605 if (BITMAP_empty(busy_above))
606 break;
607 if (BITMAP_member(OrFr_members(REMOTE_top_or_fr(i)), worker_id))
608 BITMAP_clear(busy_above);
609 BITMAP_minus(busy_above, OrFr_members(REMOTE_top_or_fr(i)));
610 }
611 }
612 if (BITMAP_empty(busy_above))
613 return FALSE;
614 /* move up to cp with all workers of bitmap busy_above */
615 do {
616 if (! move_up_one_node(NULL)) {
617 return TRUE;
618 }
619 } while (! BITMAP_subset(OrFr_members(LOCAL_top_or_fr), busy_above));
620 return FALSE;
621}
622
623
624static
625int search_for_hidden_shared_work(bitmap stable_busy){
626 CACHE_REGS
627 int i;
628 bitmap invisible_work, idle_below;
629 BITMAP_intersection(invisible_work, stable_busy, GLOBAL_bm_requestable_workers);
630 BITMAP_intersection(idle_below, OrFr_members(LOCAL_top_or_fr), GLOBAL_bm_idle_workers);
631 BITMAP_delete(idle_below, worker_id);
632 for (i = 0; i < GLOBAL_number_workers; i++) {
633 if (BITMAP_member(idle_below ,i) && YOUNGER_CP(REMOTE_top_cp(i), Get_LOCAL_top_cp()))
634 BITMAP_minus(invisible_work, OrFr_members(REMOTE_top_or_fr(i)));
635 }
636 if (BITMAP_empty(invisible_work))
637 return FALSE;
638 /* choose the first available worker */
639 for (i = 0; i < GLOBAL_number_workers; i++ ) {
640 if (BITMAP_member(invisible_work ,i))
641 break;
642 }
643 return (q_share_work(i));
644}
645#endif /* YAPOR */
Yap.h
Main definitions.
or_frame
Definition: or.structs.h:61
query_goal_solution_frame
Definition: or.structs.h:135
yami
Definition: amidefs.h:264