# Systolic Arrays algorithm for matrix multiplication

(I got class with a very fresh professor who I think really bad at teaching/pedagogical skill.) I tried to search but I don't understand this. (He seem to be so busy, and also no TAs, all I want to understand and pass this course). Hope you can help.

This is what he noted in his lecture note:

"Systolic array is a way of realizing the matrix multiplication algorithm with $$n^2$$ processors and $$O(n)$$ time complexity, by $$(i)$$ placing the $$n^2$$ processors in square ($$n \times n$$), and $$(ii)$$ assigning the computation of $$I(i,j)$$, $$A(i,j)$$, and $$O(i,j)$$ to the $$(i,j)$$-th processor. In other words, you may think of systolic array as the combination of $$(i)$$ the matrix multiplication algorithm and $$(ii)$$ a scheduling strategy for $$n^2$$ processors."

What I haven't understand here are:

What is I here? What it for ? How is it look like ? Any example ?
What is A here also ? What it for ? How is it look like ? Any example ?


I just understood a bit about "systolic arrays" by CMU slides. But it's not look the same as what my professor taught.

Also what is this mean ? (In I, A, O)

$$[(i,j) \mapsto 0]$$

The condition $$k = 3n -1$$ gives you the number of times the two matrix will intersect with each other. For a by $$4 \times 4$$ matrix you will have to intersect, multiply and accumulate 11 times. For instance, in this link you can see a short animation. You see that in fact, the process is done 11 times for the shown matrix: https://www.youtube.com/watch?v=sJltBQ4MOHA

$$[(i,j) \mapsto 0]$$: This means an assigment of value zero to the element $$(i,j)$$ of the matrix.
$$I' = [(i,j) \mapsto (i=0) ~ ? ~ X(k-j,j): I(i-1,j)]$$: This means the following. For any element $$(i,j)$$ of matrix I', if the row index $$i = 0$$, then you assign the value of $$X(k-j,j)$$ to I'(i,j). If not (by this I mean $$i \neq 0$$), you assign $$I(i-1,j)$$ to $$I'(i,j)$$.
$$I'$$ is a temporary matrix that collects the elements of $$X$$ that are at the intersection of the two matrices (elements ready for performing operations on them). Thus, the relevant input of $$X$$ is denoted by $$I'$$.
$$A'$$ is an accumulator as you can see in line 12. Each element $$W(i,j)$$ is being multiplied by each element of $$I'(i,j)$$. Recall that $$I'(i,j)$$ is obtained from $$X$$. Thus, we are multiplying $$X$$ and $$W$$ but in a different manner. $$O'$$ is the output matrix. It is moving the accumulated values of $$A'$$ to their correct positions (as if we were multiplying matrices in the standard manner).
• I did not share that link that you refer to. Watch the second link I shared (pay attention to 1:04). You will realize your matrix $W$ has not changed much but as its rows has been shifted and zero-padded. – Dunkel Jun 7 '19 at 14:57