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
A view of the parallel computing landscape
Asanovic, K., Bodik, R., Demmel, J., Keaveny, T., Keutzer, K., Kubiatowicz, J., Morgan, N., Patterson, D., Sen, K., Wawrzynek, J., et al. (2009) · Communications of the ACM · doi:10.1145/1562764.1562783 · Cited by 627
NVIDIA A100 Tensor Core GPU: Performance and Innovation
Choquette, J., Gandhi, W., Giroux, O., Stam, N., & Krashinsky, R. (2021) · IEEE Micro · doi:10.1109/mm.2021.3061394 · Cited by 410
Habanero-Java: the new adventures of old X10
Cavé, V., Zhao, J., Shirako, J., & Sarkar, V. (2011) · Principles and Practice of Programming in Java · doi:10.1145/2093157.2093165 · Cited by 263
“result() is only computed once per loop iteration since it is included in a single statement [33].”
BackgroundMethodInfluentialSelf-citationWork-first and help-first scheduling policies for async-finish task parallelism
Guo, Y., Barik, R., Raman, R., & Sarkar, V. (2009) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2009.5161079 · Cited by 180
“To that end, we focused on X10 benchmarks that have been used in past evaluations [6, 3, 16, 18 , 9].”
BackgroundMethodSelf-citationIntegrating Asynchronous Task Parallelism with MPI
Chatterjee, S., Taşırlar, S., Budimlić, Z., Cavé, V., Chabbi, M., Grossman, M., Sarkar, V., & Yan, Y. (2013) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2013.78 · Cited by 106
“HC supports phasers [12], [13] for fine-grained synchronization among dynamically created tasks.”
BackgroundSelf-citationSoftware challenges in extreme scale systems
Sarkar, V., Harrod, W. J., & Snavely, A. E. (2009) · Journal of Physics Conference Series · doi:10.1088/1742-6596/180/1/012045 · Cited by 101
Self-citationHabanero-Java library: a Java 8 framework for multicore programming
Imam, S., & Sarkar, V. (2014) · Principles and Practice of Programming in Java · doi:10.1145/2647508.2647514 · Cited by 88
“The phaser construct [37] unifies collective and point-to-point synchronization for phased computations.”
BackgroundSelf-citationThe habanero multicore software research project
Barik, R., Budimlić, Z., Cavé, V., Chatterjee, S., Guo, Y., Peixotto, D. M., Raman, R., Shirako, J., Taşırlar, S., Yan, Y., et al. (2009) · Companion to the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA Companion) · doi:10.1145/1639950.1639989 · Cited by 84
“Collective and point-to-point synchronization using the ”phasers” construct [15, 16].”
MethodSelf-citationScott, M. L. (2013) · Synthesis lectures on computer architecture · doi:10.1007/978-3-031-01740-7 · Cited by 79
A Survey of Recent Trends in Testing Concurrent Software Systems
Bianchi, F. A., Margara, A., & Pezzè, M. (2017) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2017.2707089 · Cited by 75
Architectures for Extreme-Scale Computing
Torrellas, J. (2009) · Computer · doi:10.1109/mc.2009.341 · Cited by 69
OpenCilk: A Modular and Extensible Software Infrastructure for Fast Task-Parallel Code
Schardl, T. B., & Lee, I.-T. A. (2023) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/3572848.3577509 · Cited by 50
“…parallelism continues to draw significant attention from the research community to explore different language abstractions (e.g., [11, 34, 35, 53, 68, 69, 77]), compilation techniques (e.g., [8, 9, 25, 51, 64, 78, 83]), scheduling algorithms (e.g., [5, 6, 52, 70–73]), runtime mechanisms (e.g.,…”
Chunking parallel loops in the presence of synchronization
Shirako, J., Zhao, J. M., Nandivada, V. K., & Sarkar, V. (2009) · International Conference on Supercomputing · doi:10.1145/1542275.1542304 · Cited by 50
Self-citationIntegrating task parallelism with actors
Imam, S., & Sarkar, V. (2012) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2384616.2384671 · Cited by 48
“Such coordination patterns are simple in the AFM, for example by using finish to wrap asyncs or by using phasers [26] as communication barriers.”
MethodSelf-citationScott, M. L. (2013) · Synthesis lectures on computer architecture · doi:10.2200/s00499ed1v01y201304cac023 · Cited by 48
HabaneroUPC++: a Compiler-free PGAS Library
Kumar, V., Zheng, Y., Cavé, V., Budimlić, Z., & Sarkar, V. (2014) · International Conference on Partitioned Global Address Space Programming Models (PGAS) · doi:10.1145/2676870.2676879 · Cited by 47
Self-citationMapping a data-flow programming model onto heterogeneous platforms
Sbîrlea, A., Zou, Y., Budimlić, Z., Cong, J., & Sarkar, V. (2012) · doi:10.1145/2248418.2248428 · Cited by 46
“Each dynamic instance TA of an async task has a unique Immedia Enclosing Finish (IEF) instance F of a finish statement during program execution, where F is the innermost finish containing TA [24].”
MethodSelf-citationInterprocedural Load Elimination for Dynamic Optimization of Parallel Programs
Barik, R., & Sarkar, V. (2009) · International Conference on Parallel Architectures and Compilation Techniques (PACT) · doi:10.1109/pact.2009.32 · Cited by 45
“Each dynamic instance of an X10 statement has a unique Immediately Enclosing Finish (IEF) instance [16].”
BackgroundMethodSelf-citationPhaser accumulators: A new reduction construct for dynamic parallelism
Shirako, J., Peixotto, D. M., Sarkar, V., & Scherer, W. N. (2009) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2009.5161071 · Cited by 44
“We recently introduced phasers [15], a new coordination construct that unifies collective and point-to-point synchronization in the presence of dynamic parallelism.”
BackgroundSelf-citationA Transformation Framework for Optimizing Task-Parallel Programs
Nandivada, V. K., Shirako, J., Zhao, J., & Sarkar, V. (2013) · ACM Transactions on Programming Languages and Systems · doi:10.1145/2450136.2450138 · Cited by 43
“2005] with phasers [Shirako et al. 2008] among other additions and modifications.”
BackgroundMethodInfluentialSelf-citationPedagogy and tools for teaching parallel computing at the sophomore undergraduate level
Grossman, M., Aziz, M., Chi, H., Tibrewal, A., Imam, S., & Sarkar, V. (2017) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2016.12.026 · Cited by 40
Self-citationThe design and implementation of the habanero-java parallel programming language
Budimlić, Z., Cavé, V., Raman, R., Shirako, J., Taşırlar, S., Zhao, J., & Sarkar, V. (2011) · Companion to the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA Companion) · doi:10.1145/2048147.2048198 · Cited by 36
“¸irlar Jisheng Zhao Vivek Sarkar Department of Computer Science, Rice University {zoran, vcave, raghav, shirako, sagnak, jz10, vsarkar}@rice.edu Categories and Subject Descriptors D.1.3 [Concurrent Programming] General Terms Languages Keywords Language, Parallel Programming, Habanero-Java Abstract The Habanero-Java l…”
MethodInfluentialSelf-citationLocality Optimization of Stencil Applications Using Data Dependency Graphs
Orozco, D., Garcia, E., & Gao, G. R. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19595-2_6 · Cited by 35
“Consumer-producer synchronization primitives such as phasers [ 12 ] can potentially reduce execution noise in stencil applications.”
BackgroundThe Concurrent Collections Programming Model
Burke, M., Knobe, K., Newton, R., & Sarkar, V. (2010) · Rice Research Repository (Rice University) · Cited by 35
Self-citationSierra: a SIMD extension for C++
Leißa, R., Haffner, I., & Hack, S. (2014) · Workshop on Programming Models for SIMD/Vector Processing (WPMVP) · doi:10.1145/2568058.2568062 · Cited by 32
“Therefore, the programmer has to use barrier synchronization in order to communicate across program instances [31].”
MethodEffective Barrier Synchronization on Intel Xeon Phi Coprocessor
Rodchenko, A., Nisbet, A. P., Pop, A., & Luján, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48096-0_45 · Cited by 31
“It was shown that using more relaxed synchronization constructs, like phasers, is more e ffi cient than using barriers for CG and MG [16].”
Lublinerman, R., Zhao, J., Budimlić, Z., Chaudhuri, S., & Sarkar, V. (2011) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2048066.2048133 · Cited by 31
“On the language design end, we would like greater integration of Aida with existing Habanero Java constructs for locality and directed synchronization, such as hierarchical place trees [38] and phasers [36].”
MethodSelf-citationIntermediate language extensions for parallelism
Zhao, J., & Sarkar, V. (2011) · doi:10.1145/2095050.2095103 · Cited by 30
“phasers: The phaser construct [33] 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.”
BackgroundMethodInfluentialSelf-citationAccelerating Habanero-Java programs with OpenCL generation
Hayashi, A., Grossman, M., Zhao, J., Shirako, J., & Sarkar, V. (2013) · Principles and Practice of Programming in Java · doi:10.1145/2500828.2500840 · Cited by 27
Self-citationReducing task creation and termination overhead in explicitly parallel programs
Zhao, J., Shirako, J., Nandivada, V. K., & Sarkar, V. (2010) · International Conference on Parallel Architectures and Compilation Techniques (PACT) · doi:10.1145/1854273.1854298 · Cited by 26
“The phaser construct [15] 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.”
BackgroundInfluentialSelf-citationDynamic deadlock verification for general barrier synchronisation
Cogumbreiro, T., Hu, R., Martins, F., & Yoshida, N. (2015) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2688500.2688519 · Cited by 24
“If state S is deadlocked on T and t ∈ dom( T ) , then there exists a t (cid:48) -cycle on wfg ( ϕ ( S )) such that t (cid:48) is reachable from t .”
InfluentialCooperative Scheduling of Parallel Tasks with General Synchronization Patterns
Imam, S., & Sarkar, V. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-44202-9_25 · Cited by 24
“These constructs include the well structured async-finish variant of fork-join style tasks, point-to-point synchronization with futures, localized and group synchronization using phasers, and weak atomicity in critical sections [2,17,26,3].”
BackgroundSelf-citationLLVM parallel intermediate representation: design and evaluation using OpenSHMEM communications
Khaldi, D., Jouvelot, P., Irigoin, F., Ancourt, C., & Chapman, B. (2015) · IEEE/ACM Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC) · doi:10.1145/2833157.2833158 · Cited by 23
Mapping a data-flow programming model onto heterogeneous platforms
Sbîrlea, A., Zou, Y., Budimlić, Z., Cong, J., & Sarkar, V. (2012) · ACM SIGPLAN Notices · doi:10.1145/2345141.2248428 · Cited by 23
Self-citationEarly experiences scaling VMD molecular visualization and analysis jobs on blue waters
Stone, J. E., Isralewitz, B., & Schulten, K. J. (2013) · doi:10.1109/xsw.2013.10 · Cited by 20
“The new scheduler allowed replacement of per-scanline thread barrier synchronizations with a more efficient custom-written synchronization scheme similar to a phaser [14], improving scalability for VMD/Tachyon parallel rendering jobs, and enabling the potential application of the dynamic load balancer at pixelor pixel…”
MethodExperiments with the Fresh Breeze tree-based memory model
Dennis, J. B., Gao, G. R., & Meng, X. X. (2011) · Computer Science - Research and Development · doi:10.1007/s00450-011-0165-1 · Cited by 20
“In the Fresh Breeze Memory Model [3][20] information objects and data structures are represented using fixed size chunks, which are 128 bytes in the present design.”
MethodExpressing DOACROSS Loop Dependences in OpenMP
Shirako, J., Unnikrishnan, P., Chatterjee, S., Li, K., & Sarkar, V. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40698-0_3 · Cited by 20
“As a recent research outcome, phasers in the Habanero project [10] and java.”
BackgroundSelf-citationWork-stealing for mixed-mode parallelism by deterministic team-building
Wimmer, M., & Träff, J. L. (2011) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1989493.1989507 · Cited by 19
Integrating task parallelism with actors
Imam, S., & Sarkar, V. (2012) · ACM SIGPLAN Notices · doi:10.1145/2398857.2384671 · Cited by 19
Self-citationTask Parallelism and Data Distribution: An Overview of Explicit Parallel Programming Languages
Khaldi, D., Jouvelot, P., Ancourt, C., & Irigoin, F. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-37658-0_12 · Cited by 19
“It acts as a barrier for a dynamically varying set of tasks [19] that operate in phases of execution where each phase should wait for previous ones before proceeding.”
Heterogeneous Habanero-C (H2C): A Portable Programming Model for Heterogeneous Processors
Majeti, D., & Sarkar, V. (2015) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2015.81 · Cited by 17
“• phaser-next: Phasers [14] are fine-grain synchronization constructs introduced by the Habanero programming model.”
Self-citationComparing the usability of library vs. language approaches to task parallelism
Cavé, V., Budimlić, Z., & Sarkar, V. (2010) · Evaluation and Usability of Programming Languages and Tools · doi:10.1145/1937117.1937126 · Cited by 17
“This guarantees that the statement S is executed exactly once during the phase transition [4, 5].”
BackgroundInfluentialSelf-citationDeterministic scale-free pipeline parallelism with hyperqueues
Vandierendonck, H., Chronaki, K., & Nikolopoulos, D. S. (2013) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/2503210.2503233 · Cited by 16
Determinacy and Repeatability of Parallel Program Schemata
Dennis, J. B., Gao, G. R., & Sarkar, V. (2012) · Workshop on Data-Flow Execution Models for Extreme Scale Computing (DFM) · doi:10.1109/dfm.2012.10 · Cited by 16
“Each dynamic instance TA of an async task has a unique Immediately Enclosing Finish (IEF) instance F of a finish statement during program execution, where F is the innermost finish containing TA [19].”
MethodSelf-citationHierarchical phasers for scalable synchronization and reductions in dynamic parallelism
Shirako, J., & Sarkar, V. (2010) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2010.5470414 · Cited by 14
“As described in [13], the semantics of next depends on the registration mode that A i has with each phaser that it is registered on.”
BackgroundInfluentialSelf-citationManaging Asynchronous Operations in Coarray Fortran 2.0
Yang, C., Murthy, K. S., & Mellor‐Crummey, J. (2013) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2013.17 · Cited by 13
“CAF 2.0 finish is a collective operation; it provides barrier-like synchronization that guarantees completion of asynchronous operations spawned within a finish block entered by multiple process images independently. finish in CAF 2.0 is similar to clocks in X10 [14], or phasers in Habanero Java [15] with respect to s…”
BackgroundInfluentialWhen Concurrency Matters: Behaviour-Oriented Concurrency
Cheeseman, L., Parkinson, M., Clebsch, S., Kogias, M., Drossopoulou, S., Chisnall, D., Wrigstad, T., & Liétar, P. (2023) · Proceedings of the ACM on Programming Languages · doi:10.1145/3622852 · Cited by 13
“This means for the pedagogical use of phasers presented in [Shirako et al. 2008], BoC does not have as intuitive a solution (note, it is still achievable).”
MethodIntroducing a Multithread and Multistage Mechanism for the Global Load Balancing Library of X10
Yamashita, K., & Kamada, T. (2016) · Journal of Information Processing · doi:10.2197/ipsjjip.24.416 · Cited by 13
“Phaser [7] is a new synchronization construct that unifies collective and point-to-point synchronization.”
BackgroundMSL: A Synthesis Enabled Language for Distributed Implementations
Xu, Z., Kamil, S. A., & Solar-Lezama, A. (2014) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc.2014.31 · Cited by 12
“We achieve the same goal by using a sequential tag for each message and ensuring each transfer receives only messages with the correct tag; this strategy is similar to that used in prior work on phasers [17].”
MethodIsolation for nested task parallelism
Zhao, J., Lublinerman, R., Budimlić, Z., Chaudhuri, S., & Sarkar, V. (2013) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2509136.2509534 · Cited by 12
“…compiler and runtime optimizations to further reduce the overhead of ensuring isolation by default, exploration of new strategies for delegation, and supporting greater integration of Otello with additional HJ constructs for task parallelism, including futures, data-driven tasks, and phasers [29].”
MethodSelf-citationDFGR an Intermediate Graph Representation for Macro-Dataflow Programs
Sbîrlea, A., Pouchet, L.-N., & Sarkar, V. (2014) · Workshop on Data-Flow Execution Models for Extreme Scale Computing (DFM) · doi:10.1109/dfm.2014.9 · Cited by 12
“Each dynamic instance TA of an async task has a unique Immedia Enclosing Finish (IEF) instance F of a finish statement during program execution, where F is the innermost finish containing TA [29].”
MethodSelf-citationVerification of Static and Dynamic Barrier Synchronization Using Bounded Permissions
Le, D.-K., Chin, W.-N., & Teo, Y. M. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-41202-8_16 · Cited by 12
“Second, there are restrictions on the usage of clocks and phasers in async/finish programs [22, 23].”
BackgroundMethodInfluentialUnifying Barrier and Point-to-Point Synchronization in OpenMP with Phasers
Shirako, J., Sharma, K., & Sarkar, V. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-21487-5_10 · Cited by 12
Self-citationCogumbreiro, T., Surendran, R., Martins, F., Sarkar, V., VASCONCELOS, V. T., & Grossman, M. (2017) · Proceedings of the ACM on Programming Languages · doi:10.1145/3143359 · Cited by 12
“…isolated [Imam et al. 2015] for mutual exclusion; async-finish [Charles et al. 2005], a generalization of the fork-join model where a task can await the termination of its descendants; and, phasers [Shirako et al. 2008], a generalization of barriers with producer-consumer synchronization.”
BackgroundSelf-citationTask-Parallel Reductions in OpenMP and OmpSs
Ciesko, J., Mateo, S., Teruel, X., Beltrán, V., Martorell, X., Badia, R. M., Ayguadé, E., & Labarta, J. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11454-5_1 · Cited by 11
Using shared arrays in message-driven parallel programs
Miller, P., Becker, A. T., & Kalé, L. V. (2011) · Parallel Computing · doi:10.1016/j.parco.2011.10.005 · Cited by 11
Design, verification and applications of a new read-write lock algorithm
Shirako, J., Vrvilo, N., Mercer, E. G., & Sarkar, V. (2012) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/2312005.2312015 · Cited by 11
“Although support for reader threads increases ideal parallelism, the read-lock functionality typically requires additional mechanisms, including expensive atomic operations, to handle multiple readers.”
BackgroundSelf-citationHeterogeneous work-stealing across CPU and DSP cores
Kumar, V., Sbîrlea, A., Jayaraj, A., Budimlić, Z., Majeti, D., & Sarkar, V. (2015) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec.2015.7322452 · Cited by 10
Self-citationSupport for Dependency Driven Executions among OpenMP Tasks
Ghosh, P., Yan, Y., & Chapman, B. (2012) · Workshop on Data-Flow Execution Models for Extreme Scale Computing (DFM) · doi:10.1109/dfm.2012.16 · Cited by 10
“The success of clocks led to concept of phasers [34] used in Habanero-C which apart from deadlock- free synchronization, also accomplished phase-ordering providing better point-to-point synchronization in fine-grained task-parallel programming.”
BackgroundElastic Tasks: Unifying Task Parallelism and SPMD Parallelism with an Adaptive Runtime
Sbîrlea, A., Agrawal, K., & Sarkar, V. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48096-0_38 · Cited by 10
Self-citationSpeculative Execution of Parallel Programs with Precise Exception Semantics on GPUs
Hayashi, A., Grossman, M., Zhao, J., Shirako, J., & Sarkar, V. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-09967-5_20 · Cited by 9
“Collective and point-to-point synchronization using the phasers construct [10] along with their accompanying phaser accumulators [11].”
BackgroundSelf-citationTowards Task-Parallel Reductions in OpenMP
Ciesko, J., Mateo, S., Teruel, X., Martorell, X., Ayguadé, E., Labarta, J., Duran, A., de Supinski, B. R., Olivier, S. L., Li, K., et al. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-24595-9_14 · Cited by 9
Programming at the edge of synchrony
Drăgoi, C., Widder, J., & Damien Zufferey, A. (2020) · Proceedings of the ACM on Programming Languages · doi:10.1145/3428281 · Cited by 9
DrHJ: a lightweight pedagogic IDE for Habanero Java
Payne, J., Cavé, V., Raman, R., Ricken, M., Cartwright, R., & Sarkar, V. (2011) · Principles and Practice of Programming in Java · doi:10.1145/2093157.2093180 · Cited by 9
Self-citationDynamic split model of resource utilization in MapReduce
Wang, X. W., Zhang, J., Liao, H. M., & Zha, L. (2011) · International Workshop on Data-Intensive Computing in the Clouds (DataCloud) · doi:10.1145/2087522.2087528 · Cited by 9
“We address these problems through our experience in designing a Dynamic Split Model of the resources utilization which contains two technologies, DynamicResourceAllocation considering thephasepriority as well as job requirement when allocating resources and Resource Usage Pipeline which can assign tasks dynamically.”
MethodInfluentialLublinerman, R., Zhao, J., Budimlić, Z., Chaudhuri, S., & Sarkar, V. (2011) · ACM SIGPLAN Notices · doi:10.1145/2076021.2048133 · Cited by 9
Self-citationParameterized Verification of Synchronized Concurrent Programs
Ganjei, Z. (2021) · Linköping studies in science and technology. Dissertations · doi:10.3384/diss.diva-173568 · Cited by 8
Preparing an Online Java Parallel Computing Course
Sarkar, V., Grossman, M., Budimlić, Z., & Imam, S. (2017) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2017.162 · Cited by 8
“The course then introduces loop parallelism as a common parallel pattern similar to some functional parallelism patterns, and concludes with using constructs like phasers [14] to implement dataflow and pipeline parallelism.”
Self-citationDynamic Deadlock Verification for General Barrier Synchronisation
Cogumbreiro, T., Hu, R., Martins, F., & Yoshida, N. (2018) · ACM Transactions on Programming Languages and Systems · doi:10.1145/3229060 · Cited by 8
“Phasers [8, 62] are a generalisation of barriers.”
BackgroundHardware and Software Tradeoffs for Task Synchronization on Manycore Architectures
Yan, Y., Chatterjee, S., Orozco, D., Garcia, E., Budimlić, Z., Shirako, J., Pavel, R., Gao, G. R., & Sarkar, V. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23397-5_12 · Cited by 8
Self-citationHaller, P., & Miller, H. (2011) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 8
Compiler support for work-stealing parallel runtime systems
Raman, R. (2009) · Rice Research Repository (Rice University) · Cited by 8
Variations on task scheduling for shared memory systems
Wimmer, M. (2014) · reposiTUm (TU Wien) · doi:10.34726/hss.2014.24761 · Cited by 8
The Eureka Programming Model for Speculative Task Parallelism
Imam, S., & Sarkar, V. (2015) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.ecoop.2015.421 · Cited by 7
Self-citationCoordinating Phased Activities while Maintaining Progress
Cogumbreiro, T., Martins, F., & VASCONCELOS, V. T. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38493-6_3 · Cited by 7
“With this mind, Shirako et al. introduced phasers [17], a primitive that allows some tasks to cross the barrier before synchronisation, thus relaxing condition a) above.”
InfluentialAutomatic Resource-Constrained Static Task Parallelization : A Generic Approach
Khaldi, D. (2013) · theses.fr (ABES) · doi:10.70675/e3685e86z05afz436bz9fdcz76c9f613a701 · Cited by 7
Alembic: automatic locality extraction via migration
Holt, B. A., Briggs, P., Ceze, L., & Oskin, M. (2014) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2660193.2660194 · Cited by 6
Design and Verification of Distributed Phasers
Murthy, K. S., Paul, S. R., Meel, K. S., Cogumbreiro, T., & Mellor‐Crummey, J. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-43659-3_30 · Cited by 6
“To date, the only phaser design available is for shared memory systems [11,12].”
BackgroundFormalization of Habanero phasers using Coq
Cogumbreiro, T., Shirako, J., & Sarkar, V. (2017) · Journal of Logical and Algebraic Methods in Programming · doi:10.1016/j.jlamp.2017.02.006 · Cited by 6
Self-citationChapel-on-X: Exploring Tasking Runtimes for PGAS Languages
Hayashi, A., Paul, S. R., Grossman, M., Shirako, J., & Sarkar, V. (2017) · doi:10.1145/3152041.3152086 · Cited by 6
“Important features of these runtime systems in existing literature include lightweight task creation/termination [25], efficient synchronization [23], and efficient task scheduling including work-stealing [3, 17].”
BackgroundSelf-citationPop, A., & Cohen, A. (2012) · HAL · Cited by 6
A scalable locality-aware adaptive work-stealing scheduler for multi-core task parallelism
Sarkar, V., & Guo, Y. (2010) · Rice Research Repository (Rice University) · Cited by 6
Self-citationAn ownership policy and deadlock detector for promises
Voss, C., & Sarkar, V. (2021) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/3437801.3441616 · Cited by 5
“Solutions in the logical deadlock domain include techniques that dynamically detect cycles [29, 30, 37, 38, 40, 54], that raise alarms upon the formation or possible formation of cycles [1, 6, 14, 15, 23, 55], that statically check for cycles through analysis [42, 45, 57] or through type systems [7, 52], or that precl…”
BackgroundInfluentialSelf-citationDynamic deadlock verification for general barrier synchronisation
Cogumbreiro, T., Hu, R., Martins, F., & Yoshida, N. (2015) · ACM SIGPLAN Notices · doi:10.1145/2858788.2688519 · Cited by 5
Handling errors in parallel programs based on happens before relations
Matsakis, N. D., & Gross, T. R. (2010) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2010.5470943 · Cited by 5
“Among them are phasers [10], a combination of barriers and signals which can guarantee data-race freedom.”
BackgroundSafety verification of phaser programs
Ganjei, Z., Rezine, A., Eles, P., & Peng, Z. (2017) · Formal Methods in Computer-Aided Design · doi:10.23919/fmcad.2017.8102243 · Cited by 5
“• We propose an operational model based on [2], [3], [5].”
MethodMatsakis, N. D., & Gross, T. R. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13374-9_14 · Cited by 5
“The most recent, phasers [23], are a combination of barriers and signals.”
BackgroundInsertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-Grained Parallelism
Marr, S., Verhaegen, S., Fraine, B. D., D’Hondt, T., & Meuter, W. D. (2010) · IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS) · doi:10.1109/hpcc.2010.30 · Cited by 4
“This concept was first proposed by Shirako et al. with phasers [3].”
BackgroundMethodDASH: Distributed Data Structures and Parallel Algorithms in a Global Address Space
Fürlinger, K., Gracia, J., Knüpfer, A., Fuchs, T., Hünich, D., Jungblut, P., Kowalewski, R., & Schuchart, J. (2020) · Lecture notes in computational science and engineering · doi:10.1007/978-3-030-47956-5_6 · Cited by 4
“The concept of phasers has been introduced into the X10 language to implement nonblocking barrier-like synchronization, with the distinction of readers and writers contributing to the phaser [29].”
Actors in a new "highly parallel" world
Corrêa, F. (2009) · doi:10.1145/1527033.1527041 · Cited by 4
“COMPUTER (2006) pp. 33-42 [8] Shirako et al. Phasers: a unified deadlock-free construct for collective and point-to-point synchronization.”
BackgroundInfluentialEfficient optimization of memory accesses in parallel programs
Sarkar, V., & Barik, R. (2010) · Rice Research Repository (Rice University) · Cited by 4
Self-citationTideflow: A dataflow-inspired execution model for high performance computing programs
Orozco, D. (2012) · ProQuest Demo Repository · Cited by 4
Scheduling Macro-DataFlow Programs on Task-Parallel Runtime Systems
Taşırlar, S. (2011) · Rice Research Repository (Rice University) · Cited by 4
Distributed Generalized Dynamic Barrier Synchronization
Agarwal, S., Joshi, S., & Shyamasundar, R. K. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-17679-1_13 · Cited by 3
“The other clock related works [19], [ 18 ] are directed more towards efficient implementations of X10 like clocks rather than dealing with synchronization in a distributed setting.”
BackgroundMartins, F., Vasconcelos, V. T., & Cogumbreiro, T. (2011) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.69.8 · Cited by 3
“Of particular interest to us is the finish synchronisation mechanism that waits for the termination of parallel computations and the clock primitive that allows forcing multiple concurrent activities to wait for each other at certain points in time.”
BackgroundTask Parallelism and Synchronization: An Overview of Explicit Parallel Programming Languages
Khaldi, D., Jouvelot, P., Ancourt, C., & Irigoin, F. (2012) · Cited by 3
Phaser Beams: Integrating Stream Parallelism with Task Parallelism
Shirako, J., & Peixotto, D. M. (2011) · Cited by 3
Self-citationSupporting Concurrency Abstractions in High-level Language Virtual Machines
Marr, S. (2013) · Kent Academic Repository (University of Kent) · Cited by 3
JPF Verification of Habanero Java Programs using Gradual Type Permission Regions
Anderson, P., Vrvilo, N., Mercer, E. G., & Sarkar, V. (2015) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/2693208.2693245 · Cited by 2
Self-citationTabulated Equations of State with a Many-tasking Execution Model
Anderson, M. W., Brodowicz, M., Sterling, T., Kaiser, H., & Adelstein-Lelbach, B. (2013) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2013.162 · Cited by 2
“The proposed Phasers concept in X10 would also enable incorporation of equations of state tables in multiphysics simulations [31] but such an implementation has not yet been reported.”
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.