Haskell on a shared-memory multiprocessor

ABSTRACT

Multi-core processors are coming, and we need ways to program them. The combination of purely-functional programming and explicit, monadic threads, communicating using transactional memory, looks like a particularly promising way to do so. This paper describes a full-scale implementation of shared-memory parallel Haskell, based on the Glasgow Haskell Compiler. Our main technical contribution is a lock-free mechanism for evaluating shared thunks that eliminates the major performance bottleneck in parallel evaluation of a lazy language. Our results are preliminary but promising: we can demonstrate wall-clock speedups of a serious application (GHC itself), even with only two processors, compared to the same application compiled for a uni-processor.

REFERENCES

• 1: Alpha Architecture Handbook. Compaq Computer Corporation, 4th edition, Oct. 1998.
• 2: Joe Armstrong, The development of Erlang, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.196-203, June 09-11, 1997, Amsterdam, The Netherlands
• 3: Lennart Augustsson , Thomas Johnsson, Parallel graph reduction with the (v , G)-machine, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.202-213, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99386]
• 4: R. Ennals. Adaptive Evaluation of Non-String Programs. PhD thesis, Cambridge University Computer Laboratory, 2004.
• 5: C. Flood, D. Detlefs, N. Shavit, and C. Zhang. Parallel garbage collection for shared memory multiprocessors. In USENIX Java Virtual Machine Research and Technology Symposium, Monterey, CA, Apr. 2001.
• 6: K. Fraser. Practical lock freedom. PhD thesis, Cambridge University Computer Laboratory, 2003.
• 7: Kevin Hammond , Greg Michelson, Research Directions in Parallel Functional Programming, Springer-Verlag, London, 2000
• 8: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 9: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 10: R. Jones. Tail recursion without space leaks. Journal of Functional Programming, 2(1):73--80, Jan 1992.
• 11: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 12: Kiyokuni Kawachiya , Akira Koseki , Tamiya Onodera, Lock reservation: Java locks can mostly do without atomic operations, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 13: H.-W. Loidl , F. Rubio , N. Scaife , K. Hammond , S. Horiguchi , U. Klusik , R. Loogen , G. J. Michaelson , R. Peña , S. Priebe , Á J. Rebón , P. W. Trinder, Comparing Parallel Functional Languages: Programming and Performance, Higher-Order and Symbolic Computation, v.16 n.3, p.203-251, September 2003 [doi>10.1023/A:1025641323400]
• 14: Virendra J. Marathe , William N. Scherer , Michael L. Scott, Design tradeoffs in modern software transactional memory systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-7, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066660]
• 15: Simon Marlow , Simon Peyton Jones , Wolfgang Thaller, Extending the Haskell foreign function interface with concurrency, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA [doi>10.1145/1017472.1017479]
• 16: Simon Marlow , Simon Peyton Jones , Andrew Moran , John Reppy, Asynchronous exceptions in Haskell, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.274-285, June 2001, Snowbird, Utah, United States
• 17: Will Partain, The nofib Benchmark Suite of Haskell Programs, Proceedings of the 1992 Glasgow Workshop on Functional Programming, p.195-202, July 06-08, 1992
• 18: S. Peyton Jones. Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell. In C. Hoare, M. Broy, and R. Steinbrueggen, editors, Engineering theories of software construction, Marktoberdorf Summer School 2000, NATO ASI Series, pages 47--96. IOS Press, 2001.
• 19: 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]
• 20: Alastair Reid, Putting the Spine Back in the Spineless Tagless G-Machine: An Implementation of Resumable Black-Holes, Selected Papers from the 10th International Workshop on 10th International Workshop, p.186-199, September 09-11, 1998
• 21: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 22: H. Sutter. A fundamental turn toward concurrency in software. Dr. Dobb's Journal, March 2005.
• 23: 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]
• 24: P. W. Trinder , K. Hammond , J. S. Mattson, Jr. , A. S. Partridge , S. L. Peyton Jones, GUM: a portable parallel implementation of Haskell, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.79-88, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 25: P. W. Trinder , H.-W. Loidl , R. F. Pointon, Parallel and Distributed Haskells, Journal of Functional Programming, v.12 n.5, p.469-510, July 2002 [doi>10.1017/S0956796802004343]
• 26: CORPORATE SPARC International, Inc., The SPARC architecture manual (version 9), Prentice-Hall, Inc., Upper Saddle River, NJ, 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

General Terms:
Languages, Performance