Phasers: a unified deadlock-free construct for collective and point-to-point synchronization
The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Abstract
Coordination and synchronization of parallel tasks is a major source of complexity in parallel programming. These constructs take many forms in practice including mutual exclusion in accesses to shared resources, termination detection of child tasks, collective barrier synchronization, and point-to-point synchronization. In this paper, we introduce phasers, a new coordination construct that unifies collective and point-to-point synchronizations. We establish two safety properties for phasers: deadlock-freedom and phase-ordering. Performance results obtained from a portable implementation of phasers on three different SMP platforms demonstrate that phasers can deliver superior performance to existing barrier implementations, in addition to the productivity benefits that result from their generality and safety properties.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“In this example of manycore processor speedup, a fat core needing 10 times as many resources would be more effective than the 10 thin cores it replaces.5,15”
From A view of the parallel computing landscape (2009) · cites this paper as [15]
Citations
Cites
Transactional memory: architectural support for lock-free data structures
Herlihy, M., & Moss, J. E. B. (1993) · Proceedings of the 20th annual international symposium on Computer architecture - ISCA '93 · doi:10.1145/165123.165164 · Cited by 2,141
X10: an object-oriented approach to non-uniform cluster computing
Charles, P., Grothoff, C., Saraswat, V., Donawa, C., Kielstra, A., Ebcioglu, K., von Praun, C., & Sarkar, V. (2005) · Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications · doi:10.1145/1094811.1094852 · Cited by 1,268 · cited 1×
“One of the major obstacles to improved productivity is the complexity of coordination and synchronization of parallel tasks that is inherent in current parallel programming models.”
BackgroundSelf-citationCilk: an efficient multithreaded runtime system
Blumofe, R. D., Joerg, C. F., Kuszmaul, B. C., Leiserson, C. E., Randall, K. H., & Zhou, Y. (1995) · Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming · doi:10.1145/209936.209958 · Cited by 1,021 · cited 2×
“parallel programming include transactional memory systems for mutual exclusion [7], work stealing schedulers to support dynamic nested parallel execution model with lightweight task creation and termination detection as in Cilk [11], and deadlock-free barrier synchronizations as in X10’s clocks [2].”
BackgroundInfluentialPeierls, T., Goetz, B., Bloch, J., Bowbeer, J., Lea, D., & Holmes, D. (2006) · Medical Entomology and Zoology · Cited by 424
Goetz, B., Peierls, T., Bloch, J., Bowbeer, J., Holmes, D., & Lea, D. (2006) · Cited by 264
Productivity and performance using partitioned global address space languages
Yelick, K., Bonachea, D., Chen, W.-Y., Colella, P., Datta, K., Duell, J., Graham, S. L., Hargrove, P., Hilfinger, P., Husbands, P., et al. (2007) · Proceedings of the 2007 international workshop on Parallel symbolic computation · doi:10.1145/1278177.1278183 · Cited by 192 · cited 2×
“These constraints are imposed to ensure the integrity of the single statement [16].”
BackgroundThe fuzzy barrier: a mechanism for high speed synchronization of processors
Gupta, R. (1989) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/70082.68187 · Cited by 113 · cited 3×
“Gupta’s work on fuzzy barriers [5] introduces the concept of overlapping synchronization with “real” work in a model that is now widely known as a split-phase barrier.”
BackgroundTitanium Language Reference Manual
Hilfinger, P. N., Bonachea, D., Graham, S. L., Liblit, B., Pike, G., & Yelick, K. (2001) · Cited by 94
The fuzzy barrier: a mechanism for high speed synchronization of processors
Gupta, R. (1989) · ACM SIGARCH Computer Architecture News · doi:10.1145/68182.68187 · Cited by 92
Deadlock-free scheduling of X10 computations with bounded resources
Agarwal, S., Barik, R., Bonachea, D., Sarkar, V., Shyamasundar, R. K., & Yelick, K. (2007) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1248377.1248416 · Cited by 57 · cited 3×
“In this section we precisely define the guarantees phasers provide for phase ordering and deadlock avoidance by building on the the notion of an X10 computation DAG introduced in [1] for finish and async constructs.”
BackgroundMethodInfluentialSelf-citation
Research works printed but not linked: 1
- L. A. Smith and J. M. Bull . A multithreaded java grande benchmark suite . In Proceedings of the Third Workshop on Java for High Performance Computing , June 2001 . L. A. Smith and J. M. Bull. A multithreaded java grande benchmark suite. In Proceedings of the Third Workshop on Java for High Performance Computing, June 2001.
Cited by
Items 101–141 of 141
Using Shared Arrays in Message-Driven Parallel Programs
Miller, P., Becker, A. T., & Kalé, L. V. (2011) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdps.2011.267 · Cited by 2
SCnC: Efficient Unification of Streaming with Dynamic Task Parallelism
Sbîrlea, D., Shirako, J., Newton, R., & Sarkar, V. (2011) · Workshop on Data-Flow Execution Models for Extreme Scale Computing (DFM) · doi:10.1109/dfm.2011.13 · Cited by 2
Self-citationMany-core virtual machines: decoupling abstract from concrete concurrency
Marr, S., & D’Hondt, T. (2010) · Companion to the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA Companion) · doi:10.1145/1869542.1869593 · Cited by 2
“Furthermore, recent research in the area of partitioned global address space (PGAS) languages indicates that their might be disciplined shared memory approaches[2, 10].”
BackgroundEfficient lock‐step synchronization in task‐parallel languages
Utture, A., & Nandivada, V. K. (2019) · Software Practice and Experience · doi:10.1002/spe.2726 · Cited by 2
SCaLeM: A Framework for Characterizing and Analyzing Execution Models
Chavarría-Miranda, D., Manzano, J., Krishnamoorthy, S., Vishnu, A., BARKER, K. J., & Hoisie, A. (2014) · doi:10.1145/2737909.2737910 · Cited by 1
“Synchronization operations are classified into three broad categories: data-centric, with respect to memory; control-centric, with respect to concurrency units; and termination-centric, with respect to completion of concurrency units’ execution [26].”
BackgroundFormalization of Phase Ordering
Cogumbreiro, T., Shirako, J., & Sarkar, V. (2016) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.211.2 · Cited by 1
“This section formalizes Phase Ordering, originally introduced in [13], to reason about whether two tasks should execute concurrently in terms of views V and states P .”
BackgroundMethodSelf-citationIsolation for nested task parallelism
Zhao, J., Lublinerman, R., Budimlić, Z., Chaudhuri, S., & Sarkar, V. (2013) · ACM SIGPLAN Notices · doi:10.1145/2544173.2509534 · Cited by 1
Self-citationDesigning an undergraduate curriculum based on parallelism and concurrency
Niño, J. (2011) · ACM Southeast Regional Conference (ACMSE) · doi:10.1145/2016039.2016051 · Cited by 1
Habanero-Java extensions for scientific computing
Cavé, V., Zhao, J., Budimlić, Z., Sarkar, V., Gunning, J. S., & Glinsky, M. E. (2010) · doi:10.1145/2039312.2039313 · Cited by 1
Self-citationOn Reachability in Parameterized Phaser Programs
Ganjei, Z., Rezine, A., Henrio, L., Eles, P., & Peng, Z. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-17462-0_17 · Cited by 4
Proceedings of Formal Methods in Computer Aided Design, FMCAD 2017
Design, F. M. I. C. A. (2017) · Texas ScholarWorks (Texas Digital Library) · doi:10.15781/t2js9hq7c · Cited by 1
Performance Optimizations for Software Transactional Memory
Zhang, R. (2010) · Rice Research Repository (Rice University) · Cited by 1
Execution model and optimizing compilation for execution migration
Lebedev, I. A. (2013) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 1
Intervals: Data-Race-Free Parallel Programming
Matsakis, N. D. (2011) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-a-006527833 · Cited by 1
Runtime Systems for Extreme Scale Platforms
Chatterjee, S. (2013) · Defense Technical Information Center (DTIC) · doi:10.21236/ad1000607 · Cited by 1
“Phasers [12], first introduced in the Habanero-Java multicore programming system, are synchronization constructs for task parallel programs.”
BackgroundMethodHigh-level execution models for multicore architectures
Sbîrlea, A. (2015) · Rice Research Repository (Rice University) · Cited by 1
Architecture-neutral parallelism via the Join Calculus
Calvert, P. R. (2015) · CL Technical Reports · doi:10.48456/tr-871 · Cited by 1
On algorithmic reductions in task-parallel programming models
Ciesko, J. (2017) · UPCommons institutional repository (Universitat Politècnica de Catalunya) · doi:10.5821/dissertation-2117-111500 · Cited by 1
“X10 [21], another popular programming model, introduces a phaser-accumulator [22, 23] construct for dynamic parallelism.”
Work-stealing for mixed-mode parallelism by deterministic team-buildingPreprint
Wimmer, M., & Träff, J. L. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.5030 · Cited by 1
Global task data dependencies in the partitioned global address space
Schuchart, J. (2021) · OPUS Publication Server of the University of Stuttgart (University of Stuttgart) · doi:10.18419/opus-11409 · Cited by 1
Habanero-Scala: A Hybrid Programming model integrating Fork/Join and Actor models
Imam, S. (2012) · Rice Research Repository (Rice University)
DrHJ: the cure to your multicore programming woes
Cavé, V., Payne, J., Raman, R., Ricken, M., Cartwright, C., & Sarkar, V. (2011) · Companion to the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA Companion) · doi:10.1145/2048147.2048150
“4) phasers: The phaser construct [9] integrates collective and point-to-point synchronization by giving each task the option of registering with a phaser in signal-only/wait-only mode for producer/consumer synchronization or signal-wait mode for barrier synchronization(2).”
BackgroundSelf-citationBLUE WATERS: APPLICATION!DRIVEN SYSTEM DESIGN FOR SUSTAINED PETASCALE PERFORMANCE
Fiedler, R. A., Wilhelmson, R. B., Kramer, W., & Bode, B. (2009)
SCnC: Efficient Unification of Streaming with Dynamic Task Parallelism
Sbîrlea, D., Shirako, J., Newton, R., & Sarkar, V. (2015) · International Journal of Parallel Programming · doi:10.1007/s10766-015-0353-x
Self-citationMallinson, A. C. (2026) · Warwick Research Archive Portal (University of Warwick) · doi:10.82444/warw.33723517
Compilation techniques and language support to facilitate dependence-driven computation
Sidelnik, A. (2013) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign)
Type-Aware Programming Models for Distributed Applications
Holt, B. A. (2016) · ResearchWorks at the University of Washington (University of Washington)
Honda, K., & Mycroft, A. (2013) · Queen Mary Research Online (Queen Mary University of London)
Optimized Event-Driven Runtime Systems for Programmability and Performance
Taşırlar, S. (2015) · Rice Research Repository (Rice University)
Integrating stream parallelism and task parallelism in a dataflow programming model
Sbîrlea, D. (2012) · Rice Research Repository (Rice University)
STAPL-RTS: A runtime system for massive parallelism
Papadopoulos, I. (2016) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/1492943
“, quiescence detection [67] or phasers [132].”
Parallel architectures and runtime systems co-design for task-based programming models
Villar, E. C. (2019) · UPCommons institutional repository (Universitat Politècnica de Catalunya) · doi:10.5821/dissertation-2117-134744
Mapping High Level Parallel Programming Models to Asynchronous Many-Task (AMT) Runtimes
Paul, S. R. (2018) · Rice Research Repository (Rice University)
Hyperqueues: Design and Implementation of Deterministic Concurrent Queues
Vandierendonck, H., & Nikolopoulos, D. S. (2019) · ACM Transactions on Parallel Computing · doi:10.1145/3365660
“Phasers are a multi-purpose synchronization construct applicable also to pipelines [Shirako et al. 2008].”
MethodDistributed PhasersPreprint
Paul, S. R., Murthy, K. S., Meel, K. S., & Mellor‐Crummey, J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1512.07305
“Participant Addition to SCSL : Dynamic addition of a task into an existing phaser is done using the async construct [4].”
BackgroundMethodAlembic: automatic locality extraction via migration
Holt, B. A., Briggs, P., Ceze, L., & Oskin, M. (2014) · ACM SIGPLAN Notices · doi:10.1145/2714064.2660194
“Parallel loops (we borrow the name forall used in UPC and Chapel [8, 9]) conceptually spawn a separate asynchronous task per iteration.”
MethodBarracuda, an Open Source Framework for Parallelizing Divide and Conquer Algorithm
Senghor, A. (2023) · International Journal on Cybernetics & Informatics · doi:10.5121/ijci.2023.120206
“Most of the frameworks [27][28] are fitted to only target shared-memory multiprocessors architecture.”
Background
Metadata
- Authors
- Shirako, J., Peixotto, D. M., Sarkar, V., & Scherer, W. N.
- Affiliations
- Rice University (US)
- Venue
- Proceedings of the 22nd annual international conference on Supercomputing
- Publisher
- ACM
- Published
- 2008-06-07
- Pages
- 277-288
- OpenAlex
- W1970787534
- Cited by
- 124
- References
- 12
- Citations by year
- 2023: 1 · 2021: 2 · 2020: 1 · 2019: 3 · 2018: 2 · 2017: 8 · 2016: 3 · 2015: 13 · 2014: 12 · 2013: 18 · 2012: 12
- FWCI
- 9.61
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- International Conference on Supercomputing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed systems and fault tolerance
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Keywords
- Phaser, barrier synchronization, collective synchronization, deadlock freedom, phase ordering, shared resource access, parallel programming
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.