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