Subject: Re: FW: Assign 4 Question

From: "Zheng, Qiang" <[email-masked]>
Date: Fri, 24 Mar 2000 11:01:30 -0500 (EST)

On Thu, 23 Mar 2000, Quant Marjorie V 2dLt AFRL/IFSB wrote:

> I need some clarification on assignment 4.  As I understand the problem, we
> are to sum a "function" between two particles of a system.  There are a
> total of N values for the particles in the system, so we must calculate the
> sum for each x[N] and y[N] (are we not doing this calculation twice, once
> from the x side and then once again from the y side?).  I have several
> questions:

Actually this is different from N-body problem because there are two
groups of entities, the entity in one group only correlates to the
entities in the other group. Each group contains N entities.

The task is to find out the sum of all the correlations.

The correlation between a pair of entities, say a and b, is expressed as:

f(a,b) = (a*a + b*b)

Each entity has a correlation with all the entities in the other group,

so if the first group of entities are stored in array x, and the second
stored in y, then, the sum of correlations in x[i] (0<=i<N) is:

{
  SUM_X[i] = 0.0;
  for ( j=0; j<N; j++ )
    SUM_X[i] += x[i] * x[i] + y[j] * y[j];
}

And the sum for all the correlation is:

for(i=0; i<N; i++) {
  SUM_X[i] = 0.0; 
  for ( j=0; j<N; j++ )
    SUM_X[i] += x[i] * x[i] + y[j] * y[j];
  SUM += SUM_X[i];
}

Then, SUM is the solution. No need to calculate twice.

> *(UNDER THE SECTION ENTITLED "CORRELATION PROBLEM") The problem seems to
> contradict itself by first saying that you should take the summation over j,
> from 0 to N of f(x[i],y[j]); where only the j component (and thus y) is
> changing for one x...the x[i] is the outer loop.  Later in the assignment,
> the instructions explain that this is the "very bad message passing
> algorithm" ..you should instead set y[j] as the outer loop.

The homework is not contracting itself. It says we have two ways to
perform the calculation, one is to use x[i] as outer loop. Like the
example I gave in above. The other solution is to switch the above loops,
like the following:

for(j=0; j<N; j++) {
  SUM_Y[j] = 0.0;
  for ( i=0; i<N; i++ )
    SUM_Y[j] += y[j] * y[j] + x[i] * x[i];
  SUM += SUM_Y[j];
}

The difference of the two solutions is that one will result in more
communications, which is undesired, please see "very bad/much better
message passing parallel program" for details.

> *I am unsure as to what the function we are summing over should be; is
> it f(a,b) = [a^2+b^2]?  If so, is y[j] an array to hold all values of
> b^2? Should the function read f(a[i],b[j]) = (a[i]^2+b[j]^2)? x[i] an
> array to hold all values for a^2 and

Since f(a,b) = a*a + b*b

We have f(x[i],y[j]) = x[i] * x[i] + y[j] * y[j]

a, b are just normal variables in two groups, the meaning is general, x
and y are arrays to contain two groups of entities.

> *What exactly are we computing with (a^2+b^2)?  Should this be a distance
> (such as the sqrt of (a^2+b^2))?

I don't know what is the meaning of a*a + b*b. I believe it is a function
randomly picked up.

Thank you.

---

From: "Zheng, Qiang" <[email-masked]>
Date: Fri, 24 Mar 2000 11:01:30 -0500 (EST)

f(a,b) = (a*a + b*b)

{
  SUM_X[i] = 0.0;
  for ( j=0; j<N; j++ )

for(i=0; i<N; i++) {
  SUM_X[i] = 0.0; 
  for ( j=0; j<N; j++ )

for(j=0; j<N; j++) {
  SUM_Y[j] = 0.0;
  for ( i=0; i<N; i++ )

Since f(a,b) = a*a + b*b

Thank you.

---

From: "Zheng, Qiang" <[email-masked]>
Date: Fri, 24 Mar 2000 11:57:47 -0500 (EST)

I have misunderstanding of the order of loop in my last email. Please use
this one as correct explanation. Thank you.

> *Are both x[i] and y[j] separated onto n processors?  Then x[i] is
> calculated while y[j] is passed in a ring through all the processors until
> the original y[j] values return to the original processor, then the next
> x[i+1] value is computed?

Yeah, they both do.

For the second question, the above implies the very bad algorithm.

The interesting thing is how we design the communication model to keep the
overhead as small as possible.

Say, we have entities x[0] to x[3], y[0] to y[3] in processor 0 
and we have entities x[0] to x[4], y[4] to y[7] in processor 0 

We want to find out the SUM of correlation, first we calculate the sum of
correlation in each x[i]. Then in each processor, we have the following
loop:

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];
}

Here, we should notice that for the entities in array y, it is possible
that they are located in another processor. so we need to get y's value
remotely. But if we change the loop in each node as the following:

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];
  }
}

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

And if we design the communication as a ring, we can see, since the y is
in outer loop, every time when a block of y is sent to a processor from
remote processor, the local node takes full advantage of it. Thus, each
block of y only is sent to each processor once. Another difference is that
all the SUM_X[I], before all the computing finishes, are not complete.

Is that clear? Thank you.

---

From: "Zheng, Qiang" <[email-masked]>
Date: Fri, 24 Mar 2000 11:57:47 -0500 (EST)

Yeah, they both do.

---

From: "Zheng, Qiang" <[email-masked]>
Date: Fri, 24 Mar 2000 12:09:13 -0500 (EST)

>     SUM_X[i] += x[i] * x[i] + y[j] * y[j];

I forgot to emphasize that we only need to compute the SUM from SUM_X[i],
we don't need to compute SUM from SUM_Y[j]. They are different things.

> message passing parallel program" for details.

Thus, this explanation is wrong. For here, if we find out SUM from SUM_Y,
the communication is the same as the one above. As to the reason why
changing the order of two loops can reduce the comminication, please see
my last email. Please notice that that solution is more effirient when
the number of nodes are large.

Thank you.

---

From: "Zheng, Qiang" <[email-masked]>
Date: Fri, 24 Mar 2000 12:09:13 -0500 (EST)

Thank you.