Subject: "Limits to implicit parallelism in functional applications"
Date: Sunday 31st December 2006 00:29:18 UTC (over 10 years ago)
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