Speculative synchronization
José F. Martínez, Josep Torrellas · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · 2002
Barriers, locks, and flags are synchronizing operations widely used programmers and parallelizing compilers to produce race-free parallel programs. Often times, these operations are placed suboptimally, either because of conservative assumptions about the program, or merely for code simplicity.We propose Speculative Synchronization, which applies the philosophy behind Thread-Level Speculation (TLS) to explicitly parallel applications. Speculative threads execute past active barriers, busy locks, and unset flags instead of waiting. The proposed hardware checks for conflicting accesses and, if a violation is detected, offending speculative thread is rolled back to the synchronization point and restarted on the fly. TLS's principle of always keeping a safe thread is key to our proposal: in any speculative barrier, lock, or flag, the existence of one or more safe threads at all times guarantees forward progress, even in the presence of access conflicts or speculative buffer overflow. Our proposal requires simple hardware and no programming effort. Furthermore, it can coexist with conventional synchronization at run time.We use simulations to evaluate 5 compiler- and hand-parallelized applications. Our results show a reduction in the time lost to synchronization of 34% on average, and a reduction in overall program execution time of 7.4% on average.
Cited by 181 works. doi:10.1145/605397.605400
Authors
References
- Computer Architecture: A Quantitative Approach
- The SPLASH-2 programs
- Computer architecture (2nd ed.): a quantitative approach
- On optimistic methods for concurrency control
- OpenMP: an industry standard API for shared-memory programming
- The directory-based cache coherence protocol for the DASH multiprocessor
- Transactional memory
- Portable Programs for Parallel Processors
- The Mips R10000 superscalar microprocessor
- A methodology for implementing highly concurrent data objects