The design of a task parallel library

ABSTRACT

The Task Parallel Library (TPL) is a library for .NET that makes it easy to take advantage of potential parallelism in a program. The library relies heavily on generics and delegate expressions to provide custom control structures expressing structured parallelism such as map-reduce in user programs. The library implementation is built around the notion of a task as a finite CPU-bound computation. To capture the ubiquitous apply-to-all pattern the library also introduces the novel concept of a replicable task. Tasks and replicable tasks are assigned to threads using work stealing techniques, but unlike traditional implementations based on the THE protocol, the library uses a novel data structure called a 'duplicating queue'. A surprising feature of duplicating queues is that they have sequentially inconsistent behavior on architectures with weak memory models, but capture this non-determinism in a benign way by sometimes duplicating elements. TPL ships as part of the Microsoft Parallel Extensions for the .NET framework 4.0, and forms the foundation of Parallel LINQ queries (however, note that the productized TPL library may differ in significant ways from the basic design described in this article).

REFERENCES

• 1: Umut A. Acar, Guy E. Blelloch, and Robert D. Blumofe. The data locality of work stealing. In SPAA '00: Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, pages 1--12, 2000.
• 2: Shail Aditya, Arvind, Lennart Augustsson, Jan-Willem Maessen, and Rishiyur S. Nikhil. Semantics of pH: A Parallel Dialect of Haskell. In Paul Hudak, editor, Proc. Haskell Workshop, La Jolla, CA USA, pages 35--49, June 1995.
• 3: Kunal Agrawal, Yuxiong He, Wen Jing Hsu, and Charles E. Leiserson. Adaptive scheduling with parallelism feedback. In PPoPP '06: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 100--109, 2006.
• 4: Eric Allen, David Chase, Christine Flood, Victor Luchangco, Jan-Willem Maessen, Sukyoung Ryu, and Guy L. Steele Jr. Project fortress: A multicore language for multicore processors. In Linux Magazine, September 2007.
• 5: Nimar S. Arora, Robert D. Blumofe, and C. Greg Plaxton. Thread scheduling for multiprogrammed multiprocessors. In ACM Symposium on Parallel Algorithms and Architectures, pages 119--129, 1998a.
• 6: Nimar S. Arora, Robert D. Blumofe, and C. Greg Plaxton. Thread scheduling for multiprogrammed multiprocessors. In SPAA '98: Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, pages 119--129, 1998b.
• 7: Robert D. Blumofe and Charles E. Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM, 46(5):720--748, September 1999.
• 8: Robert D. Blumofe and Dionisios Papadopoulos. Hood: A user-level threads library for multiprogrammed multiprocessors. Technical report, University of Texas, Austin, 1999.
• 9: Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. Cilk: an efficient multithreaded runtime system. SIGPLAN Not., 30(8):207--216, 1995.
• 10: S. Burckhardt, R. Alur, and M. Martin. CheckFence: Checking consistency of concurrent data types on relaxed memory models. In Programming Language Design and Implementation (PLDI), pages 12--21, 2007.
• 11: WilliamW. Collier. Reasoning about Parallel Architectures. Prentice Hall, 1992.
• 12: John S. Danaher, I-Ting Angelina Lee, and Charles E. Leiserson. The jcilk language for multithreaded computing. In Synchronization and Concurrency in Object-Oriented Languages (SCOOL), San Diego, California, October 2005.
• 13: John S. Danaher, I-Ting Angelina Lee, and Charles E. Leiserson. Programming with exceptions in jcilk. Science of Computer Programming (SCP), 63(2):147--171, December 2006.
• 14: E. W. Dijkstra. Solution of a problem in concurrent programming control. Commun. ACM, 8(9):569, 1965.
• 15: Dawson R. Engler, Dawson R. Engler, Gregory R. Andrews, Gregory R. Andrews, David K. Lowenthal, and David K. Lowenthal. Filaments: Efficient support for fine-grain parallelism. Technical Report TR 93-13a, University of Arizona, 1993.
• 16: Cormac Flanagan and Matthias Felleisen. The semantics of future and its use in program optimization. In Rice University, pages 209--220, 1995.
• 17: Matteo Frigo, Charles E. Leiserson, and Keith H. Randall. The implementation of the Cilk-5 multithreaded language. In Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation, pages 212--223, Montreal, Quebec, Canada, June 1998. Proceedings published ACM SIGPLAN Notices, Vol. 33, No. 5, May, 1998.
• 18: Kourosh Gharachorloo, Sarita V. Adve, Anoop Gupta, John L. Hennessy, and Mark D. Hill. Programming for different memory consistency models. Journal of Parallel and Distributed Computing, 15:399--407, 1992.
• 19: R.H. Halstead jr. Multilisp: A language for concurrent symbolic computation. ACM Transactions on Programming Languages and Systems, 7(4):501--538, October 1985.
• 20: Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, March 2008.
• 21: Paul Hudak. Building domain-specific embedded languages. ACM Comput. Surv., page 196, 1996.
• 22: Doug Lea. Concurrent Programming in Java. Second Edition: Design Principles and Patterns. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1999. ISBN 0201310090.
• 23: Doug Lea. A java fork/join framework. In Java Grande, pages 36--43, 2000.
• 24: Maged M. Michael, Martin T. Vechev, and Vijay A. Saraswat. Idempotent work stealing. In PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 45--54, 2009.
• 25: Microsoft. Parallel extensions to .NET. June 2008. URL http://msdn.microsoft.com/en-us/concurrency.
• 26: Luc Moreau. The semantics of scheme with future. In In In ACM SIGPLAN International Conference on Functional Programming (ICFP'96, pages 146--156, 1996.
• 27: Lev Nachmanson and Lynn Powers. Microsoft automatic graph layout library (msagl). research.microsoft.com/en-us/projects/msagl, 2008.
• 28: Polyvios Pratikakis, Jaime Spacco, and Michael Hicks. Transparent proxies for java futures. SIGPLAN Not., 39 (10):206--223, 2004. ISSN 0362-1340.
• 29: Keith H. Randall. Cilk: Efficient Multithreaded Computing. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, May 1998.
• 30: Pradeep S. Sindhu, Jean-Marc Frailong, and Michel Cekleov. Formal specification of memory models. Technical Report CSL-91-11, Xerox Palo Alto Research Center, December 1991.
• 31: Guy Steele. Parallel programming and parallel abstractions in fortress. In Invited talk at the Eighth International Symposium on Functional and Logic Programming (FLOPS), April 2006.
• 32: Kenjiro Taura, Kunio Tabata, and Akinori Yonezawa. Stackthreads/mp: integrating futures into calling standards. SIGPLAN Not., 34(8):60--71, 1999.
• 33: John Thornley. Performance of a class of highlyparallel divide-and-conquer algorithms. Technical Report 1995.cs-tr-95-10, California Institute of Technology, 1995.
• 34: Adam Welc, Suresh Jagannathan, and Antony Hosking. Safe futures for java. In OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN conference on Objectoriented programming, systems, languages, and applications, pages 439--453, 2005.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Algorithms, Design, Languages

Keywords:
domain specific languages, duplicating queue, parallelism, work stealing