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.
Claims42
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 conflicts 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 conflict and squashing the speculative execution of the critical section if there has been a conflict.
A lock elision circuit for a computer architecture allowing the access of common memory by multiple program threads, the circuit comprising:
- means for controlling the execution of each given program thread to:
- (a) detect the beginning of a critical section of the given program thread in which conflicts to access of the common memory could occur resulting from execution of other program threads;
- (b) speculatively execute the critical section;
- and
- (c) commit the speculative execution of the critical section if there has been no conflict and squashing the speculative execution of the critical section if there has been a conflict.
Dependencies are inferred from the claim text.