Previous | Next --- Slide 38 of 70
Back to Lecture Thumbnails

The intuition Professor Kayvon gave for this schedule: The amount of computation done by each processor is proportional to the area of the region it's assigned to. The amount of communication done by each processor is proportional to the perimeter of the region it's assigned to. How do we maximize the ratio of area:perimeter over all the processors? We can give each processor equally sized squares in the grid.


Why is elements computed per processor N/P^(1/2)=12/3=4? For instance, I thought P1 had to communicate 4 elements to P2 and 4 elements to P4.


I think the slide is saying that the elements communicated is on the order of $\dfrac{N}{\sqrt{P}}$, not exactly equal. The scale factor for this example should be around 4 since there are 4 side to communicate. Also, squares along the edges will have less to communicate.


So in the worse case for each grid, they need to communicate top, bottom, left, right. Notice that each edge of the box has N/sqrt(P) elements. Hence the amount is upper bounded by 4N/sqrt(P).