Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!lanl!jashley
From: jashley@lanl.gov (J. Michael Ashley)
Newsgroups: comp.lang.functional
Subject: performance of array comprehensions in Id
Keywords: dataflow
Message-ID: <55973@lanl.gov>
Date: 4 Jul 90 16:37:06 GMT
Organization: Graceland
Lines: 29

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