Instruction systolic array (ISA)

Program transformations


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 ntimesn-matrix can be done recursively in the following way, assuming that n is a power of 2:


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


Figure 1 shows how a 2times2-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.


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 2times2-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 2times2-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
Transformation replicate

This program is obtained from the first program by the program transformation replicate. This operation takes a program p for a ktimesk-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 2times2-submatrices of a 4times4-matrix is obtained from the program transpose(2) that transposes a 2times2-matrix by the following statement:

    replicate(transpose(2), 2, 2);
Transformation 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 }
    ringshift_row(n, n/2, [1..n/2]);

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 }

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 ntimesn-matrix.

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



Next:   [Sorting]   or   up


homeH.W. Lang   FH Flensburg   Impressum   ©   Created: 09.09.2002   Updated: 11.10.2008
Valid HTML 4.01 Transitional