Subject: Re: FW: Assign 4 Question

From: "Zheng, Qiang" <[email-masked]>
Date: Tue, 28 Mar 2000 14:47:58 -0500 (EST)

> Can you say few more words to the list on why the use of more nodes
> is more efficient than fewer nodes?

Say, if we have x[0] to x[3], y[0] to y[3] in one node, and
x[4] to x[7], y[4] to y[7] in another node.

The two solutions:

First one is:
for(i=lower_x; i<upper_x; i++) {
  SUM_X[i] = 0.0;
  for ( j=lower_y; j<upper_y; i++ ) {
    SUM_X[i] += x[j] * x[j] + y[i] * y[i]; 
    /* communicate for remote data here */
    ...
  }
}

and 

The second one with the ring topology communication.
for(j=lower_y; j<upper_y; j++) {
  for ( i=lower_x; i<upper_x; i++ ) {
    SUM_X[I] += y[j] * y[j] + x[i] * x[i];
  }
  /* communicate for remote data here */
  ...
}

for ( i=lower_x; i<upper_x; i++)
  SUM += SUM_X[I]

The above two solutions almost have no difference in communication cost if
only two nodes involved in computing because they only need to communicate
once if the data block is big enough. 

And it is somehow apparent that the communication in inner loop is much
worse than comminication in outer loop because the cost is much higher. In
the first solution, the communication cost is about O(p^2) and the latter
one is O(p). p is the number of processors here. So the more nodes, the more
efficient the latter solution is compared to the first solution.

Thank you.

Zheng, Qiang