# 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 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: if n>1 then transpose the four n/2 × n/2-submatrices 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

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

 H.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 09.09.2002   Updated: 20.06.2018