Subject: hpff-task: Re: not atached "new" directive

From: [email-masked] (Chuck Koelbel)
Date: Tue, 2 Jan 1996 11:50:28 -0600

---------------------------------------------------------------------------
[email-masked] is a mailing list for discussion of control-parallel
features in HPF.  Instructions for adding or deleting yourself from this
list appear at the bottom of this message.
---------------------------------------------------------------------------

Hi, Fabien -

Again, a suggestion probably better directed at hpff-task (considering task
and other forms of parallelism) than at hpff-distribute (considering data
mapping)...

>Hi Chuck,
>
>> chpf$ reduce(s)
>>       forall(i=2:n-1)
>>         s = s + a(i)
>>         a(i) = a(i)+a(i-1)+a(i+1)
>>       end forall
>
>The example I just posted on the net reminds me my (really real)
>application with "private" scalars that required a "new" clause outside
>a loop. Forall constructs may also use scalars to avoid redundant
>computations:
>
>chpf$ new(x) ! apply on the next loop, here the forall...
>      forall(i=2:n)
>        x = a(i-1)+2*a(i)+a(i+1) ! x used to store an intermediate value.
>        b(i) = f1(x)             ! some pure function.
>        a(i) = f2(x)             ! idem.
>      end forall
>
>Here the loop is NOT independent and x must be private to each iteration
>for parallelism. I guess the compiler must expand the scalar into an array
>for such a loop. I think that this kind of loop should be allowed by HPF,
>and that it is not with the current definition of forall/new.
>The other way around is to assume that a scalar in a forall *must* be
>private (?) or to perform some analysis to prove it, but I understood that
>one of the goal of the HPF Forum is that no advanced analysis technique is
>needed by compilers for handling HPF.
>
>Hope this help. Have a nice day,
>
>Fabien.

I'm confused what you are asking for.

The intent of FORALL was to provide a different syntax and more general
shapes for array assignments.  This makes it orthogonal to reduction
operators like the one in your first example.  Is it really a problem to
call the SUM intrinsic outside the FORALL?

You could write the second loop as an INDEPENDENT DO loop without trouble.
Why is it vital that you use the keyword FORALL?  Many other cases of
temporary scalars can be handled by declaring a local variable in a PURE
function.  (This doesn't work here, obviously.)

It seems that you want FORALL to be a general-purpose construct for "do
this in parallel".  However, FORALL is something more limited - this was a
concious decision to make the construct simpler.  The INDEPENDENT DO loop
seems to be closer to what you want in any case.

                                                Chuck

---------------------------------------------------------------------------
To (un)subscribe to this list, send mail to [email-masked].
Leave the subject line blank, and in the body put the line
(un)subscribe <email-address>
---------------------------------------------------------------------------

---

From: Fabien COELHO <[email-masked]>
Date: Wed, 3 Jan 96 11:26:00 +0100

Chuck,

> >chpf$ new(x)
> >      forall(i=2:n)              ! NOT independent!
> >        x = a(i-1)+2*a(i)+a(i+1) ! refer to old A values.
> >        b(i) = f1(x)
> >        a(i) = f2(x)             ! new A defined here.
> >      end forall
> >
> >Here the loop is NOT independent [...]
> 
> operators like the one in your first example.

My understanding of "orthogonal" is that two concepts may apply on
something with no special constraint or interaction. This is just my
point! the "reduction", "new" and possibly "on" concepts apply to parallel
loops, whether "independent" or not. I think they also apply on sections
of code, as I argued for the corner computations of my basic seismic
application in a previous mail. I'll argue on that in another mail, 
some day.

> Is it really a problem to call the SUM intrinsic outside the FORALL?

Just a matter of scanning the array once or twice, for the reduction
example. Just cache misses and control overheads issues. Just a
performance problem. (I guess this has to do with HPF:-).

The same remark holds for independent do loops with reductions. You may
call the SUM or PROD or whatever instrinsic outside of the loop instead.
But nevertheless the Forum is considering a "reduction" directive for
independent loops. Why shouldn't it apply also on foralls? Let's discuss
this point:

For the second example, you need to use explicitely a temporary
array do simulate the SIMD execution order, that is you have to declare it
and it may be big, while if the compiler manages it I guess it will be
stack-allocated and the space reused if needed for the next loop. And your
code will be cleaner. 

> Why is it vital that you use the keyword FORALL? 

I'm not promoting the FORALL. It is neither Fortran 77 nor Fortran 90, so
any code that do use a forall cannot be compiled and is not portable apart
on HPF compilers. I hope F95 (F96?) will have the same one? Well...

There are 2 "parallel" loops in HPF. The FORALL may or may not be
"independent", it is nevertheless parallel, with a SIMD execution
order. HPF allows "independent" to characterize these loops, but not "new"
(constraint line 10, page 81 of HPF 1.0). I cannot see why, apart the
history of the proposal, where forall is an extension of the array
assignment syntax. I'm arguing that *if possible*, "new" and "reduction"
and "on" or whatever directive should apply on foralls as well as on do
loops. 

I would summarize the FORALL as a loop for which you don't have to bother
about dependences on a same array because a temporary is managed somehow
by the compiler. If it is independent it should be tagged so because it
helps the compiler by relaxing some potential dependences. As a user I
cannot see obvious reasons to explain why I would be prevented from using
some directives for a loop and not for another, if it does make sense to
do so in my parallel application. If I can write

chpf$ independent, new(x)
      do i=2, n
         x = A(i-1)+2*A(i)+A(i+1)
         B(i) = f1(x)
         C(i) = f2(x) ! C array
       enddo

I should be allowed to write in HPF

chpf$ new(x) ! but NOT independent...
      forall(i=2:n)
         x = A(i-1)+2*A(i)+A(i+1) 
         B(i) = f1(x)
         A(i) = f2(x) ! A array written
      endforall

instead of the explicite temporary management:

      real TMP(n)
chpf$ align TMP with A
      TMP(2:n-1) = A(1:n-2) + 2*A(2:n-1) + A(3:n)
      B(2:n-1) = f1(TMP(2:n-1))
      A(2:n-1) = f2(TMP(2:n-1))

BUT:

A point against my case is that if the FORALL is allowed in some
sequential Fortran, such a loop would not be legal because the "new"
directive is needed for correctness, and I guess no such directive would be
provided to the user. What is actually needed for "new" is the ability to
declare variables local to the body. For reductions, this is a problem.

This issue is not related to HPF as a parallel language. It is related to
"sequential compatibility". It may be THE case against "new" and
"reduction" for foralls. But it is the only one I can see, and the
language loses on expressivity, in my opinion. 

> Many other cases of

You do not necessary want to pay for a function call within the loop nest.

> this in parallel". 

Ya. With a "SIMD" execution order on each assignment. That's the way I
perceive it. 

I've seen codes where the forall is used as the only mean for parallelism,
that is all the computations where simply expressed with foralls, while
they were independent. They were not tagged as independent. Because the
compiler was not analyzing this directive "yet".  I think many people feel
the forall as more powerful and general than the do loop. Proof is that it
is an HPF extension, nothing to do with old Fortran! Joking:-)

> However, FORALL is something more limited - this was a
> concious decision to make the construct simpler. 

You might limit the content of body inside the loop. But I guess my
example make sense, as a point that HPF directives should apply on any
piece of code where it does mean something and it may help the compiler.
Something is lost in the language by disallowing orthogonality.

> The INDEPENDENT DO loop seems to be closer to what you want in any case.

Means I have to manage a temporary array by hand to do something else...
So I'll do it by hand:-)

Conclusion: I think I must give up on "new" and "reduction" directives on
foralls, but the language loses expressivity and orthogonality. If the
forall is not to be considered by some sequential fortran, it should be
allowed in HPF.

I guess it is worth the discussion, at least...

Fabien.

--
Fabien COELHO __ http://www.cri.ensmp.fr/~coelho __ [email-masked]
  CRI, ENSMP, 35, rue Saint Honoré, 77305 Fontainebleau Cedex, France
     phone: 33 1 64 69 {voice: 48 52, fax: 47 09, standard: 47 08}
       ________  All opinions expressed here are mine  ________
---------------------------------------------------------------------------
To (un)subscribe to this list, send mail to [email-masked].
Leave the subject line blank, and in the body put the line
(un)subscribe <email-address>
---------------------------------------------------------------------------