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.
A transposition of an n × nmatrix can be done recursively in the following way, assuming that n is a power of 2:
Procedure transpose(n)  
Input:  n × nmatrix A 
Output:  transposed n × nmatrix A^{T} 
Method: 

Figure 1 shows how a 2 × 2matrix 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 2x2matrix  
On the ISA, the following program performs a transposition of the upper left 2 × 2submatrix.
Figure 2: Transposition of a 2x2matrix on the ISA 
The next program is quite similar, it transposes all four 2 × 2submatrices. The sequence of instructions is the same as before, but the row and column selectors have been duplicated.
Figure 3: Transposition of all 2x2submatrices 
This program is obtained from the first program by the program transformation replicate. This operation takes a program p for a k × karray and two numbers r and s as arguments and puts sidebyside 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 × 2submatrices of a 4 × 4matrix is obtained from the program transpose(2) that transposes a 2 × 2matrix by the following statement:
replicate(transpose(2), 2, 2); 
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/2submatrices } 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/2submatrices } 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.
The following Laisa program realizes the transposition of an n × nmatrix.
procedure transpose(n); begin(n) if 
Next: [Sorting] or 
H.W. Lang Hochschule Flensburg lang@hsflensburg.de Impressum Datenschutz © Created: 09.09.2002 Updated: 20.06.2018 