Multi-directional Scans

5 Multi-directional Scans

A multi-directional scan has more than one direction vectors, other parameters being the same:

Scan( D,(e₁,...,e_k),b,d,g) .

The direction vectors e₁,...,e_k span a linear subspace H and define a family of affine subspaces H+d for an arbitrary translation vector d. Formula (9) defines as many scans as there are affine subspaces whose intersection with D is not empty. b is the scan operator, and the scan order is lexicographic order on the coordinates of each point relative to its affine subspace. Points which cannot be reached from other points of D by a positive integral combination of direction vectors are given the initial values as defined by g. The reader may notice that this definition defaults back to the definition of a uni-directional scan when k=1.

Our first observation is that multi-directional scans are more efficient than multiple uni-directional scans.

Take the example of the sum of the elements of a n× n matrix. With only uni-directional scans, one must compute n sequential scans operating on n data. With P processors, the run-time is of the order of n(n/P+log₂(P)). With a multi-directional scan, a run-time of the order of n²/P+log₂(P) is expected. In the best case (when n=P) the speed-up is about 1+log₂(P).

In our system, multi-directional scans cannot be detected directly. They can be found using multistage elimination. When working at pseudo-depth p, a direction may be added to a scan if its initial values reference the clause c in which it lays and if the scan operator is the clause c itself. The second condition is that a new direction e₀ can be extracted from the definitions of the scan initial values. A new direction cannot be an arbitrary vector: some checks must be done on the definition of each initial value v₀ of the former Scan which are not initial values of the enhanced Scan. Namely, such a definition must be the application of the Scan operator to the data corresponding to v₀ and the data corresponding to the predecessor of v₀ according to the directions e₀ to e_k.

Practically, the problem of extracting a new direction may be solved using the PIP software [6], since testing the validity constraint is equivalent to the computation of a lexicographic maximum.

Let us consider again the summation of the elements of a matrix. The corresponding system is:
x[i,j] =
   case
     i,j | i=1, j=1         : a[i,j] ;
     i,j | 2<=i<=n, j=1     : x[i-1,n] + a[i,j] ;
     i,j | 1<=i<=n, 2<=j<=n : x[i,j-1] + a[i,j] ;
   esac ;

 
Pattern matching is applied for the detection of scans at pseudo-depth 1. A closed form is introduced for the clause x.2:
x[i,j] =
   case
     i,j | i=1, j=1         : a[i,j] ;
     i,j | 2<=i<=n, j=1     : x[i-1,n] + a[i,j] ;
     i,j | 1<=i<=n, 2<=j<=n :
          Scan( i',j' | 1<=i'<=n, 1<=j'<=n,
                ([0 1]), +, a[i',j'], x[i',j'] );
   esac ;

 
Removing inter-components references leads to the inclusion of the clauses x.0 and x.1 into the initial value of the Scan operator.
x[i,j] =
   case
     i,j | 1<=i<=n, 2<=j<=n :
          Scan( i',j' | 1<=i'<=n, 1<=j'<=n,
                ([0 1]), +, a[i',j'],
                 case 
                    k,l | k=1, l=1     :
                         a[1,1] ;
                    k,l | 2<=k<=n, l=1 :
                         x[k-1,n] + a[k,l] ;
                 esac ; )
   esac ;

 
Since this system is already normalized for pseudo-depth 0, a pattern-matching can be applied. No new uni-directional scan can be detected. But we can try to add a direction to the previously detected scan. Two necessary conditions for scan enhancement are fulfilled: the scan is the clause expression, and the second clause of the initial value is referencing x.0 at pseudo-depth 0 using the scan binary operation (here an addition).

Now, a new direction e₀ must be extracted. The direction must verify that for k in {2,...,n} the point (k , 1) has for predecessor in scan order defined by e₀ and e₁ the point (k-1 , n) . A solution is the integer vector (1 , 0) .

The scan enhancement is successful, we obtain a two-directional scan:
x[i,j] =
   case
     i,j | 1<=i<=n, 2<=j<=n :
          Scan( i',j' | 1<=i'<=n, 1<=j'<=n,
                ([1 0] [0 1]), +,
                a[i',j'], a[1,1] ) ;
   esac ;

 