Batched replays of divergent operations

Patent metadata

Field	Value
Publication number	US-9817668-B2
Application number	US-201113329066-A
Country	US
Kind code	B2
Filing date	Dec 16, 2011
Priority date	Dec 16, 2011
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

One embodiment of the present invention sets forth an approach for executing replay operations for divergent operations in a parallel processing subsystem. Specifically, the streaming multiprocessor (SM) includes a multistage pipeline configured to batch two or more replay operations for processing via replay loop. A logic element within the multistage pipeline detects whether the current pipeline stage is accessing a shared resource, such as loading data from a shared memory. If the threads are accessing data which are distributed across multiple cache lines, then the multistage pipeline batches two or more replay operations, where the replay operations are inserted into the pipeline back-to-back.

First claim

What is claimed is:

1. A computer-implemented method for replaying a shared resource access operation, the method comprising:
selecting a first thread and a second thread from a group of threads configured to simultaneously execute an instruction in a multi-stage pipeline, wherein neither the first thread nor the second thread has yet executed the instruction after one or more execution operations of the instruction for the group of threads, the first thread accesses a first shared resource, the second thread accesses a second shared resource, and the first shared resource and the second shared resource are not retrievable during the same execution operation;
selecting a first set of threads to associate with the first thread;
selecting a second set of threads to associate with the second thread;
inserting a first replay operation associated with the first thread and the first set of threads into the multi-stage pipeline to execute the instruction; and
inserting a second replay operation associated with the second thread and the second set of threads into the multi-stage pipeline to execute the instruction, wherein the second replay operation is inserted into the multi-stage pipeline serially relative to the first replay operation.

2. The method of claim 1 , wherein the first thread and the first set of threads share no common thread with the second thread and the second set of threads.

3. The method of claim 1 , wherein the first set of threads is selected concurrently with the selection of the first thread, and the second set of threads is selected concurrently with the selection of the second thread.

4. The method of claim 1 , wherein the second replay operation associated with the second thread and the second set of threads is inserted into the multi-stage pipeline one pipeline stage subsequent to the first replay operation associated with the first thread and the first set of threads.

5. The method of claim 1 , wherein the first thread and each thread in the first set of threads are configured to access the first shared resource, and the second thread and each thread in the second set of threads are configured to access the second shared resource.

6. The method of claim 5 , wherein the first replay operation associated with the first thread and the first set of threads and the second replay operation associated with the second thread and the second set of threads are inserted into the multi-stage pipeline via a first pipeline stage of the multi-stage pipeline that is subsequent to a second pipeline stage of the multi-stage pipeline.

7. The method of claim 5 , wherein a second instruction is inserted into the multi-stage pipeline serially relative to the second replay operation associated with the second thread and the second set of threads.

8. A subsystem for replaying a shared resource access operation, comprising:
a load-store unit (LSU) configured to:
select a first thread and a second thread from a group of threads configured to simultaneously execute an instruction in a multi-stage pipeline, wherein neither the first thread nor the second thread has yet executed the instruction after one or more execution operations of the instruction for the group of threads, the first thread accesses a first shared resource, the second thread accesses a second shared resource, and the first shared resource and the second shared resource are not retrievable during the same execution operation;
select a first set of threads to associate with the first thread;
select a second set of threads to associate with the second thread;
insert a first replay operation associated with the first thread and the first set of threads into the multi-stage pipeline to execute the instruction; and
insert a second replay operation associated with the second thread and the second set of threads into the multi-stage pipeline to execute the instruction, wherein the second replay operation is inserted into the multi-stage pipeline serially relative to the first replay operation.

9. The subsystem of claim 8 , wherein the first thread and the first set of threads share no common thread with the second thread and the second set of threads.

10. The subsystem of claim 8 , wherein the first set of threads is selected concurrently with the selection of the first thread, and the second set of threads is selected concurrently with the selection of the second thread.

11. The subsystem of claim 8 , wherein the second replay operation associated with the second thread and the second set of threads is inserted into the multi-stage pipeline one pipeline stage subsequent to the first replay operation associated with the first thread and the first set of threads.

12. The subsystem of claim 8 , wherein the first thread and each thread in the first set of threads are configured to access the first shared resource, and the second thread and each thread in the second set of threads are configured to access the second shared resource.

13. The subsystem of claim 12 , wherein the first replay operation associated with the first thread and the first set of threads and the second replay operation associated with the second thread and the second set of threads are inserted into the multi-stage pipeline via a first pipeline stage of the multi-stage pipeline that is subsequent to a second pipeline stage of the multi-stage pipeline.

14. The subsystem of claim 12 , wherein a second instruction is inserted into the multi-stage pipeline serially relative to the second replay operation associated with the second thread and the second set of threads.

15. A computing device, comprising:
a subsystem that includes a load-store unit (LSU) configured to:
select a first thread and a second thread from a group of threads configured to simultaneously execute an instruction in a multi-stage pipeline, wherein neither the first thread nor the second thread has yet executed the instruction after one or more execution operations of the instruction for the group of threads, the first thread accesses a first shared resource, the second thread accesses a second shared resource, and the first shared resource and the second shared resource are not retrievable during the same execution operation;
select a first set of threads to associate with the first thread;
select a second set of threads to associate with the second thread;
insert a first replay operation associated with the first thread and the first set of threads into the multi-stage pipeline to execute the instruction; and
insert a second replay operation associated with the second thread and the second set of threads into the multi-stage pipeline to execute the instruction, wherein the second replay operation is inserted into the multi-stage pipeline serially relative to the replay operation.

16. The computing device of claim 15 , wherein the first thread and each thread in the first set of threads are configured to access the first shared resource, and the second thread and each thread in the second set of threads are configured to access the second shared resource.

17. The computing device of claim 16 , wherein the first replay operation associated with the first thread and the first set of threads and the second replay operation associated with the second thread and the second set of threads are inserted into the multi-stage pipeline via a first pipeline stage of the multi-stage pipeline that is subsequent to a second pipeline stage of the multi-stage pipeline.

18. The computing device of claim 16 , wherein a second instruction is inserted into the multi-stage pipeline

Assignees

• Fetterman Michael
• Choquette Jack Hilaire
• Paranjape Omkar
• Rajendran Anjana
• Hill Eric Lyell
• Carlton Stewart Glenn
• Selvanesan Rajeshwaran
• Hahn Douglas J
• Heinrich Steven James
• Nvidia Corp

Inventors

• Fetterman Michael
• Choquette Jack Hilaire
• Paranjape Omkar
• Rajendran Anjana
• Hill Eric Lyell
• Carlton Stewart Glenn
• Selvanesan Rajeshwaran
• Hahn Douglas J
• Heinrich Steven James

Classifications

• G06F9/3861

  Recovery, e.g. branch miss-prediction, exception handling (error detection or correction G06F11/00) · CPC title

• G06F9/3851 Primary

  from multiple instruction streams, e.g. multistreaming · CPC title

• G06F9/3888

  controlled by a single instruction for multiple threads [SIMT] in parallel · CPC title