Instruction systolic array (ISA)

Program transformations

 up

Program transformations are a powerful means for writing elegant programs, especially recursive programs. A program transformation takes an ISA program as an argument and transforms it into another ISA program. Two transformations are considered in the following, using a program for matrix transposition as an example.

Matrix transposition

A transposition of an n × n-matrix can be done recursively in the following way, assuming that n is a power of 2:

 

Procedure transpose(n)
Input:n × n-matrix A
Output:transposed n × n-matrix AT
Method:
  1. if n>1 then
    1. transpose the four n/2 × n/2-submatrices
    2. exchange the upper right with the lower left submatrix

 

Figure 1 shows how a 2 × 2-matrix is transposed according to this method; the diagonal exchange between the upper right and the lower left submatrix is realized as three subsequent horizontal and vertical exchanges.

 

Figure 1: Transposition of a 2x2-matrix
Figure 1: Transposition of a 2x2-matrix

 

On the ISA, the following program performs a transposition of the upper left 2 × 2-submatrix.

Enable Java to see an animation of this figure
Transposition of a 2x2-matrix on the ISA
Figure 2: Transposition of a 2x2-matrix on the ISA

The next program is quite similar, it transposes all four 2 × 2-submatrices. The sequence of instructions is the same as before, but the row and column selectors have been duplicated.

Enable Java to see an animation of this figure
Transposition of all 2x2-submatrices
Figure 3: Transposition of all 2x2-submatrices
Trans­formation replicate

This program is obtained from the first program by the program transformation replicate. This operation takes a program p for a k × k-array and two numbers r and s as arguments and puts side-by-side r copies of p in horizontal direction and s copies of that result in vertical direction.

The program of Figure 3 that transposes all 2 × 2-submatrices of a 4 × 4-matrix is obtained from the program transpose(2) that transposes a 2 × 2-matrix by the following statement:

    replicate(transpose(2), 2, 2);
Trans­formation mirror

In the matrix transposition algorithm, an exchange of the two upper submatrices is the same as a ring shift of the corresponding rows 1, ..., n/2 by n/2 steps. In Laisa, this is realized by a call of the ring shift program:

procedure exchange_upper(n : integer);
{ exchanges the two upper n/2xn/2-submatrices }
begin(n)
    ringshift_row(n, n/2, [1..n/2]);
end;

An exchange of the two left submatrices can be done in essentially the same way. The corresponding program is obtained by mirroring the above program at the main diagonal.

procedure exchange_left(n : integer);
{ exchanges the two left n/2xn/2-submatrices }
begin(n)
    mirror(exchange_upper(n));
end;

The operation mirror is again a program transformation. It exchanges row selectors with column selectors and, in instructions, replaces all occurrences of CE by CS and all occurrences of CW by CN, and vice versa.

Laisa program for matrix transposition

The following Laisa program realizes the transposition of an n × n-matrix.

procedure transpose(n);
begin(n)
    if n>1 then
    begin
        { transpose the four n/2xn/2-submatrices }
        replicate(transpose(n/2), 2, 2);
        { exchange upper right with lower left submatrix }
        exchange_upper(n);
        exchange_left(n);
        exchange_upper(n);
    end
end;

 

Next:   [Sorting]   or   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 09.09.2002   Updated: 20.06.2018
Valid HTML 4.01 Transitional