Previous Up Next

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:

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

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:

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:

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:

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:

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:

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:

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.

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:

4.1 Exported constants and types

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

These types are described in section 1

4.2 Exported procedures and function

The following procedures and function are exported by this module:

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

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

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

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

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

This procedure initializes the global variables succ, Lpred and Rpred, and sets the global variable nodes used to empty.

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

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

This procedure is described in subsection 2.2

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

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

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.


My life as a hacker | My home page