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

Figure 1 shows how a 22matrix 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 22submatrix.
Figure 2: Transposition of a 2x2matrix on the ISA 
The next program is quite similar, it transposes all four 22submatrices. 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 kkarray 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 22submatrices of a 44matrix is obtained from the program transpose(2) that transposes a 22matrix 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 nnmatrix.
procedure transpose(n); begin(n) if 
Next: [Sorting] or 
H.W. Lang FH Flensburg lang@fhflensburg.de Impressum © Created: 09.09.2002 Updated: 11.10.2008 