(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]$
Best Answer
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
Regarding your questions:
$[(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 would also recommend this other video, if you need to learn more: https://www.youtube.com/watch?v=cmy7LBaWuZ8.