Speculative Instruction Issue in a Simultaneously Multithreaded Processor

• US 20080189521A1
• Filed: 04/17/2008
• Published: 08/07/2008
• Est. Priority Date: 09/17/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sartorius, Thomas Andrew, Smith, Rodney Wayne, Bridges, Jeffrey Todd, Augsburg, Victor Roberts, Mcilvaine, Michael Scott
• Granted Patent: US 7,725,684 B2
• Time in Patent Office: Days
• US Class Current: 712/214
• CPC Class Codes: G06F 9/3826 Bypassing or forwarding of data results, e.g. locally between pipeline stages or within a pipeline stage
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming

Abstract

A method for optimizing throughput in a microprocessor that is capable of processing multiple threads of instructions simultaneously. Instruction issue logic is provided between the input buffers and the pipeline of the microprocessor. The instruction issue logic speculatively issues instructions from a given thread based on the probability that the required operands will be available when the instruction reaches the stage in the pipeline where they are required. Issue of an instruction is blocked if the current pipeline conditions indicate that there is a significant probability that the instruction will need to stall in a shared resource to wait for operands. Once the probability that the instruction will stall is below a certain threshold, based on current pipeline conditions, the instruction is allowed to issue.

Claims

1-15. -15. (canceled)

16. A simultaneous multithreaded computer processor with speculative instruction issue that increases throughput, the computer processor comprising:

multiple independent input buffers, wherein one set of buffers is provided for each of a plurality of independent threads of instructions;

instruction issue logic that has an output buffer and is connected to the independent input buffers, wherein the instruction issue logic;

receives a set of instructions comprising one instruction from each of the threads of instructions;

identifies as dependent instructions those received instructions that require a result from a prerequisite instruction;

determines a probability for each instruction that the each instruction will complete all stages of a multi-stage instruction pipeline of the processor without causing a stall, wherein the probability for each received instruction is expressed as a percentage value;

selects the received instruction of the set that is least likely to cause a stall in the multi-stage pipeline; and

issues the selected instruction into the pipeline for processing, from the instruction issue logic, when the probability for the selected instruction is above a predetermined threshold that is 50%; and

wherein a first stage of the multi-stage pipeline is connected to an output buffer of the instruction issue logic.

17. The computer processor of claim 16, wherein the instruction issue logic determines whether there is a shared resource conflict between two or more of the received instructions.

18. The computer processor of claim 17, wherein the instruction issue logic resolves a given one of said shared resource conflicts, between two or more of said received instructions, after said given conflict has been discovered.

20. The computer processor of claim 16, wherein the instruction issue logic predicts a stage, within the multi-stage instruction pipeline, where results of each instruction will be available, and determines the probability for a dependent instruction by calculating a critical distance comprising a number of stages between a stage when the dependent instruction will need a given result, and a stage when the result will be available.

21. The computer processor of claim 16, wherein the instruction issue logic further identifies as dependent instructions those received instructions that have a conflict over a shared resource within a computer system in which the computer processor operates.

22. The computer processor of claim 21, wherein the probability for a dependent instruction is determined based upon a current location and a predicted stage of any prerequisite instruction and upon a predicted resolution of any identified shared resource conflict.

23. The computer processor of claim 22, wherein the instruction issue logic dynamically recalculates the probability for each instruction based on current contents of the pipeline and a current status of any shared resources.

19. (canceled)

24. (canceled)

25. (canceled)

26. (canceled)

27. (canceled)

28. (canceled)

29. (canceled)

30. (canceled)

31. (canceled)

32. (canceled)

33. (canceled)

34. A computer program product in a computer readable medium for issuing instructions in a multithreaded computer processor, wherein the computer program product comprises:

first instructions for receiving a set of computer instructions in an instruction issue logic, wherein each instruction of said set comprises one instruction from each of a plurality of independent instruction threads;

second instructions for identifying as dependent instructions those received instructions that require a result from a prerequisite instruction;

third instructions for determining a probability for each received instruction that the received instruction will complete all stages of the processor without causing a stall wherein the probability for each received instruction is expressed as a percentage value;

fourth instructions for selecting the received instruction of the set that is least likely to cause a stall in the multi-stage pipeline; and

fifth instructions for issuing the selected instruction into the pipeline for processing, from the instruction issue logic, when the probability for the selected instruction is above a predetermined threshold that is 50%.

35. The computer program product of claim 34, further comprising:

sixth instructions for determining whether there is a shared resource conflict between two or more of the received instructions of said set.

36. The computer program product of claim 35, wherein a given one of said shared resource conflicts, between two or more of said received instructions, is resolved after said given conflict has been discovered.

38. The computer program product of claim 34, further comprising:

seventh instructions for predicting a stage, within the multi-stage instruction pipeline, where results of each instruction will be available, and determining a probability for a received instruction by calculating a critical distance comprising a number of stages between a stage when the received instruction will need a given result, and the stage when a result will be available.

39. The computer program product of claim 38, wherein the probability for a dependent instruction is determined based upon a current location and a predicted stage of any prerequisite instruction and upon a predicted resolution of any identified shared resource conflict.

40. The computer program product of claim 39, wherein the probability for each instruction is dynamically recalculated, based on the current contents of the pipeline and a current status of any shared resources.

37. (canceled)