2
$\begingroup$

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

enter image description here

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]$

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The explaination is ok but video in this post is quite not matched in the algo. please check this, youtube.com/watch?v=eK5fjuEFJu0. In my algorithm, the W matrix is allocated in inside the systolic array already. $\endgroup$ Jun 7, 2019 at 9:19
  • $\begingroup$ 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. $\endgroup$
    – Duns
    Jun 7, 2019 at 14:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .