Go to  ECE459   Experiment   |   1   |    2  |    3    |    4    |   Lab manuals   |   ECE Lab home

ECE459 Advanced Computer System Design Lab

Chapter 2

Experiment 2

Systolic-Array Implementation of Matrix-By-Matrix Multiplication

2.1   Objective

The multiplication of matrices is a very common operation in engineering and scientific problems. The sequential implementation of this operation is very time consuming for large matrices; the brute-force solution results in computation time O(n³), for n x n matrices. For this reason, several parallel algorithms have been developed to solve this problem more efficiently. Here, a simple parallel algorithm is presented for this problem and a "hardwired" (actually, systolic-array) implementation of the algorithm becomes our objective.

 

The two matrices A and B are shifted into the boundary processors in column 1 and row 1, respectively, as shown in Figure 2.2. The leading and trailing 0s in rows and columns are employed so that elements a_ir and b_rj arrive at processor P_ij simultaneously for the operation  a_ir ●  b_rj  to be performed. c_ij is initialized to 0 in P_ij , for all   i,  j  = 1, 2, 3, 4.  At the end, processor P_ij will contain c_ij , for   1 ≤  i, j   ≤  4

Whenever a processor P_ij receives two inputs b and a from the north and the west, respectively, it performs the following set of operations, in this order:

1. it calculates a ● b;

2. it adds the result to the previous value c_ij , and stores the result  in  c_ij ;

3. it sends  a     to     P_i,j+1,         unless j = 4;  and

4. it sends  b      to     P_{i + 1, j},      unless i = 4.

This algorithm takes time O(n), for  n  x  n  matrices.

 

Figure 2.2: A  4 x 4 mesh (systolic array) of processors for matrix multiplication.

 

Go to  ECE459   Experiment   |   1   |    2  |    3    |    4    |   Lab manuals   |    ECE Lab home