Re: Unpopular parameter passing mechanisms and parallelisation (was Re: sequential binary parallelization at run-time)

On Sun, 28 Oct 2007 19:06:41 +0000, Anton Lokhmotov <al407@cam.ac.uk>
wrote:


>George Neuner wrote:
>> I been thinking about adaptive parallelization for a while and my
>> own opinion, FWIW, is that the right way to accomplish it on
>> close-coupled shared memory systems is to aggressively compile
>> call-by-need, make each call-by-need function an independently
>> schedulable entity (ie. a microthread), and structure the code as a
>> state machine graph of microthreads ordered by data dependencies...
>
>> Few languages currently implement call-by-need and those that do try
>> to avoid it as much as possible because aggressively creating
>> functions is inefficient for a single CPU.
>
>It's interesting you mention that call-by-need (CBN) parameter passing
>semantics is not particularly popular today. I'm not an expert in CBN
>but my impression that it only makes sense in functional languages (or
>languages allowing to specify that a function is pure, i.e. does not
>have side-effects), ...


Not quite. CBN (actually Lazy Memoized (LM)CBN) is associated these
days with Haskell, but it can be used relatively easily with any
mostly functional source - it does not require the language to have
either purity or lazy evaluation. As long as you can impose a total
ordering on dependent computations, you can use it.


And functional languages are closer than you might think - it turns
out that compilers like functional languages better than imperative
ones and many important IR transformations are meant to
"functionalize" it where necessary. For example, performing the SSA
transform on an imperative program produces an equivalent functional
program (though at such a low level most people overlook it). Even
the simpler technique of value numbering produces a mostly functional
result. Likewise, performing the CPS transform on a program produces
a more functional program as a result.




>... and we know that functional programs are well-suited for
>parallelisation.


Actually the current crop of functional languages were designed for
serial computation and much of the parallelism inherent in programs is
well hidden. Compiling for CBN exposes potential parallelism, but the
dependency chains are backward ... suitable for demand execution (lazy
evaluation) but not for forward chaining eager evaluation strategies.




>As for imperative programming, another undeservedly abandoned
>parameter passing semantics is call-by-value-result (CBVR). In CBVR,
>writes to the caller's memory by the callee do not happen until the
>callee returns but the callee keeps track of them.
      :
<snip examples>
      :
>This semantics is similar to that of vector assignment statements in
>Fortran 90 (which we discussed here around August) and allows the
>callee's code to be automatically parallelised even if it contains
>references or pointers that can potentially alias (which complicates
>dependence analysis in mainstream programming languages).


Fortran's semantics were designed to correspond with the behavior of
real hardware - serial pipelined vector processors. If the vector was
longer than the hardware pipeline than CBVR was violated - results
would be written back before the entire vector could be read.
Nowadays we don't even have the vector processors, the SIMD units in
todays CPUs don't have the same semantics. Additional temporary
storage is almost always required to get the desired behavior.


For vector processing, CBVR is mostly an intellectual convenience for
the programmer rather than a useful execution strategy. It doesn't
buy you any more than other vector methods.


As a parameter passing method, CBVR was deprecated because most
programmers found it confusing.


George

Return to the comp.compilers page.
Search the comp.compilers archives again.