🚀 go-pugleaf

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