performance of array comprehensions in Id

Thread View: comp.lang.functional

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by J. Michael Ashley Wed, 04 Jul 1990 16:37

#330

Author: J. Michael Ashley
Date: Wed, 04 Jul 1990 16:37

29 lines
1359 bytes

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

Re: performance of array comprehensions in Id

#331

Author: Thorsten von Eicken
Date: Sat, 07 Jul 1990 08:39

30 lines
1699 bytes

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

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads