[m-rev.] diff: Start working on the 'goal push' feedback.
Paul Bone
pbone at csse.unimelb.edu.au
Tue Dec 21 23:02:56 AEDT 2010
Zoltan and I worked on most of this together, in a sense it has already been
reviewed.
---
Start working on the 'goal push' feedback.
This feedback information is part of automatic parallelisation feedback. It
describes cases where goals after a branch goal but in the same conjunction
should be pushed into the branches of the branching goal. This can allow the
pushed goal to be parallelised against goals that already exist in one or more
arms of the branch goal without parallelising the whole branch goal.
This change simply creates the data-structures within the feedback framework on
which this feature will be based.
nmdbcomp/feedback.automatic_parallelism.m:
Introduce new push_goal structure that describes the transformation.
mdbcomp/feedback.m:
Incremented feedback format version number.
deep_profiler/mdprof_fb.automatic_parallelism.m:
compiler/implicit_parallelism.m:
Conform to changes in feedback.automatic_parallelism.m.
The code to generate or use this feedback has not been implemented, that
will come later.
Index: compiler/implicit_parallelism.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/implicit_parallelism.m,v
retrieving revision 1.25
diff -u -p -b -r1.25 implicit_parallelism.m
--- compiler/implicit_parallelism.m 20 Dec 2010 07:47:32 -0000 1.25
+++ compiler/implicit_parallelism.m 21 Dec 2010 11:20:25 -0000
@@ -277,7 +277,9 @@ maybe_parallelise_proc(ModuleInfo, Paral
HasParallelConj = no,
proc_info_get_goal(ProcInfo0, Goal0),
- CPCProc = candidate_par_conjunctions_proc(VarTable, CPCs0),
+ CPCProc = candidate_par_conjunctions_proc(VarTable, _PushGoals,
+ CPCs0),
+ % XXX Obey _PushGoals
Context = goal_info_get_context(Goal0 ^ hlds_goal_info),
term.context_file(Context, FileName),
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.23
diff -u -p -b -r1.23 mdprof_fb.automatic_parallelism.m
--- deep_profiler/mdprof_fb.automatic_parallelism.m 20 Dec 2010 07:47:46 -0000 1.23
+++ deep_profiler/mdprof_fb.automatic_parallelism.m 21 Dec 2010 11:42:10 -0000
@@ -557,10 +557,11 @@ candidate_parallel_conjunctions_clique_p
candidate_par_conjunctions_proc(T)::out) is det.
merge_candidate_par_conjs_proc(A, B, Result) :-
- A = candidate_par_conjunctions_proc(VarTableA, CPCsA),
- B = candidate_par_conjunctions_proc(VarTableB, CPCsB),
- Result = candidate_par_conjunctions_proc(VarTableA, CPCs),
+ A = candidate_par_conjunctions_proc(VarTableA, PushGoalsA, CPCsA),
+ B = candidate_par_conjunctions_proc(VarTableB, PushGoalsB, CPCsB),
+ Result = candidate_par_conjunctions_proc(VarTableA, PushGoals, CPCs),
CPCs = CPCsA ++ CPCsB,
+ PushGoals = PushGoalsA ++ PushGoalsB,
( VarTableA = VarTableB ->
true
;
@@ -671,8 +672,10 @@ candidate_parallel_conjunctions_proc(Opt
candidate_par_conjunctions::in, candidate_par_conjunctions::out) is det.
build_candidate_par_conjunction_maps(ProcLabel, VarTable, Candidate, !Map) :-
+ % XXX: This predicate will also need to add pushes to CandiateProc.
( map.search(!.Map, ProcLabel, CandidateProc0) ->
- CandidateProc0 = candidate_par_conjunctions_proc(VarTablePrime, CPCs0),
+ CandidateProc0 = candidate_par_conjunctions_proc(VarTablePrime,
+ PushGoals, CPCs0),
CPCs = [ Candidate | CPCs0 ],
( VarTable = VarTablePrime ->
true
@@ -680,9 +683,11 @@ build_candidate_par_conjunction_maps(Pro
unexpected($module, $pred, "var tables do not match")
)
;
- CPCs = [ Candidate ]
+ CPCs = [ Candidate ],
+ PushGoals = []
),
- CandidateProc = candidate_par_conjunctions_proc(VarTable, CPCs),
+ CandidateProc = candidate_par_conjunctions_proc(VarTable, PushGoals,
+ CPCs),
svmap.set(ProcLabel, CandidateProc, !Map).
:- pred goal_get_conjunctions_worth_parallelising(
@@ -693,6 +698,9 @@ build_candidate_par_conjunction_maps(Pro
goal_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
!Goal, Candidates, Messages) :-
+ % XXX: This predicate should return a list of costly goals within compund
+ % goals that next to which it might be desirable to push later goals to
+ % allow parallelisation within a branch of a compound goal.
GoalExpr0 = !.Goal ^ goal_expr_rep,
Coverage = !.Goal ^ goal_annotation ^ pgd_coverage,
get_coverage_before_det(Coverage, Calls),
@@ -3237,10 +3245,18 @@ css_to_call(Deep, CSS, Call) :-
create_candidate_parallel_conj_proc_report(Proc - CandidateParConjunctionProc,
Report) :-
CandidateParConjunctionProc =
- candidate_par_conjunctions_proc(VarTable, CandidateParConjunctions),
+ candidate_par_conjunctions_proc(VarTable, PushGoals,
+ CandidateParConjunctions),
+ map(create_push_goal_report, PushGoals, PushGoalReports),
map(create_candidate_parallel_conj_report(VarTable, Proc),
- CandidateParConjunctions, Reports),
- Report = cord_list_to_cord(Reports).
+ CandidateParConjunctions, CandidateParConjunctionReports),
+ Report = cord_list_to_cord(PushGoalReports) ++
+ cord_list_to_cord(CandidateParConjunctionReports).
+
+:- pred create_push_goal_report(push_goal::in, cord(string)::out) is det.
+
+create_push_goal_report(_, _) :-
+ sorry($module, $pred).
:- pred create_candidate_parallel_conj_report(var_table::in,
string_proc_label::in, candidate_par_conjunction(pard_goal)::in,
Index: mdbcomp/feedback.automatic_parallelism.m
===================================================================
RCS file: /home/mercury1/repository/mercury/mdbcomp/feedback.automatic_parallelism.m,v
retrieving revision 1.8
diff -u -p -b -r1.8 feedback.automatic_parallelism.m
--- mdbcomp/feedback.automatic_parallelism.m 20 Dec 2010 07:47:48 -0000 1.8
+++ mdbcomp/feedback.automatic_parallelism.m 21 Dec 2010 11:23:51 -0000
@@ -131,9 +131,49 @@
% sensible names.
cpcp_var_table :: var_table,
+ % Each push represents a program transformation.
+ % Most of the time, we expect the list to be empty,
+ % but if it isn't, then the list of candidate conjunctions
+ % is valid only AFTER the transformations described
+ % by this list have been applied. (The transformations
+ % should be independent of one another, so it should be
+ % OK to apply them in any order.)
+ cpcp_push_goals :: list(push_goal),
+
cpcp_par_conjs :: list(candidate_par_conjunction(GoalType))
).
+ % This goal describes 'push goal' transformations.
+ %
+ % This is where a goal may be pushed into the arms of a branching goal that
+ % occurs before it in the same conjunction. It can allow the pushed goal
+ % to be parallelised against goals in one or more branches without
+ % parallelising the whole branch goal (whose per-call cost may be two
+ % small).
+ %
+:- type push_goal
+ ---> push_goal(
+ % The goal path of the conjunction in which the push is done.
+ pg_goal_path :: goal_path_string,
+
+ % The range of conjuncts to push.
+ pg_pushee_lo :: int,
+ pg_pushee_hi :: int,
+
+ % The set of expensive goals inside earlier conjuncts in that
+ % conjunction "next" to which the pushee goals should be
+ % pushed. By "next", we mean that the pushee goals should be
+ % added to the end of whatever conjunction contains the
+ % expensive goal, creating a containing conjunction if
+ % there wasn't one there before.
+ %
+ % Each of these expensive goals should be on a different
+ % execution path.
+ %
+ % This list should not be empty.
+ pg_pushed_into :: list(goal_path_string)
+ ).
+
:- type candidate_par_conjunctions_proc ==
candidate_par_conjunctions_proc(pard_goal).
@@ -323,9 +363,9 @@ parallel_exec_metrics_get_cpu_time(PEM)
%
convert_candidate_par_conjunctions_proc(Conv, CPCProcA, CPCProcB) :-
- CPCProcA = candidate_par_conjunctions_proc(VarTable, CPCA),
+ CPCProcA = candidate_par_conjunctions_proc(VarTable, PushGoals, CPCA),
map(convert_candidate_par_conjunction(Conv), CPCA, CPCB),
- CPCProcB = candidate_par_conjunctions_proc(VarTable, CPCB).
+ CPCProcB = candidate_par_conjunctions_proc(VarTable, PushGoals, CPCB).
convert_candidate_par_conjunction(Conv0, CPC0, CPC) :-
CPC0 = candidate_par_conjunction(GoalPath, FirstGoalNum,
Index: mdbcomp/feedback.m
===================================================================
RCS file: /home/mercury1/repository/mercury/mdbcomp/feedback.m,v
retrieving revision 1.19
diff -u -p -b -r1.19 feedback.m
--- mdbcomp/feedback.m 16 Oct 2010 04:11:05 -0000 1.19
+++ mdbcomp/feedback.m 21 Dec 2010 11:19:00 -0000
@@ -535,7 +535,7 @@ feedback_first_line = "Mercury Compiler
:- func feedback_version = string.
-feedback_version = "14".
+feedback_version = "15".
%-----------------------------------------------------------------------------%
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 489 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20101221/6bde37e3/attachment.sig>
More information about the reviews
mailing list