Concurrent execution of critical sections by eliding ownership of locks

• US 20030079094A1
• Filed: 10/19/2001
• Published: 04/24/2003
• Est. Priority Date: 10/19/2001
• Status: Active Grant

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Rajwar, Ravi, Goodman, James R.
• Granted Patent: US 7,120,762 B2
• Time in Patent Office: Days
• US Class Current: 711/150
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0844 Multiple simultaneous or quasi-simultaneous cache accessing
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 12/1458 by checking the subject access rights
• CPC Class Codes: G06F 12/1475 in a virtual system, e.g. with translation means
• CPC Class Codes: G06F 2212/1041 Resource optimization
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: G06F 2212/283 Plural cache memories
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/3009 Thread control instructions
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/528 by using speculative mechanisms

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.

Claims