(allsmp)

This module implements the Simple Multi-Pass (SMP) algorithm as described in [3.2.2-3.3]. The dependency graph is derived from the attribute assignments by the Dependency Graph Generation Module [depend 4], using some of the procedures defined in this module, see section 2.1 In section 3 we describe how this dependency graph is used to find a partition of the attributes over a number of passes, if a solution exists.

In this section we describe how the dependency graph and its relation to the (attribute,element) pairs is represented in this implementation. We also describe how the solution found by the SMP algorithm is represented.

The nodes of the dependency graph are represented by a unique number. The range of these numbers is restricted by the implementation. It is defined by the following sub-range type, in which ` max node nr `is a constant determined by the implementation:

max_range = 0..max_node_nr;

The following type is used to represent a subset of the node numbers:

tset_node = SET OF max_range;

The global variable` nodes used `of type

The clause "`node `**in** `set of nodes`" is represented by* node*` IN`` set of nodes`, where

The following type is used to represent a binary relation on the nodes:

trel_node = ARRAY[0..max_node_nr] OF tset_node;

The clause "**(**`node1`**,**`node2`**) ****in** `rel on nodes`" is represented by* node2*` IN`* rel on nodes*`[`*node1*`]`, where` node1 `and

The set of (attribute,element) pairs defined by "` all attr elem pairs`" [3.1] is used as the nodes of the dependency graph. The procedure

nodes = ARRAY[max_range] OF RECORD attr, elem : pnode END;

Each element of this array type represents one (attribute,element) pair, where the record field` attr `points to the attribute identifier and the record field

As described in [3.1.3] a dependency graph is a 4-tuple, which consists of a set of nodes, a set of directed edges and two subsets of this set of edges which indicate the edges that are labelled left and right, respectively. A set of edges is represented by the type` trel node`. There are three global variables of this type that describe the sets of edges. The global variable

The dependency graph is represented by the four global variables` nodes used`,

The solution consists of three parts: the number of passes, the evaluation directions of the passes and the partition of the (attribute,element) pairs over the passes. To represent the solution, the following types are used:

tdirection = (none, left, right, both); tpartition = ARRAY[0..max_part_nr] OF tset_node; tpart_dir = ARRAY[0..max_part_nr] OF tdirection;

The type` tdirection `is used to describe the kind of evaluation directions that are possible. The value

`Remark`: The constant` max part nr `is used here incorrectly. It is used to describe the maximum number of parts in a tree rule. This has no correlation with the number of passes. A constant with the name

In this section we describe a number of procedures that manipulate the internal representation of the dependency graph. These include procedures to create the dependency graph, and to extract information from the dependency graph.

When creating the dependency graph, first of all the internal representation has to be initialized. This is done by the following procedure:

PROCEDURE initialize_smp_algorithm

This procedure clears the four global variables that are used to represent the dependency graph.

Adding a node to the dependency graph is done by the following procedure:

PROCEDURE add_a_node(nr, elem_nr, attr_nr : integer);

This procedure adds the node, with node number equal to the value of the parameter` nr`, to the set of used nodes, and updates the global variable

To add a dependency to the dependency graph, the following procedure is used:

PROCEDURE add_a_dependency(from, to_ : integer; dir : direction);

The parameters` from `and

The solution is represented by giving the subset of nodes that should be evaluated in each pass. The following procedure can be used to find which attributes with each element are represented by these subsets of nodes.

PROCEDURE make_attr_at_elem(node_set : t_set_node; VAR attr_at_elem : tattr_at_elem);

The second reference parameter` attr at elem `of type

The procedure` print a node `prints the names of the attribute and element that are associated with the node, with the node number equal to the value of the parameter

The procedure` print a dependency `prints the dependency between the nodes represented by the first two parameters

The procedure` print dependencies `prints the dependencies as represented by the parameters

The procedure` print set `prints the (attribute,element) pairs associated with the elements in the set represented by the parameter

The procedure` print groups `prints the groups as represented by the first parameter

The function` smp algorithm `returns the value

The implementation of the Simple Multi-Pass algorithm can be divided into three steps. The first step is the calculation of the transitive closure of the dependencies. In this step the group relation is also calculated. A group (here used as a synonym for a strongly connected component) is the maximum subset of nodes in which all nodes depend on each other through the dependencies.

The second step finds those nodes that have to be either evaluated in a left-to-right pass or a right-to-left pass. When the intersection of these two sets is not empty, it is impossible to find an SMP-evaluation strategy.

The third step is only done when an SMP evaluation strategy is possible. In this step the implementation asks for a maximum search depth until a complete solution is found. For each maximum search depth the algorithm that tries to find a complete solution is started. Each time a solution is found it is processed, and the best complete solution found so far is kept.

In the following subsections these steps will be described in more detail.

The local procedure` make all closures `calculates the transitive closure of the relation represented in the parameter

It is simple to construct the transitive closure for each relation that has at least one complete ordering. This means that the graph, represented by the relation, has no cycles, and thus has no strongly connected component. A way to construct the transitive closure for this special case is to call a recursive function for all the nodes, which calculates the set of nodes that can be reached starting from a node. This algorithm can be made faster by using memorization, which is storing and using the intermediate results. In this way the subset of nodes that can be reached from a node is only calculated the first time, and stored with the node. All other times the stored value is returned immediately, and no calculation is done.

When this algorithm is applied to a relation whose graph does have strongly connected components, it does not store correct values for the nodes within the components. (Due to memorization, indefinite recursion is prevented.) We define the set of `first nodes `as those nodes of each component for which the recursive function was called first. Each component has precisely one first node. It turns out, however, that a correct value is attached to the first node. It is possible to remember how the other nodes of a component were reached (by recursive calls) from their first node by a kind of backward chaining.

The local variable` group of `is used to store the backward chains. For each node in a strongly connected component, it returns the node number within this component, from which it was called by the recursive function. The first nodes point to themselves.

Using these backward chains it is now possible to find the correct value for all the nodes in a strongly connected component. The time needed to traverse the backward chains can be reduced by updating the backward chains each time we traverse them.

In the body of the procedure` make all closures `the procedure

The procedure` make semi closure `is the recursive procedure that constructs the transitive closure starting from the node with the number equal to the value of the parameter

The function` test made and update `tests whether for a given node, which has the number equal to the parameter

The local procedure` update `traverses a backward chain as represented by

The procedure` make group relation `constructs the group relation by using the local variable

The procedure` make in L or R pass `constructs the subsets of nodes in the reference parameters

The procedure` find SMP solution `finds all the correct SMP solutions for the problem as represented by the parameters

The local procedure` make choices `is the implementation of the formal function "

The nested procedure` accept choice `calls the procedure

The local function` find next attribute partition `is the implementation of the formal function "

The procedure` process solution `processes a solution found by the procedure

When a complete solution is found the solution is printed on the listing file, and the procedure` find best `is called. This procedure is described in the following subsection.

When the solution is printed by the procedure` print solution`, the set of one pass attributes [3.3] is calculated. This procedure prints for each pass the allowed evaluation directions of the pass, and the set of (attribute,element) pairs that have to be evaluated during that pass. These sets are printed by calling the procedure

The procedure` print part with numbers `prints the set represented by the parameter

The local variable` cum `of the procedure

The procedure` find best `selects the best solution of all the correct solutions. The global variables

The function` value `returns a value for each solution, indicating how good the solution is. The better the solution the higher the number. The number is determined by the number of passes, the number of left-to-right passes, and whether the last and the first pass are a left-to-right pass.

The following modules are used by this module:

definitions, perform, listing, bintree, screen.

The following constant and type definitions are exported by this module:

CONST max_node_nr = 225; { see subsection 1.1 } minint = -100000; { see subsection 3.5 } TYPE max_range = 0..max_node_nr; tset_node = SET OF max_range; trel_node = ARRAY[0..max_node_nr] OF tset_node; nodes = ARRAY[0..max_node_nr] OF RECORD attr, elem : pnode END; tgroup_of = ARRAY[0..max_node_nr] OF integer; tdirection = (none, left, right, both); tpartition = ARRAY[0..max_part_nr] OF tset_node; tpart_dir = ARRAY[0..max_part_nr] OF tdirection;

These types are described in section 1

The following procedures and function are exported by this module:

PROCEDURE print_a_node(nr : integer);

This procedure prints the (attribute,element) pair assigned with the node with the number equal to the parameter` nr`. See subsection 2.3

PROCEDURE print_a_dependency(from, to_ : integer; dir : tdirection);

This procedure prints the dependency between the nodes represented by the first two parameter` s from `and

PROCEDURE print_dependencies(VAR succ, Lpred, Rpred : trel_node);

This procedure prints the dependencies, as represented by the parameters` succ`,

PROCEDURE print_set(a_set : tset_node);

This procedure prints the set of elements represented by the parameter` a set`. See subsection 2.3

PROCEDURE print_groups(VAR group : trel_node; VAR in_L_pass, in_R_pass : tset_node);

This procedure prints all the groups using the group function represented by the first parameter` group`, in increasing number of the lowest member of the group. See subsection 2.3

PROCEDURE initialize_smp_algorithm;

This procedure initializes the global variables` succ`,

PROCEDURE add_a_node(nr, elem_nr, attr_nr : integer);

This procedure adds the node with the number represented by the first parameter` nr`, with the (element,attribute) pair represented by the second and third parameter

PROCEDURE add_a_dependency(from, to_ : integer; dir : tdirection);

This procedure adds a dependency between the nodes represented by the first two parameters` from `and

PROCEDURE make_attr_at_elem_for(node_set : tset_node; VAR attr_at_elem : tattr_at_elem);

This procedure is described in subsection 2.2

FUNCTION smp_algorithm(VAR bestpartition : tpartition; VAR bestpart_dir : tpart_dir; VAR bestone_pass : tset_node; VAR bestpasses : integer) : boolean;

This function returns the value` TRUE`, when an SMP-solution exists, otherwise it returns the value

[ENVIRONMENT ('allsmp.pen'), INHERIT ('definitions.pen', 'perform.pen', 'listing.pen', 'bintree.pen', '[-.SCREEN]screen.pen')]MODULE simple_multi_pass(input,output); (* PROGRAM ALLSMP *) (* This program finds one optical Simple Multi-Pass solution for the *) (* problem as formulated on the input dependency file, and outputs this *) (* on the solution file. *) CONST max_node_nr = 225; minint = -100000; TYPE max_range = 0..max_node_nr; tset_node = SET OF max_range; trel_node = ARRAY[0..max_node_nr] OF tset_node; nodes = ARRAY[0..max_node_nr] OF RECORD attr, elem : pnode END; tgroup_of = ARRAY[0..max_node_nr] OF integer; tdirection = (none, left, right, both); tpartition = ARRAY[0..max_part_nr] OF tset_node; tpart_dir = ARRAY[0..max_part_nr] OF tdirection; [HIDDEN] VAR (* local for this program are: *) succ , Lpred , Rpred : trel_node; node : nodes; nodes_used : tset_node; |

The procedures on this page are for printing of the different relations that are generated during the process. Mainly used for debugging.

PROCEDURE print_a_node(nr : integer); BEGIN print_alfa(node[nr].attr^.name); print_alfa(' OF '); print_alfa(node[nr].elem^.name); END; PROCEDURE print_a_dependency(from, to_ : integer; dir : tdirection); BEGIN print_a_node(from); CASE dir OF none : print_alfa(' ---none---> '); left : print_alfa(' ---left---> '); right : print_alfa(' ---right--> '); both : print_alfa(' ---both---> ') END; print_a_node(to_); print_newline END; PROCEDURE print_dependencies(VAR succ, Lpred, Rpred : trel_node); (* This procedure prints the dependencies, as represented by succ, Lpred *) (* and Rpred. The dependencies are printed in increasing number, followed *) (* by the indications NON, LEFT, RIGHT or BOTH, which indicate the *) (* restrictions on this dependency. *) VAR from, to_ : integer; dir : tdirection; BEGIN write(listing,'The collected dependencies are :'); print_newline(2); FOR from := 0 TO max_node_nr DO IF from IN nodes_used THEN FOR to_ := 0 TO max_node_nr DO IF to_ IN succ[from] THEN BEGIN IF from IN Lpred[to_] THEN IF from IN Rpred[to_] THEN dir := both ELSE dir := left ELSE IF from IN Rpred[to_] THEN dir := right ELSE dir := none; print_a_dependency(from, to_, dir) END; print_newline(2) END; PROCEDURE print_set(a_set : tset_node); VAR pair_nr : integer; not_first : boolean; BEGIN print_char('['); shift_right(1); not_first := FALSE; pair_nr := start_nr; WHILE a_set <> [] DO BEGIN REPEAT pair_nr := pair_nr + 1 UNTIL pair_nr IN a_set; a_set := a_set - [pair_nr]; IF not_first THEN print_alfa(', ') ELSE not_first := TRUE; print_a_node(pair_nr) END; print_char(']'); shift_left(1) END; PROCEDURE print_groups(VAR group : trel_node; VAR in_L_pass, in_R_pass : tset_node); (* This procedure prints all the groups using the group function, in *) (* increasing number of the lowest member of the group. *) VAR in_group : tset_node; i : integer; BEGIN write(listing, 'The groups, with their evaluation direction, are :'); print_newline(2); in_group := []; FOR i := 0 TO max_node_nr DO IF (i IN nodes_used) AND NOT (group[i] <= in_group) THEN BEGIN IF i IN in_L_pass THEN IF i IN in_R_pass THEN print_alfa('NON - ') ELSE print_alfa('RIGHT - ') ELSE IF i IN in_R_pass THEN print_alfa('LEFT - ') ELSE print_alfa('BOTH - '); shift_right(8); print_set(group[i]); shift_left(8); print_newline(1); in_group := in_group + group[i] END; print_newline(2) END; |

PROCEDURE initialize_smp_algorithm; (* This procedure initializes succ, Lpred and Rpred, and sets the set *) (* nodes_used to empty. *) VAR i : integer; BEGIN (* initialization of succ, Lpred and Rpred *) FOR i := 0 TO max_node_nr DO succ[i] := []; Lpred := succ; Rpred := succ; nodes_used := [] END; PROCEDURE add_a_node(nr, elem_nr, attr_nr : integer); BEGIN IF nr <= max_node_nr THEN BEGIN node[nr].attr := attribute[attr_nr]; node[nr].elem := element[elem_nr]; IF with_dep_info THEN BEGIN write(listing, nr:3 ,' '); print_a_node(nr); print_newline END; nodes_used := nodes_used + [nr] END END; PROCEDURE add_a_dependency(from, to_ : integer; dir : tdirection); BEGIN succ[from] := succ[from] + [to_]; IF dir IN [both, left] THEN Lpred[to_] := Lpred[to_] + [from]; IF dir IN [both, right] THEN Rpred[to_] := Rpred[to_] + [from]; IF with_dep_info THEN print_a_dependency(from, to_, dir); END; |

PROCEDURE make_attr_at_elem_for(node_set : tset_node; VAR attr_at_elem : tattr_at_elem); VAR nr : integer; BEGIN (* initialize attr_at_elem *) FOR nr := 0 TO nr_of_elem DO attr_at_elem[nr] := []; (* fill attr_at_elem with the relation representation *) nr := start_nr; WHILE node_set <> [] DO BEGIN REPEAT nr := nr + 1 UNTIL nr IN node_set; node_set := node_set - [nr]; WITH node[nr] DO attr_at_elem[elem^.elem_nr] := attr_at_elem[elem^.elem_nr] + [attr^.attr_nr] END; END; |

FUNCTION smp_algorithm(VAR bestpartition : tpartition; VAR bestpart_dir : tpart_dir; VAR bestone_pass : tset_node; VAR bestpasses : integer) : boolean; VAR group , semi_closure : trel_node; in_L_pass , in_R_pass : tset_node; max_depth : integer; bestvalue : integer; PROCEDURE make_all_closures(VAR succ, semi_closure, group : trel_node); (* This procedure makes the closure using the variable succ, and makes it *) (* in semi_closure. Also th(VAR succ, semi_closure, group : trel_node);s to *) (* the number of the vertex with which the group is identified. *) (* The test whether a vertex is in a group is : v IN semi_closwith every *) (* element a group is given. The variable group_of is used in the closure *) (* algorithm to construct the semi_closure in an efficient way. It will *) (* point to another member of the group, if it is in a group. Afterwards *) (* it points to a unique leader of the group. This is used to make the *) (* group relation. *) VAR elem_nr : integer; group_of : ARRAY[0..max_node_nr] OF integer; done : tset_node; FUNCTION test_made_and_update(n : integer) : boolean; (* This function tests whether an element has been visited before, this *) (* can been seen because the done status has been set, or group_of[n]<>n *) (* In case status is not done and group_of[n] <> n, an updating process is*) (* done. TRUE is returned if the element was not visited before. *) PROCEDURE update(n : integer); (* This procedure start an updating process from vertex n. Updating *) (* proceeds if group_of[n] <> n and n does not have the done status. If *) (* a done status can be concluded this is done. Group and semi_closure *) (* are updated. *) VAR group_of_n : integer; BEGIN enter_level('update'); group_of_n := group_of[n]; IF NOT (group_of_n IN done) THEN IF group_of[group_of_n] <> group_of_n THEN update(group_of_n); IF group_of_n IN done THEN done := done + [n]; semi_closure[n] := semi_closure[group_of_n]; group_of[n] := group_of[group_of_n]; exit_level END; BEGIN (* of test_made_and_update *) enter_level('test made and update'); IF n IN done THEN test_made_and_update := FALSE ELSE IF group_of[n] = n THEN test_made_and_update := TRUE ELSE BEGIN update(n); test_made_and_update := FALSE END; exit_level END; PROCEDURE make_semi_closure(e : integer; F : tset_node); (* This function returns the semi_closure starting with e. This will not *) (* always be the complete semi_closure, if this vertex is in a group. *) (* F holds the vertices that are visited. If a vertex n from e is in F *) (* this means that there is a cycle and that they are in the same group. *) VAR successors : tset_node; n : integer; BEGIN enter_level('make semi closure'); semi_closure[e] := succ[e]; successors := succ[e] - F; n := -1; WHILE successors <> [] DO BEGIN REPEAT n := n + 1 UNTIL n IN successors; successors := successors - [n]; IF test_made_and_update(n) THEN make_semi_closure(n, F + [n]); IF semi_closure[n] * F <> [] THEN group_of[n] := e ELSE done := done + [n]; semi_closure[e] := semi_closure[e] + semi_closure[n] END; exit_level END; PROCEDURE make_group_relation; (* This procedure makes the group relation using the variable group_of. *) (* First the group relation is made in such a way that group[e] = [e], if *) (* e in semi_closure[e], thus is in a group. Secondly the members of a *) (* group are stored in the leader of the group, which can be found using *) (* the group_of relation. Thirdly all the other members are filled with *) (* the value of the leader of the group. *) VAR i : integer; BEGIN enter_level('make group rel'); FOR i := 0 TO max_node_nr DO group[i] := []; FOR i := 0 TO max_node_nr DO IF i IN nodes_used THEN IF i IN semi_closure[i] THEN group[group_of[i]] := group[group_of[i]] + [i]; FOR i := 0 TO max_node_nr DO IF i IN nodes_used THEN group[i] := group[group_of[i]]; exit_level END; BEGIN (* begin of make_all_closures *) enter_level('make all closures'); semi_closure := succ; FOR elem_nr := 0 TO max_node_nr DO group_of[elem_nr] := elem_nr; done := []; FOR elem_nr := 0 TO max_node_nr DO IF elem_nr IN nodes_used THEN IF test_made_and_update(elem_nr) THEN BEGIN make_semi_closure(elem_nr, [elem_nr]); done := done + [elem_nr]; END; make_group_relation; exit_level; write_elapsed_time END; |

PROCEDURE make_in_L_or_R_pass(VAR succ, Lpred, Rpred, group : trel_node; VAR in_L_pass, in_R_pass : tset_node ); (* This procedure generates the sets in_L_pass and in_R_pass, which can be *) (* used to test whether the dependencies are SMP, and whether more L or R *) (* passes are needed. *) VAR i : integer; hgroup : tset_node; BEGIN in_L_pass := []; in_R_pass := []; FOR i := 0 TO max_node_nr DO IF i IN nodes_used THEN BEGIN hgroup := group[i]; IF hgroup <> [] THEN BEGIN IF Lpred[i] * hgroup <> [] THEN in_R_pass := in_R_pass + hgroup; IF Rpred[i] * hgroup <> [] THEN in_L_pass := in_L_pass + hgroup END END END; |

On this page the procedure that searches for all solutions is given.

PROCEDURE process_solution(VAR partition:tpartition; VAR part_dir:tpart_dir; passes : integer; remaining : tset_node); FORWARD; PROCEDURE find_SMP_solution(VAR semi_closure, Lpred, Rpred : trel_node); VAR solution : tpartition; sol_dir : tpart_dir; FUNCTION find_next_attribute_partition (A_left : tset_node; direction : tdirection) : tset_node; (* This function gives the next attribute partition with the still left *) (* attributes in A_left, for the direction direction. *) VAR n : integer; result , try : tset_node; FUNCTION Dpred(n : integer) : tset_node; (* This function returns the Lpred or Rpred sets for n, depending on *) (* the direction direction. *) BEGIN IF direction = right THEN Dpred := Lpred[n] ELSE Dpred := Rpred[n] END; BEGIN (* of find_next_attribute_partition *) result := A_left; try := A_left; n := -1; REPEAT REPEAT n := n + 1 UNTIL n IN try; try := try - [n]; IF Dpred(n) * A_left <> [] THEN BEGIN result := result - [n] - semi_closure[n]; try := try - semi_closure[n] END UNTIL try = []; find_next_attribute_partition := result END; PROCEDURE make_choices(A_left : tset_node; depth : integer); (* This procedure makes the choices which directions are exploited *) (* further, if the attributes A_left are left over. *) VAR L_next , R_next : tset_node; PROCEDURE accept_choice(dir : tdirection; next : tset_node); (* This procedure accepts the choices that have been made. The choices *) (* consist out of a direction, and the maximal next subset of elements *) (* that has been constructed with this direction. *) (* If the rest is not empty and the maximal depth is not reached, the *) (* procedure make_choices is called recursively with the remaining *) (* subset of elements. Otherwise the solution, so far found, is printed.*) BEGIN solution[depth] := next; sol_dir [depth] := dir; IF (A_left = next) OR (depth = max_depth) THEN process_solution(solution, sol_dir, depth, A_left - next) ELSE make_choices(A_left - next, depth + 1) END; BEGIN (* of make_choices *) L_next := find_next_attribute_partition(A_left, Left); R_next := find_next_attribute_partition(A_left, right); IF L_next = R_next THEN accept_choice(both, L_next) ELSE BEGIN IF (L_next - R_next) <> [] THEN accept_choice(left, L_next); IF (R_next - L_next) <> [] THEN accept_choice(right, R_next) END END; BEGIN (* of find_SMP_solution *) make_choices(nodes_used, 1) END; |

This page is dealing with a procedure that finds the best solution.

PROCEDURE find_best(VAR partition : tpartition; VAR part_dir : tpart_dir; passes : integer; VAR one_pass : tset_node); (* This procedure checks whether the solution represented by partition and *) (* part_dir has a higher value, using the value function, than a previous *) (* one. If so this one is saved in the global variables bestpartition, *) (* bestpart_dir and bestpasses. The current value is held in the global *) (* variable bestvalue. *) VAR newvalue : integer; FUNCTION value(VAR part_dir : tpart_dir; passes : integer) : integer; (* This function returns the value of a solution. This value is the sum *) (* of 3 aspects: the total number of passes, whether the first and the *) (* last pass are left-to-right, the total number of left-to-right passes. *) (* These 3 aspects are multiplied by 3 weight factors : fac_nr_passes, *) (* fac_fila_ltr and fac_nr_ltr. *) CONST fac_nr_passes = -100; fac_fila_ltr = 10; fac_nr_ltr = 1; VAR fila_ltr , nr_ltr , nr : integer; BEGIN IF part_dir[1] <> right THEN fila_ltr := 1 ELSE fila_ltr := 0; IF part_dir[passes] <> right THEN fila_ltr := fila_ltr + 1; nr_ltr := 0; FOR nr := 1 TO passes DO IF part_dir[nr] <> right THEN nr_ltr := nr_ltr + 1; value := fac_nr_passes * passes + fac_fila_ltr * fila_ltr + fac_nr_ltr * nr_ltr END; BEGIN (* of find_best *) newvalue := value(part_dir, passes); IF newvalue > bestvalue THEN BEGIN bestpartition := partition; bestpart_dir := part_dir; bestpasses := passes; bestone_pass := one_pass; bestvalue := newvalue END END; |

The procedures on this page concern the post processing of the solutions that are found. Sometimes it is better to shift attributes from a pass to the next pass, if they become one pass.

PROCEDURE process_solution;(* VAR partition:tpartition; *) (* VAR part_dir : tpart_dir; passes : integer; *) (* remaining : tset_node); *) (* This procedure post processes a solution generated by the ALL-SMP- *) (* algorithm. *) VAR one_pass : tset_node; PROCEDURE print_solution; (* This procedure prints a solution using the variables partition, *) (* part_dir and passes, by printing the directions and the subsets found *) (* in increasing order, each on a new line. If both directions are *) (* giving the same result '?_pass' is printed. Otherwise 'L_pass' or *) (* 'R_pass'. *) VAR cum : tpartition; pass_nr : integer; PROCEDURE make_cumulative_partition_sets; VAR i : integer; BEGIN cum[1] := partition[1]; FOR i := 2 TO passes DO cum[i] := cum[pred(i)] + partition[i] END; PROCEDURE print_part_with_numbers(part : tset_node; pass_nr : integer); VAR ord_nr : integer; ord_set : tset_node; PROCEDURE find_for_ord(part : tset_node; VAR ord_set : tset_node; inthis : tset_node); VAR attr_nr : integer; BEGIN ord_set := []; attr_nr := start_nr; REPEAT REPEAT attr_nr := attr_nr + 1 UNTIL attr_nr IN part; part := part - [attr_nr]; IF succ[attr_nr] <= inthis THEN ord_set := ord_set + [attr_nr] UNTIL part = [] END; BEGIN (* of print_part_with_numbers *) ord_nr := 0; WHILE part <> [] DO BEGIN find_for_ord(part, ord_set, cum[pass_nr + ord_nr]); ord_nr := ord_nr + 1; IF ord_nr = 1 THEN one_pass := one_pass + ord_set; IF ord_nr > 10 THEN print_char(chr(ord_nr DIV 10 + ord('0'))) ELSE print_char(' '); print_char(chr(ord_nr MOD 10 + ord('0'))); print_alfa('-pass : '); shift_right(10); print_set(ord_set); shift_left(10); print_newline(1); part := part - ord_set END END; BEGIN (* of print_solution *) one_pass := []; make_cumulative_partition_sets; FOR pass_nr := 1 TO passes DO BEGIN CASE part_dir[pass_nr] OF left : write(listing, 'L-pass'); right : write(listing, 'R-pass'); both : write(listing, 'L- or R-pass') END; print_newline(1); print_part_with_numbers(partition[pass_nr], pass_nr) END; print_alfa('ONE PASS : '); shift_right(11); print_set(one_pass); shift_left(11); print_newline(1) END; BEGIN (* of process_solution *) IF remaining = [] THEN BEGIN print_solution; find_best(partition, part_dir, passes, one_pass) END ELSE BEGIN write(listing, 'incomplete partition found'); print_newline(2); END END; |

BEGIN (* of smp_algorithm *) perf_start_time(perf_4_pr_dep); print_dependencies(succ, Lpred, Rpred); perf_end_time (perf_4_pr_dep); perf_start_time(perf_4_mk_rel); make_all_closures(succ, semi_closure, group); make_in_L_or_R_pass(succ, Lpred, Rpred, group, in_L_pass, in_R_pass); perf_end_time (perf_4_mk_rel); purge_level_stack; print_groups(group, in_L_pass, in_R_pass); IF in_L_pass * in_R_pass <> [] THEN smp_algorithm := FALSE ELSE BEGIN perf_start_time(perf_4_find); write(listing, 'Simple Multi Pass solutions : '); print_newline(1); (* init bestvalue to find best solution *) bestvalue := minint; REPEAT write_screen('give maximal depth : '); readln(input, max_depth); writecr_screen; write(listing, '(max depth : ',max_depth:1, ')'); print_newline(2); find_SMP_solution(semi_closure, Lpred, Rpred); IF bestvalue = minint THEN writeln_screen('No solution found for this maximal depth'); UNTIL bestvalue <> minint; smp_algorithm := TRUE; perf_end_time (perf_4_find) END END; END. |

My life as a hacker | My home page