[m-rev.] for post-commit review: Recent auto-parallelisation changes.
Paul Bone
pbone at csse.unimelb.edu.au
Mon Dec 13 15:34:33 AEDT 2010
For post-commit review by Zoltan.
Zoltan intends to modify this code soon anyway.
A reviewer should pay attention to my change to library/array.m.
---
Improve the efficiency of the algorithms that select the best parallelsation of
a conjunction. Now (by default) the search will stop creating choice points if
it has already created too many choice points.
deep_profiler/mdprof_fb.automatic_parallelism.m:
Fix a large number of whitespace problems, such as trailing whitespace at
the end of lines.
Never attempt to parallelise goals that arn't det or cc_multi.
Remove the original greedy search, it's now an option in the branch and
bound search code. Note that the greedy search algorithm has changed and
sacrifices more solutions for runtime than before.
Note that there are bugs remaining in a few cases causing incorrect
parallel execution times to be calculated for dependant parallelisations.
deep_profiler/mdprof_feedback.m:
Conform to changes in mdbcomp/feedback.automatic_parallelism.m.
Update parsing of options for the choice of best parallelsation algorithm.
deep_profiler/branch_and_bound.m:
Allow branch and bound code to track how many 'alternatives' have been
created and alter the search in response to this.
Branch and bound code must now be impure as it may call these impure
predicates.
Flush the output stream in debugging trace goals for branch and bound.
deep_profiler/measurements.m:
Adjust the interface to the parallelsation metrics structure, so that it is
easier to use with the new parallelsation search code.
Changes to the goal costs code:
Rename zero_goal_cost to dead_goal_cost, it is the cost of goals that are
never executed.
Modify atomic_goal_cost to take as a parameter the number of calls made to
this goal.
add_goal_costs has been renamed to add_goal_costs_seq since it computes
the cost of a sequential conjunction of goals.
The goal_cost_csq type has changed to track the number of calls made to
trivial goals.
deep_profiler/message.m:
Added a notice message to be used when the candidate parallel conjunction
is not det or cc_multi.
mdbcomp/feedback.automatic_parallelism.m:
Modify the alternatives for 'best parallelisation algorithm'.
This type now represents the new ways of selecting complete vs greedy
algorithms.
mdbcomp/program_representation.m:
Add a multi-moded detism_components/3 predicate and refactor
detism_get_solutions/1 and detism_get_can_fail/1 to call it.
Add a multi-moded detism_committed_choice/2 predicate and a
committed_choice type.
Fix whitespace errors in this file.
library/array.m:
modify fetch_items/4 to do bounds checking. This change helped me track
down a bug.
Index: deep_profiler/branch_and_bound.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/branch_and_bound.m,v
retrieving revision 1.1
diff -u -p -b -r1.1 branch_and_bound.m
--- deep_profiler/branch_and_bound.m 14 Jul 2010 00:40:22 -0000 1.1
+++ deep_profiler/branch_and_bound.m 13 Dec 2010 04:29:59 -0000
@@ -45,6 +45,8 @@
bnbp_new_best_solution :: int,
bnbp_new_equal_solution :: int,
bnbp_not_best_solution :: int,
+ bnbp_open_branches :: int,
+ bnbp_closed_branches :: int,
bnbp_time_msecs :: int
).
@@ -58,7 +60,7 @@
% The set of best solutions is returned, it is up to the caller to break
% ties if necessary.
%
-:- pred branch_and_bound(semipure pred(bnb_state(T), T),
+:- pred branch_and_bound(impure pred(bnb_state(T), T),
func(T) = float, set(T), bnb_profile).
:- mode branch_and_bound(pred(in, out) is nondet,
func(in) = out is det, out, out) is det.
@@ -72,6 +74,31 @@
%
:- semipure pred test_incomplete_solution(bnb_state(T)::in, T::in) is semidet.
+ % score_solution(State, Solution, Score).
+ %
+ % Score the complete or partial solution without comparing it to the best
+ % solution.
+ %
+:- pred score_solution(bnb_state(T)::in, T::in, float::out) is det.
+
+ % add_alternative(State).
+ %
+ % Record that a new alternative is being added to the search.
+ %
+:- impure pred add_alternative(bnb_state(T)::in) is det.
+
+ % close_alternative(State).
+ %
+ % Note that a branch failed such that we're now executing it's alternative.
+ %
+:- impure pred close_alternative(bnb_state(T)::in) is det.
+
+ % num_alternatives(State, Open, Closed).
+ %
+ % Retrive the number of alternative branches both opened and closed.
+ %
+:- semipure pred num_alternatives(bnb_state(T)::in, int::out, int::out) is det.
+
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -121,7 +148,7 @@ branch_and_bound(Generator, ObjectiveFn,
),
Profile = Profile0 ^ bnbp_time_msecs := Time.
-:- pred branch_and_bound_2(semipure pred(bnb_state(T), T),
+:- pred branch_and_bound_2(impure pred(bnb_state(T), T),
func(T) = float, unit,
pair(set(T), bnb_profile)).
:- mode branch_and_bound_2(pred(in, out) is nondet,
@@ -131,20 +158,22 @@ branch_and_bound_2(Generator, ObjectiveF
% Use a failure driven loop to implement a branch and bound solver.
promise_pure (
trace [compile_time(flag("debug_branch_and_bound")), io(!IO)] (
- io.write_string("D: Branch and bound loop starting\n", !IO)
+ io.write_string("D: Branch and bound loop starting\n", !IO),
+ io.flush_output(!IO)
),
impure new_mutvar(no_best_solutions, BestSolutionsMutvar),
impure new_mutvar(new_bnb_profile, ProfileMutvar),
State = bnb_state(BestSolutionsMutvar, ObjectiveFn, ProfileMutvar),
(
- semipure Generator(State, CurrentSolution),
+ impure Generator(State, CurrentSolution),
impure test_complete_solution(State, CurrentSolution),
trace [compile_time(flag("debug_branch_and_bound")), io(!IO)] (
CurrentObjective = ObjectiveFn(CurrentSolution),
io.format(
"D: Branch and bound: Solution found with objective: %f\n",
- [f(CurrentObjective)], !IO)
+ [f(CurrentObjective)], !IO),
+ io.flush_output(!IO)
),
semidet_fail
@@ -158,7 +187,8 @@ branch_and_bound_2(Generator, ObjectiveF
impure get_mutvar(BestSolutionsMutvar, FinalBestSolutions0),
impure get_mutvar(ProfileMutvar, FinalProfile),
trace [compile_time(flag("debug_branch_and_bound")), io(!IO)] (
- io.write_string("D: Branch and bound loop finished\n", !IO)
+ io.write_string("D: Branch and bound loop finished\n", !IO),
+ io.flush_output(!IO)
),
(
FinalBestSolutions0 = no_best_solutions,
@@ -243,39 +273,84 @@ test_incomplete_solution(State, Solution
%-----------------------------------------------------------------------------%
+score_solution(State, Solution, Score) :-
+ ObjectiveFn = State ^ objective_function,
+ Score = ObjectiveFn(Solution).
+
+%----------------------------------------------------------------------------%
+
+add_alternative(State) :-
+ ProfileMutvar = State ^ profile,
+ impure get_mutvar(ProfileMutvar, Profile0),
+ profile_add_alternative(Profile0, Profile),
+ impure set_mutvar(ProfileMutvar, Profile).
+
+close_alternative(State) :-
+ ProfileMutvar = State ^ profile,
+ impure get_mutvar(ProfileMutvar, Profile0),
+ profile_close_alternative(Profile0, Profile),
+ impure set_mutvar(ProfileMutvar, Profile).
+
+num_alternatives(State, Open, Closed) :-
+ ProfileMutvar = State ^ profile,
+ promise_semipure (
+ impure get_mutvar(ProfileMutvar, Profile)
+ ),
+ profile_num_alternatives(Profile, Open, Closed).
+
+%-----------------------------------------------------------------------------%
+
:- func new_bnb_profile = bnb_profile.
-new_bnb_profile = bnb_profile(0, 0, 0, 0, 0, 0).
+new_bnb_profile = bnb_profile(0, 0, 0, 0, 0, 1, 0, 0).
:- pred profile_new_best_solution(bnb_profile::in, bnb_profile::out) is det.
-profile_new_best_solution(Profile0, Profile) :-
- Profile = Profile0 ^ bnbp_new_best_solution :=
- Profile0 ^ bnbp_new_best_solution + 1.
+profile_new_best_solution(!Profile) :-
+ !Profile ^ bnbp_new_best_solution :=
+ !.Profile ^ bnbp_new_best_solution + 1.
:- pred profile_equal_best_solution(bnb_profile::in, bnb_profile::out) is det.
-profile_equal_best_solution(Profile0, Profile) :-
- Profile = Profile0 ^ bnbp_new_equal_solution :=
- Profile0 ^ bnbp_new_equal_solution + 1.
+profile_equal_best_solution(!Profile) :-
+ !Profile ^ bnbp_new_equal_solution :=
+ !.Profile ^ bnbp_new_equal_solution + 1.
:- pred profile_not_best_solution(bnb_profile::in, bnb_profile::out) is det.
-profile_not_best_solution(Profile0, Profile) :-
- Profile = Profile0 ^ bnbp_not_best_solution :=
- Profile0 ^ bnbp_not_best_solution + 1.
+profile_not_best_solution(!Profile) :-
+ !Profile ^ bnbp_not_best_solution :=
+ !.Profile ^ bnbp_not_best_solution + 1.
:- pred profile_test_succeeded(bnb_profile::in, bnb_profile::out) is det.
-profile_test_succeeded(Profile0, Profile) :-
- Profile = Profile0 ^ bnbp_tests_succeeded :=
- Profile0 ^ bnbp_tests_succeeded + 1.
+profile_test_succeeded(!Profile) :-
+ !Profile ^ bnbp_tests_succeeded :=
+ !.Profile ^ bnbp_tests_succeeded + 1.
:- pred profile_test_failed(bnb_profile::in, bnb_profile::out) is det.
-profile_test_failed(Profile0, Profile) :-
- Profile = Profile0 ^ bnbp_tests_failed :=
- Profile0 ^ bnbp_tests_failed + 1.
+profile_test_failed(!Profile) :-
+ !Profile ^ bnbp_tests_failed :=
+ !.Profile ^ bnbp_tests_failed + 1.
+
+:- pred profile_add_alternative(bnb_profile::in, bnb_profile::out) is det.
+
+profile_add_alternative(!Profile) :-
+ !Profile ^ bnbp_open_branches :=
+ !.Profile ^ bnbp_open_branches + 1.
+
+:- pred profile_close_alternative(bnb_profile::in, bnb_profile::out) is det.
+
+profile_close_alternative(!Profile) :-
+ !Profile ^ bnbp_closed_branches :=
+ !.Profile ^ bnbp_closed_branches + 1.
+
+:- pred profile_num_alternatives(bnb_profile::in, int::out, int::out) is det.
+
+profile_num_alternatives(Profile, Open, Closed) :-
+ Open = Profile ^ bnbp_open_branches,
+ Closed = Profile ^ bnbp_closed_branches.
%-----------------------------------------------------------------------------%
Index: deep_profiler/mdprof_fb.automatic_parallelism.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/mdprof_fb.automatic_parallelism.m,v
retrieving revision 1.20
diff -u -p -b -r1.20 mdprof_fb.automatic_parallelism.m
--- deep_profiler/mdprof_fb.automatic_parallelism.m 16 Oct 2010 04:11:04 -0000 1.20
+++ deep_profiler/mdprof_fb.automatic_parallelism.m 13 Dec 2010 04:29:59 -0000
@@ -685,6 +685,8 @@ build_candidate_par_conjunction_maps(Pro
goal_get_conjunctions_worth_parallelising(Info, GoalPath, !Goal, Candidates,
Messages) :-
GoalExpr0 = !.Goal ^ goal_expr_rep,
+ Coverage = !.Goal ^ goal_annotation ^ pgd_coverage,
+ get_coverage_before_det(Coverage, Calls),
(
(
GoalExpr0 = conj_rep(Conjs0),
@@ -692,7 +694,13 @@ goal_get_conjunctions_worth_parallelisin
GoalPath),
Conjs0, Conjs, Candidatess, Messagess, 1, _),
conj_build_candidate_conjunctions(Info, GoalPath, Conjs,
- Cost, MessagesB, MaybeCandidate),
+ MaybeCost, MessagesB, MaybeCandidate),
+ (
+ MaybeCost = yes(Cost)
+ ;
+ MaybeCost = no,
+ Cost = !.Goal ^ goal_annotation ^ pgd_cost
+ ),
GoalExpr = conj_rep(Conjs),
Messages = cord_list_to_cord(Messagess) ++ MessagesB,
(
@@ -707,7 +715,7 @@ goal_get_conjunctions_worth_parallelisin
map3_foldl(disj_get_conjunctions_worth_parallelising(Info,
GoalPath),
Disjs0, Disjs, Candidatess, Messagess, 1, _),
- disj_calc_cost(Disjs, Cost),
+ disj_calc_cost(Disjs, Calls, Cost),
GoalExpr = disj_rep(Disjs),
Messages = cord_list_to_cord(Messagess),
Candidates = condense(Candidatess)
@@ -716,9 +724,7 @@ goal_get_conjunctions_worth_parallelisin
map3_foldl(switch_case_get_conjunctions_worth_parallelising(Info,
GoalPath),
Cases0, Cases, Candidatess, Messagess, 1, _),
- get_coverage_before_det(!.Goal ^ goal_annotation ^ pgd_coverage,
- CountBefore),
- switch_calc_cost(Cases, CountBefore, Cost),
+ switch_calc_cost(Cases, Calls, Cost),
GoalExpr = switch_rep(Var, CanFail, Cases),
Messages = cord_list_to_cord(Messagess),
Candidates = condense(Candidatess)
@@ -821,11 +827,11 @@ ite_get_conjunctions_worth_parallelising
% of calls we've found and make any parallelisation decisions.
%
:- pred conj_build_candidate_conjunctions(implicit_parallelism_info::in,
- goal_path::in, list(pard_goal_detail)::in, goal_cost_csq::out,
+ goal_path::in, list(pard_goal_detail)::in, maybe(goal_cost_csq)::out,
cord(message)::out, maybe(candidate_par_conjunction(pard_goal_detail))::out)
is det.
-conj_build_candidate_conjunctions(Info, GoalPath, Conjs, Cost, Messages,
+conj_build_candidate_conjunctions(Info, GoalPath, Conjs, MaybeCost, Messages,
MaybeCandidate) :-
ProcLabel = Info ^ ipi_proc_label,
Location = goal(ProcLabel, GoalPath),
@@ -835,80 +841,58 @@ conj_build_candidate_conjunctions(Info,
% Preprocess the conjunction to find the costly calls and where they
% are.
- foldl2(identify_costly_goals, Conjs, 1, _,
- no_costly_goals, CostlyGoalsInfo),
- (
- ( CostlyGoalsInfo = no_costly_goals
- ; CostlyGoalsInfo = one_costly_goal(_)
- ),
- conj_calc_cost(Conjs, Cost),
+ identify_costly_goals(Conjs, 1, CostlyGoalsIndexes),
+ NumCostlyGoals = length(CostlyGoalsIndexes),
+ ( NumCostlyGoals < 2 ->
+ MaybeCost = no,
MaybeCandidate = no
;
- CostlyGoalsInfo = many_costly_goals(_, _, NumCostlyCalls),
-
append_message(Location,
- info_found_conjs_above_callsite_threshold(NumCostlyCalls),
+ info_found_conjs_above_callsite_threshold(NumCostlyGoals),
!Messages),
pardgoals_build_candidate_conjunction(Info, Location, GoalPath,
- Conjs, MaybeCandidate),
+ Conjs, MaybeCandidate, !Messages),
(
MaybeCandidate = yes(Candidate),
append_message(Location,
info_found_n_conjunctions_with_positive_speedup(1),
!Messages),
ExecMetrics = Candidate ^ cpc_par_exec_metrics,
- Cost = call_goal_cost(ExecMetrics ^ pem_num_calls,
- ExecMetrics ^ pem_par_time)
+ MaybeCost = yes(call_goal_cost(ExecMetrics ^ pem_num_calls,
+ ExecMetrics ^ pem_par_time))
;
MaybeCandidate = no,
- conj_calc_cost(Conjs, Cost)
+ MaybeCost = no
)
),
Messages = !.Messages
).
-:- type costly_goals_info
- ---> no_costly_goals
- ; one_costly_goal(
- ocg_index :: int
- )
- ; many_costly_goals(
- ocg_first_index :: int,
- ocg_last_index :: int,
- ocg_mum_goals :: int
- ).
+:- pred identify_costly_goals(list(pard_goal_detail)::in, int::in,
+ list(int)::out) is det.
-:- pred identify_costly_goals(pard_goal_detail::in, int::in, int::out,
- costly_goals_info::in, costly_goals_info::out) is det.
-
-identify_costly_goals(Goal, !Index, !CostlyGoalsInfo) :-
+identify_costly_goals([], _, []).
+identify_costly_goals([Goal | Goals], Index, Indexes) :-
+ identify_costly_goals(Goals, Index + 1, Indexes0),
identify_costly_goal(Goal, Costly),
(
( Costly = is_costly_atomic_goal
; Costly = is_costly_compound_goal
),
- (
- !.CostlyGoalsInfo = no_costly_goals,
- !:CostlyGoalsInfo = one_costly_goal(!.Index)
- ;
- !.CostlyGoalsInfo = one_costly_goal(FirstIndex),
- !:CostlyGoalsInfo = many_costly_goals(FirstIndex, !.Index, 2)
- ;
- !.CostlyGoalsInfo = many_costly_goals(FirstIndex, _, Num),
- !:CostlyGoalsInfo = many_costly_goals(FirstIndex, !.Index, Num+1)
- )
+ Indexes = [Index | Indexes0]
;
- Costly = is_not_costly_goal
- ),
- !:Index = !.Index + 1.
+ Costly = is_not_costly_goal,
+ Indexes = Indexes0
+ ).
:- pred pardgoals_build_candidate_conjunction(implicit_parallelism_info::in,
program_location::in, goal_path::in, list(pard_goal_detail)::in,
- maybe(candidate_par_conjunction(pard_goal_detail))::out) is det.
+ maybe(candidate_par_conjunction(pard_goal_detail))::out,
+ cord(message)::in, cord(message)::out) is det.
pardgoals_build_candidate_conjunction(Info, Location, GoalPath, Goals,
- MaybeCandidate) :-
+ MaybeCandidate, !Messages) :-
% Setting up the first parallel conjunct is a different algorithm to the
% latter ones, at this point we have the option of moving goals from before
% the first costly call to either before or during the parallel
@@ -916,15 +900,19 @@ pardgoals_build_candidate_conjunction(In
% efficient. However if goals within other parallel conjuncts depend on
% them and don't depend upon the first costly call then this would make the
% conjunction dependent when it could be independent.
- find_best_parallelisation(Info, Location, Goals, BestParallelisation),
+ find_best_parallelisation(Info, Location, Goals, MaybeBestParallelisation,
+ !Messages),
+ (
+ MaybeBestParallelisation = yes(BestParallelisation),
FirstConjNum = 1,
ParalleliseDepConjs = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs,
BestParallelisation = bp_parallel_execution(GoalsBefore, ParConjs,
GoalsAfter, IsDependent, Metrics),
Speedup = parallel_exec_metrics_get_speedup(Metrics),
- conj_calc_cost(GoalsBefore, GoalsBeforeCost0),
+ Calls = Metrics ^ pem_num_calls,
+ conj_calc_cost(GoalsBefore, Calls, GoalsBeforeCost0),
GoalsBeforeCost = goal_cost_get_percall(GoalsBeforeCost0),
- conj_calc_cost(GoalsAfter, GoalsAfterCost0),
+ conj_calc_cost(GoalsAfter, Calls, GoalsAfterCost0),
GoalsAfterCost = goal_cost_get_percall(GoalsAfterCost0),
Candidate = candidate_par_conjunction(goal_path_to_string(GoalPath),
FirstConjNum, IsDependent, GoalsBefore, GoalsBeforeCost, ParConjs,
@@ -951,8 +939,8 @@ pardgoals_build_candidate_conjunction(In
( Location = clique(_)
; Location = call_site_dynamic(_)
),
- error("Location is a clique or CSD when it should be a proc " ++
- "or goal")
+ error("Location is a clique or CSD when it should be a "
+ ++ "proc or goal")
),
convert_candidate_par_conjunction(pard_goal_detail_to_pard_goal,
@@ -965,6 +953,10 @@ pardgoals_build_candidate_conjunction(In
io.write_string(append_list(cord.list(Report)), !IO),
io.flush_output(!IO)
)
+ )
+ ;
+ MaybeBestParallelisation = no,
+ MaybeCandidate = no
).
:- type best_parallelisation
@@ -978,66 +970,69 @@ pardgoals_build_candidate_conjunction(In
:- pred find_best_parallelisation(implicit_parallelism_info::in,
program_location::in, list(pard_goal_detail)::in,
- best_parallelisation::out) is det.
+ maybe(best_parallelisation)::out,
+ cord(message)::in, cord(message)::out) is det.
-find_best_parallelisation(Info, Location, Goals, BestParallelisation) :-
+find_best_parallelisation(Info, Location, Goals, MaybeBestParallelisation,
+ !Messages) :-
% Decide which algorithm to use.
ConjunctionSize = length(Goals),
choose_algorithm(Info, ConjunctionSize, Algorithm),
-
- preprocess_conjunction(Goals, Algorithm, PreprocessedGoals),
+ preprocess_conjunction(Goals, MaybePreprocessedGoals, Location, !Messages),
(
- Algorithm = bpa_complete_bnb(_),
+ MaybePreprocessedGoals = yes(PreprocessedGoals),
find_best_parallelisation_complete_bnb(Info, Location,
- PreprocessedGoals, BestParallelisation)
+ Algorithm, PreprocessedGoals, MaybeBestParallelisation)
;
- Algorithm = bpa_greedy,
- find_best_parallelisation_greedy(Info, Location,
- PreprocessedGoals, BestParallelisation)
+ MaybePreprocessedGoals = no,
+ MaybeBestParallelisation = no
).
+:- type best_par_algorithm_simple
+ ---> bpas_complete(maybe(int))
+ ; bpas_greedy.
+
:- pred choose_algorithm(implicit_parallelism_info::in,
- int::in, best_par_algorithm::out) is det.
+ int::in, best_par_algorithm_simple::out) is det.
choose_algorithm(Info, ConjunctionSize, Algorithm) :-
Algorithm0 = Info ^ ipi_opts ^ cpcp_best_par_alg,
(
- Algorithm0 = bpa_complete_bnb(Limit),
- ( Limit \= 0, Limit < ConjunctionSize ->
- Algorithm = bpa_greedy
+ (
+ Algorithm0 = bpa_complete_branches(BranchesLimit),
+ MaybeBranchesLimit = yes(BranchesLimit)
+ ;
+ Algorithm0 = bpa_complete,
+ MaybeBranchesLimit = no
+ ),
+ Algorithm = bpas_complete(MaybeBranchesLimit)
;
- Algorithm = Algorithm0
+ Algorithm0 = bpa_complete_size(SizeLimit),
+ ( SizeLimit < ConjunctionSize ->
+ Algorithm = bpas_greedy
+ ;
+ Algorithm = bpas_complete(no)
)
;
Algorithm0 = bpa_greedy,
- Algorithm = Algorithm0
+ Algorithm = bpas_greedy
).
:- type goal_group(T)
- ---> gg_singleton(pard_goal_detail, T)
- ; gg_group(int, list(pard_goal_detail), T).
-
-:- inst gg_singleton
- ---> gg_singleton(ground, ground).
-
-:- pred gg_get_details(goal_group(T)::in, int::out,
- list(pard_goal_detail)::out, T::out) is det.
+ ---> gg_single(
+ ggs_index :: int,
+ ggs_abstract :: T
+ )
+ ; gg_multiple(
+ ggm_index :: int,
+ ggm_count :: int,
+ ggm_abstract :: T
+ ).
-gg_get_details(gg_singleton(Goal, P), 1, [Goal], P).
-gg_get_details(gg_group(Num, Goals, P), Num, Goals, P).
+:- pred gg_get_details(goal_group(T)::in, int::out, int::out, T::out) is det.
-:- func new_group(list(pard_goal_detail), T) = goal_group(T).
-
-new_group([], _) = _ :-
- error(this_file ++ "Can not construct empty goal group").
-new_group([G | Gs], P) = GoalGroup :-
- (
- Gs = [],
- GoalGroup = gg_singleton(G, P)
- ;
- Gs = [_ | _],
- GoalGroup = gg_group(length(Gs)+1, [G | Gs], P)
- ).
+gg_get_details(gg_single(Index, P), Index, 1, P).
+gg_get_details(gg_multiple(Index, Num, P), Index, Num, P).
% NOTE: These commented out types are relevant for some work that hasn't been
% done. They will either be used or removed in a future change.
@@ -1073,183 +1068,225 @@ new_group([G | Gs], P) = GoalGroup :-
---> gc_cheap_goals
; gc_costly_goals.
+ % A summerisation of goals before parallelistion.
+ %
+ % All indexes are 0-based except where otherwise noded.
+ %
:- type goals_for_parallelisation
---> goals_for_parallelisation(
+ gfp_goals :: array(pard_goal_detail),
+
+ gfp_first_costly_goal :: int,
+ gfp_last_costly_goal :: int,
+
gfp_groups ::
list(goal_group(goal_classification)),
- gfp_goals ::
- list(pard_goal_detail),
+ % The indexes in the dependency graph are 1-based.
gfp_dependency_graphs :: dependency_graphs,
+
gfp_costly_goal_indexes :: list(int),
gfp_num_calls :: int
).
:- inst goals_for_parallelisation
---> goals_for_parallelisation(
- non_empty_list, ground, ground,
+ ground, ground, ground,
+ non_empty_list,
+ ground,
non_empty_list,
ground).
:- pred preprocess_conjunction(list(pard_goal_detail)::in,
- best_par_algorithm::in,
- goals_for_parallelisation::out(goals_for_parallelisation)) is det.
+ maybe(goals_for_parallelisation)::out(maybe(goals_for_parallelisation)),
+ program_location::in, cord(message)::in, cord(message)::out) is det.
+
+preprocess_conjunction(Goals, MaybeGoalsForParallelisation, Location,
+ !Messages) :-
+ GoalsArray = array.from_list(Goals),
-preprocess_conjunction(Goals0, Algorithm, GoalsForParallelisation) :-
% Phase 1: Build a dependency map.
- build_dependency_graphs(Goals0, DependencyGraphs),
- % Phase 2: Find the costly calls.
- preprocess_conjunction_into_groups(Goals0, Algorithm, 1, GoalGroups,
- CostlyGoalsIndexes),
+ build_dependency_graphs(Goals, DependencyGraphs),
- % Get the number of calls into this conjunction.
+ % Phase 2: Find the costly calls.
+ identify_costly_goals(Goals, 0, CostlyGoalsIndexes),
(
- CostlyGoalsIndexes = [FirstCostlyGoalIndex | _],
- list.index1(Goals0, FirstCostlyGoalIndex, FirstCostlyGoal)
+ CostlyGoalsIndexes = [FirstCostlyGoalIndexPrime | OtherIndexes],
+ last(OtherIndexes, LastCostlyGoalIndexPrime)
->
- Cost = FirstCostlyGoal ^ goal_annotation ^ pgd_cost,
- NumCalls = goal_cost_get_calls(Cost)
+ FirstCostlyGoalIndex = FirstCostlyGoalIndexPrime,
+ LastCostlyGoalIndex = LastCostlyGoalIndexPrime
;
- error(this_file ++ "Expected call goal")
+ error(this_file ++ "too few costly goals")
),
- GoalsForParallelisation = goals_for_parallelisation(GoalGroups,
- Goals0, DependencyGraphs, CostlyGoalsIndexes, NumCalls).
+ % Phase 3: Check that all the middle goals are model det.
+ foldl_sub_array(goal_accumulate_detism, GoalsArray,
+ FirstCostlyGoalIndex, LastCostlyGoalIndex, det_rep, Detism),
+ (
+ ( Detism = det_rep
+ ; Detism = cc_multidet_rep
+ ),
- % identify_costly_goals(Goals, 1, GoalGroups, SortedCostlyIndexes).
- %
- % GoalGroups are Goals divided into groups of single costly calls and
- % multiple goals in-between these calls. SortedCostlyIndexes are the
- % indexes of the costly calls in the original list (starting at 1). This
- % predicate is undefined if any of the goals in Goals are non-atomic.
- %
-:- pred preprocess_conjunction_into_groups(list(pard_goal_detail)::in,
- best_par_algorithm::in, int::in,
- list(goal_group(goal_classification))::out, list(int)::out) is det.
+ % Phase 3: Process the middle section into groups.
+ foldl_sub_array(preprocess_conjunction_into_groups, GoalsArray,
+ FirstCostlyGoalIndex, LastCostlyGoalIndex, [], RevGoalGroups),
+ reverse(RevGoalGroups, GoalGroups),
-preprocess_conjunction_into_groups([], _, _, [], []).
-preprocess_conjunction_into_groups([Goal | Goals], Alg, Index, GoalGroups,
- Indexes) :-
- preprocess_conjunction_into_groups(Goals, Alg, Index+1, GoalGroups0,
- Indexes0),
- identify_costly_goal(Goal, Costly),
- (
- ( Costly = is_costly_atomic_goal
- ; Costly = is_costly_compound_goal
+ FirstCostlyGoal = lookup(GoalsArray, FirstCostlyGoalIndex),
+ Cost = FirstCostlyGoal ^ goal_annotation ^ pgd_cost,
+ NumCalls = goal_cost_get_calls(Cost),
+
+ GoalsForParallelisation = goals_for_parallelisation(GoalsArray,
+ FirstCostlyGoalIndex, LastCostlyGoalIndex, GoalGroups,
+ DependencyGraphs, CostlyGoalsIndexes, NumCalls),
+ MaybeGoalsForParallelisation = yes(GoalsForParallelisation)
+ ;
+ ( Detism = semidet_rep
+ ; Detism = multidet_rep
+ ; Detism = nondet_rep
+ ; Detism = erroneous_rep
+ ; Detism = failure_rep
+ ; Detism = cc_nondet_rep
),
- GoalClassification = gc_costly_goals,
- Indexes = [Index | Indexes0]
+ MaybeGoalsForParallelisation = no,
+ append_message(Location, notice_candidate_conjunction_not_det(Detism),
+ !Messages)
+ ).
+
+:- pred foldl_sub_array(pred(int, T, A, A), array(T), int, int, A, A).
+:- mode foldl_sub_array(pred(in, in, in, out) is det,
+ in, in, in, in, out) is det.
+
+foldl_sub_array(Pred, Array, Index, Last, !A) :-
+ ( Index =< Last ->
+ X = lookup(Array, Index),
+ Pred(Index, X, !A),
+ foldl_sub_array(Pred, Array, Index + 1, Last, !A)
;
- Costly = is_not_costly_goal,
- GoalClassification = gc_cheap_goals,
- Indexes = Indexes0
- ),
+ true
+ ).
+
+:- pred goal_accumulate_detism(int::in, pard_goal_detail::in,
+ detism_rep::in, detism_rep::out) is det.
+
+goal_accumulate_detism(_, Goal, !Detism) :-
+ detism_components(!.Detism, Solutions0, CanFail0),
+ detism_committed_choice(!.Detism, CommittedChoice0),
+ Detism = Goal ^ goal_detism_rep,
+ detism_components(Detism, GoalSolutions, GoalCanFail),
+ detism_committed_choice(Detism, GoalCommittedChoice),
(
- Alg = bpa_greedy,
- % Group cheap goals together.
+ GoalSolutions = at_most_zero_rep,
+ Solutions = at_most_zero_rep
+ ;
+ GoalSolutions = at_most_one_rep,
+ Solutions = Solutions0
+ ;
+ GoalSolutions = at_most_many_rep,
(
- GoalClassification = gc_cheap_goals,
- GoalGroups0 = [LastGoalGroup | GoalGroups1Prime],
- gg_get_details(LastGoalGroup, NumLastGoals, LastGoals,
- gc_cheap_goals)
- ->
- GoalGroup = gg_group(NumLastGoals+1, [Goal | LastGoals],
- gc_cheap_goals),
- GoalGroups1 = GoalGroups1Prime
+ Solutions0 = at_most_zero_rep,
+ Solutions = at_most_zero_rep
;
- GoalGroup = gg_singleton(Goal, GoalClassification),
- GoalGroups1 = GoalGroups0
+ ( Solutions0 = at_most_one_rep
+ ; Solutions0 = at_most_many_rep
+ ),
+ Solutions = GoalSolutions
)
+ ),
+ (
+ GoalCanFail = can_fail_rep,
+ CanFail = can_fail_rep
;
- Alg = bpa_complete_bnb(_),
- GoalGroup = gg_singleton(Goal, GoalClassification),
- GoalGroups1 = GoalGroups0
+ GoalCanFail = cannot_fail_rep,
+ CanFail = CanFail0
),
- GoalGroups = [GoalGroup | GoalGroups1].
-
-:- type incomplete_parallelisation
- ---> incomplete_parallelisation(
- ip_goals_before :: list(pard_goal_detail),
- ip_par_conjs :: list(seq_conj(pard_goal_detail)),
- ip_par_exec_overlap :: parallel_execution_overlap,
- ip_par_exec_metrics :: parallel_exec_metrics_incomplete,
- ip_productions_map :: map(var_rep, float)
+ (
+ GoalCommittedChoice = committed_choice,
+ CommittedChoice = CommittedChoice0
+ ;
+ GoalCommittedChoice = not_committed_cnoice,
+ CommittedChoice = not_committed_cnoice
+ ),
+ (
+ promise_equivalent_solutions [FinalDetism] (
+ detism_components(FinalDetism, Solutions, CanFail),
+ detism_committed_choice(FinalDetism, CommittedChoice)
+ )
+ ->
+ !:Detism = FinalDetism
+ ;
+ error(this_file ++ "Cannot compute detism from components.")
).
-:- pred start_building_parallelisation(implicit_parallelism_info::in,
- int::in, list(pard_goal_detail)::in, incomplete_parallelisation::out)
- is det.
+ % foldl(preprocess_conjunction_into_groups, Goals, FirstCostlyGoalIndex,
+ % LastCostlyGoalIndex, RevGoalGroups)).
+ %
+ % GoalGroups are Goals divided into groups of single costly goals, Larger
+ % groups are not currently used. Only the goals within the range of costly
+ % goals inclusive are analysed.
+ %
+:- pred preprocess_conjunction_into_groups(int::in, pard_goal_detail::in,
+ list(goal_group(goal_classification))::in,
+ list(goal_group(goal_classification))::out) is det.
-start_building_parallelisation(Info, NumCalls, GoalsBefore, Parallelisation)
- :-
- SparkCost = Info ^ ipi_opts ^ cpcp_sparking_cost,
- SparkDelay = Info ^ ipi_opts ^ cpcp_sparking_delay,
- ContextWakeupDelay = Info ^ ipi_opts ^ cpcp_context_wakeup_delay,
- conj_calc_cost(GoalsBefore, CostBefore0),
- CostBefore = goal_cost_get_percall(CostBefore0),
- Metrics = init_empty_parallel_exec_metrics(CostBefore, NumCalls,
- float(SparkCost), float(SparkDelay), float(ContextWakeupDelay)),
- Overlap = peo_empty_conjunct,
- Parallelisation = incomplete_parallelisation(GoalsBefore, [], Overlap,
- Metrics, init).
-
- % Finalise the metrics and determine if this is the best solution so
- % far.
- %
-:- pred finalise_parallelisation(list(pard_goal_detail)::in,
- incomplete_parallelisation::in, best_parallelisation::out) is det.
-
-finalise_parallelisation(GoalsAfter, !Parallelisation) :-
- !.Parallelisation = incomplete_parallelisation(GoalsBefore, Conjuncts,
- Overlap, Metrics0, _),
- conj_calc_cost(GoalsAfter, CostAfter0),
- CostAfter = goal_cost_get_percall(CostAfter0),
- Metrics = finalise_parallel_exec_metrics(Metrics0, CostAfter),
- par_conj_overlap_is_dependent(Overlap, IsDependent),
- !:Parallelisation = bp_parallel_execution(GoalsBefore, Conjuncts,
- GoalsAfter, IsDependent, Metrics).
+preprocess_conjunction_into_groups(Index, Goal, !RevGoalGroups) :-
+ identify_costly_goal(Goal, Costly),
+ (
+ ( Costly = is_costly_atomic_goal
+ ; Costly = is_costly_compound_goal
+ ),
+ GoalClassification = gc_costly_goals
+ ;
+ Costly = is_not_costly_goal,
+ GoalClassification = gc_cheap_goals
+ ),
+ % XXX Goal grouping is not yet implemented/tested.
+ GoalGroup = gg_single(Index, GoalClassification),
+ !:RevGoalGroups = [GoalGroup | !.RevGoalGroups].
%----------------------------------------------------------------------------%
% Find the best parallelisation using the branch and bound algorithm.
%
:- pred find_best_parallelisation_complete_bnb(implicit_parallelism_info::in,
- program_location::in, goals_for_parallelisation::in,
- best_parallelisation::out) is det.
+ program_location::in, best_par_algorithm_simple::in,
+ goals_for_parallelisation::in, maybe(best_parallelisation)::out) is det.
-find_best_parallelisation_complete_bnb(Info, Location,
- PreprocessedGoals, BestParallelisation) :-
- PreprocessedGoals = goals_for_parallelisation(GoalGroups, _,
- DependencyMaps, CostlyCallsIndexes, NumCalls),
- ( last(CostlyCallsIndexes, LastCostlyCallIndexPrime) ->
- LastCostlyCallIndex = LastCostlyCallIndexPrime
- ;
- error(this_file ++ "no costly calls found")
+find_best_parallelisation_complete_bnb(Info, Location, Algorithm,
+ PreprocessedGoals, MaybeBestParallelisation) :-
+ trace [compile_time(flag("debug_branch_and_bound")), io(!IO)] (
+ io.format("D: Find best parallelisation for:\n%s\n",
+ [s(LocationString)], !IO),
+ location_to_string(1, Location, LocationCord),
+ string.append_list(list(LocationCord), LocationString),
+ NumGoals = size(PreprocessedGoals ^ gfp_goals),
+ NumGoalsBefore = PreprocessedGoals ^ gfp_first_costly_goal,
+ NumGoalsAfter = NumGoals - PreprocessedGoals ^ gfp_last_costly_goal - 1,
+ NumGoalsMiddle = NumGoals - NumGoalsBefore - NumGoalsAfter,
+ io.format("D: Problem size (before, middle, after): %d,%d,%d\n",
+ [i(NumGoalsBefore), i(NumGoalsMiddle), i(NumGoalsAfter)], !IO),
+ io.flush_output(!IO)
),
branch_and_bound(
- generate_parallelisations(Info, Location, LastCostlyCallIndex,
- NumCalls, DependencyMaps, GoalGroups),
+ generate_parallelisations(Info, Algorithm, PreprocessedGoals),
parallelisation_get_objective_value,
Solutions, Profile),
trace [compile_time(flag("debug_branch_and_bound")), io(!IO)] (
- io.format("D: Find best parallelisation for:\n%s\n",
- [s(LocationString)], !IO),
- location_to_string(1, Location, LocationCord),
- string.append_list(list(LocationCord), LocationString),
- io.format("D: Problem size: %d Solutions: %d\n",
- [i(length(GoalGroups)), i(count(Solutions))], !IO),
+ io.format("D: Solutions: %d\n",
+ [i(count(Solutions))], !IO),
io.format("D: Branch and bound profile: %s\n\n",
[s(string(Profile))], !IO),
io.flush_output(!IO)
),
(
- promise_equivalent_solutions [BestParallelisationPrime]
- member(BestParallelisationPrime, Solutions)
+ promise_equivalent_solutions [BestParallelisation]
+ member(BestParallelisation, Solutions)
->
- BestParallelisation = BestParallelisationPrime
+ MaybeBestParallelisation = yes(BestParallelisation)
;
ParalleliseDepConjs = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs,
(
@@ -1257,7 +1294,7 @@ find_best_parallelisation_complete_bnb(I
; ParalleliseDepConjs = parallelise_dep_conjs_naive
; ParalleliseDepConjs = parallelise_dep_conjs_num_vars
),
- error(this_file ++ "Execpted at least one solution from bnb solver")
+ MaybeBestParallelisation = no
;
ParalleliseDepConjs = do_not_parallelise_dep_conjs,
% Try again to get the best dependent parallelisation. This is
@@ -1265,7 +1302,7 @@ find_best_parallelisation_complete_bnb(I
TempInfo = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs :=
parallelise_dep_conjs_overlap,
find_best_parallelisation_complete_bnb(TempInfo, Location,
- PreprocessedGoals, BestParallelisation)
+ Algorithm, PreprocessedGoals, MaybeBestParallelisation)
)
).
@@ -1279,489 +1316,414 @@ parallelisation_get_objective_value(Para
Metrics = Parallelisation ^ bp_par_exec_metrics,
Value = Metrics ^ pem_par_time + Metrics ^ pem_par_overheads * 2.0.
-:- semipure pred generate_parallelisations(implicit_parallelism_info::in,
- program_location::in, int::in, int::in, dependency_graphs::in,
- list(goal_group(goal_classification))::in,
+:- impure pred generate_parallelisations(implicit_parallelism_info::in,
+ best_par_algorithm_simple::in, goals_for_parallelisation::in,
bnb_state(best_parallelisation)::in, best_parallelisation::out) is nondet.
-generate_parallelisations(Info, _Location, LastCostlyCallIndex,
- NumCalls, DependencyMaps, !.GoalGroups, BNBState,
- BestParallelisation) :-
- some [!GoalNum, !Parallelisation] (
- !:GoalNum = 1,
-
- generate_parallelisations_goals_before(GoalsBeforeConj, !GoalNum,
- !GoalGroups),
- start_building_parallelisation(Info, NumCalls, GoalsBeforeConj,
+generate_parallelisations(Info, Algorithm, GoalsForParallelisation,
+ BNBState, BestParallelisation) :-
+ some [!Parallelisation, !GoalGroups] (
+ start_building_parallelisation(Info, GoalsForParallelisation,
!:Parallelisation),
- semipure generate_parallelisations_body(Info, DependencyMaps, 0,
- BNBState, LastCostlyCallIndex, !GoalNum, !GoalGroups,
- !Parallelisation),
+ !:GoalGroups = GoalsForParallelisation ^ gfp_groups,
+ start_first_par_conjunct(!GoalGroups, !Parallelisation),
+ impure generate_parallelisations_body(Info, BNBState, Algorithm,
+ !.GoalGroups, !Parallelisation),
- generate_parallelisations_goals_after(!.GoalNum, !.GoalGroups,
- GoalsAfterConj),
+ (
+ semipure should_expand_search(BNBState, Algorithm)
+ ->
+ % Try to push goals into the first and last parallel conjuncts from
+ % outside the parallel conjunction.
+ semipure add_goals_into_first_par_conj(BNBState, !Parallelisation),
+ semipure add_goals_into_last_par_conj(BNBState, !Parallelisation)
+ ;
+ true
+ ),
- finalise_parallelisation(GoalsAfterConj, !.Parallelisation,
- BestParallelisation)
+ finalise_parallelisation(!.Parallelisation, BestParallelisation)
),
semipure test_incomplete_solution(BNBState, BestParallelisation).
-:- pred generate_parallelisations_goals_before(list(pard_goal_detail)::out,
- int::in, int::out,
- list(goal_group(goal_classification))::in,
- list(goal_group(goal_classification))::out) is multi.
+:- semipure pred add_goals_into_first_par_conj(
+ bnb_state(best_parallelisation)::in,
+ incomplete_parallelisation::in, incomplete_parallelisation::out) is multi.
+
+add_goals_into_first_par_conj(BNBState, !Parallelisation) :-
+ FirstGoal0 = !.Parallelisation ^ ip_first_par_goal,
+ (
+ FirstGoal0 > 0,
+ Goals = !.Parallelisation ^ ip_goals,
+ Goal = lookup(Goals, FirstGoal0 - 1),
+ can_parallelise_goal(Goal),
+
+ % There are goals before the parallel conjunction that can be included
+ % in the parallel conjunction.
+ add_one_goal_into_first_par_conj(!Parallelisation),
+ semipure test_parallelisation(BNBState, !Parallelisation),
+ semipure add_goals_into_first_par_conj(BNBState, !Parallelisation)
+ ;
+ true
+ ).
-generate_parallelisations_goals_before([], !GoalNum, !GoalGroups).
-generate_parallelisations_goals_before(Goals, !GoalNum, !GoalGroups) :-
- !.GoalGroups = [GoalGroup | !:GoalGroups],
- (
- GoalGroup = gg_singleton(Goal, Classification),
- !:GoalNum = !.GoalNum + 1,
- NewGoals = [Goal]
+:- semipure pred add_goals_into_last_par_conj(
+ bnb_state(best_parallelisation)::in,
+ incomplete_parallelisation::in, incomplete_parallelisation::out) is multi.
+
+add_goals_into_last_par_conj(BNBState, !Parallelisation) :-
+ NumGoals = ip_get_num_goals(!.Parallelisation),
+ LastParGoal = !.Parallelisation ^ ip_last_par_goal,
+ (
+ LastParGoal < NumGoals - 1,
+ Goals = !.Parallelisation ^ ip_goals,
+ Goal = lookup(Goals, LastParGoal + 1),
+ can_parallelise_goal(Goal),
+
+ % Try to move a goal from after the parallelisation into the
+ % parallelisation.
+ add_one_goal_into_last_par_conj(!Parallelisation),
+ semipure test_parallelisation(BNBState, !Parallelisation),
+ semipure add_goals_into_last_par_conj(BNBState, !Parallelisation)
;
- GoalGroup = gg_group(Num, NewGoals, Classification),
- !:GoalNum = !.GoalNum + Num
- ),
- Classification = gc_cheap_goals,
- generate_parallelisations_goals_before(Goals0, !GoalNum, !GoalGroups),
- Goals = NewGoals ++ Goals0.
+ true
+ ).
-:- pred generate_parallelisations_goals_after(int::in,
- list(goal_group(goal_classification))::in, list(pard_goal_detail)::out)
- is det.
+ % Set the last scheduled goal to the goal at the end of the first group,
+ % popping the first group off the list. This initialises the
+ % parallelistion with the first goal group occurring first in the first
+ % parallel conjunction.
+ %
+ % This is done outside of the loop below since the first goal group will
+ % always be added to the first (initially empty) parallel conjunction.
+ %
+:- pred start_first_par_conjunct(
+ list(goal_group(T))::in, list(goal_group(T))::out,
+ incomplete_parallelisation::in, incomplete_parallelisation::out) is det.
-generate_parallelisations_goals_after(_, [], []).
-generate_parallelisations_goals_after(Num0, [GG | GGs], Goals) :-
+start_first_par_conjunct(!GoalGroups, !Parallelisation) :-
(
- GG = gg_singleton(Goal, _),
- Num = Num0 + 1,
- NewGoals = [Goal]
- ;
- GG = gg_group(NewNum, NewGoals, _),
- Num = Num0 + NewNum
- ),
- generate_parallelisations_goals_after(Num, GGs, Goals0),
- Goals = NewGoals ++ Goals0.
-
-:- semipure pred generate_parallelisations_body(implicit_parallelism_info::in,
- dependency_graphs::in, int::in, bnb_state(best_parallelisation)::in,
- int::in, int::in, int::out,
+ !.GoalGroups = [],
+ error(this_file ++ "No goal groups.")
+ ;
+ !.GoalGroups = [Group | !:GoalGroups],
+ gg_get_details(Group, Index, Num, _),
+ LastScheduledGoal = Index + Num - 1,
+ !Parallelisation ^ ip_last_scheduled_goal := LastScheduledGoal
+ ).
+
+:- impure pred generate_parallelisations_body(implicit_parallelism_info::in,
+ bnb_state(best_parallelisation)::in, best_par_algorithm_simple::in,
list(goal_group(goal_classification))::in,
- list(goal_group(goal_classification))::out,
incomplete_parallelisation::in, incomplete_parallelisation::out) is nondet.
-generate_parallelisations_body(Info, DependencyMaps, NumConjuncts0,
- BNBState, LastCostlyCallIndex, !GoalNum, !GoalGroups,
- !Parallelisation) :-
- (
- !.GoalNum > LastCostlyCallIndex
- ->
- % if we have already visited all the costly calls then there are no
- % further parallelisations to make.
- % Verify that we've generated at least two parallel conjuncts,
- NumConjuncts0 >= 1
- ;
- % We continue building more parallel conjuncts.
- !.GoalGroups = [_ | _],
- generate_parallel_conjunct(ParConjGoals, !GoalNum, !GoalGroups),
-
- % Don't build a single parallel conjunct containing all the costly
- % calls.
- ( NumConjuncts0 = 0 => LastCostlyCallIndex >= !.GoalNum ),
-
- ( LastCostlyCallIndex >= !.GoalNum ->
- IsInnermostConjunct = is_not_innermost_conjunct
- ;
- IsInnermostConjunct = is_innermost_conjunct
- ),
- calculate_parallel_cost_step(Info, IsInnermostConjunct, NumConjuncts0,
- ParConjGoals, !Parallelisation),
- Overlap = !.Parallelisation ^ ip_par_exec_overlap,
+generate_parallelisations_body(_, _, _, [], !Parallelisation) :-
+ % Verify that we've generated at least two parallel conjuncts.
+ ip_get_num_parallel_conjuncts(!.Parallelisation) >= 2.
+generate_parallelisations_body(Info, BNBState, Algorithm,
+ [GoalGroup | GoalGroups], !Parallelisation) :-
+ LastScheduledGoal0 = !.Parallelisation ^ ip_last_scheduled_goal,
+ gg_get_details(GoalGroup, _Index, Num, _Classification),
+
+ LastScheduledGoal = LastScheduledGoal0 + Num,
+ some [!AddToLastParallelisation, !AddToNewParallelisation] (
+ !:AddToLastParallelisation = !.Parallelisation,
+ !:AddToNewParallelisation = !.Parallelisation,
+
+ % Consider adding this goal to the last parallel conjunct.
+ !AddToLastParallelisation ^ ip_last_scheduled_goal := LastScheduledGoal,
+ score_parallelisation(BNBState, MaybeAddToLastScore,
+ !AddToLastParallelisation),
+
+ % Consider putting this goal into a new parallel conjunct.
+ ParConjsRevLastGoal0 = !.Parallelisation ^ ip_par_conjs_rev_last_goal,
+ ParConjsRevLastGoal = [LastScheduledGoal0 | ParConjsRevLastGoal0],
+ !AddToNewParallelisation ^ ip_par_conjs_rev_last_goal :=
+ ParConjsRevLastGoal,
+ !AddToNewParallelisation ^ ip_last_scheduled_goal := LastScheduledGoal,
+ score_parallelisation(BNBState, MaybeAddToNewScore,
+ !AddToNewParallelisation),
- % Reject parallelisations that have dependent variables if we're not
- % allowed to create such parallelisations.
- ParalleliseDepConjs = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs,
- par_conj_overlap_is_dependent(Overlap, IsDependent),
(
- ParalleliseDepConjs = do_not_parallelise_dep_conjs
- =>
- IsDependent = conjuncts_are_independent
- ),
-
- % Test the corrent solution.
- finalise_parallelisation([], !.Parallelisation, TestParallelisation),
- semipure test_incomplete_solution(BNBState, TestParallelisation),
-
- NumConjuncts = NumConjuncts0 + 1,
- semipure generate_parallelisations_body(Info, DependencyMaps,
- NumConjuncts, BNBState, LastCostlyCallIndex, !GoalNum, !GoalGroups,
- !Parallelisation)
- ).
-
-:- pred generate_parallel_conjunct(
- list(pard_goal_detail)::out(non_empty_list), int::in, int::out,
- list(goal_group(goal_classification))::in(non_empty_list),
- list(goal_group(goal_classification))::out) is multi.
-
-generate_parallel_conjunct(Goals, !GoalNum, !GoalGroups) :-
- !.GoalGroups = [GoalGroup | !:GoalGroups],
+ MaybeAddToLastScore = yes(AddToLastScore),
(
- GoalGroup = gg_singleton(Goal, _),
- NewGoals = [Goal],
- NumNewGoals = 1
- ;
- GoalGroup = gg_group(NumNewGoals, NewGoals, _)
- ),
- !:GoalNum = !.GoalNum + NumNewGoals,
+ MaybeAddToNewScore = yes(AddToNewScore),
(
- !.GoalGroups = [],
- Goals0 = []
+ % Smaller scores are better.
+ AddToNewScore > AddToLastScore
+ ->
+ % Adding to the last parallel conjunct is better.
+ BestOption = !.AddToLastParallelisation,
+ MaybeSndBestOption = yes(!.AddToNewParallelisation)
;
- !.GoalGroups = [_ | _],
- % With these disjuncts in this order the predicate will return larger
- % conjuncts first.
- (
- generate_parallel_conjunct(Goals0, !GoalNum, !GoalGroups)
+ % Adding to a new parallel conjunct is better.
+ BestOption = !.AddToNewParallelisation,
+ MaybeSndBestOption = yes(!.AddToLastParallelisation)
+ )
;
- Goals0 = []
+ MaybeAddToNewScore = no,
+ % Adding to the last parallel conjunct is the only option.
+ BestOption = !.AddToLastParallelisation,
+ MaybeSndBestOption = no
+ )
+ ;
+ MaybeAddToLastScore = no,
+ % Adding to a new parallel conjunct is the only option.
+ BestOption = !.AddToNewParallelisation,
+ MaybeSndBestOption = no
)
),
- Goals = NewGoals ++ Goals0.
-
-%----------------------------------------------------------------------------%
-
- % The greedy algorithm for finding the best parallelisation of a
- % conjunction.
- %
-:- pred find_best_parallelisation_greedy(implicit_parallelism_info::in,
- program_location::in,
- goals_for_parallelisation::in(goals_for_parallelisation),
- best_parallelisation::out) is det.
-
-find_best_parallelisation_greedy(Info, _Location,
- PreprocessedGoals, !:Parallelisation) :-
- some [!GoalGroups, !ConjNum] (
- PreprocessedGoals = goals_for_parallelisation(!:GoalGroups, _,
- DependencyMaps, CostlyCallIndexes, NumCalls),
- !:ConjNum = 1,
- !.GoalGroups = [ FirstGroup | !:GoalGroups ],
- gg_get_details(FirstGroup, _, FirstGoals, FirstClassification),
(
- FirstClassification = gc_cheap_goals,
- build_goals_before_greedy(Info, DependencyMaps, CostlyCallIndexes,
- GoalsBeforeConj, !ConjNum, FirstGoals, RemainingGoals),
+ MaybeSndBestOption = no,
+ !:Parallelisation = BestOption
+ ;
+ MaybeSndBestOption = yes(SndBestOption),
+ (
+ % Should an alternative branch be created here?
+ semipure should_expand_search(BNBState, Algorithm)
+ ->
+ % Create a branch.
+ impure add_alternative(BNBState),
+ % This tries the leftmost disjunct first, so try the best option
+ % there.
(
- RemainingGoals = []
+ !:Parallelisation = BestOption
;
- RemainingGoals = [_ | _],
- !:GoalGroups =
- [new_group(RemainingGoals, gc_cheap_goals) | !.GoalGroups]
+ impure close_alternative(BNBState),
+ !:Parallelisation = SndBestOption
)
;
- FirstClassification = gc_costly_goals,
- !:GoalGroups = [ FirstGroup | !.GoalGroups ],
- GoalsBeforeConj = []
+ !:Parallelisation = BestOption
+ )
),
- start_building_parallelisation(Info, NumCalls, GoalsBeforeConj,
- !:Parallelisation),
- build_parallel_conjuncts_greedy(Info, DependencyMaps,
- CostlyCallIndexes, 0, [], [], LastParConj, !ConjNum,
- !GoalGroups, !Parallelisation),
+ semipure test_parallelisation(BNBState, !Parallelisation),
- (
- !.GoalGroups = [LastGroup | EmptyGroups],
- require(unify(EmptyGroups, []), "EmptyGroups \\= []"),
- gg_get_details(LastGroup, _, LastGoals0, LastClassification),
- require(unify(LastClassification, gc_cheap_goals),
- "LastClassification \\= gc_cheap_goals")
- ;
- !.GoalGroups = [],
- LastGoals0 = []
- ),
+ impure generate_parallelisations_body(Info, BNBState, Algorithm,
+ GoalGroups, !Parallelisation).
- build_goals_after_greedy(Info, !.ConjNum, LastParConj,
- LastGoals0, LastGoals, !Parallelisation),
- finalise_parallelisation(LastGoals, !Parallelisation)
- ).
-
- % build_goals_before_greedy(Info, Deps, CostlyCallIndexes,
- % GoalsBefore, GoalsWithin, !GoalNum, !Goals).
- %
- % Take GoalsBefore goals from !Goals, that should be run sequentially
- % before the parallelisation begins. !.GaolNum gives the index of the
- % first goal in !.Goals.
- %
-:- pred build_goals_before_greedy(implicit_parallelism_info::in,
- dependency_graphs::in, list(int)::in(non_empty_list),
- list(pard_goal_detail)::out, int::in, int::out,
- list(pard_goal_detail)::in, list(pard_goal_detail)::out) is det.
-
-build_goals_before_greedy(Info, DependencyMaps, CostlyCallIndexes,
- GoalsBefore, !ConjNum, !Goals) :-
- build_goals_par_before_first_call(Info, DependencyMaps, CostlyCallIndexes,
- [], GoalsBeforeRev, [], GoalsParRev, !ConjNum, !Goals),
- reverse(GoalsBeforeRev, GoalsBefore),
- !:Goals = reverse(GoalsParRev) ++ !.Goals,
- !:ConjNum = !.ConjNum - length(GoalsParRev).
-
-:- pred build_goals_par_before_first_call(implicit_parallelism_info::in,
- dependency_graphs::in, list(int)::in(non_empty_list),
- list(pard_goal_detail)::in, list(pard_goal_detail)::out,
- list(pard_goal_detail)::in, list(pard_goal_detail)::out,
- int::in, int::out,
- list(pard_goal_detail)::in, list(pard_goal_detail)::out) is det.
+ % True if we should expand the search for parallelisation alternatives by
+ % creating a choice point.
+ %
+:- semipure pred should_expand_search(bnb_state(T)::in,
+ best_par_algorithm_simple::in) is semidet.
-build_goals_par_before_first_call(Info, DependencyMaps, CostlyCallIndexes,
- !GoalsBeforeRev, !GoalsParRev, !ConjNum, !Goals) :-
- Goals0 = !.Goals,
- (
- !.Goals = [Goal | !:Goals],
- CostlyCallIndexes = [FirstCostlyCallIndex | OtherCostlyCallIndexes],
+should_expand_search(BNBState, Algorithm) :-
+ Algorithm = bpas_complete(MaybeLimit),
(
- !.ConjNum >= FirstCostlyCallIndex
- ->
- % This goal is the first costly call. This group mustn't be
- % included in the goals before the parallel conjunction.
- % Put it back before we return.
- !:Goals = Goals0
- ;
- depends_lookup_tc(DependencyMaps, !.ConjNum, DepsTC),
- depends_lookup(DependencyMaps, !.ConjNum, Deps),
- (
- (
- % This goal provides a direct dependency to a costly call
- % other than the first costly call. It must be scheduled
- % before the parallel conjunction.
- some [Dep] (
- member(Dep, Deps),
- member(Dep, OtherCostlyCallIndexes)
- )
- ;
- % This goal provides a dependency to a costly call other
- % than the first and does not provide a dependency to the
- % first.
- some [Dep] (
- member(Dep, DepsTC),
- member(Dep, OtherCostlyCallIndexes)
- )
- % XXX: Comment this out. This means that we avoid some
- % dependencies at the cost of not generating some more
- % optimal solutions. What we actually want here is to
- % sequentialize this goal if it provides a transitive
- % dependency to a later call that the first costly call is
- % _not_ on the same dependecy path.
- %not (
- % member(FirstCostlyCallIndex, DepsTC)
- %)
- )
- ->
- % Schedule this goal and all of !.GoalsParRev before the
- % paralle conjunction.
- !:GoalsBeforeRev = [Goal | !.GoalsParRev ++ !.GoalsBeforeRev],
- !:GoalsParRev = []
+ MaybeLimit = yes(Limit),
+ semipure num_alternatives(BNBState, Open, Closed),
+ Open + Closed < Limit
;
- !:GoalsParRev = [Goal | !.GoalsParRev]
- ),
- !:ConjNum = !.ConjNum + 1,
- build_goals_par_before_first_call(Info, DependencyMaps,
- CostlyCallIndexes, !GoalsBeforeRev, !GoalsParRev, !ConjNum,
- !Goals)
- )
- ;
- !.Goals = []
+ MaybeLimit = no
).
-:- pred build_parallel_conjuncts_greedy(implicit_parallelism_info::in,
- dependency_graphs::in, list(int)::in, int::in, list(pard_goal_detail)::in,
- list(pard_goal_detail)::in, list(pard_goal_detail)::out, int::in, int::out,
- list(goal_group(goal_classification))::in,
- list(goal_group(goal_classification))::out,
+ % Test the parallelisation against the best one known to the branch and
+ % bound solver.
+ %
+:- semipure pred test_parallelisation(bnb_state(best_parallelisation)::in,
+ incomplete_parallelisation::in, incomplete_parallelisation::out) is semidet.
+
+test_parallelisation(BNBState, !Parallelisation) :-
+ calculate_parallel_cost(CostData, !Parallelisation),
+ Info = !.Parallelisation ^ ip_info,
+ test_dependance(Info, CostData),
+ % XXX: We shouldn't need to finalize the parallelisation before testing it.
+ % This is a limitation of the branch and bound module.
+ finalise_parallelisation(!.Parallelisation, TestParallelisation),
+ semipure test_incomplete_solution(BNBState, TestParallelisation).
+
+ % Score the parallelisation.
+ %
+:- pred score_parallelisation(bnb_state(best_parallelisation)::in,
+ maybe(float)::out,
incomplete_parallelisation::in, incomplete_parallelisation::out) is det.
-build_parallel_conjuncts_greedy(Info, DependencyMaps, CostlyCallIndexes,
- NumConjuncts0, InbetweenGoals0, !LastParConj, !GoalNum, !GoalGroups,
- !Parallelisation) :-
- (
- !.GoalGroups = [GoalGroup | !:GoalGroups],
- gg_get_details(GoalGroup, NumGoals, Goals, Classification),
-
- (
- Classification = gc_cheap_goals,
- % These cheap goals may be parallelised in between some other goals
- % once we find a costly goal.
- InbetweenGoals = InbetweenGoals0 ++ Goals,
- NumConjuncts = NumConjuncts0
- ;
- Classification = gc_costly_goals,
- % Find the best construction of the most recent two parallel
- % conjuncts.
- (
- !.LastParConj = [],
- % There is no last parallel conjunction, the current goals will
- % become the last one and the decision will be deffered.
- !:LastParConj = InbetweenGoals0 ++ Goals,
- InbetweenGoals = [],
- NumConjuncts = NumConjuncts0
- ;
- !.LastParConj = [_ | _],
- build_parallel_conjuncts_greedy_pair(Info,
- InbetweenGoals0, Goals, NumConjuncts0, !LastParConj,
- !Parallelisation),
- InbetweenGoals = [],
- NumConjuncts = NumConjuncts0 + 1
- )
- ),
- !:GoalNum = !.GoalNum + NumGoals,
- build_parallel_conjuncts_greedy(Info, DependencyMaps, CostlyCallIndexes,
- NumConjuncts, InbetweenGoals, !LastParConj, !GoalNum, !GoalGroups,
- !Parallelisation)
- ;
- !.GoalGroups = [],
- (
- InbetweenGoals0 = [_ | _],
- !:GoalGroups = [new_group(InbetweenGoals0, gc_cheap_goals)]
+score_parallelisation(BNBState, MaybeScore, !Parallelisation) :-
+ calculate_parallel_cost(CostData, !Parallelisation),
+ Info = !.Parallelisation ^ ip_info,
+ ( test_dependance(Info, CostData) ->
+ finalise_parallelisation(!.Parallelisation, TestParallelisation),
+ score_solution(BNBState, TestParallelisation, Score),
+ MaybeScore = yes(Score)
;
- InbetweenGoals0 = []
- )
+ MaybeScore = no
).
-:- pred build_parallel_conjuncts_greedy_pair(implicit_parallelism_info::in,
- list(pard_goal_detail)::in, list(pard_goal_detail)::in, int::in,
- list(pard_goal_detail)::in, list(pard_goal_detail)::out,
- incomplete_parallelisation::in, incomplete_parallelisation::out) is det.
+ % Test that the parallelisation only included dependant parallelism if
+ % permitted by the user.
+ %
+:- pred test_dependance(implicit_parallelism_info::in,
+ parallelisation_cost_data::in) is semidet.
-build_parallel_conjuncts_greedy_pair(Info, InbetweenGoals,
- Goals, ConjunctNum, !LastParConj, !Parallelisation) :-
+test_dependance(Info, CostData) :-
+ Overlap = CostData ^ pcd_par_exec_overlap,
ParalleliseDepConjs = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs,
- branch_and_bound(
- (semipure pred(_State::in, Parallelisation::out) is nondet :-
- append(GoalsA, GoalsB, InbetweenGoals),
-
- ParConjA = !.LastParConj ++ GoalsA,
- calculate_parallel_cost_step(Info, is_not_innermost_conjunct,
- ConjunctNum, ParConjA, !.Parallelisation, Parallelisation0),
- Overlap0 = Parallelisation0 ^ ip_par_exec_overlap,
- par_conj_overlap_is_dependent(Overlap0, IsDependent0),
+ par_conj_overlap_is_dependent(Overlap, IsDependent),
(
ParalleliseDepConjs = do_not_parallelise_dep_conjs
=>
- IsDependent0 = conjuncts_are_independent
- ),
+ IsDependent = conjuncts_are_independent
+ ).
- ParConjB = GoalsB ++ Goals,
- calculate_parallel_cost_step(Info, is_not_innermost_conjunct,
- ConjunctNum + 1, ParConjB, Parallelisation0, Parallelisation1),
- Overlap1 = Parallelisation1 ^ ip_par_exec_overlap,
- par_conj_overlap_is_dependent(Overlap1, IsDependent1),
- (
- ParalleliseDepConjs = do_not_parallelise_dep_conjs
- =>
- IsDependent1 = conjuncts_are_independent
- ),
+%----------------------------------------------------------------------------%
- finalise_parallelisation([], Parallelisation1, Parallelisation)
- ),
- parallelisation_get_objective_value, Parallelisations, _),
- (
- promise_equivalent_solutions [BestParallelisation]
- member(BestParallelisation, Parallelisations)
- ->
- ParConjsRev = reverse(BestParallelisation ^ bp_par_conjs),
- (
- ParConjsRev =
- [seq_conj(LastParConjPrime) | [seq_conj(SndLastParConj) | _]]
- ->
- % Commit to the second last parallel conjunction.
- calculate_parallel_cost_step(Info, is_not_innermost_conjunct,
- ConjunctNum, SndLastParConj, !Parallelisation),
+:- type incomplete_parallelisation
+ ---> incomplete_parallelisation(
+ ip_info :: implicit_parallelism_info,
- % Save the last parallel conjunction as part of the next one.
- !:LastParConj = LastParConjPrime
- ;
- error(this_file ++ "Expected at least 2 parallel conjuncts")
- )
- ;
- (
- ( ParalleliseDepConjs = parallelise_dep_conjs_overlap
- ; ParalleliseDepConjs = parallelise_dep_conjs_num_vars
- ; ParalleliseDepConjs = parallelise_dep_conjs_naive
- ),
- error(this_file ++ "Execpted at least one solution from bnb solver")
- ;
- ParalleliseDepConjs = do_not_parallelise_dep_conjs,
- % Try again to get the best dependent parallelisation. This is
- % used for guided parallelisation.
- TempInfo = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs :=
- parallelise_dep_conjs_overlap,
- build_parallel_conjuncts_greedy_pair(TempInfo, InbetweenGoals,
- Goals, ConjunctNum, !LastParConj, !Parallelisation)
- )
+ ip_goals :: array(pard_goal_detail),
+
+ % The index of the first goal in the parallelised goals,
+ % This is also the number of goals executed in sequence before
+ % the parallel conjunction.
+ ip_first_par_goal :: int,
+
+ % The index of the last goal in the parallel conjunction.
+ ip_last_par_goal :: int,
+
+ % The index of the last goal that has been (tentativly)
+ % scheduled. All goals between this +1 and ip_last_par_goal
+ % have not been scheduled.
+ ip_last_scheduled_goal :: int,
+
+ % The index of the last goal in each of the parallel conjuncts.
+ % the very last parallel conjunct is donated by
+ % ip_last_par_goal.
+ ip_par_conjs_rev_last_goal :: list(int),
+
+ % The number of calls into this conjunction.
+ ip_num_calls :: int,
+
+ % Dependency relationships between goals.
+ ip_dependency_graphs :: dependency_graphs,
+
+ % These are implied by the above fields but we maintain them
+ % here to provide a cache.
+ ip_maybe_goals_before_cost :: maybe(goal_cost_csq),
+ ip_maybe_goals_after_cost :: maybe(goal_cost_csq),
+
+ ip_maybe_par_cost_data :: maybe(parallelisation_cost_data)
).
-:- pred build_goals_after_greedy(implicit_parallelism_info::in,
- int::in, list(pard_goal_detail)::in,
- list(pard_goal_detail)::in, list(pard_goal_detail)::out,
- incomplete_parallelisation::in, incomplete_parallelisation::out) is det.
+:- type parallelisation_cost_data
+ ---> parallelisation_cost_data(
+ pcd_par_exec_overlap :: parallel_execution_overlap,
+ pcd_par_exec_metrics :: parallel_exec_metrics_incomplete,
+ pcd_productions_map :: map(var_rep, float)
+ ).
-build_goals_after_greedy(Info, ConjunctNum, !.LastParConj, !LastGoals,
- !Parallelisation) :-
- ParalleliseDepConjs = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs,
+:- func ip_get_goals_before(incomplete_parallelisation) =
+ list(pard_goal_detail).
- branch_and_bound(
- (semipure pred(_State::in, (Parallelisation - LastGoals)::out)
- is nondet :-
- append(GoalsPar, LastGoals, !.LastGoals),
- ParConjTest = !.LastParConj ++ GoalsPar,
- calculate_parallel_cost_step(Info, is_innermost_conjunct,
- ConjunctNum, ParConjTest, !.Parallelisation, Parallelisation0),
- Overlap0 = Parallelisation0 ^ ip_par_exec_overlap,
- par_conj_overlap_is_dependent(Overlap0, IsDependent0),
- (
- ParalleliseDepConjs = do_not_parallelise_dep_conjs
- =>
- IsDependent0 = conjuncts_are_independent
- ),
- finalise_parallelisation([], Parallelisation0, Parallelisation)
- ),
- (func(Parallelisation - _) =
- parallelisation_get_objective_value(Parallelisation)),
- Parallelisations, _),
+ip_get_goals_before(Parallelisation) = GoalsBefore :-
+ Goals = Parallelisation ^ ip_goals,
+ FirstParGoalIndex = Parallelisation ^ ip_first_par_goal,
+ fetch_items(Goals, 0, FirstParGoalIndex - 1, GoalsBefore).
+:- func ip_get_goals_after(incomplete_parallelisation) =
+ list(pard_goal_detail).
+
+ip_get_goals_after(Parallelisation) = GoalsAfter :-
+ Goals = Parallelisation ^ ip_goals,
+ LastParGoalIndex = Parallelisation ^ ip_last_par_goal,
+ NumGoals = size(Goals),
+ fetch_items(Goals, LastParGoalIndex + 1, NumGoals - 1, GoalsAfter).
+
+:- func ip_get_par_conjs(incomplete_parallelisation) =
+ list(seq_conj(pard_goal_detail)).
+
+ip_get_par_conjs(Incomplete) = ParConjs :-
+ Goals = Incomplete ^ ip_goals,
+ Start = Incomplete ^ ip_first_par_goal,
+ Last = Incomplete ^ ip_last_scheduled_goal,
+ LastGoalsRev0 = Incomplete ^ ip_par_conjs_rev_last_goal,
+ LastGoalsRev = [Last | LastGoalsRev0],
+ reverse(LastGoalsRev, LastGoals),
+ ip_get_par_conjs2(Goals, Start, LastGoals, ParConjs).
+
+:- pred ip_get_par_conjs2(array(pard_goal_detail)::in, int::in,
+ list(int)::in, list(seq_conj(pard_goal_detail))::out) is det.
+
+ip_get_par_conjs2(_, _, [], []).
+ip_get_par_conjs2(Array, First, [Last | Lasts], [Conj | Conjs]) :-
+ ip_get_par_conjs2(Array, Last + 1, Lasts, Conjs),
+ fetch_items(Array, First, Last, Goals),
+ Conj = seq_conj(Goals).
+
+:- func ip_get_num_goals(incomplete_parallelisation) = int.
+
+ip_get_num_goals(Incomplete) = size(Incomplete ^ ip_goals).
+
+:- func ip_get_num_parallel_conjuncts(incomplete_parallelisation) = int.
+
+ip_get_num_parallel_conjuncts(Incomplete) =
+ length(Incomplete ^ ip_par_conjs_rev_last_goal) + 1.
+
+:- func ip_get_num_goals_middle(incomplete_parallelisation) = int.
+
+ip_get_num_goals_middle(Incomplete) = LastParGoal - FirstParGoal + 1 :-
+ FirstParGoal = Incomplete ^ ip_first_par_goal,
+ LastParGoal = Incomplete ^ ip_last_par_goal.
+
+:- pred start_building_parallelisation(implicit_parallelism_info::in,
+ goals_for_parallelisation::in,
+ incomplete_parallelisation::out) is det.
+
+start_building_parallelisation(Info, PreprocessedGoals, Parallelisation) :-
+ GoalsArray = PreprocessedGoals ^ gfp_goals,
+ FirstParGoal = PreprocessedGoals ^ gfp_first_costly_goal,
+ LastParGoal = PreprocessedGoals ^ gfp_last_costly_goal,
+ NumCalls = PreprocessedGoals ^ gfp_num_calls,
+ DependencyGraphs = PreprocessedGoals ^ gfp_dependency_graphs,
+ Parallelisation = incomplete_parallelisation(Info, GoalsArray, FirstParGoal,
+ LastParGoal, FirstParGoal, [], NumCalls, DependencyGraphs, no, no, no).
+
+ % Finalise the parallelisation.
+ %
+:- pred finalise_parallelisation(incomplete_parallelisation::in,
+ best_parallelisation::out) is det.
+
+finalise_parallelisation(Incomplete, Best) :-
+ GoalsBefore = ip_get_goals_before(Incomplete),
+ GoalsAfter = ip_get_goals_after(Incomplete),
+
+ MaybeCostData = Incomplete ^ ip_maybe_par_cost_data,
(
- promise_equivalent_solutions [BestParallelisationPair]
- member(BestParallelisationPair, Parallelisations)
- ->
- BestParallelisationPair = BestParallelisation - !:LastGoals,
- ParConjsRev = reverse(BestParallelisation ^ bp_par_conjs),
- (
- ParConjsRev = [seq_conj(LastParConjPrime) | _]
- ->
- % Commit to the last parallel conjunction.
- calculate_parallel_cost_step(Info, is_innermost_conjunct,
- ConjunctNum, LastParConjPrime, !Parallelisation)
- ;
- error(this_file ++ "Expected at least 1 parallel conjunct")
- )
+ MaybeCostData = yes(CostData)
;
- (
- ( ParalleliseDepConjs = parallelise_dep_conjs_overlap
- ; ParalleliseDepConjs = parallelise_dep_conjs_num_vars
- ; ParalleliseDepConjs = parallelise_dep_conjs_naive
+ MaybeCostData = no,
+ error(this_file ++ "finalise_parallelisation: "
+ ++ "Parallelisation has no cost data")
),
- error(this_file ++ "Execpted at least one solution from bnb solver")
- ;
- ParalleliseDepConjs = do_not_parallelise_dep_conjs,
- % Try again to get the best dependent parallelisation. This is
- % used for guided parallelisation.
- TempInfo = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs :=
- parallelise_dep_conjs_overlap,
- build_goals_after_greedy(TempInfo, ConjunctNum, !.LastParConj,
- !LastGoals, !Parallelisation)
- )
- ).
+ CostData = parallelisation_cost_data(Overlap, Metrics0, _),
+
+ Metrics = finalise_parallel_exec_metrics(Metrics0),
+ par_conj_overlap_is_dependent(Overlap, IsDependent),
+ ParConjs = ip_get_par_conjs(Incomplete),
+ Best = bp_parallel_execution(GoalsBefore, ParConjs,
+ GoalsAfter, IsDependent, Metrics).
+
+:- pred add_one_goal_into_first_par_conj(incomplete_parallelisation::in,
+ incomplete_parallelisation::out) is det.
+
+add_one_goal_into_first_par_conj(!Parallelisation) :-
+ FirstGoal0 = !.Parallelisation ^ ip_first_par_goal,
+ FirstGoal = FirstGoal0 - 1,
+ !Parallelisation ^ ip_first_par_goal := FirstGoal,
+ !Parallelisation ^ ip_maybe_goals_before_cost := no,
+ !Parallelisation ^ ip_maybe_par_cost_data := no.
+
+:- pred add_one_goal_into_last_par_conj(incomplete_parallelisation::in,
+ incomplete_parallelisation::out) is det.
+
+add_one_goal_into_last_par_conj(!Parallelisation) :-
+ LastGoal0 = !.Parallelisation ^ ip_last_par_goal,
+ LastGoal = LastGoal0 + 1,
+ !Parallelisation ^ ip_last_par_goal := LastGoal,
+ !Parallelisation ^ ip_maybe_goals_after_cost := no,
+ !Parallelisation ^ ip_maybe_par_cost_data := no.
%----------------------------------------------------------------------------%
@@ -1795,66 +1757,120 @@ build_goals_after_greedy(Info, ConjunctN
% references for those variables that will become futures.
).
-:- type is_innermost_conjunct
- ---> is_innermost_conjunct
- ; is_not_innermost_conjunct.
-
- % calculate_parallel_cost(Info, Conjunctions, IsInnermostConjunct,
- % ParallelExecMetrics, ParallelExecOverlap, ProductionsMap, NumConjuncts).
+ % calculate_parallel_cost(Info, !Parallelisation).
%
% Analyse the parallel conjuncts and determine their likely performance.
- % This code performs one step of the computation the steps are linked
- % together by find_best_parallelisation.
%
% This is the new parallel execution overlap algorithm, it is general and
% therefore we also use is for independent conjunctions.
%
- % + CallerVars is the set of vars for which our caller wants us to build a
- % productions map for.
- %
- % + ParallelExecOpverlap: A representation of how the parallel conjuncts'
- % executions overlap.
- %
- % + ProductionsMap: A productions map that covers the production of
- % CallerVars.
- %
-:- pred calculate_parallel_cost_step(implicit_parallelism_info::in,
- is_innermost_conjunct::in, int::in, list(pard_goal_detail)::in,
+:- pred calculate_parallel_cost(parallelisation_cost_data::out,
incomplete_parallelisation::in, incomplete_parallelisation::out) is det.
-calculate_parallel_cost_step(Info, IsInnermostConjunct, NumConjuncts, Goals,
- !Parallelisation) :-
- Conjs0 = !.Parallelisation ^ ip_par_conjs,
- Conjs = Conjs0 ++ [seq_conj(Goals)],
- !Parallelisation ^ ip_par_conjs := Conjs,
- Algorithm = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs,
+calculate_parallel_cost(CostData, !Parallelisation) :-
+ ParConj = ip_get_par_conjs(!.Parallelisation),
+ NumCalls = !.Parallelisation ^ ip_num_calls,
+
+ maybe_calc_sequential_cost(
+ (func(P) = P ^ ip_maybe_goals_before_cost),
+ (func(P0, MaybeCost) = P0 ^ ip_maybe_goals_before_cost := MaybeCost),
+ ip_get_goals_before, CostBeforePercall, NumCalls, !Parallelisation),
+ maybe_calc_sequential_cost(
+ (func(P) = P ^ ip_maybe_goals_after_cost),
+ (func(P0, MaybeCost) = P0 ^ ip_maybe_goals_after_cost := MaybeCost),
+ ip_get_goals_after, CostAfterPercall, NumCalls, !Parallelisation),
+
+ Info = !.Parallelisation ^ ip_info,
+ Opts = Info ^ ipi_opts,
+ SparkCost = Opts ^ cpcp_sparking_cost,
+ SparkDelay = Opts ^ cpcp_sparking_delay,
+ ContextWakeupDelay = Opts ^ cpcp_context_wakeup_delay,
+ Metrics0 = init_empty_parallel_exec_metrics(CostBeforePercall,
+ CostAfterPercall, NumCalls, float(SparkCost), float(SparkDelay),
+ float(ContextWakeupDelay)),
+ Overlap0 = peo_empty_conjunct,
+
+ CostData0 = parallelisation_cost_data(Overlap0, Metrics0, init),
+ NumMiddleGoals = ip_get_num_goals_middle(!.Parallelisation),
+ foldl3(calculate_parallel_cost_step(Info, NumMiddleGoals), ParConj, 1, _,
+ 0, _, CostData0, CostData),
+ !Parallelisation ^ ip_maybe_par_cost_data := yes(CostData).
+
+:- pred maybe_calc_sequential_cost((func(T) = maybe(goal_cost_csq))::in,
+ (func(T, maybe(goal_cost_csq)) = T)::in,
+ (func(T) = list(pard_goal_detail))::in, float::out,
+ int::in, T::in, T::out) is det.
+
+maybe_calc_sequential_cost(GetMaybe, SetMaybe, GetGoals, CostPercall, Calls,
+ !Acc) :-
+ MaybeCost = GetMaybe(!.Acc),
+ (
+ MaybeCost = yes(Cost)
+ ;
+ MaybeCost = no,
+ Goals = GetGoals(!.Acc),
+ conj_calc_cost(Goals, Calls, Cost),
+ !:Acc = SetMaybe(!.Acc, yes(Cost))
+ ),
+ CostPercall = goal_cost_get_percall(Cost).
+
+:- type is_last_par_conjunct
+ ---> is_last_par_conjunct
+ ; not_last_par_conjunct.
+
+:- pred calculate_parallel_cost_step(implicit_parallelism_info::in,
+ int::in, seq_conj(pard_goal_detail)::in, int::in, int::out,
+ int::in, int::out,
+ parallelisation_cost_data::in, parallelisation_cost_data::out) is det.
+
+calculate_parallel_cost_step(Info, NumMiddleGoals, Conjunct, !ConjNum,
+ !NumGoals, !CostData) :-
+ !.CostData = parallelisation_cost_data(Overlap0, Metrics0, PM0),
+ !:NumGoals = !.NumGoals + length(Conjuncts),
+ ( !.NumGoals = NumMiddleGoals ->
+ IsLastConjunct = is_last_par_conjunct
+ ;
+ IsLastConjunct = not_last_par_conjunct
+ ),
+ Conjunct = seq_conj(Conjuncts),
+ calculate_parallel_cost_step(Info, IsLastConjunct, Conjuncts, !ConjNum,
+ PM0, PM, Overlap0, Overlap, Metrics0, Metrics),
+ !:CostData = parallelisation_cost_data(Overlap, Metrics, PM).
- ProductionsMap0 = !.Parallelisation ^ ip_productions_map,
+:- pred calculate_parallel_cost_step(implicit_parallelism_info::in,
+ is_last_par_conjunct::in, list(pard_goal_detail)::in, int::in, int::out,
+ map(var_rep, float)::in, map(var_rep, float)::out,
+ parallel_execution_overlap::in, parallel_execution_overlap::out,
+ parallel_exec_metrics_incomplete::in,
+ parallel_exec_metrics_incomplete::out) is det.
+
+calculate_parallel_cost_step(Info, IsLastConjunct, Conjunct, !ConjNum,
+ !ProductionsMap, !Overlap, !Metrics) :-
+ Algorithm = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs,
- conj_calc_cost(Goals, CostB0),
+ Calls = parallel_exec_metrics_get_num_calls(!.Metrics),
+ conj_calc_cost(Conjunct, Calls, CostB0),
CostB = goal_cost_get_percall(CostB0),
- foldl(pardgoal_consumed_vars_accum, Goals, set.init,
+ foldl(pardgoal_consumed_vars_accum, Conjunct, set.init,
RightConsumedVars),
ProducedVars =
- set.from_sorted_list(map.sorted_keys(ProductionsMap0)),
+ set.from_sorted_list(map.sorted_keys(!.ProductionsMap)),
Vars = set.intersect(ProducedVars, RightConsumedVars),
% This conjunct will actually start after it has been sparked by
% the prevous conjunct. Which in turn may have been sparked by an
% earlier conjunct.
SparkDelay = Info ^ ipi_opts ^ cpcp_sparking_delay,
- StartTime0 = float(NumConjuncts * SparkDelay),
+ StartTime0 = float((!.ConjNum - 1) * SparkDelay),
% If there are conjuncts after this conjunct we will have the
% additional cost of sparking them.
(
- IsInnermostConjunct = is_not_innermost_conjunct,
- % The cost of sparking a computation, (that is calling fork) is charged
- % to the leftmost conjunct.
+ IsLastConjunct = not_last_par_conjunct,
SparkCost = Info ^ ipi_opts ^ cpcp_sparking_cost,
StartTime = StartTime0 + float(SparkCost)
;
- IsInnermostConjunct = is_innermost_conjunct,
+ IsLastConjunct = is_last_par_conjunct,
StartTime = StartTime0
),
@@ -1863,12 +1879,12 @@ calculate_parallel_cost_step(Info, IsInn
% Get the list of variables consumed by this conjunct that will be
% turned into futures.
- foldl3(get_consumptions_list, Goals, Vars, _, 0.0, _,
+ foldl3(get_consumptions_list, Conjunct, Vars, _, 0.0, _,
[], ConsumptionsList0),
reverse(ConsumptionsList0, ConsumptionsList),
% Determine how the parallel conjuncts overlap.
- foldl5(calculate_dependent_parallel_cost_2(Info, ProductionsMap0),
+ foldl5(calculate_dependent_parallel_cost_2(Info, !.ProductionsMap),
ConsumptionsList, 0.0, LastSeqConsumeTime,
StartTime, LastParConsumeTime, StartTime, LastResumeTime,
[], RevExecution0, map.init, ConsumptionsMap),
@@ -1893,23 +1909,18 @@ calculate_parallel_cost_step(Info, IsInn
CostSignals = 0.0
),
- Metrics0 = !.Parallelisation ^ ip_par_exec_metrics,
- Metrics = init_parallel_exec_metrics_incomplete(Metrics0, CostSignals,
+ !:Metrics = init_parallel_exec_metrics_incomplete(!.Metrics, CostSignals,
CostB, CostBPar),
- !Parallelisation ^ ip_par_exec_metrics := Metrics,
- % Build the productions map for our parent. This map contains all
+ % Build the productions map for the next conjunct. This map contains all
% the variables produced by this code, not just that are used for
% dependent parallelisation.
- foldl3(get_productions_map, Goals, StartTime, _, Execution, _,
- ProductionsMap0, ProductionsMap),
- !Parallelisation ^ ip_productions_map := ProductionsMap,
+ foldl3(get_productions_map, Conjunct, StartTime, _, Execution, _,
+ !ProductionsMap),
DepConjExec = dependent_conjunct_execution(Execution,
- ProductionsMap, ConsumptionsMap),
- Overlap0 = !.Parallelisation ^ ip_par_exec_overlap,
- Overlap = peo_conjunction(Overlap0, DepConjExec, Vars),
- !Parallelisation ^ ip_par_exec_overlap := Overlap.
+ !.ProductionsMap, ConsumptionsMap),
+ !:Overlap = peo_conjunction(!.Overlap, DepConjExec, Vars).
% calculate_dependent_parallel_cost_2(Info, ProductionsMap,
% Var - SeqConsTime, !PrevSeqConsumeTime, !PrevParConsumeTime,
@@ -2102,6 +2113,10 @@ build_dependency_graph([PG | PGs], ConjN
% foldl(get_productions_map(Goals, 0,0, _, Vars, _, map.init, Map).
%
+ % If Goals is semidet this can produce incorrect values in the !Time
+ % accumulator that lead to exceptions. This is prevented by only
+ % attempting to parallelise goals that are det or cc_multi.
+ %
% Build a map of variable productions in Goals.
%
:- pred get_productions_map(pard_goal_detail::in, float::in, float::out,
@@ -2290,12 +2305,19 @@ pardgoal_consumed_vars_accum(Goal, !Vars
% Check if it is appropriate to parallelise this call. That is it must be
% model_det and have a cost above the call site cost threshold.
%
-:- pred can_parallelise_goal(implicit_parallelism_info::in,
- detism_rep::in, goal_cost_csq::in) is semidet.
+:- pred can_parallelise_goal(goal_rep(T)::in) is semidet.
-can_parallelise_goal(Info, Detism, Cost) :-
+can_parallelise_goal(Goal) :-
+ Detism = Goal ^ goal_detism_rep,
( Detism = det_rep
- ; Detism = cc_multidet_rep ),
+ ; Detism = cc_multidet_rep ).
+ % XXX We would check purity here except that purity information is not
+ % present in the bytecode.
+
+:- pred goal_cost_above_par_threshold(implicit_parallelism_info::in,
+ goal_cost_csq::in) is semidet.
+
+goal_cost_above_par_threshold(Info, Cost) :-
goal_cost_get_calls(Cost) > 0,
PercallCost = goal_cost_get_percall(Cost),
PercallCost > float(Info ^ ipi_opts ^ cpcp_call_site_threshold).
@@ -2323,15 +2345,14 @@ atomic_pard_goal_type(Info, GoalPath, At
).
:- pred atomic_pard_goal_cost(implicit_parallelism_info::in, goal_path::in,
- atomic_goal_rep::in, goal_cost_csq::out) is det.
+ coverage_info::in, atomic_goal_rep::in, goal_cost_csq::out) is det.
-atomic_pard_goal_cost(Info, GoalPath, AtomicGoal, Cost) :-
+atomic_pard_goal_cost(Info, GoalPath, Coverage, AtomicGoal, Cost) :-
atomic_goal_is_call(AtomicGoal, IsCall),
(
IsCall = atomic_goal_is_trivial,
- % XXX: Should include the number of calls here since the 0 makes this
- % code appear to be dead when it probably isn't.
- Cost = atomic_goal_cost
+ get_coverage_before_det(Coverage, Calls),
+ Cost = atomic_goal_cost(Calls)
;
IsCall = atomic_goal_is_call(_),
map.lookup(Info ^ ipi_call_sites, GoalPath, CallSite),
@@ -2644,13 +2665,13 @@ goal_to_pard_goal(Info, GoalPath, !Goal,
GoalExpr0 = conj_rep(Conjs0),
map_foldl2(conj_to_pard_goals(Info, GoalPath), Conjs0, Conjs, 1, _,
!Messages),
- conj_calc_cost(Conjs, Cost),
+ conj_calc_cost(Conjs, Before, Cost),
GoalExpr = conj_rep(Conjs)
;
GoalExpr0 = disj_rep(Disjs0),
map_foldl2(disj_to_pard_goals(Info, GoalPath), Disjs0, Disjs, 1, _,
!Messages),
- disj_calc_cost(Disjs, Cost),
+ disj_calc_cost(Disjs, Before, Cost),
GoalExpr = disj_rep(Disjs)
;
GoalExpr0 = switch_rep(Var, CanFail, Cases0),
@@ -2700,7 +2721,7 @@ goal_to_pard_goal(Info, GoalPath, !Goal,
GoalExpr = atomic_goal_rep(Context, Line, BoundVars, AtomicGoal),
atomic_pard_goal_type(Info, GoalPath, AtomicGoal, InstMapInfo,
PardGoalType, Messages),
- atomic_pard_goal_cost(Info, GoalPath, AtomicGoal, Cost),
+ atomic_pard_goal_cost(Info, GoalPath, Coverage, AtomicGoal, Cost),
foldl(atomic_goal_build_use_map(AtomicGoal, GoalPath, Info,
var_use_production),
@@ -2715,7 +2736,10 @@ goal_to_pard_goal(Info, GoalPath, !Goal,
% XXX: The goal annotations cannot represent reasons why a goal
% can't be parallelised, for example it could be nondet, semidet or
% impure.
- ( can_parallelise_goal(Info, Detism, Cost) ->
+ (
+ can_parallelise_goal(!.Goal),
+ goal_cost_above_par_threshold(Info, Cost)
+ ->
CostAboveThreshold = cost_above_par_threshold
;
CostAboveThreshold = cost_not_above_par_threshold
@@ -2757,41 +2781,46 @@ case_to_pard_goal(Info, GoalPath0, !Case
%----------------------------------------------------------------------------%
-:- pred conj_calc_cost(list(pard_goal_detail)::in, goal_cost_csq::out)
- is det.
+:- pred conj_calc_cost(list(pard_goal_detail)::in, int::in,
+ goal_cost_csq::out) is det.
-conj_calc_cost([], zero_goal_cost).
-conj_calc_cost([Conj | Conjs], Cost) :-
- conj_calc_cost(Conjs, ConjsCost),
+conj_calc_cost([], Calls, simple_goal_cost(Calls)).
+conj_calc_cost([Conj | Conjs], _, Cost) :-
+ Coverage = Conj ^ goal_annotation ^ pgd_coverage,
+ get_coverage_after_det(Coverage, After),
+ conj_calc_cost(Conjs, After, ConjsCost),
ConjCost = Conj ^ goal_annotation ^ pgd_cost,
- Cost = add_goal_costs(ConjsCost, ConjCost).
+ Cost = add_goal_costs_seq(ConjCost, ConjsCost).
-:- pred disj_calc_cost(list(pard_goal_detail)::in, goal_cost_csq::out)
- is det.
+:- pred disj_calc_cost(list(pard_goal_detail)::in, int::in,
+ goal_cost_csq::out) is det.
-disj_calc_cost([], zero_goal_cost).
-disj_calc_cost([Disj | Disjs], Cost) :-
+disj_calc_cost([], Calls, simple_goal_cost(Calls)).
+disj_calc_cost([Disj | Disjs], _, Cost) :-
Coverage = Disj ^ goal_annotation ^ pgd_coverage,
- get_coverage_before_det(Coverage, Before),
+ get_coverage_before_and_after_det(Coverage, Before, After),
( Before = 0 ->
% Avoid a divide by zero.
- Cost = zero_goal_cost
+ Cost = dead_goal_cost
;
- DisjCost = Disj ^ goal_annotation ^ pgd_cost,
- disj_calc_cost(Disjs, DisjsCost),
+ _Successes = After,
+ Failures = Before - After,
% XXX: We assume this is a semidet disjunction
- Branch = add_goal_costs_branch(Before, DisjsCost, zero_goal_cost),
- Cost = add_goal_costs(DisjCost, Branch)
+ disj_calc_cost(Disjs, Failures, FailureCost),
+ DisjCost = Disj ^ goal_annotation ^ pgd_cost,
+ SuccessCost = atomic_goal_cost(After),
+ BranchCost = add_goal_costs_branch(Before, FailureCost, SuccessCost),
+ Cost = add_goal_costs_seq(DisjCost, BranchCost)
).
:- pred switch_calc_cost(list(case_rep(pard_goal_detail_annotation))::in,
int::in, goal_cost_csq::out) is det.
-switch_calc_cost([], _, zero_goal_cost).
+switch_calc_cost([], Calls, simple_goal_cost(Calls)).
switch_calc_cost([Case | Cases], TotalCalls, Cost) :-
( TotalCalls = 0 ->
% Avoid a divide by zero.
- Cost = zero_goal_cost
+ Cost = dead_goal_cost
;
Coverage = Case ^ cr_case_goal ^ goal_annotation ^ pgd_coverage,
get_coverage_before_det(Coverage, CaseCalls),
@@ -2810,7 +2839,16 @@ ite_calc_cost(Cond, Then, Else, Cost) :-
Coverage = Cond ^ goal_annotation ^ pgd_coverage,
get_coverage_before_det(Coverage, Before),
ThenElseCost = add_goal_costs_branch(Before, ThenCost, ElseCost),
- Cost = add_goal_costs(CondCost, ThenElseCost).
+ Cost = add_goal_costs_seq(CondCost, ThenElseCost).
+
+:- func simple_goal_cost(int) = goal_cost_csq.
+
+simple_goal_cost(Calls) = Cost :-
+ ( Calls = 0 ->
+ Cost = dead_goal_cost
+ ;
+ Cost = atomic_goal_cost(Calls)
+ ).
%----------------------------------------------------------------------------%
%
Index: deep_profiler/mdprof_feedback.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/mdprof_feedback.m,v
retrieving revision 1.30
diff -u -p -b -r1.30 mdprof_feedback.m
--- deep_profiler/mdprof_feedback.m 16 Oct 2010 04:11:04 -0000 1.30
+++ deep_profiler/mdprof_feedback.m 13 Dec 2010 04:29:59 -0000
@@ -299,14 +299,18 @@ help_message =
--implicit-parallelism-best-parallelisation-algorithm <option>
Select which algorithm to use to find the best way to
parallelise a conjunction. The options are:
- complete-bnb(N): A complete algorithm with a branch and
- bound search, this can be rather slow since it has an
- exponential time complexity. This option allows a single
- parameter, N, Any conjunction with more than N conjuncts
- will be solved using the greedy algorithm instead. If N
- is zero this check is disabled.
greedy: A greedy algorithm with a linear time complexity.
- The default is complete-bnb(10).
+ complete: A complete algorithm with a branch and bound
+ search, this can be slow for problems larger then 50
+ conjuncts, it has an exponential xomplexity.
+ complete-size(N): As above exept that it takes a single
+ parameter, N. A conjunction has more than N conjuncts
+ then the greedy algorithm will be used.
+ complete-branches(N): The same as the complete algorithm,
+ except that it allows at most N branches to be created
+ during the search. Once N branches have been created a
+ greedy search is used on each open branch.
+ The default is complete-branches(1000).
The following options select specific types of feedback information
and parameterise them:
@@ -483,7 +487,7 @@ defaults(implicit_parallelism_dependant_
defaults(implicit_parallelism_dependant_conjunctions_algorithm,
string("overlap")).
defaults(implicit_parallelism_best_parallelisation_algorithm,
- string("complete-bnb(10)")).
+ string("complete-branches(1000)")).
:- pred construct_measure(string::in, stat_measure::out) is semidet.
@@ -671,10 +675,20 @@ best_par_algorithm_parser(Src, Algorithm
->
Algorithm = bpa_greedy
;
- keyword(idchars, "complete-bnb", Src, _, !PS),
+ keyword(idchars, "complete-branches", Src, _, !PS),
brackets("(", ")", int_literal, Src, N, !PS),
- N >= 0,
- Algorithm = bpa_complete_bnb(N)
+ N >= 0
+ ->
+ Algorithm = bpa_complete_branches(N)
+ ;
+ keyword(idchars, "complete-size", Src, _, !PS),
+ brackets("(", ")", int_literal, Src, N, !PS),
+ N >= 0
+ ->
+ Algorithm = bpa_complete_size(N)
+ ;
+ keyword(idchars, "complete", Src, _, !PS),
+ Algorithm = bpa_complete
),
eof(Src, _, !PS).
@@ -685,8 +699,11 @@ idchars = "abcdefghijklmnopqrstuvwxyzABC
:- pred best_par_algorithm_string(best_par_algorithm::in, string::out) is det.
best_par_algorithm_string(bpa_greedy, "greedy").
-best_par_algorithm_string(bpa_complete_bnb(N),
- format("complete_bnb(%d)", [i(N)])).
+best_par_algorithm_string(bpa_complete_branches(N),
+ format("complete-branches(%d)", [i(N)])).
+best_par_algorithm_string(bpa_complete_size(N),
+ format("complete-size(%d)", [i(N)])).
+best_par_algorithm_string(bpa_complete, "complete").
:- pred parse_parallelise_dep_conjs_string(bool::in, string::in,
parallelise_dep_conjs::out) is semidet.
Index: deep_profiler/measurements.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/measurements.m,v
retrieving revision 1.23
diff -u -p -b -r1.23 measurements.m
--- deep_profiler/measurements.m 14 Oct 2010 04:02:22 -0000 1.23
+++ deep_profiler/measurements.m 13 Dec 2010 04:29:59 -0000
@@ -149,9 +149,17 @@
%
:- type goal_cost_csq.
-:- func atomic_goal_cost = goal_cost_csq.
+ % atomic_goal_cost(Calls) = Cost.
+ %
+ % Cost is the cost of an atomic goal called Calls times.
+ %
+:- func atomic_goal_cost(int) = goal_cost_csq.
-:- func zero_goal_cost = goal_cost_csq.
+ % dead_goal_cost = Cost.
+ %
+ % Cost is the cost of a goal that is never called.
+ %
+:- func dead_goal_cost = goal_cost_csq.
% call_goal_cost(NumCalls, PerCallCost) = Cost
%
@@ -159,7 +167,14 @@
:- func call_goal_cost(cs_cost_csq) = goal_cost_csq.
-:- func add_goal_costs(goal_cost_csq, goal_cost_csq) = goal_cost_csq.
+ % add_goal_costs_seq(Earlier, Later) = Cost.
+ %
+ % Add goal costs that form a sequence with Earlier being the cost of goals
+ % earlier in the sequence and Later being the cost of goals later in the
+ % sequence. This operation is associative provided that the above
+ % condition is met.
+ %
+:- func add_goal_costs_seq(goal_cost_csq, goal_cost_csq) = goal_cost_csq.
% add_goal_costs_branch(TotalCalls, BranchA, BranchB) = Cost.
%
@@ -259,28 +274,30 @@
:- func init_parallel_exec_metrics_incomplete(parallel_exec_metrics_incomplete,
float, float, float) = parallel_exec_metrics_incomplete.
- % StartMetrics = init_empty_parallel_exec_metrics(CostBefore, NumCalls,
- % SparkCost, SparkDelay, ContextWakeupDelay).
+ % StartMetrics = init_empty_parallel_exec_metrics(CostBefore, CostAfter,
+ % NumCalls, SparkCost, SparkDelay, ContextWakeupDelay).
%
% Use this function to start with an empty set of metrics for an empty
% conjunction. Then use init_parallel_exec_metrics_incomplete to continue
% adding conjuncts on the right.
%
-:- func init_empty_parallel_exec_metrics(float, int, float, float, float) =
- parallel_exec_metrics_incomplete.
+:- func init_empty_parallel_exec_metrics(float, float, int, float, float,
+ float) = parallel_exec_metrics_incomplete.
- % Metrics = finalise_parallel_exec_metrics(IncompleteMetrics,
- % CostAfterConj).
+ % Metrics = finalise_parallel_exec_metrics(IncompleteMetrics).
%
% Make the metrics structure complete.
%
- % RightConjDelay is the delay before the conjunct to the right of & will
- % begin executing. & is considered to be right-associative since that's
- % how sparks are sparked.
- %
-:- func finalise_parallel_exec_metrics(parallel_exec_metrics_incomplete, float)
+:- func finalise_parallel_exec_metrics(parallel_exec_metrics_incomplete)
= parallel_exec_metrics.
+ % Calls = parallel_exec_metrics_get_num_calls(IncompleteMetrics).
+ %
+ % Get the number of calls.
+ %
+:- func parallel_exec_metrics_get_num_calls(parallel_exec_metrics_incomplete)
+ = int.
+
%-----------------------------------------------------------------------------%
:- pred weighted_average(list(float)::in, list(float)::in, float::out) is det.
@@ -703,15 +720,18 @@ cs_cost_per_proc_call(cs_cost_csq(CSCall
%----------------------------------------------------------------------------%
:- type goal_cost_csq
- ---> trivial_goal
- ; non_trivial_goal(
- tg_avg_cost :: cost,
+ ---> dead_goal
+ ; trivial_goal(
tg_calls :: int
+ )
+ ; non_trivial_goal(
+ ntg_avg_cost :: cost,
+ ntg_calls :: int
).
-atomic_goal_cost = trivial_goal.
+atomic_goal_cost(Calls) = trivial_goal(Calls).
-zero_goal_cost = trivial_goal.
+dead_goal_cost = dead_goal.
call_goal_cost(Calls, PercallCost) = non_trivial_goal(Cost, Calls) :-
Cost = cost_per_call(PercallCost).
@@ -720,46 +740,91 @@ call_goal_cost(CSCost) = non_trivial_goa
Calls = round_to_int(cs_cost_get_calls(CSCost)),
Cost = CSCost ^ cscc_csq_cost.
-add_goal_costs(trivial_goal, trivial_goal) =
- trivial_goal.
-add_goal_costs(trivial_goal, R at non_trivial_goal(_, _)) = R.
-add_goal_costs(R at non_trivial_goal(_, _), trivial_goal) = R.
-add_goal_costs(non_trivial_goal(CostA, CallsA), non_trivial_goal(CostB, CallsB))
+add_goal_costs_seq(dead_goal, dead_goal) = dead_goal.
+add_goal_costs_seq(dead_goal, R at trivial_goal(_)) = R.
+add_goal_costs_seq(dead_goal, R at non_trivial_goal(_, _)) = R.
+add_goal_costs_seq(R at trivial_goal(_), dead_goal) = R.
+add_goal_costs_seq(trivial_goal(CallsA), trivial_goal(_CallsB)) =
+ trivial_goal(CallsA).
+add_goal_costs_seq(trivial_goal(Calls), non_trivial_goal(CostB, CallsB)) =
+ non_trivial_goal(Cost, Calls) :-
+ CostTotal = cost_get_total(float(CallsB), CostB),
+ Cost = cost_total(CostTotal).
+add_goal_costs_seq(R at non_trivial_goal(_, _), dead_goal) = R.
+add_goal_costs_seq(R at non_trivial_goal(_, _), trivial_goal(_)) = R.
+add_goal_costs_seq(non_trivial_goal(CostA, CallsA),
+ non_trivial_goal(CostB, CallsB))
= non_trivial_goal(Cost, Calls) :-
- Calls = max(CallsA, CallsB),
- Cost = cost_total(cost_get_total(float(CallsA), CostA) +
- cost_get_total(float(CallsB), CostB)).
+ Calls = CallsA,
+ CostTotal = cost_get_total(float(CallsA), CostA) +
+ cost_get_total(float(CallsB), CostB),
+ Cost = cost_total(CostTotal),
+ (
+ Calls = 0,
+ CostTotal \= 0.0
+ ->
+ error(this_file ++ "add_goal_costs_seq/2: Calls = 0, Cost \\= 0")
+ ;
+ true
+ ).
add_goal_costs_branch(TotalCalls, A, B) = R :-
( TotalCalls = 0 ->
- R = zero_goal_cost
+ R = dead_goal
;
(
- A = trivial_goal,
+ A = dead_goal,
+ CallsA = 0,
(
- B = trivial_goal,
- R = trivial_goal
+ B = dead_goal,
+ error("TotalCalls \\= 0 for a dead goal")
;
- B = non_trivial_goal(Cost, _),
+ B = trivial_goal(CallsB),
+ R = trivial_goal(TotalCalls)
+ ;
+ B = non_trivial_goal(Cost, CallsB),
+ R = non_trivial_goal(Cost, TotalCalls)
+ )
+ ;
+ A = trivial_goal(CallsA),
+ (
+ B = dead_goal,
+ CallsB = 0,
+ R = trivial_goal(TotalCalls)
+ ;
+ B = trivial_goal(CallsB),
+ R = trivial_goal(TotalCalls)
+ ;
+ B = non_trivial_goal(Cost, CallsB),
R = non_trivial_goal(Cost, TotalCalls)
)
;
A = non_trivial_goal(CostA, CallsA),
(
- B = trivial_goal,
+ B = dead_goal,
+ CallsB = 0,
+ R = non_trivial_goal(CostA, TotalCalls)
+ ;
+ B = trivial_goal(CallsB),
R = non_trivial_goal(CostA, TotalCalls)
;
B = non_trivial_goal(CostB, CallsB),
Cost = sum_costs(float(CallsA), CostA, float(CallsB), CostB),
- Calls = CallsA + CallsB,
- require(unify(Calls, TotalCalls),
- this_file ++ "TotalCalls \\= CallsA + CallsB"),
- R = non_trivial_goal(Cost, Calls)
- )
+ R = non_trivial_goal(Cost, CallsA + CallsB)
)
+ ),
+ check_total_calls(CallsA, CallsB, TotalCalls)
).
-goal_cost_get_percall(trivial_goal) = 0.0.
+:- pred check_total_calls(int::in, int::in, int::in) is det.
+
+check_total_calls(CallsA, CallsB, TotalCalls) :-
+ Calls = CallsA + CallsB,
+ require(unify(Calls, TotalCalls),
+ this_file ++ "TotalCalls \\= CallsA + CallsB").
+
+goal_cost_get_percall(dead_goal) = 0.0.
+goal_cost_get_percall(trivial_goal(_)) = 0.0.
goal_cost_get_percall(non_trivial_goal(Cost, Calls)) =
( Calls = 0 ->
0.0
@@ -767,7 +832,8 @@ goal_cost_get_percall(non_trivial_goal(C
cost_get_percall(float(Calls), Cost)
).
-goal_cost_get_calls(trivial_goal) = 0.
+goal_cost_get_calls(dead_goal) = 0.
+goal_cost_get_calls(trivial_goal(Calls)) = Calls.
goal_cost_get_calls(non_trivial_goal(_, Calls)) = Calls.
%----------------------------------------------------------------------------%
@@ -902,6 +968,7 @@ exceeded_desired_parallelism(DesiredPara
:- type parallel_exec_metrics_incomplete
---> pem_incomplete(
pemi_time_before_conj :: float,
+ pemi_time_after_conj :: float,
pemi_num_calls :: int,
@@ -960,14 +1027,14 @@ init_parallel_exec_metrics_incomplete(Me
),
Metrics = Metrics0 ^ pemi_internal := yes(Internal).
-init_empty_parallel_exec_metrics(TimeBefore, NumCalls, SparkCost,
+init_empty_parallel_exec_metrics(TimeBefore, TimeAfter, NumCalls, SparkCost,
SparkDelay, ContextWakeupDelay) =
- pem_incomplete(TimeBefore, NumCalls, SparkCost, SparkDelay,
+ pem_incomplete(TimeBefore, TimeAfter, NumCalls, SparkCost, SparkDelay,
ContextWakeupDelay, no).
-finalise_parallel_exec_metrics(IncompleteMetrics, TimeAfter) = Metrics :-
- IncompleteMetrics = pem_incomplete(TimeBefore, NumCalls, SparkCost,
- SparkDelay, ContextWakeupDelay, MaybeInternal),
+finalise_parallel_exec_metrics(IncompleteMetrics) = Metrics :-
+ IncompleteMetrics = pem_incomplete(TimeBefore, TimeAfter, NumCalls,
+ SparkCost, SparkDelay, ContextWakeupDelay, MaybeInternal),
(
MaybeInternal = yes(Internal)
;
@@ -1004,6 +1071,9 @@ finalise_parallel_exec_metrics(Incomplet
Metrics = parallel_exec_metrics(NumCalls, SeqTime, ParTime, ParOverheads,
FirstConjDeadTime, FutureDeadTime).
+parallel_exec_metrics_get_num_calls(Pem) =
+ Pem ^ pemi_num_calls.
+
% The expected parallel execution time.
%
:- func parallel_exec_metrics_internal_get_par_time(
@@ -1088,7 +1158,7 @@ weighted_average(Weights, Values, Averag
:- func this_file = string.
-this_file = "measurements.m".
+this_file = "measurements.m: ".
%----------------------------------------------------------------------------%
:- end_module measurements.
Index: deep_profiler/message.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/message.m,v
retrieving revision 1.9
diff -u -p -b -r1.9 message.m
--- deep_profiler/message.m 14 Oct 2010 04:02:22 -0000 1.9
+++ deep_profiler/message.m 13 Dec 2010 04:29:59 -0000
@@ -122,6 +122,11 @@
%
; notice_partition_does_not_have_costly_calls(int, int)
+ % The candidate conjunction has goals that arn't
+ % determinstic or cc_multi amongst the costly calls.
+ %
+ ; notice_candidate_conjunction_not_det(detism_rep)
+
% Couldn't find the proc defn in the progrep data, maybe the
% procedure is built-in.
%
@@ -276,6 +281,8 @@ message_type_to_level(notice_callpair_ha
message_notice.
message_type_to_level(notice_partition_does_not_have_costly_calls(_, _)) =
message_notice.
+message_type_to_level(notice_candidate_conjunction_not_det(_)) =
+ message_notice.
message_type_to_level(warning_cannot_lookup_proc_defn) = message_warning.
message_type_to_level(warning_cannot_compute_procrep_coverage_fallback(_)) =
message_warning.
@@ -327,6 +334,11 @@ message_type_to_string(MessageType) = Co
++ " parallelised",
[i(PartNum), i(NumCalls)], String)
;
+ MessageType = notice_candidate_conjunction_not_det(Detism),
+ string.format("There are %d goals amoungst goals above the "
+ ++ "parallelisation overhead.",
+ [s(string(Detism))], String)
+ ;
MessageType = warning_cannot_lookup_proc_defn,
String = "Could not look up proc defn, perhaps this procedure is"
++ " built-in"
Index: library/array.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/array.m,v
retrieving revision 1.178
diff -u -p -b -r1.178 array.m
--- library/array.m 18 Nov 2010 04:12:11 -0000 1.178
+++ library/array.m 13 Dec 2010 04:29:59 -0000
@@ -1562,7 +1562,20 @@ array.to_list(Array, List) :-
%-----------------------------------------------------------------------------%
array.fetch_items(Array, Low, High, List) :-
- List = do_foldr_func(func(X, Xs) = [X | Xs], Array, [], Low, High).
+ ( High < Low ->
+ % If High is less than Low then there cannot be any array indexes
+ % within the range Low -> High (inclusive). This can happen when
+ % calling to_list/2 on the empty array. Testing for this condition
+ % here rather than in to_list/2 is more general.
+ List = []
+ ;
+ array.in_bounds(Array, Low),
+ array.in_bounds(Array, High)
+ ->
+ List = do_foldr_func(func(X, Xs) = [X | Xs], Array, [], Low, High)
+ ;
+ error("array.fetch_items/4: One or more index is out of bounds")
+ ).
%-----------------------------------------------------------------------------%
Index: mdbcomp/feedback.automatic_parallelism.m
===================================================================
RCS file: /home/mercury1/repository/mercury/mdbcomp/feedback.automatic_parallelism.m,v
retrieving revision 1.5
diff -u -p -b -r1.5 feedback.automatic_parallelism.m
--- mdbcomp/feedback.automatic_parallelism.m 16 Oct 2010 04:11:05 -0000 1.5
+++ mdbcomp/feedback.automatic_parallelism.m 13 Dec 2010 04:29:59 -0000
@@ -104,13 +104,22 @@
% algorithm use use to search through the clique graph.
%
:- type best_par_algorithm
- ---> bpa_complete_bnb(
- % If nonzero, a conjunction with more than this many conjuncts
- % will be solved with the greedy algorithm instead of a
- % complete but exponential algorithm. The recommended value
- % is 10.
+ ---> bpa_complete_branches(
+ % Use the complete algorithm until this many branches have been
+ % created during the search. Once this many evaluations have
+ % occurred the greedy algorithm is used; that is to say that
+ % once this fallsback, all existing alternatives will be
+ % explored but no new ones will be generated.
int
)
+ ; bpa_complete_size(
+ % Use the complete algorithm for conjunctions with fewer than
+ % this many conjuncts, or a greedy algorithm. The recommended
+ % value is 50.
+ int
+ )
+ ; bpa_complete
+ % The complete (bnb) algorithm with no fallback.
; bpa_greedy.
% Always use a greedy and linear algorithm.
Index: mdbcomp/program_representation.m
===================================================================
RCS file: /home/mercury1/repository/mercury/mdbcomp/program_representation.m,v
retrieving revision 1.53
diff -u -p -b -r1.53 program_representation.m
--- mdbcomp/program_representation.m 11 Oct 2010 00:49:27 -0000 1.53
+++ mdbcomp/program_representation.m 13 Dec 2010 04:29:59 -0000
@@ -356,10 +356,22 @@
---> can_fail_rep
; cannot_fail_rep.
+:- type committed_choice
+ ---> committed_choice
+ ; not_committed_cnoice.
+
:- func detism_get_solutions(detism_rep) = solution_count_rep.
:- func detism_get_can_fail(detism_rep) = can_fail_rep.
+:- pred detism_components(detism_rep, solution_count_rep, can_fail_rep).
+:- mode detism_components(in, out, out) is det.
+:- mode detism_components(out, in, in) is multi.
+
+:- pred detism_committed_choice(detism_rep, committed_choice).
+:- mode detism_committed_choice(in, out) is det.
+:- mode detism_committed_choice(out, in) is multi.
+
% A table of var_rep to string mappings.
%
% This table may not contain all the variables in the procedure. Variables
@@ -1109,23 +1121,29 @@ project_case_rep_goal(Case) = Case ^ cr_
%-----------------------------------------------------------------------------%
-detism_get_solutions(det_rep) = at_most_one_rep.
-detism_get_solutions(semidet_rep) = at_most_one_rep.
-detism_get_solutions(multidet_rep) = at_most_many_rep.
-detism_get_solutions(nondet_rep) = at_most_many_rep.
-detism_get_solutions(cc_multidet_rep) = at_most_one_rep.
-detism_get_solutions(cc_nondet_rep) = at_most_one_rep.
-detism_get_solutions(erroneous_rep) = at_most_zero_rep.
-detism_get_solutions(failure_rep) = at_most_zero_rep.
-
-detism_get_can_fail(det_rep) = cannot_fail_rep.
-detism_get_can_fail(semidet_rep) = can_fail_rep.
-detism_get_can_fail(multidet_rep) = cannot_fail_rep.
-detism_get_can_fail(nondet_rep) = can_fail_rep.
-detism_get_can_fail(cc_multidet_rep) = cannot_fail_rep.
-detism_get_can_fail(cc_nondet_rep) = can_fail_rep.
-detism_get_can_fail(erroneous_rep) = cannot_fail_rep.
-detism_get_can_fail(failure_rep) = can_fail_rep.
+detism_get_solutions(Detism) = Solutions :-
+ detism_components(Detism, Solutions, _).
+
+detism_get_can_fail(Detism) = CanFail :-
+ detism_components(Detism, _, CanFail).
+
+detism_components(det_rep, at_most_one_rep, cannot_fail_rep).
+detism_components(semidet_rep, at_most_one_rep, can_fail_rep).
+detism_components(multidet_rep, at_most_many_rep, cannot_fail_rep).
+detism_components(nondet_rep, at_most_many_rep, can_fail_rep).
+detism_components(cc_multidet_rep, at_most_one_rep, cannot_fail_rep).
+detism_components(cc_nondet_rep, at_most_one_rep, can_fail_rep).
+detism_components(erroneous_rep, at_most_zero_rep, cannot_fail_rep).
+detism_components(failure_rep, at_most_zero_rep, can_fail_rep).
+
+detism_committed_choice(det_rep, not_committed_cnoice).
+detism_committed_choice(semidet_rep, not_committed_cnoice).
+detism_committed_choice(multidet_rep, not_committed_cnoice).
+detism_committed_choice(nondet_rep, not_committed_cnoice).
+detism_committed_choice(cc_multidet_rep, committed_choice).
+detism_committed_choice(cc_nondet_rep, committed_choice).
+detism_committed_choice(erroneous_rep, not_committed_cnoice).
+detism_committed_choice(failure_rep, not_committed_cnoice).
%-----------------------------------------------------------------------------%
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20101213/668b6807/attachment.sig>
More information about the reviews
mailing list