[Haskell] "Limits to implicit parallelism in functional applications"

[John DeTreville]

Hello,

True or False? "Many interesting functional applications contain
significant amounts of implicit parallelism that we can imagine usefully
exploiting." I've recently written a short paper about how much implicit
parallelism there might be in ordinary functional applications. Here's
an abstract.

    Today's sequential software is executed more and more often on
    parallel hardware from which it obtains no incremental performance
    benefit. We can address this mismatch by rewriting old software,
    and writing new software, in an explicitly parallel style that is
    better suited to the hardware, or we might take advantage of any
    implicit parallelism already present in the sequential software.
    While it is imagined that there might be useful amounts of implicit
    parallelism in many common applications, particularly in
    applications written in non-strict functional languages, finding and
    exploiting it has proven difficult. We have performed a novel limit
    study to measure the implicit parallelism in one large realistic
    application written in a non-strict functional language, and find
    that the amount of implicit parallelism is relatively small. We have
    also analyzed the measurements to find bottlenecks in the
    application that limit its implicit parallelism, and we describe how
    small rewrites directed by these analyses can increase the amount of
    implicit parallelism available. We also outline ways in which
    control speculation might help to exploit further implicit
    parallelism.

The aforementioned limit study measures the execution of the NHC98
compiler using the Hat tracer and a few extra pieces. I'd appreciate
comments. A draft of the paper is (should be) available at
http://www.detreville.org/papers/Limits.pdf, modulo any embarrassing
typos on my part.

Cheers,
John