Abstract Feedback directed implicit parallelism

In this paper we present an automated way of using spare CPU resources within a shared memory multi-processor or multi-core machine. Our approach is (i) to profile the execution of a program, (ii) from this to identify pieces of work which are promising sources of parallelism, (iii) recompile the program with this work being performed speculatively via a work-stealing system and then (iv) to detect at run time any attempt to perform operations that would reveal the presence of speculation. We assess the practicality of the approach through an implementation based on GHC 6.6 along with a limit study based on the execution profiles we gathered. We use 20 of the larger programs from the ‘nofib ’ benchmark suite as tests. The limit study shows that programs vary a lot in the parallelism we can identify: some have none, several have a potential 2x speedup, one has 32x. In practice, our implementation running on quad-core processor, shows 10-80 % speedups on several programs. We support the full Concurrent STM Haskell language compiled with traditional optimizations and including IO operations and synchronization as well as pure computation. This approach is not a replacement for manual parallelization, but rather a way of squeezing extra performance out of the threads of an already-parallel program or out of a program that has not yet been parallelized. 1