   # Simple multi-pass module (allsmp)

## Introduction

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.

## 1 Representation of the dependency graph and the solution

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.

### 1.1 Representation of the nodes

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 tset node contains the set of node numbers that is used to represent the nodes of the dependency graph.

The clause "node in set of nodes" is represented by node IN set of nodes, where node is a variable of type max range and set of nodes is a variable of type tset node.

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,node2in rel on nodes" is represented by node2 IN rel on nodes[node1], where node1 and node2 are variables of type max range and rel on nodes is a variable of type trel node.

### 1.2 Representation of the (attribute,element) pairs

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 make numbering for pairs [depend 3.1] tries to assign a unique node number to each pair. The global variable nodes used contains the subset of possible node numbers to which a pair has been assigned. The information about which (attribute,element) pair belongs to each node number is stored in the global variable node of type nodes. This type is declared by:

```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 elem points to the element identifier.

### 1.3 Representation of the dependencies

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 succ represents the set of all dependencies. The global variables Lpred and Rpred represent the set of edges that when reversed cannot be evaluated in a left-to-right or right-to-left pass, respectively.

### 1.4 Representation of the dependency graph

The dependency graph is represented by the four global variables nodes used, succ, Lpred and Rpred. Take into consideration that the global variable Lpred and Rpred contain the values of the inverse relations "P/L" and "P/R" of the definition of the dependency graph in [3.1.3].

### 1.5 Representation of the solution

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 none will never be found in the representation of a correct solution. The value both is used for those passes that can be evaluated in both directions. The type tpart dir represents the evaluation directions for a number of passes. The type tpartition is used to represent the partition of the attributes over the passes.

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 max pass nr should have been used instead.

## 2 Manipulating the dependency graph

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.

### 2.1 Creating 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 node using the parameters elem nr and attr nr, that indicate which (attribute,element) pair is associated with this node. The node is printed on the listing file when the global boolean variable with dep info is equal to TRUE. This procedure is called by the procedure make numbering for pairs [depend 3.1].

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 to contain the numbers between which the dependency should be added. The parameter dir indicates the direction in which the dependency cannot be evaluated. The procedure updates the global variables succ, Lpred and Rpred, and prints the dependency on the listing file when the global boolean variable with dep info is equal to TRUE. This procedure is called by the procedure generate dependencies [depend 4.3].

### 2.2 Retrieving

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 tattr at elem [bintree 1.3], will be filled with information about which attributes at each element are referred to in the set of nodes as represented by the first parameter node set. In this conversion the global variable node is used to find out which (attribute,element) pair is associated with each node in the given set.

### 2.3 Printing procedures

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 nr.

The procedure print a dependency prints the dependency between the nodes represented by the first two parameters from and to, with the direction indicated by the third parameter dir. The procedure print a node is used to print the (attribute,element) pairs associated with the nodes.

The procedure print dependencies prints the dependencies as represented by the parameters succ, Lpred and Rpred.

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

The procedure print groups prints the groups as represented by the first parameter group of type trel node, using the two subsets of nodes as represented by the other two parameters in L pass and in R pass. The relation represented by the parameter group indicates for each node to which group of nodes it belongs, if it belongs to a group. The two other parameters are used to print the evaluation restrictions on the nodes in a group.

## 3 Simple multi-pass algorithm

The function smp algorithm returns the value TRUE, when a SMP-solution is found, otherwise it returns the value FALSE. Whenever a solution is found, this solution is stored in the reference parameters of the function. The first parameter bestpartition represents the partition of the (attribute,element) pairs. The second parameter bestpart dir represents the directions of the passes. The third parameter bestone pass represents the one pass (attribute,element) pairs. And the last parameters bestpasses contains the number passes of the solution.

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.

### 3.1 Calculating closure and group relations

The local procedure make all closures calculates the transitive closure of the relation represented in the parameter succ, in the reference parameter semi closure. As a side effect the group relation is returned in the reference parameter group. The group relation is the relation between an element and its strongly connected component in (the graph represented by) a given relation. When an element is not a part of a strongly connected component the group relation does not exist between this element and any of the other elements. The local variable group of plays an important role in the implementation of the transitive closure algorithm, and is used to construct the group relation.

#### 3.1.1 Transitive closure algorithm

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 make semi closure is called for each node.

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 e, and the set of nodes that have been followed so far as represented by the parameter F. This set is used to detect directed cycles.

The function test made and update tests whether for a given node, which has the number equal to the parameter n, the transitive closure has been calculated yet. It also finds the correct values for those nodes of a strongly connected component, by following the backward chain using the procedure update.

The local procedure update traverses a backward chain as represented by group of, starting with the node equal to the parameter n. The backward chain is optimized whenever possible.

#### 3.1.2 Constructing group relation

The procedure make group relation constructs the group relation by using the local variable group of and the transitive closure as represented by the reference parameter semi closure. The construction is done in two steps. Because the backward chains have been optimized, all the nodes of a component point to its first node. In the first step this property of the backward chain is used to calculate the group relation for the first nodes. In the second step the group relation found with the first nodes is assigned to all the other nodes, using the backward chains.

### 3.2 Finding in-l-pass and in-r-pass relations

The procedure make in L or R pass constructs the subsets of nodes in the reference parameters in L pass and in R pass, which have to evaluated in a left-to-right or right-to-left pass, using the dependencies as represented by the parameters succ, Lpred and Rpred, together with the group relation as represented by the parameter group. All the nodes of a group which have an edge that cannot be evaluated in a certain direction, cannot be evaluated in a single pass with this direction. Whenever an edge in a group is found that cannot be evaluated in one of the two directions the whole group is added to the set of nodes that cannot be evaluated in the given direction.

### 3.3 Finding smp solutions

The procedure find SMP solution finds all the correct SMP solutions for the problem as represented by the parameters semi closure, Lpred and Rpred, to a maximum search depth equal to the global variable max depth. For each solution that is found and is correct and/or has the maximum depth, the procedure process solution is called. This procedure is described in the following subsection.

The local procedure make choices is the implementation of the formal function "find" in [3.2.2], where the parameter A left represents the set of remaining nodes, the set of remaining (attribute,element) pairs. The local variables L next and R next represent "Next R" and "Next R" in the formal definition of "find".

The nested procedure accept choice calls the procedure process solution when a complete solution is found, or when the maximum search depth is reached, otherwise the procedure make choices is called recursively with an updated set of the remaining nodes.

The local function find next attribute partition is the implementation of the formal function "find next SMP" in [3.2.3], where the parameter A left represents "A'", and the parameter direction represents "d" in the formal definition.

### 3.4 Process solutions

The procedure process solution processes a solution found by the procedure find SMP solution. The third parameter passes contains the number of passes. The first parameter partition represents the partition of the (attribute,element) pairs over the nodes, and the second parameter part dir represents the allowed evaluation directions of each pass. The fourth parameter remaining contains the (attribute,element) pairs that are not assigned to a pass yet. A solution is a correct solution when the value of the parameter remaining is equal to the empty set.

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 print part with numbers.

The procedure print part with numbers prints the set represented by the parameter part as a partition depending on the life cycle of the (attribute,element) pairs. The life cycle of a pair is the number of passes it has to keep for later usage. One pass attributes have a life cycle equal to one. The procedure find for ord finds the subset of the set with a certain life cycle. The parameter inthis represents all the pairs that have been evaluated after a certain pass, which is determined by the current pass number and the life cycle.

The local variable cum of the procedure print solution contains the cumulative sets of (attribute,element) pairs that have been evaluated. The variable is initialized by the local procedure make cumulative partition sets.

### 3.5 Selecting the best solution

The procedure find best selects the best solution of all the correct solutions. The global variables bestpartition, bestpart dir, bestpasses and bestone pass are used to represent the best solution found so far. The global variable bestvalue contains the value as calculated by the function value of the best solution. If no solution is yet found, then the value of bestvalue is equal to the constant minint.

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.

## 4 Interface

The following modules are used by this module:

`definitions, perform, listing, bintree, screen.`

### 4.1 Exported constants and types

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

### 4.2 Exported procedures and function

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 parameters from and to, in the direction given by the third parameter dir. See subsection 2.3

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

This procedure prints the dependencies, as represented by the parameters 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. See subsection 2.3

`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, Lpred and Rpred, and sets the global variable nodes used to empty.

`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 elem nr and attr nr. See subsection 2.1

```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 to, in the direction represented by the third parameter dir. See subsection 2.1

```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 FALSE. When a solution is found it is represented using the reference parameters. See section 3 for a detailed description.

## 5 The listing

 ```[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; ```

### 5.1 Printing procedures

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; ```

### 5.2 Storing procedures

 ``` 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; ```

### 5.3 Converting procedure

 ``` 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; ```

### 5.4 Closure and group procedures

 ```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; ```

### 5.5 Find in-l-pass and in-r-pass relations

 ``` 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; ```

### 5.6 Simple multi-pass algorithm

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; ```

### 5.7 Selecting the best solution

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 <> 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; ```

### 5.8 Process solutions

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 := partition; 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; ```

### 5.9 Body of smp algorithm

 ```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. ```