Concurrent execution of critical sections by eliding ownership of locks
AssigneeWisconsin Alumni Research Foundation
InventorsRavi Rajwar, James R. Goodman
Life of this patent
Estimating the term…
Abstract
Critical sections of multi-threaded programs, normally protected by locks providing access by only one thread, are speculatively executed concurrently by multiple threads with elision of the lock acquisition and release. Upon a completion of the speculative execution without actual conflict as may be identified using standard cache protocols, the speculative execution is committed, otherwise the speculative execution is squashed. Speculative execution with elision of the lock acquisition, allows a greater degree of parallel execution in multi-threaded programs with aggressive lock usage.
Claims43
A method of coordinating access to common memory by multiple program threads comprising the steps of:
- in each given program thread,
- (a) detecting the beginning of a critical section of the given program thread in which interruption to access of the common memory could occur resulting from execution of other program threads;
- (b) speculatively executing the critical section;
- and
- (c) committing the speculative execution of the critical section if there has been no interruption to access of the common memory and squashing the speculative execution of the critical section if there has been an interruption wherein the speculative execution is committed upon the occurrence of a non cacheable operation limiting further speculation.
A method of coordinating access to common memory by multiple program threads comprising the steps of:
- in each given program thread,
- (a) detecting the beginning of a critical section of the given program thread in which interruption to access of the common memory could occur resulting from execution of other program threads;
- (b) speculatively executing the critical section;
- and
- (c) committing the speculative execution of the critical section if there has been no interruption to access of the common memory and squashing the speculative execution of the critical section if there has been an interruption wherein the speculation executes the critical section eliding write instructions that do not change a value of memory location being written to.
Dependencies are inferred from the claim text.