ATOMIC-OPERATION COALESCING TECHNIQUE IN MULTI-CHIP SYSTEMS

• US 20110289510A1
• Filed: 02/02/2010
• Published: 11/24/2011
• Est. Priority Date: 02/17/2009
• Status: Active Grant

• Current Assignee: Rambus Inc.
• Original Assignee: Rambus Inc.
• Inventors: Lin, Qi, Sheffler, Thomas J., Peng, Liang, Hampel, Craig E., Rychlik, Bohuslav, Woo, Steven C.
• Granted Patent: US 8,473,681 B2
• Time in Patent Office: Days
• US Class Current: 718/106
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency

Abstract

A cache-coherence protocol distributes atomic operations among multiple processors (or processor cores) that share a memory space. When an atomic operation that includes an instruction to modify data stored in the shared memory space is directed to a first processor that does not have control over the address(es) associated with the data, the first processor sends a request, including the instruction to modify the data, to a second processor. Then, the second processor, which already has control of the address(es), modifies the data. Moreover, the first processor can immediately proceed to another instruction rather than waiting for the address(es) to become available.

Claims

1. A processor, comprising:

processing elements;

caches associated with respective ones of the processing elements; and

a communication channel coupled to the processing elements and to memory, the memory including an address space that is shared by the processing elements;

wherein, prior to executing an atomic operation, a first processing element determines if data associated with the atomic operation is stored in a first cache associated with the first processing element, the data having a state defined by a cache-coherence protocol;

wherein, if the first processing element determines that the data is not stored in the first cache, the first processing element sends a request including the atomic operation for the data on via the communication channel to at least one of the other processing elements; and

wherein, if the data having the state is stored in a second cache associated with a second processing element, the second processing element executes the atomic operation.

2. The processor of claim 1, wherein processing elements without the data having the state stored in their associated caches provide additional replies to the first processing element via the communication channel.

3. The processor of claim 2, further comprising the memory, wherein, if no other processing element performs the atomic operation in response to the request, the first processing element receives the data having the state from the memory and performs the atomic operation.

4. The processor of claim 1, further comprising a cache-coherence mechanism coupled to the communication channel, wherein the first processing element provides the request to the cache-coherence mechanism, which determines if the data is stored in another of the caches with the data having the state;

and, if yes, the cache-coherence mechanism provides the request, including the atomic operation, to another processing element associated with the other cache.

5. The processor of claim 4, wherein the cache-coherence mechanism determines if the data is stored in another of the caches, with the data having the state, by performing a lookup into a look-up table, which includes storage and state information for the caches.

6. The processor of claim 1, wherein the atomic operation is indicated by a tag which is specified by software that provides instructions including the atomic operation to the processor.

7. The processor of claim 1, wherein the atomic operation includes one or more instructions for a respective instruction set architecture that, when executed, either completes or fails in its entirety, and which executes without a conflict occurring at one or more addresses associated with the data.

10. The processor of claim 1, wherein the state can be one of a modified state and an exclusive state.

16. The processor of claim 1, wherein, prior to executing a non-atomic operation, the first processing element determines if data associated with the non-atomic operation is stored in the first cache, and, if not, the first processing element makes another request for the data associated with the non-atomic operation on the communication channel;

and

wherein the other request excludes the non-atomic operation.

17. The processor of claim 1, wherein the atomic operation produces the data as an output.

18. The processor of claim 1, wherein the atomic operation uses the data as an input.

19. The processor of claim 1, wherein the request specifies a time interval during which the atomic operation is to be performed;

and

wherein the request expires if the atomic operation has not been performed during the time interval.

20. The processor of claim 1, wherein the atomic operation includes multiple atomic operations which are to be executed as a unit.

21. The processor of claim 1, wherein the request includes multiple addresses associated with the data.

22. The processor of claim 1, further comprising:

the memory; and

a memory controller coupled to the communication channel and the memory, wherein the memory controller waits for replies to the request from at least the one of the other processing elements prior to taking action in response to the request.

23. The processor of claim 1, further comprising:

the memory; and

a memory controller coupled to the communication channel and the memory, wherein, if none of the other processing elements performs the atomic operation, the memory controller performs the atomic operation and replies to the first processing element via the communication channel.

24. The processor of claim 1, further comprising the memory, wherein, if no other processing element performs the atomic operation, the memory performs the atomic operation and replies to the first processing element via the communication channel.

25. The processor of claim 1, wherein the second processing element associated with the second cache provides a reply on the communication channel if the second processing element executes the atomic operation.

8. (canceled)

9. (canceled)

11. (canceled)

12. (canceled)

13. (canceled)

14. (canceled)

15. (canceled)

26. (canceled)

27. (canceled)

28. (canceled)

29. A computer system, comprising:

processing elements;

caches associated with respective ones of the processing elements;

a communication channel coupled to the processing elements; and

memory coupled to the communication channel, the memory including an address space that is shared by the processing elements;

wherein, prior to executing an atomic operation, a first processing element determines if data associated with the atomic operation is stored in a first cache associated with the first processing element, the data having a state defined by a cache-coherence protocol;

wherein, if the first processing element determines that the data is not stored in the first cache, the first processing element sends a request including the atomic operation for the data on via the communication channel to at least one of the other processing elements; and

wherein, if the data having the state is stored in a second cache associated with a second processing element, the second processing element executes the atomic operation.

30. A method for processing an atomic operation in a processor that includes multiple processing elements and associated caches, which reside in a shared address space, comprising:

assigning the atomic operation to a first processing element, wherein, prior to executing an atomic operation, the first processing element performs one or more actions, including;

determining if data associated with the atomic operation is stored in a first cache associated with the first processing element, the data having a state defined by a cache-coherence protocol; and

,

if the first processing element determines that the data is not stored in the first cache, providing a request including the atomic operation for the data on a communication channel in the processor, wherein the communication channel couples the processing elements to at least one of the other processing elements; and

wherein a second processing element performs one or more additional actions, including;

determining if the data associated with the state is stored in a second cache associated with the second processing element; and

if so, executing the atomic operation.

31. The method of claim 30, wherein, if the determination is negative, the one or more additional actions performed by the second processing element includes providing a reply to the first processing element via the communication channel.

32. The method of claim 30, wherein the first processing element provides the request to a cache-coherence mechanism, which performs one or more additional actions, including:

determining if the data is stored in another of the caches, with the data having the state; and

, if yes,

providing the request, including the atomic operation, to another processing element associated with the other cache.

33. The method of claim 30, wherein the atomic operation is indicated by a tag which is specified by software that provides instructions including the atomic operation to the processor.

34. The method of claim 30, wherein the atomic operation includes one or more instructions for an instruction set architecture that, when executed, either complete or fail as a unit, and which execute without a conflict occurring at one or more addresses associated with the data.

35. The method of claim 30, wherein the state can be one of a modified state and an exclusive state.

37. The method of claim 30, wherein the first processing element performs additional actions, including:

receiving the data having the state from a memory coupled to the communication channel if no other processing element performs the atomic operation; and

performing the atomic operation.

38. The method of claim 30, wherein the atomic operation produces the data as an output.

39. The method of claim 30, wherein the atomic operation uses the data as an input.

40. The method of claim 30, wherein the request specifies a time interval during which the atomic operation is to be performed;

and

wherein the request expires if the atomic operation has not been performed during the time interval.

41. The method of claim 30, wherein the atomic operation includes multiple atomic operations which are to be executed as a unit.

42. The method of claim 30, wherein the request includes multiple addresses associated with the data.

43. The method of claim 30, wherein a memory controller, coupled to the communication channel, performs one or more additional actions, including:

waiting for replies to the request from at least the one of the other processing elements prior to taking action in response to the request.

44. The method of claim 30, wherein the one or more additional actions performed by the second processing element includes providing a reply on the communication channel if the second processing element executes the atomic operation.

45. The method of claim 30, wherein a memory controller, coupled to the communication channel, performs one or more additional actions, including:

performing the atomic operation if no other processing element performs the atomic operation; and

replying to the first processing element via the communication channel.

46. The method of claim 30, wherein a memory, coupled to the communication channel, performs one or more additional actions, including:

performing the atomic operation if no other processing element performs the atomic operation; and

replying to the first processing element via the communication channel

36. (canceled)