SPECULATIVE EXECUTION AND ROLLBACK

• US 20130117541A1
• Filed: 11/04/2011
• Published: 05/09/2013
• Est. Priority Date: 11/04/2011
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: Jack Hilaire Choquette
• Inventors: Giroux, Olivier, Stoll, Robert J., Qiu, Xiaogang, CHOQUETTE, Jack Hilaire
• Granted Patent: US 9,830,158 B2
• Time in Patent Office: Days
• US Class Current: 712/214
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]

Abstract

One embodiment of the present invention sets forth a technique for speculatively issuing instructions to allow a processing pipeline to continue to process some instructions during rollback of other instructions. A scheduler circuit issues instructions for execution assuming that, several cycles later, when the instructions reach multithreaded execution units, that dependencies between the instructions will be resolved, resources will be available, operand data will be available, and other conditions will not prevent execution of the instructions. When a rollback condition exists at the point of execution for an instruction for a particular thread group, the instruction is not dispatched to the multithreaded execution units. However, other instructions issued by the scheduler circuit for execution by different thread groups, and for which a rollback condition does not exist, are executed by the multithreaded execution units. The instruction incurring the rollback condition is reissued after the rollback condition no longer exists.

Claims

1. A method of performing rollback of speculatively issued instructions, the method comprising:

issuing a first set of instructions for a first thread group;

issuing a second set of instructions for a second thread group;

detecting a rollback condition for at least one thread in the first thread group during pre-execution processing of an instruction in the first set of instructions;

stopping issuing of additional instructions for the first thread group;

discarding in-flight instructions that have issued and have not been executed in the first set of instructions; and

executing the second set of instructions for the second thread group.

2. The method of claim 1, further comprising:

issuing a third set of instructions for a third thread group;

detecting a partial rollback condition for at least one thread in the third thread group during pre-execution processing of a first instruction in the third set of instructions;

storing a partial rollback active mask indicating a first portion of threads in the third thread group that diverge for the first instruction; and

executing the first instruction for a second portion of the threads in the third thread group that do not diverge for the first instruction.

3. The method of claim 2, further comprising,

reissuing the first instruction for the third thread group;

and

executing the first instruction for the first portion of threads based on the partial rollback active mask.

4. The method of claim 1, wherein the instruction in the first set of instructions specifies an invalid super-scalar-pair of two operations that cannot be performed in parallel.

5. The method of claim 4, further comprising:

issuing a first operation of the invalid super-scalar-pair as a first instruction for the first thread group; and

issuing a first operation of the invalid super-scalar-pair as a second instruction for the first thread group.

6. The method of claim 1, wherein the instruction in the first set of instructions is a barrier synchronization instruction configured to synchronize the first thread group with the second thread group.

7. The method of claim 1, wherein the instruction in the first set of instructions specifies an operand that is corrupted.

8. The method of claim 1, further comprising:

determining that the rollback condition is removed; and

reissuing the first set of instructions for the first thread group.

9. The method of claim 1, wherein the in-flight instructions are discarded after completing the pre-execution processing.

10. The method of claim 1, further comprising:

determining that the rollback condition is removed; and

reissuing the first set of instructions for the first thread group before all of the in-flight instructions are discarded.

11. A system for scheduling compute tasks for execution, the system comprising:

a memory that is configured to store a first set of instructions for a first thread group and a second set of instructions for a second thread group;

a scheduler unit that is configured to;

issue the first set of instructions for the first thread group;

issue the second set of instructions for the second thread group; and

stop issuing additional instructions for the first thread group when a rollback condition is detected;

a dispatch unit that is configured to;

detect the rollback condition for at least one thread in the first thread group during pre-execution processing of an instruction in the first set of instructions; and

discard in-flight instructions that have issued and have not been executed in the first set of instructions; and

multiple execution units configured to execute the second set of instructions for the second thread group.

12. The system of claim 11, wherein the scheduler unit is further configured to:

issue a third set of instructions for a third thread group,

the dispatch unit is further configured to;

detect a partial rollback condition for at least one thread in the third thread group during pre-execution processing of a first instruction in the third set of instructions; and

store a partial rollback active mask indicating a first portion of threads in the third thread group that diverge for the first instruction, and

the multiple execution units are further configured to;

execute the first instruction for a second portion of the threads in the third thread group that do not diverge for the first instruction.

13. The system of claim 12, wherein the scheduler unit is further configured to reissue the first instruction for the third thread group and the multiple execution units are further configured to execute the first instruction for the first portion of threads based on the partial rollback active mask.

14. The system of claim 11, wherein the instruction in the first set of instructions specifies an invalid super-scalar-pair of two operations that cannot be performed in parallel.

15. The system of claim 14, wherein the scheduler unit is further configured to:

issue a first operation of the invalid super-scalar-pair as a first instruction for the first thread group; and

issue a first operation of the invalid super-scalar-pair as a second instruction for the first thread group.

16. The system of claim 11, wherein the instruction in the first set of instructions is a barrier synchronization instruction configured to synchronize the first thread group with the second thread group.

17. The system of claim 11, wherein the instruction in the first set of instructions specifies an operand that is corrupted.

18. The system of claim 11, wherein the scheduler unit is further configured to reissue the first set of instructions for the first thread group after the rollback condition is removed.

19. The system of claim 11, wherein the dispatch unit is further configured to discard the in-flight instructions after completing the pre-execution processing of the in-flight instructions.

20. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to perform rollback of speculatively issued instructions, by performing the steps of:

issuing a first set of instructions for a first thread group;

issuing a second set of instructions for a second thread group;

detecting a rollback condition for at least one thread in the first thread group during pre-execution processing of an instruction in the first set of instructions;

stopping issuing of additional instructions in the first set of instructions for the first thread group;

discarding in-flight instructions that have issued and have not been executed in the first set of instructions; and

executing the second set of instructions for the second thread group.