Path: utzoo!attcan!uunet!mcsun!unido!tub!tubopal!wg From: wg@opal.cs.tu-berlin.de (Wolfgang Grieskamp) Newsgroups: comp.lang.functional Subject: Re: Id array comprehensions revisited Message-ID: <1671@opal.tubopal.UUCP> Date: 21 Jul 90 07:33:02 GMT References: <51369@iuvax.cs.indiana.edu> Sender: news@tubopal.UUCP Reply-To: wg@opal.cs.tu-berlin.de Followup-To: comp.lang.functional Organization: Technical University of Berlin Lines: 54 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