1
$\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$
0
$\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$
  • $\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$ – chickensoup Jun 7 '19 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$ – Dunkel Jun 7 '19 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.