Conditional atomic operations in single instruction multiple data processors

• US 10,209,990 B2
• Filed: 06/02/2015
• Issued: 02/19/2019
• Est. Priority Date: 06/02/2015
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Wood, David A., Reinhardt, Steven K., Beckmann, Bradford M., Orr, Marc S.
• Primary Examiner(s): Petranek, Jacob
• Application Number:
  US14/728,643
• Publication Number:
  US 20160357551A1
• Time in Patent Office: 1,358 Days
• 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/345 of multiple operands or results addressing multiple banks G06F12/06
• 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/526 Mutual exclusion algorithms

Abstract

A conditional fetch-and-phi operation tests a memory location to determine if the memory locations stores a specified value and, if so, modifies the value at the memory location. The conditional fetch-and-phi operation can be implemented so that it can be concurrently executed by a plurality of concurrently executing threads, such as the threads of wavefront at a GPU. To execute the conditional fetch-and-phi operation, one of the concurrently executing threads is selected to execute a compare-and-swap (CAS) operation at the memory location, while the other threads await the results. The CAS operation tests the value at the memory location and, if the CAS operation is successful, the value is passed to each of the concurrently executing threads.

Claims

1. A method comprising:

in response to a request to execute conditionally a first atomic operation for a plurality of threads at a processor;

selecting, at the processor, a first thread of the plurality of threads to execute a second atomic operation, wherein the second atomic operation is a conditional operation whose completion depends on contents of a memory location targeted by the second atomic operation; and

executing, at the processor, the second atomic operation at the first thread.

2. The method of claim 1, further comprising:

selecting the first thread from among the plurality of threads to execute the second atomic operation.

3. The method of claim 2, further comprising:

providing a result of the second atomic operation executed at the first thread to other threads of the plurality of threads.

4. The method of claim 3, wherein providing the result of the second atomic operation comprises:

indicating a success result of the second atomic operation to the other threads.

5. The method of claim 3, wherein providing the result comprises:

providing the result of the second atomic operation to the other threads via execution of a reduction instruction.

6. The method of claim 2, wherein the first atomic operation is a fetch-and-phi operation.

7. The method of claim 6, wherein the first atomic operation is a fetch-and-add operation.

8. The method of claim 6, wherein the second atomic operation is a compare-and-swap operation.

9. A method, comprising:

receiving a request to execute a fetch-and-phi operation for each of a plurality of threads concurrently executing at a processor; and

in response to the request to execute the fetch-and-phi operation, executing, at the processor, a compare-and-swap (CAS) operation whose completion depends on contents of a memory location targeted by the CAS operation at a selected one of the plurality of concurrently executing threads.

10. The method of claim 9, further comprising:

communicating a result of the CAS operation to each of the plurality of concurrently executing threads to indicate a success or failure of the fetch-and-phi operation.

11. The method of claim 10, wherein communicating the result of the CAS operation comprises communicating the result via a reduction instruction.

12. The method of claim 9, further comprising:

communicating a value returned by the CAS operation to each of the plurality of concurrently executing threads.

13. The method of claim 12, further comprising:

modifying the value returned by the CAS operation at each of the plurality of concurrently executing threads by a different offset.

14. A non-transitory computer readable storage medium embodying a set of executable instructions, the set of executable instructions to manipulate at least one processor to:

in response to a request to execute conditionally a first atomic operation for a plurality of threads at a processor, the first atomic operation being a non-conditional operation;

select a first thread of the plurality of threads; and

execute a second atomic operation at the first thread, wherein the second atomic operation is a conditional operation whose completion depends on contents of a memory location targeted by the second atomic operation.

15. The computer readable medium of claim 14, further comprising:

instructions to manipulate the at least one processor to provide a result of the second atomic operation to a second thread of the plurality of threads.

16. The computer readable medium of claim 15, further comprising:

instructions to manipulate the processor to indicate a success result of the second atomic operation to the second thread.

17. The computer readable medium of claim 15, wherein instructions to provide the result of the second atomic operation comprise instructions to instructions to manipulate the processor to provide the result of the second atomic operation to each of the plurality of threads via a reduction instruction.

18. The computer readable medium of claim 15, wherein the first atomic operation is a fetch-and-phi operation.

19. The computer readable medium of claim 18, wherein the second atomic operation is a compare-and-swap operation.

20. The computer readable medium of claim 18, wherein the first atomic operation is a fetch-and-add operation.