Feedback directed implicit parallelism

ABSTRACT

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 support the full Concurrent Haskell language compiled with traditional optimizations and including I/O operations and synchronization as well as pure computation. We use 20 of the larger programs from the 'nofib' benchmark suite. The limit study shows that programs vary a lot in the parallelism we can identify: some have none, 16 have a potential 2x speed-up, 4 have 32x. In practice, on a 4-core processor, we get 10-80% speed-ups on 7 programs. This is mainly achieved at the addition of a second core rather than beyond this.

This approach is therefore 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.

REFERENCES

• 1: Arvind, David E. Culler, and Gino K. Maa. Assessing the benefits of fine-grained parallelism in dataflow programs. Technical Report 279, Computation Structures Group, MIT, March 1988.
• 2: K. E. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computing Conference, 1969.
• 3: R. Blumofe and C. Leiserson. Scheduling multithreaded computations by work stealing. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico., pages 356--368, November 1994.
• 4: Robert Ennals. Adaptive Evaluation of Non-Strict Programs. PhD thesis, Cambridge University Computer Laboratory, 2004.
• 5: Robert Ennals , Simon Peyton Jones, Optimistic evaluation: an adaptive evaluation strategy for non-strict programs, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.287-298, August 25-29, 2003, Uppsala, Sweden
• 6: Kevin Hammond. Parallel functional programming: An introduction. In International Symposium on Parallel Symbolic Computation, Hagenberg/Linz, Austria, September 1994.
• 7: Timothy L. Harris, Dynamic adaptive pre-tenuring, ACM SIGPLAN Notices, v.36 n.1, p.127-136, Jan 2001
• 8: Tim Harris , Simon Marlow , Simon Peyton Jones, Haskell on a shared-memory multiprocessor, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.49-61, September 30-30, 2005, Tallinn, Estonia [doi>10.1145/1088348.1088354]
• 9: Danny Hendler, Yossi Lev, Mark Moir, and Nir Shavit. A dynamic-sized nonblocking work stealing deque. Technical Report TR-2005-144, Sun Microsystems Laboratories, 2005.
• 10: Raj Jain. The art of computer systems performance analysis. Wiley, 1991.
• 11: H-W. Loidl. Granularity in Large-Scale Parallel Functional Programming. PhD thesis, Department of Computing Science, University of Glasgow, March 1998.
• 12: James Stewart Mattson. An effective speculative evaluation technique for parallel supercombinator graph reduction. PhD thesis, University of California at San Diego.
• 13: Implicit parallel programming in pH, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 14: Randy B. Osborne, Speculative computation in multilisp, Proceedings of the 1990 ACM conference on LISP and functional programming, p.198-208, June 27-29, 1990, Nice, France [doi>10.1145/91556.91644]
• 15: Simon Peyton Jones , Andrew Gordon , Sigbjorn Finne, Concurrent Haskell, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-308, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237794]
• 16: Paul Roe. Parallel Programming Using Functional Languages. PhD thesis, Department of Computing Science, University of Glasgow, 1991.
• 17: Kenneth R. Traub, Implementation of non-strict functional programming languages, MIT Press, Cambridge, MA, 1991
• 18: Kenneth R. Traub , Gregory M. Papadopoulos , Michael J. Beckerle , James E. Hicks , Jonathan Young, Overview of the Monsoon Project, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.150-155, October 14-16, 1991
• 19: P. W. Trinder , K. Hammond , H.-W. Loidl , S. L. Peyton Jones, Algorithm + strategy = parallelism, Journal of Functional Programming, v.8 n.1, p.23-60, January 1998 [doi>10.1017/S0956796897002967]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Languages, Performance

Keywords:
functional programming, haskell, implicit parallelism