🚀 go-pugleaf

I don't think array initialization such as the one described is necessarily
linear.  If we think of an array as a monolithic object, then yes the updates
must happen sequentially.  However if the array is somehow divided into
pieces, it is clear that we know which updates could affect a given piece, so
the pieces can be constructed independently, although it takes time to put
them together.

There are simple algorithms to do insertion and deletion in arrays, but they
become slow with large arrays.  To avoid linear time in such operations you
have to use more sophisticated data structures, using a divide-and-conquer
approach.  The array is hierarchically broken down into smaller pieces which
are better handled with simple algorithms.  This sort of indexing is done by
B-trees, 2-3 trees, splay trees, etc.

It is interesting that this same change also solves the parallelism problem.
The initialization of the array will follow the structure of the data
structure, because the different parts at each node in the hierarchy can be
done independently.

This does it in logarithmic time, which is the best we can do assuming that in
a given amount of time a computation can only fork off a limited number of
parallel sub-computations.

jashley@silver.ucs.indiana.edu (J. Michael Ashley) writes:

>Put aside dataflow for a minute.  Just assume we have a lazy language.  Then
>the question now is not whether init1 is strict in its first argument, but
>whether or not update is strict in its first argument.  I think it is, so
>this simple version of init1 is sequential.

Yes, thats right. init1 is strict in its first argument, if update
is (seufz). But if we assume, that the first argument of init1 is
evaluated lazy (what I wanted to say), then there IS no 
reason why init1 should block through the calculation of update or
one of its Arguments. In general sub-calculations may be parallized
over recursion levels, if the induction variable(s) do not depend on
them.

>using dataflow, it is certainly sequential!

Maybe. You probably need a hybrid. The pure dataflow model ist just
(nice) theory.

>it's an easy optimization to make init1 run O(log n) using a divide and
>conquer algorithm.  this can be done since i-structures are being used to
>represent arrays.  no analysis is necessary.

O(log n) isnt really good. Its mandatory to exploit (at least partial
available) linear memory. The key of effience in imperative languages are
arrays with access O(1) und update O(1), and effience (BTW, imperative
languages too) makes the world go around. You can have O(1) access in functional
languages, providing you have builtin or handcoded array structures,
and O1(1) update in the lucky exclusive case, if you additionally have sharing 
analysis or reference counting (I heard, some people have observed the 
lucky case appears >60% with standard problems).

The main problem is not wheter O(xyz) or inherent parallelism, but the
underlying machine structure. Having ($$$) MIMDs with shared memory, 
then it would be a good idea to parallize the initialization maximal 
(unless you know, the initializer is trivial). Having loosely coupled
MIMDs, you must carefully estimate the comm. effort against the
initializer effort. I guess, on l.c. MIMDs parallel array 
initialization is an exotic case, and pipeling of streams is the
case of interest.

>constructing the index list by concatenating sublists is usually what happens,
>so the analysis won't work.  at any rate, even if it could theoretically work,
>i bet it would take forever to do the analysis on real codes.

Dont be so pesimistic, Michael! Its not the question of forever, but, say,
10 user minutes against 0.5 for a medium module. For example, full 
unification is much more expansive.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Wolfgang Grieskamp 		-fullOpt    => *compiler* thinks:
				"lazy or not lazy, this is here the question!"
wg@opal.cs.tu-berlin.de      tub!tubopal!wg            wg%opal@DB0TUI11.BITNET