How does "do in parallel" work

Question

currently i'm preparing for an exam in a high performance computing course. In this course we discuss several common parallel algorithm patterns called "dwarfs". The first dwarfs we had was the "dense linear algebra", so basically matrix multiplication. In one of the first slides there is a example for a basic matrix multiplication:

MatrixMult PRAM(A:Matrix[n], B:Matrix[n], C:Matrix[n]) {
for i from 1 to n do in parallel
    for k from 1 to n do in parallel
        for j from 1 to n do
            C[i,k] = C[i,k] + A[i,j]∗B[j,k]
}

Nothing really fancy, just the basic matrix multiplication. But below this piece of code the slide states:

• synchronized execution of the for-j-loop;

→ in the first step:

• all processors $P_{i,k}$ simultaneously access A[i,1]

• all processors $P_{i,k}$ simultaneously access B[1,k]

I don't understand why all processors access these elements at the same time. I thought every processor has a different value for i and k, so every processor should access a different element. For example, n=3:

1. Time step (execute first for loop in parallel on all P):
   • P1 -> i = 1
   • P2 -> i = 2
   • P3 -> i = 3
2. Time step (execute second for loop in parallel on all P):
   • P1 -> k = 1
   • P2 -> k = 2
   • P3 -> k = 3
3. Time step (execute third for loop sequential on all P):
   • P1 -> j = 1, i=1, k=1 ==> A[1,1] B[1,1]
   • P2 -> j = 1, i=2, k=2 ==> A[2,1] B[1,2]
   • P3 -> j = 1, i=3, k=3 ==> A[3,1] B[1,3]
4. Time step:
   • P1 -> j = 2
   • P2 -> j = 2
   • P3 -> j = 3
5. etc..

So in the third time step every processor would access another element. So i'm not quite sure if i understand the "do in parallel" statement correct. I thought that every statement in this loop would be executed on every processor but with different index as Joseph JáJá defines the "pardo statement" (i think it's the same like "do in parallel") as follows:

for l $\leq$ i $\leq$ u pardo statement

The statement (which can be a sequence of statements) following the pardo depends on the index i. The statement corresponding to all the values of i between l and u are executed concurrently (from "An Introduction to parallel algorithms", Jospeh JáJá page 27)

So the question is, why do all processors access the same element and how does the "do in parallel" statement work? I'm not sure if i understood this statement.

Answer 1

Two consequent parallel loops maybe joined like "product", so this code can be effectively parallelized up to $n^2$ (9 in your example) processors. Each such processor can be indexed by $i,k$ pair.

Now,

all processors $P_{i,k}$ access simultaneously $A[i,1]$

means that all processors which have the first index equal to $i$ and second index equal to anything (to some $k$ but it does not restrict the cell), will simultaneously access $A[i,1]$. In your example, you parallelize only by $i$ (first for loop), so you have only one processor per each such cell. If you parallelize completely (by pairs $(i,k)$), you will have $n$ processors per each such cell.