Go to  COE498   Experiment   |   1   |    2  |    3    |    4    |     Part List    |   Lab manuals   |   ECE Lab home

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

2-dimensional, mesh-connected parallel computers are often used in systolic-array configuration for the multiplication of matrices. For the sake of simplicity, we assume input matrices of size 4 x 4 containing one-bit integer elements. Figure 2.1 shows the operations to be performed. The ● and + represent the integer operations multiplication and addition, respectively.

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:

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

 

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.

Go to  COE498   Experiment   |   1   |    2  |    3    |    4    |     Part List    |   Lab manuals   |   ECE Lab home