Method for proactive synchronization within a computer system

• US 7,636,819 B2
• Filed: 08/23/2006
• Issued: 12/22/2009
• Est. Priority Date: 08/23/2005
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Alsup, Mitchell
• Primary Examiner(s): Kim; Matt
• Assistant Examiner(s): SCHNEE, HAL W
• Application Number:
  US11/508,646
• Publication Number:
  US 20070050562A1
• Time in Patent Office: 1,217 Days
• Field of Search: 711/152, 711/155, 711/147, 711/163
• US Class Current: 711/152
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means
• CPC Class Codes: G06F 12/0862 with prefetch
• 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 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/3017 Runtime instruction translation, e.g. macros
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method for providing proactive synchronization in a computer system includes a processor requesting exclusive access to a given memory resource. The request may include one or more addresses associated with the given memory resource. The method also includes comparing each of the addresses in the request to each address in a plurality of sets of addresses. Each address in the sets of addresses may correspond to a respective memory resource to which a requestor has exclusive access. In addition, in response to any address of the one or more addresses matching any address in the plurality of sets of addresses, the method includes returning a count value associated with the set including the matching address. The count value may be indicative of the number of requestors contending for the matching address. Software may utilize this count value to proactively choose an item with lower contention probabilities in subsequent attempts.

Claims

1. A method comprising:

a processor that implements an x86 architecture requesting exclusive access to one or more memory resources, wherein each request includes one or more mov instructions each specifying an address associated with a respective one of the memory resources, and wherein each mov instruction includes an x86 LOCK instruction prefix;

comparing each address specified in the one or more mov instructions to each address of a plurality of sets of addresses, wherein each address of the plurality of sets of addresses corresponds to a respective memory resource to which a requestor has been granted exclusive access;

in response to any address specified in the one or more mov instructions matching any address in the plurality of sets of addresses, returning a count value associated with the matching address, wherein the count value is indicative of a number of requestors contending for the matching address; and

using the count value to avoid interference on any subsequent synchronization attempt to access the requested memory resources, and to select one or more different memory resources in subsequent operations.

2. The method as recited in claim 1, further comprising returning a pass count value of zero in response to no address specified in the one or more mov instructions matching any address in the plurality of sets of addresses.

3. The method as recited in claim 1, further comprising storing each set of the plurality of sets of addresses in a respective entry of a storage.

4. The method as recited in claim 3, further comprising adding the addresses specified in the one or more mov instructions to the plurality of sets of addresses and obtaining exclusive access to the requested memory resources in response to no address specified in the one or more mov instructions matching any address in the plurality of sets of addresses.

5. The method as recited in claim 3, further comprising storing a plurality of count values in the respective entry, each count value corresponding to a respective address in the respective entry.

6. The method as recited in claim 3, further comprising storing the count value that corresponds to each set of the plurality of sets of addresses in the respective entry.

7. The method as recited in claim 3, further comprising removing the addresses specified in the one or more mov instructions from the plurality of sets of addresses in response to completion of operation on data in the requested memory resources.

8. The method as recited in claim 1, further comprising increasing the count value associated with the matching address prior to returning the count value.

9. The method as recited in claim 1, wherein the x86 LOCK instruction prefix causes addresses specified in the one or more mov instructions to be marked with one or more indication bits during instruction decode.

10. The method as recited in claim 9, wherein requesting exclusive access further comprises executing an acquire instruction that causes each of the addresses specified in the one or more mov instructions to be compared to each address of the plurality of sets of addresses.

11. The method as recited in claim 10, further comprising storing the addresses specified in the one or more mov instructions in a processor buffer, and in response to execution of the acquire instruction sending all the addresses in the processor buffer, as a set, to be compared.

12. The method as recited in claim 10, wherein the acquire instruction further causes the returned count value to be stored in a processor register specified during execution of the acquire instruction.

13. The method as recited in claim 10, wherein the acquire instruction further causes a condition code associated with the returned count value to be stored in a processor condition code register during execution of the acquire instruction.

14. A computer system comprising:

one or more processors that implement an x86 architecture and are coupled together and to one or more memories, wherein each of the one or more processors is configured to execute instructions to request exclusive access to one or more memory resources, wherein each request includes one or more mov instructions each specifying an address associated with a respective one of the memory resources, and wherein each mov instruction includes an x86 LOCK instruction prefix; and

an arbitration unit coupled to compare each address specified in the one or more mov instructions to each address of a plurality of sets of addresses, wherein each address of the plurality of sets of addresses corresponds to a respective memory resource to which a requestor has been granted exclusive access;

wherein the arbitration unit is configured to return a count value associated with the matching address in response to any address specified in the one or more mov instructions matching any address in the plurality of sets of addresses, wherein the count value is indicative of a number of requestors contending for the matching address; and

wherein each of the processors is configured to use the count value to avoid interference on any subsequent synchronization attempt to access the requested memory resources, and to select one or more different memory resources in subsequent operations.

15. The computer system as recited in claim 14, wherein the arbitration unit is further configured to return a pass count value of zero in response to no address specified in the one or more mov instructions matching any address in the plurality of sets of addresses.

16. The computer system as recited in claim 14, wherein the arbitration unit is further configured to store each set of the plurality of sets of addresses in a respective entry of a storage.

17. The computer system as recited in claim 16, wherein the arbitration unit is further configured to add the addresses specified in the one or more mov instructions to the plurality of sets of addresses in response to no address specified in the one or more mov instructions matching any address in the plurality of sets of addresses, thereby allowing exclusive access to the requested memory resources.

18. The computer system as recited in claim 16, wherein the arbitration unit is further configured to store a plurality of count values in the respective entry, each count value corresponding to a respective address in the respective entry.

19. The computer system as recited in claim 16, wherein the arbitration unit is further configured to store the count value that corresponds to each set of the plurality of sets of addresses in the respective entry.

20. The computer system as recited in claim 16, wherein the arbitration unit is further configured to remove the addresses specified in the one or more mov instructions from the plurality of sets of addresses in response to a notification of completion of operation on data in the requested memory resources.

21. The computer system as recited in claim 14, wherein the arbitration unit is further configured to increase the count value associated with the matching address prior to returning the count value.

22. The computer system as recited in claim 14, wherein each of the one or more processors is further configured to mark with one or more indication bits during instruction decode, each address specified in the one or more mov instructions having the x86 LOCK instruction prefix.

23. The computer system as recited in claim 22, wherein each of the one or more processors is further configured to execute an acquire instruction that causes each of the addresses specified in the one or more mov instructions to be compared to each address of the plurality of sets of addresses.

24. The computer system as recited in claim 23, wherein each of the one or more processors includes an interface unit configured to store the addresses specified in the one or more mov instructions in a processor buffer, and in response to execution of the acquire instruction the interface unit is further configured to send, as a set, all the addresses in the processor buffer to be compared.

25. The computer system as recited in claim 23, wherein the interface unit is further configured to route the returned count value for storage within a register of a requesting processor of the one or more processors, wherein the register is specified during execution of the acquire instruction.