[comp.lang.functional] performance of array comprehensions in Id

jashley@lanl.gov (J. Michael Ashley) (07/04/90)

i'm disappointed with the implementation of array comprehensions in 
dataflow architectures.  Consider this code:

Def shuffle v =
{
  (_, size) = bounds v ;
  middle    = fix (size / 2) ;
In
  ({ array (1, middle) | [i] = v[i*2-1] || i <- 1 to middle },
   { array (1, middle) | [i] = v[i*2]   || i <- 1 to middle })
} ;

It turns out that the i's get generated sequentially, which is really
too bad since there is no data dependency between the elements of the two
arrays being built.

I can accept this, but MIT's very fine GITA software tells me that this
is the bottleneck of my FFT code.  I'd like to rewrite it to be a little
more parallel.  I haven't been very satisfied so far.

So, has anybody else come across this sort of problem, and if so, have they
worked out a solution?  I know that I am not the only one at LANL concerned
with this problem.

Thanks

--
J. Michael Ashley              internet: jashley@lanl.gov
Los Alamos National Labs                 ashley@occs.cs.oberlin.edu

tve@sprite.berkeley.edu (Thorsten von Eicken) (07/07/90)

In article <55973@lanl.gov> jashley@lanl.gov (J. Michael Ashley) writes:
>In
>  ({ array (1, middle) | [i] = v[i*2-1] || i <- 1 to middle },
>   { array (1, middle) | [i] = v[i*2]   || i <- 1 to middle })
>} ;
>
>It turns out that the i's get generated sequentially, which is really
>too bad since there is no data dependency between the elements of the two
>arrays being built.

Well, what do you expect?  I don't think anyone has come up with an
ALU that can generate all values for i at once...
Seriously, the "optimal" solution would be to generate the i's in
a tree, but we've found that it's usually sufficient to recode the
loop as two nested loops. Let the outer one go by large increments and
the inner one fill the in-betweens. For example:
{ array (1, mid) | [i] = v[i*2-1] || i <- j to j+15 & j <- 1 to mid by 16}
(I realize I'm not worrying about the bounds very much).

>Thanks
>
>--
>J. Michael Ashley              internet: jashley@lanl.gov
>Los Alamos National Labs                 ashley@occs.cs.oberlin.edu

Hope that helps you a bit...
---
Thorsten von Eicken		tve@sprite.berkeley.edu
Computer Science Div.
UC Berkeley