Serialization sets: a dynamic dependence-based parallel execution model

ABSTRACT

This paper proposes a new parallel execution model where programmers augment a sequential program with pieces of code called serializers that dynamically map computational operations into serialization sets of dependent operations. A runtime system executes operations in the same serialization set in program order, and may concurrently execute operations in different sets. Because serialization sets establish a logical ordering on all operations, the resulting parallel execution is predictable and deterministic.

We describe the API and design of Prometheus, a C++ library that implements the serialization set abstraction through compile-time template instantiation and a runtime support library. We evaluate a set of parallel programs running on the x86_64 and SPARC-V9 instruction sets and study their performance on multicore, symmetric multiprocessor, and ccNUMA parallel machines. By contrast with conventional parallel execution models, we find that Prometheus programs are significantly easier to write, test, and debug, and their parallel execution achieves comparable performance.

REFERENCES

• 1: Christian Bienia , Sanjeev Kumar , Jaswinder Pal Singh , Kai Li, The PARSEC benchmark suite: characterization and architectural implications, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454128]
• 2: K. Czarnecki and U. W. Eisenecker. Generative Programming. Addison-Wesley, 2000.
• 3: Raja Das , Mustafa Uysal , Joel Saltz , Yuan-Shin Hwang, Communication optimizations for irregular scientific computations on distributed memory architectures, Journal of Parallel and Distributed Computing, v.22 n.3, p.462-478, Sept. 1994 [doi>10.1006/jpdc.1994.1104]
• 4: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 5: Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.212-223, June 17-19, 1998, Montreal, Quebec, Canada
• 6: John Giacomoni , Tipp Moseley , Manish Vachharajani, FastForward for efficient pipeline parallelism: a cache-optimized concurrent lock-free queue, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345215]
• 7: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 8: C. Hewitt. Viewing control structures as patterns of passing messages. Journal of Aritificial Intelligence, 8:323--363, 1977.
• 9: Intel. Threading building blocks. http://threadingbuildingblocks.org.
• 10: Milind Kulkarni , Keshav Pingali , Bruce Walter , Ganesh Ramanarayanan , Kavita Bala , L. Paul Chew, Optimistic parallelism requires abstractions, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 11: R. Greg Lavender , Douglas C. Schmidt, Active object: an object behavioral pattern for concurrent programming, Pattern languages of program design 2, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 12: Edward A. Lee, The Problem with Threads, Computer, v.39 n.5, p.33-42, May 2006 [doi>10.1109/MC.2006.180]
• 13: C. E. Leiserson. Cilk++: Multicore-enabling legacy C++ code. Carnegie Mellon University Parallel Thinking Series, April 2008.
• 14: Microsoft. Programming the ThreadPool in .NET. http://msdn.microsoft.com/en-us/library/ms973903.aspx.
• 15: Microsoft. Task parallel library (TPL). http://msdn.microsoft.com/en-us/magazine/cc163340.aspx.
• 16: OpenMP. The OpenMP API specification for parallel programming. http://openmp.org/wp/.
• 17: J. Pisharath et al. NU-MineBench 2.0. Technical Report CUCIS-2005-08-01, Northwestern University, 2005.
• 18: R. Rajwar and J. Larus. Transactional Memory. Morgan Claypool, October 2006.
• 19: C. Ranger et al. Evaluating MapReduce for multi-core and multiprocessor systems, 2007.
• 20: Martin C. Rinard , Monica S. Lam, The design, implementation, and evaluation of Jade, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.483-545, May 1998 [doi>10.1145/291889.291893]
• 21: Herb Sutter , James Larus, Software and the Concurrency Revolution, Queue, v.3 n.7, September 2005 [doi>10.1145/1095408.1095421]
• 22: T. Veldhuizen. Using C++ template metaprograms. C++ Report, 7(4):36--43, May 1995.

INDEX TERMS

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

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

General Terms:
Languages, Performance

Keywords:
parallel computing, runtime system, serialization sets, serializer