24static inline void PUT_IN_ROOT_NODE(
int);
25static inline void PUT_OUT_ROOT_NODE(
int);
26static inline void PUT_IN_FINISHED(
int);
27#ifdef TABLING_INNER_CUTS
28static inline void PUT_IN_PRUNING(
int);
29static inline void PUT_OUT_PRUNING(
int);
32static inline void PUT_IN_REQUESTABLE(
int);
33static inline void PUT_OUT_REQUESTABLE(
int);
34static inline void SCH_update_local_or_tops(
void);
35static inline void SCH_refuse_share_request_if_any(
void);
36static inline void SCH_set_load(
choiceptr);
37static inline void SCH_new_alternative(
yamop *,
yamop *);
39static inline void CUT_send_prune_request(
int,
choiceptr);
40static inline void CUT_reset_prune_request(
void);
42static inline int CUT_last_worker_left_pending_prune(
or_fr_ptr);
43static inline or_fr_ptr CUT_leftmost_or_frame(
void);
44#ifdef TABLING_INNER_CUTS
50static inline void CUT_join_answers_in_an_unique_frame(
qg_sol_fr_ptr);
62#define YAMOP_CUT_FLAG 0x8000
63#define YAMOP_SEQ_FLAG 0x4000
64#define YAMOP_FLAGS_BITS 0xc000
65#define YAMOP_LTT_BITS 0x3fff
67#define YAMOP_CUT_FLAG 0x80000000
68#define YAMOP_SEQ_FLAG 0x40000000
69#define YAMOP_FLAGS_BITS 0xc0000000
70#define YAMOP_LTT_BITS 0x3fffffff
72#define YAMOP_CUT_FLAG 0x8000000000000000
73#define YAMOP_SEQ_FLAG 0x4000000000000000
74#define YAMOP_FLAGS_BITS 0xc000000000000000
75#define YAMOP_LTT_BITS 0x3fffffffffffffff
77#define YAMOP_CUT_FLAG OOOOPPS!!! Unknown Integer Sizeof
78#define YAMOP_SEQ_FLAG OOOOPPS!!! Unknown Integer Sizeof
79#define YAMOP_FLAGS_BITS OOOOPPS!!! Unknown Integer Sizeof
80#define YAMOP_LTT_BITS OOOOPPS!!! Unknown Integer Sizeof
83#define YAMOP_OR_ARG(INST) ((INST)->y_u.Otapl.or_arg)
84#define YAMOP_LTT(INST) (((INST)->y_u.Otapl.or_arg) & YAMOP_LTT_BITS)
85#define YAMOP_SEQ(INST) (((INST)->y_u.Otapl.or_arg) & YAMOP_SEQ_FLAG)
86#define YAMOP_CUT(INST) (((INST)->y_u.Otapl.or_arg) & YAMOP_CUT_FLAG)
87#define YAMOP_FLAGS(INST) (((INST)->y_u.Otapl.or_arg) & YAMOP_FLAGS_BITS)
89#define INIT_YAMOP_LTT(INST, LTT) ((INST)->y_u.Otapl.or_arg = LTT+1)
90#define PUT_YAMOP_LTT(INST, LTT) (INST)->y_u.Otapl.or_arg = YAMOP_FLAGS(INST) | (LTT+1)
91#define PUT_YAMOP_SEQ(INST) (INST)->y_u.Otapl.or_arg |= YAMOP_SEQ_FLAG
92#define PUT_YAMOP_CUT(INST) (INST)->y_u.Otapl.or_arg |= YAMOP_CUT_FLAG
94#define BRANCH(WORKER, DEPTH) GLOBAL_branch(WORKER, DEPTH)
95#define BRANCH_LTT(WORKER, DEPTH) (BRANCH(WORKER, DEPTH) & YAMOP_LTT_BITS)
96#define BRANCH_CUT(WORKER, DEPTH) (BRANCH(WORKER, DEPTH) & YAMOP_CUT_FLAG)
104#define PARALLEL_MODE_OFF 0
105#define PARALLEL_MODE_ON 1
106#define PARALLEL_MODE_RUNNING 2
114#define worker_offset(X) ((GLOBAL_number_workers + X - worker_id) % GLOBAL_number_workers * Yap_worker_area_size)
116#define LOCK_OR_FRAME(fr) LOCK(OrFr_lock(fr))
117#define UNLOCK_OR_FRAME(fr) UNLOCK(OrFr_lock(fr))
119#define LOCK_WORKER(w) LOCK(REMOTE_lock(w))
120#define UNLOCK_WORKER(w) UNLOCK(REMOTE_lock(w))
128#define SCH_top_shared_cp(CP) (Get_LOCAL_top_cp() == CP)
130#define SCH_any_share_request (LOCAL_share_request != MAX_WORKERS)
132#define SCHEDULER_GET_WORK() \
138#define SCH_check_prune_request() \
139 if (Get_LOCAL_prune_request()) { \
140 SCHEDULER_GET_WORK(); \
143#if defined(YAPOR_COPY) || defined(YAPOR_SBA) || defined(YAPOR_THREADS)
144#define SCH_check_share_request() \
145 if (SCH_any_share_request) { \
152#define SCH_check_share_request() \
153 if (SCH_any_share_request) { \
154 if (! p_share_work()) \
159#define SCH_check_requests() \
160 SCH_check_prune_request(); \
161 SCH_check_share_request()
163#define SCH_last_alternative(curpc, CP_PTR) \
164 HR = HBREG = PROTECT_FROZEN_H(CP_PTR); \
165 CPREG = CP_PTR->cp_cp; \
166 ENV = CP_PTR->cp_env; \
167 SCH_new_alternative(curpc, NULL)
175#define CUT_prune_to(PRUNE_CP) \
176 if (YOUNGER_CP(Get_LOCAL_top_cp(), PRUNE_CP)) { \
177 if (! Get_LOCAL_prune_request()) \
178 prune_shared_branch(PRUNE_CP, NULL); \
179 PRUNE_CP = Get_LOCAL_top_cp(); \
182#define CUT_wait_leftmost() \
183 if (GLOBAL_parallel_mode == PARALLEL_MODE_RUNNING) { \
185 int i, loop, depth, ltt; \
187 or_fr_ptr leftmost_or_fr; \
188 leftmost_or_fr = LOCAL_top_or_fr; \
190 depth = OrFr_depth(leftmost_or_fr); \
191 ltt = BRANCH_LTT(worker_id, depth); \
194 SCH_check_requests(); \
195 BITMAP_copy(members, OrFr_members(leftmost_or_fr)); \
196 BITMAP_delete(members, worker_id); \
197 for (i = 0; i < GLOBAL_number_workers; i++) { \
201 if (BITMAP_member(members, i) && \
202 BRANCH_LTT(i, depth) > ltt && \
203 (! BITMAP_member(GLOBAL_bm_idle_workers, i) || \
204 leftmost_or_fr != REMOTE_top_or_fr(i))) { \
210 leftmost_or_fr = OrFr_nearest_leftnode(leftmost_or_fr); \
211 } while (leftmost_or_fr != GLOBAL_root_or_fr); \
220void PUT_IN_ROOT_NODE(
int worker_num) {
221 LOCK(GLOBAL_locks_bm_root_cp_workers);
222 BITMAP_insert(GLOBAL_bm_root_cp_workers, worker_num);
223 UNLOCK(GLOBAL_locks_bm_root_cp_workers);
229void PUT_OUT_ROOT_NODE(
int worker_num) {
230 LOCK(GLOBAL_locks_bm_root_cp_workers);
231 BITMAP_delete(GLOBAL_bm_root_cp_workers, worker_num);
232 UNLOCK(GLOBAL_locks_bm_root_cp_workers);
237void PUT_IN_FINISHED(
int w) {
238 LOCK(GLOBAL_locks_bm_finished_workers);
239 BITMAP_insert(GLOBAL_bm_finished_workers, w);
240 UNLOCK(GLOBAL_locks_bm_finished_workers);
245#ifdef TABLING_INNER_CUTS
247void PUT_IN_PRUNING(
int w) {
248 LOCK(GLOBAL_locks_bm_pruning_workers);
249 BITMAP_insert(GLOBAL_bm_pruning_workers, w);
250 UNLOCK(GLOBAL_locks_bm_pruning_workers);
256void PUT_OUT_PRUNING(
int w) {
257 LOCK(GLOBAL_locks_bm_pruning_workers);
258 BITMAP_delete(GLOBAL_bm_pruning_workers, w);
259 UNLOCK(GLOBAL_locks_bm_pruning_workers);
271void PUT_IN_REQUESTABLE(
int p) {
272 LOCK(GLOBAL_locks_bm_requestable_workers);
273 BITMAP_insert(GLOBAL_bm_requestable_workers, p);
274 UNLOCK(GLOBAL_locks_bm_requestable_workers);
280void PUT_OUT_REQUESTABLE(
int p) {
281 LOCK(GLOBAL_locks_bm_requestable_workers);
282 BITMAP_delete(GLOBAL_bm_requestable_workers, p);
283 UNLOCK(GLOBAL_locks_bm_requestable_workers);
289void SCH_update_local_or_tops(
void) {
291 Set_LOCAL_top_cp(Get_LOCAL_top_cp()->cp_b);
292 LOCAL_top_or_fr = Get_LOCAL_top_cp()->cp_or_fr;
298void SCH_refuse_share_request_if_any(
void) {
300 if (SCH_any_share_request) {
301 REMOTE_reply_signal(LOCAL_share_request) = no_sharing;
302 LOCAL_share_request = MAX_WORKERS;
303 PUT_OUT_REQUESTABLE(worker_id);
313 choiceptr previous_cp = current_cp->cp_b;
315#define INIT_CP_LUB(CP, LUB) CP->cp_or_fr = (struct or_frame *)(LUB)
316#define CP_LUB(CP) (Int)(CP->cp_or_fr)
318 if (SCH_top_shared_cp(previous_cp))
320 else if (YAMOP_SEQ(previous_cp->cp_ap))
321 lub = CP_LUB(previous_cp);
323 lub = CP_LUB(previous_cp) + YAMOP_LTT(previous_cp->cp_ap);
324 INIT_CP_LUB(current_cp, lub);
326 if (YAMOP_SEQ(current_cp->cp_ap))
329 LOCAL_load = lub + YAMOP_LTT(current_cp->cp_ap);
334void SCH_new_alternative(
yamop *curpc,
yamop *
new) {
336 OrFr_alternative(LOCAL_top_or_fr) =
new;
337 BRANCH(worker_id, OrFr_depth(LOCAL_top_or_fr)) = YAMOP_OR_ARG(curpc);
338 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
349void CUT_send_prune_request(
int worker,
choiceptr prune_cp) {
351 if (YOUNGER_CP(REMOTE_top_cp(worker), prune_cp) &&
352 (! Get_REMOTE_prune_request(worker) || YOUNGER_CP(Get_REMOTE_prune_request(worker), prune_cp)))
353 Set_REMOTE_prune_request(worker, prune_cp);
354 UNLOCK_WORKER(worker);
360void CUT_reset_prune_request(
void) {
362 LOCK_WORKER(worker_id);
363 if (Get_LOCAL_prune_request() && EQUAL_OR_YOUNGER_CP(Get_LOCAL_prune_request(), Get_LOCAL_top_cp()))
364 Set_LOCAL_prune_request(NULL);
365 UNLOCK_WORKER(worker_id);
382 ltt = OrFr_pend_prune_ltt(
or_frame);
384 BITMAP_delete(members, worker_id);
385 for (i = 0; i < GLOBAL_number_workers; i++) {
386 if (BITMAP_member(members, i) && BRANCH_LTT(i, depth) > ltt)
398 or_fr_ptr leftmost_or_fr, or_fr, nearest_or_fr;
400 BITMAP_clear(members);
401 BITMAP_insert(members, worker_id);
402 leftmost_or_fr = LOCAL_top_or_fr;
403 depth = OrFr_depth(leftmost_or_fr);
405 ltt = BRANCH_LTT(worker_id, depth);
406 BITMAP_difference(members, OrFr_members(leftmost_or_fr), members);
408 for (i = 0; i < GLOBAL_number_workers; i++)
409 if (BITMAP_member(members, i) && BRANCH_LTT(i, depth) > ltt)
410 goto update_nearest_leftnode_data;
411 BITMAP_copy(members, OrFr_members(leftmost_or_fr));
412 leftmost_or_fr = OrFr_nearest_leftnode(leftmost_or_fr);
413 depth = OrFr_depth(leftmost_or_fr);
416update_nearest_leftnode_data:
417 or_fr = LOCAL_top_or_fr;
418 nearest_or_fr = OrFr_nearest_leftnode(or_fr);
419 while (OrFr_depth(nearest_or_fr) > depth) {
420 LOCK_OR_FRAME(or_fr);
421 OrFr_nearest_leftnode(or_fr) = leftmost_or_fr;
422 UNLOCK_OR_FRAME(or_fr);
423 or_fr = nearest_or_fr;
424 nearest_or_fr = OrFr_nearest_leftnode(or_fr);
427 return leftmost_or_fr;
431#ifdef TABLING_INNER_CUTS
435 bitmap prune_members, members;
439 leftmost_or_fr = OrFr_nearest_leftnode(start_or_fr);
440 depth = OrFr_depth(leftmost_or_fr);
441 if (depth > until_depth) {
442 BITMAP_copy(prune_members, GLOBAL_bm_pruning_workers);
443 BITMAP_delete(prune_members, worker_id);
444 ltt = BRANCH_LTT(worker_id, depth);
445 BITMAP_intersection(members, prune_members, OrFr_members(leftmost_or_fr));
447 for (i = 0; i < GLOBAL_number_workers; i++) {
448 if (BITMAP_member(members, i) &&
449 BRANCH_LTT(i, depth) > ltt &&
450 EQUAL_OR_YOUNGER_CP(GetOrFr_node(leftmost_or_fr), REMOTE_pruning_scope(i)))
451 return leftmost_or_fr;
453 BITMAP_minus(prune_members, members);
456 leftmost_or_fr = OrFr_nearest_leftnode(leftmost_or_fr);
457 depth = OrFr_depth(leftmost_or_fr);
458 while (depth > until_depth) {
459 ltt = BRANCH_LTT(worker_id, depth);
460 BITMAP_intersection(members, prune_members, OrFr_members(leftmost_or_fr));
462 for (i = 0; i < GLOBAL_number_workers; i++) {
463 if (BITMAP_member(members, i) &&
464 BRANCH_LTT(i, depth) > ltt &&
465 EQUAL_OR_YOUNGER_CP(GetOrFr_node(leftmost_or_fr), REMOTE_pruning_scope(i))) {
467 OrFr_nearest_leftnode(start_or_fr) = leftmost_or_fr;
468 start_or_fr = OrFr_nearest_leftnode(start_or_fr);
469 nearest_or_fr = OrFr_nearest_leftnode(start_or_fr);
470 while (OrFr_depth(nearest_or_fr) > depth) {
471 LOCK_OR_FRAME(start_or_fr);
472 OrFr_nearest_leftnode(start_or_fr) = leftmost_or_fr;
473 UNLOCK_OR_FRAME(start_or_fr);
474 start_or_fr = nearest_or_fr;
475 nearest_or_fr = OrFr_nearest_leftnode(start_or_fr);
477 return leftmost_or_fr;
480 BITMAP_minus(prune_members, members);
482 leftmost_or_fr = OrFr_nearest_leftnode(leftmost_or_fr);
483 depth = OrFr_depth(leftmost_or_fr);
486 OrFr_nearest_leftnode(start_or_fr) = leftmost_or_fr;
487 start_or_fr = OrFr_nearest_leftnode(start_or_fr);
488 nearest_or_fr = OrFr_nearest_leftnode(start_or_fr);
489 while (OrFr_depth(nearest_or_fr) > depth) {
490 LOCK_OR_FRAME(start_or_fr);
491 OrFr_nearest_leftnode(start_or_fr) = leftmost_or_fr;
492 UNLOCK_OR_FRAME(start_or_fr);
493 start_or_fr = nearest_or_fr;
494 nearest_or_fr = OrFr_nearest_leftnode(start_or_fr);
513 ltt = BRANCH_LTT(worker_id, OrFr_depth(
or_frame));
514 solution_ptr = & OrFr_qg_solutions(
or_frame);
515 while (*solution_ptr && ltt > SolFr_ltt(*solution_ptr)) {
516 solution_ptr = & SolFr_next(*solution_ptr);
518 if (*solution_ptr && ltt == SolFr_ltt(*solution_ptr)) {
519 AnsFr_next(SolFr_last(*solution_ptr)) = new_answer;
520 SolFr_last(*solution_ptr) = new_answer;
523 ALLOC_QG_SOLUTION_FRAME(new_solution);
524 SolFr_next(new_solution) = *solution_ptr;
525 SolFr_ltt(new_solution) = ltt;
526 SolFr_first(new_solution) = new_answer;
527 SolFr_last(new_solution) = new_answer;
528 *solution_ptr = new_solution;
540 ltt = BRANCH_LTT(worker_id, OrFr_depth(
or_frame));
541 solution_ptr = & OrFr_qg_solutions(
or_frame);
542 while (*solution_ptr && ltt > SolFr_ltt(*solution_ptr)) {
543 solution_ptr = & SolFr_next(*solution_ptr);
545 if (*solution_ptr && ltt == SolFr_ltt(*solution_ptr)) {
546 AnsFr_next(SolFr_last(*solution_ptr)) = SolFr_first(new_solution);
547 SolFr_last(*solution_ptr) = SolFr_last(new_solution);
548 FREE_QG_SOLUTION_FRAME(new_solution);
550 SolFr_next(new_solution) = *solution_ptr;
551 SolFr_ltt(new_solution) = ltt;
552 *solution_ptr = new_solution;
559void CUT_join_answers_in_an_unique_frame(
qg_sol_fr_ptr join_solution) {
562 while ((next_solution = SolFr_next(join_solution))) {
563 AnsFr_next(SolFr_last(join_solution)) = SolFr_first(next_solution);
564 SolFr_last(join_solution) = SolFr_last(next_solution);
565 SolFr_next(join_solution) = SolFr_next(next_solution);
566 FREE_QG_SOLUTION_FRAME(next_solution);
576 current_answer = SolFr_first(solution);
578 next_answer = AnsFr_next(current_answer);
579 FREE_QG_ANSWER_FRAME(current_answer);
580 current_answer = next_answer;
581 }
while (current_answer);
582 FREE_QG_SOLUTION_FRAME(solution);
588void CUT_free_solution_frames(
qg_sol_fr_ptr current_solution) {
591 while (current_solution) {
592 next_solution = SolFr_next(current_solution);
593 CUT_free_solution_frame(current_solution);
594 current_solution = next_solution;
604 while (solutions && ltt > SolFr_ltt(solutions)) {
605 next_solution = SolFr_next(solutions);
606 CUT_free_solution_frame(solutions);
607 solutions = next_solution;