Predictive ownership control of shared memory computing system data

• US 8,370,584 B2
• Filed: 06/22/2012
• Issued: 02/05/2013
• Est. Priority Date: 04/30/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cantin, Jason F., Kunkel, Steven R.
• Primary Examiner(s): Elms, Richard
• Assistant Examiner(s): NGUYEN, HIEN N
• Application Number:
  US13/530,857
• Publication Number:
  US 20120265942A1
• Time in Patent Office: 228 Days
• Field of Search: 365/49, 365/189.03, 365/189.04, 365/189.19, 711/151, 711/152, 711/144, 711/145, 711/E12.023, 711/E12.018, 711/E12.091
• US Class Current: 711/152
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 9/528 by using speculative mechanisms

Abstract

A method, circuit arrangement, and design structure utilize a lock prediction data structure to control ownership of a cache line in a shared memory computing system. In a first node among the plurality of nodes, lock prediction data in a hardware-based lock prediction data structure for a cache line associated with a first memory request is updated in response to that first memory request, wherein at least a portion of the lock prediction data is predictive of whether the cache line is associated with a release operation. The lock prediction data is then accessed in response to a second memory request associated with the cache line and issued by a second node and a determination is made as to whether to transfer ownership of the cache line from the first node to the second node based at least in part on the accessed lock prediction data.

Claims

1. A method to control ownership of a cache line in a shared memory computing system of the type that includes a plurality of nodes and that performs synchronization behaviors including a lock behavior and an atomic update behavior, the method comprising, in a first node among the plurality of nodes:

in response to a first memory request, updating lock prediction data for a cache line associated with the first memory request within a hardware-based lock prediction data structure resident in the first node, wherein at least a portion of the lock prediction data is predictive of whether the cache line associated with the first memory request is further associated with a release operation; and

in response to a second memory request that is associated with the cache line and issued by a second node among the plurality of nodes, accessing the lock prediction data in the lock prediction data structure and determining whether to transfer ownership of the cache line from the first node to the second node based at least in part on the accessed lock prediction data.

2. The method of claim 1, wherein updating the lock prediction data for the cache line associated with the first memory request includes:

in response to determining that a release operation for the cache line associated with the first memory request followed the first memory request, updating the lock prediction data for the cache line to indicate the release operation, wherein the indication of the release operation is predictive that the cache line is associated with the release operation.

3. The method of claim 1, wherein the accessed lock prediction data predicts that the cache line associated with the first and second memory requests is associated with the release operation.

4. The method of claim 3, further comprising:

in response to the accessed lock prediction data predicting that the cache line associated with the first and second memory requests is associated with the release operation, preserving ownership of the cache line with the first node.

5. The method of claim 4, wherein preserving ownership of the cache line with the first node further comprises:

copying the cache line and transferring a read-only copy of the cache line to the second node.

6. The method of claim 3, wherein the accessed lock prediction data includes data associated with a plurality of release operations of a plurality of memory requests associated with the cache line, wherein the accessed lock prediction data predicts that the cache line associated with the first and second memory requests is further associated with the release operation.

7. The method of claim 2, wherein the accessed lock prediction data predicts that the cache line associated with the first and second memory requests is not associated with the release operation.

8. The method of claim 7, further comprising:

in response to the accessed lock prediction data predicting that the cache line associated with the first and second memory requests is not associated with the release operation, migrating the cache line and ownership of the cache line from the first node to the second node; and

invalidating the cache line from a cache of the first node.

9. The method of claim 1, wherein the first memory request includes at least one acquire operation and at least one release operation.

10. The method of claim 1, wherein the first memory request includes at least one release operation such that lock prediction data predicts that the cache line associated with the first memory request is further associated with the release operation.

11. The method of claim 1, wherein the lock prediction data structure includes a tagged set-associative array.

12. The method of claim 11, wherein the lock prediction data for the cache line associated with the first memory request includes validity data associated with the cache line, address data for the cache line, state data for the cache line, and replacement policy data for the cache line.

13. The method of claim 12, wherein the state data indicates a state selected from the group consisting of an invalid state, an atomically updated state, a potentially atomically updated state, a locked state, and a potentially-locked state.

14. The method of claim 1, wherein the lock prediction data structure includes a tagless address-hash-indexed array.

15. The method of claim 14, wherein the lock prediction data for the cache line associated with the first memory request includes state data for the cache line.

16. The method of claim 15, wherein the state data indicates a state selected from the group consisting of an invalid state, an atomically updated state, a potentially atomically updated state, a locked state, and a potential-lock state.

17. A circuit arrangement configured to perform synchronization behaviors including a lock behavior and an atomic update behavior, comprising:

a cache configured to store a plurality of cache lines;

a hardware-based lock prediction data structure configured to store lock prediction data for a cache line stored in the cache and associated with a first memory request, wherein at least a portion of the lock prediction data is predictive of whether the cache line associated with the first memory request is further associated with a release operation; and

control logic coupled to the lock prediction data structure configured to, in response to a second memory request associated with the cache line, access the lock prediction data in the lock prediction data structure to determine whether to transfer ownership of the cache line based at least in part on the accessed lock prediction data.

18. The circuit arrangement of claim 17, wherein the hardware-based lock prediction data structure includes an address-hashed-index data structure, the circuit arrangement further comprising:

a hash index operable to be accessed to determine an entry in the hardware-based lock prediction data structure associated with the cache line.

19. A shared memory computing system of the type that includes a plurality of nodes each comprising the circuit arrangement of claim 17.

20. The shared memory computing system of claim 19, wherein the second memory request is issued from a second node among the plurality of nodes, and wherein a first node is configured to determine whether to transfer ownership of the cache line from the first node to the second node based at least in part on the accessed lock prediction data.

21. A design structure embodied in a non-transitory machine readable medium for designing or manufacturing an integrated circuit device, the integrated circuit device comprising the circuit arrangement of claim 17.

22. An apparatus configured to perform synchronization behaviors including a lock behavior and an atomic update behavior, the apparatus comprising:

a cache configured to store a plurality of cache lines;

a hardware-based lock prediction data structure configured to store lock prediction data for a cache line stored in the cache and associated with a first memory request, wherein at least a portion of the lock prediction data is predictive of whether the cache line associated with the first memory request is further associated with a release operation; and

control logic coupled to the lock prediction data structure, the control logic configured to, in response to a second memory request associated with the cache line, access the lock prediction data in the lock prediction data structure to determine whether to transfer ownership of the cache line based at least in part on the accessed lock prediction data.