Intel Corporation

Wisconsin Alumni Research Foundation

James R Goodman

Herbert H J Hum

Ravi Rajwar

Robert H Beers

Stefanos Kaxiras

Douglas C Burger

Rajnish Ghughal

Alain Kagi

A conflict resolution technique provides consistency such that all conflicts can be detected by at least one of the conflicting requestors if each node monitors all requests after that node has made its own request. If a line is in the Exclusive, Modified or Forward state, conflicts are resolved at the node holding the unique copy. The winner of the conflict resolution, and possibly the losers, report the conflict to the home node, which pairs conflict reports and issues forwarding instructions to assure that all requesting nodes eventually receive the requested data. If a requested cache line is either uncached or present only in the Shared state, the home node provides a copy of the cache node and resolves conflicts. In one embodiment, a blackout period after all responses until an acknowledgement message has been received allows all conflicting nodes to be aware of conflicts in which they are involved.

Speculative distributed conflict resolution for a cache coherency protocol

One embodiment of the present invention provides a system that facilitates avoiding locks by speculatively executing critical sections of code. During operation, the system allows a process to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section. If the process subsequently completes the critical section without encountering an interfering data access from another process, the system commits changes made during the speculative execution, and resumes normal non-speculative execution of the program past the critical section. Otherwise, if an interfering data access from another process is encountered during execution of the critical section, the system discards changes made during the speculative execution, and attempts to re-execute the critical section.

Concurrent execution of critical sections by eliding ownership of locks

Use of an import cache and/or an export directory with an agent within to respond to requests for data. The import cache stores data that has been imported through the agent. The export directory stores information related to data that has been exported through the agent. Because the import cache and the export directory only store data that has passed through the agent, not all data transferred within a system are tracked by a single import cache or export directory.

Hierarchical directories for cache coherency in a multiprocessor system

Non-speculative distributed conflict resolution for a cache coherency protocol

The cache coherency protocol described herein can be used to maintain a virtual model of a system, where the virtual model does not change as the system configuration changes. In general, the virtual model is based on the assumption that each node in the system can directly communicate with some number of other nodes in the system. In one embodiment, for each cache line, the address of the cache line is used to designate a node as the 'home' node and all other nodes as 'peer' nodes. The protocol specifies one set of messages for communication with the line's home node and another set of messages for communication with the line's peer nodes.

Hierarchical virtual model of a cache hierarchy in a multiprocessor system

Hardware resolution of data conflicts in critical sections of programs executed in shared memory computer architectures are resolved using a hardware-based ordering system and without acquisition of the lock variable.

Computer architecture providing transactional, lock-free execution of lock-based programs

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.

Described herein is a cache coherency protocol having five states: Modified, Exclusive, Shared, Invalid and Forward (MESIF). The MESIF cache coherency protocol includes a Forward (F) state that designates a single copy of data from which further copies can be made. A cache line in the F state is used to respond to request for a copy of the cache line. In one embodiment, the newly created copy is placed in the F state and the cache line previously in the F state is put in the Shared (S) state, or the Invalid (I) state. Thus, if the cache line is shared, one shared copy is in the F state and the remaining copies of the cache line are in the S state.

Forward state for use in cache coherency in a multiprocessor system

Critical sections of a program, providing exclusive access to shared data in a multi-processor architecture may be inferred from standard instructions and used to invoke a cache protocol that delays the response of requests of other cache and thus counter intuitively improving performance of the system. During this delay, read-only copies of data may be provided and the delay may recognize two priorities of requests, one of which is not delayed so as to improve the release of locks held by different processors.

Growing community of inventors

Madison, WI, United States of America

James R Goodman