research-article

Serialization sets: a dynamic dependence-based parallel execution model

Authors:

Matthew D. Allen,

Srinath Sridharan,

Gurindar S. SohiAuthors Info & Claims

ACM SIGPLAN Notices, Volume 44, Issue 4

Pages 85 - 96

https://doi.org/10.1145/1594835.1504190

Published: 14 February 2009 Publication History

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]

C. Bienia et al. The PARSEC benchmark suite: Characterization and architectural implications. In Proceedings of the 17th international conference on Parallel Architectures and Compilation Techniques (PACT), October 2008.

Digital Library

[2]

K. Czarnecki and U. W. Eisenecker. Generative Programming. Addison-Wesley, 2000.

Digital Library

[3]

R. Das et al. Communications optimizations for irregular scientific computations on distributed memory architectures. Journal of Parallel and Distributed Computing, 22:462--478, September 1994.

Digital Library

[4]

J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In Proceedings of the 6th symposium on Operating System Design and Implementation (OSDI), 2004.

Digital Library

[5]

M. Frigo et al. The implementation of the Cilk-5 multithreaded language. In Proceedings of the 1998 conference on Programming Language Design and Implementation (PLDI), pages 212--223, 1998.

Digital Library

[6]

J. Giacomoni et al. FastForward for efficient pipeline parallelism: A cache-optimized concurrent lock-free queue. In Proceedings of the 13th symposium on Principles and Practice of Parallel Programming (PPoPP), pages 43--52, 2008.

Digital Library

[7]

R. H. Halstead. MULTILISP: A language for concurrent symbolic computation. ACM Transactions on Programming Languages and Systems, 7(4):501--538, 1985.

Digital Library

[8]

C. Hewitt. Viewing control structures as patterns of passing messages. Journal of Aritificial Intelligence, 8:323--363, 1977.

Digital Library

[9]

Intel. Threading building blocks. http://threadingbuildingblocks.org.

[10]

M. Kulkarni et al. Optimistic parallelism requires abstractions. In Proceedings of the 2007 conference on Programming Language Design and Implementation (PLDI), pages 211--222, 2007.

Digital Library

[11]

R. G. Lavender and D. C. Schmidt. Active object: An object behavioral pattern for concurrent programming. In Proceedings of the 2nd conference on Pattern Languages of Programs (PLoP), 1995.

Digital Library

[12]

E. A. Lee. The problem with threads. IEEE Computer, 39(5):33--42, May 2006.

Digital Library

[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]

M. C. Rinard and M. S. Lam. The design, implementation, and evaluation of jade. ACM Transactions on Programming Languages and Systems, 20(3):483--545, 1998.

Digital Library

[21]

H. Sutter and J. Larus. Software and the concurrency revolution. ACM Queue, 3(7), September 2005.

Digital Library

[22]

T. Veldhuizen. Using C++ template metaprograms. C++ Report, 7(4):36--43, May 1995.

Cited By

Wang JTian YFu X(2020)EQueue: Elastic Lock-Free FIFO Queue for Core-to-Core Communication on Multi-Core ProcessorsIEEE Access10.1109/ACCESS.2020.29970718(98729-98741)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2997071
Tzannes AHeumann SEloussi LVakilian MAdve VHan M(2019)Region and effect inference for safe parallelismAutomated Software Engineering10.1007/s10515-019-00257-326:2(463-509)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10515-019-00257-3
Faes MGross T(2018)Concurrency-aware object-oriented programming with rolesProceedings of the ACM on Programming Languages10.1145/32765002:OOPSLA(1-30)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276500
Show More Cited By

Index Terms

Serialization sets: a dynamic dependence-based parallel execution model
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Concurrent programming structures
      2. Language types
        Parallel programming languages

Recommendations

Serialization sets: a dynamic dependence-based parallel execution model
PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming

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 ...
Programming with exceptions in JCilk
Special issue: Synchronization and concurrency in object-oriented languages

JCilk extends the serial subset of the Java language by importing the fork-join primitives spawn and sync from the Cilk multithreaded language, thereby providing call-return semantics for multithreaded subcomputations. In addition, JCilk transparently ...
The implementation of the Cilk-5 multithreaded language

The fifth release of the multithreaded language Cilk uses a provably good "work-stealing" scheduling algorithm similar to the first system, but the language has been completely redesigned and the runtime system completely reengineered. The efficiency of ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 44, Issue 4

PPoPP '09

April 2009

294 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1594835

Issue’s Table of Contents

PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming
February 2009
322 pages
ISBN:9781605583976
DOI:10.1145/1504176
General Chair:
Daniel Reed
Microsoft Research, USA
,
Program Chair:
Vivek Sarkar
Rice University, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 February 2009

Published in SIGPLAN Volume 44, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
817
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang JTian YFu X(2020)EQueue: Elastic Lock-Free FIFO Queue for Core-to-Core Communication on Multi-Core ProcessorsIEEE Access10.1109/ACCESS.2020.29970718(98729-98741)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2997071
Tzannes AHeumann SEloussi LVakilian MAdve VHan M(2019)Region and effect inference for safe parallelismAutomated Software Engineering10.1007/s10515-019-00257-326:2(463-509)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10515-019-00257-3
Faes MGross T(2018)Concurrency-aware object-oriented programming with rolesProceedings of the ACM on Programming Languages10.1145/32765002:OOPSLA(1-30)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276500
Wang JTian YLi TFu X(2017)A Flexible Communication Mechanism for Pipeline Parallelism2017 IEEE International Symposium on Parallel and Distributed Processing with Applications and 2017 IEEE International Conference on Ubiquitous Computing and Communications (ISPA/IUCC)10.1109/ISPA/IUCC.2017.00119(778-785)Online publication date: Dec-2017
https://doi.org/10.1109/ISPA/IUCC.2017.00119
Meng XZeng XChen XYe X(2017)A cache-friendly concurrent lock-free queue for efficient inter-core communication2017 IEEE 9th International Conference on Communication Software and Networks (ICCSN)10.1109/ICCSN.2017.8230170(538-542)Online publication date: May-2017
https://doi.org/10.1109/ICCSN.2017.8230170
Zhao DMahakode ALakshminarasaiah SRaicu I(2016)High-Performance Storage Support for Scientific Big Data Applications on the CloudResource Management for Big Data Platforms10.1007/978-3-319-44881-7_8(147-170)Online publication date: 28-Oct-2016
https://doi.org/10.1007/978-3-319-44881-7_8
Pan APai VKern JVetter J(2015)Runtime-driven shared last-level cache management for task-parallel programsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/2807591.2807625(1-12)Online publication date: 15-Nov-2015
https://dl.acm.org/doi/10.1145/2807591.2807625
Heumann STzannes AAdve V(2015)Scalable Task Scheduling and Synchronization Using Hierarchical EffectsProceedings of the 2015 International Conference on Parallel Architecture and Compilation (PACT)10.1109/PACT.2015.25(125-137)Online publication date: 18-Oct-2015
https://dl.acm.org/doi/10.1109/PACT.2015.25
Tzannes AHeumann SEloussi LVakilian MAdve VHan MCohen MGrunske LWhalen M(2015)Region and effect inference for safe parallelismProceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2015.59(512-523)Online publication date: 9-Nov-2015
https://dl.acm.org/doi/10.1109/ASE.2015.59
Komuravelli RAdve SChou C(2014)Revisiting the Complexity of Hardware Cache Coherence and Some ImplicationsACM Transactions on Architecture and Code Optimization10.1145/266334511:4(1-22)Online publication date: 8-Dec-2014
https://dl.acm.org/doi/10.1145/2663345
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents