Look-ahead wake-and-go engine with speculative execution

• US 8,316,218 B2
• Filed: 02/01/2008
• Issued: 11/20/2012
• Est. Priority Date: 02/01/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Arimilli, Ravi K., Sharma, Satya P., Swanberg, Randal C.
• Primary Examiner(s): Chan, Eddie P
• Assistant Examiner(s): LINDLOF, JOHN M
• Application Number:
  US12/024,419
• Publication Number:
  US 20110173419A1
• Time in Patent Office: 1,754 Days
• Field of Search: None
• US Class Current: 712/220
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming

Abstract

A wake-and-go mechanism is provided for a microprocessor. The wake-and-go mechanism looks ahead in the instruction stream of a thread for programming idioms that indicate that the thread is waiting for an event. if a look-ahead polling operation succeeds, the look-ahead wake-and-go engine may record an instruction address for the corresponding idiom so that the wake-and-go mechanism may have the thread perform speculative execution at a time when the thread is waiting for an event. During execution, when the wake-and-go mechanism recognizes a programming idiom, the wake-and-go mechanism may store the thread state in the thread state storage. Instead of putting the thread to sleep, the wake-and-go mechanism may perform speculative execution.

Claims

1. A method, in a data processing system, for performing speculative execution, the method comprising:

examining an instruction stream being pre-fetched for a thread for instances of a programming idiom that causes the thread to wait for an event associated with a target address;

in response to detecting a first instance of the programming idiom in the instruction stream, performing a first look-ahead polling operation to determine whether an event associated with the first instance of the programming idiom has already occurred;

in response to the first look-ahead polling operation resulting in a determination that the event associated with the first instance of the programming idiom has not already occurred, storing a first entry in a wake-and-go storage array wherein the first entry comprises a first target address associated with the first instance of the programming idiom;

in response to detecting a second instance of the programming idiom in the instruction stream, performing a second look-ahead polling operation to determine whether an event associated with the second instance of the programming idiom has already occurred;

in response to the second look-ahead polling operation resulting in a determination that the event associated with the second instance of the programming idiom has already occurred, recording an instruction address for speculative execution of instructions following the second instance of the programming idiom in the instruction stream of the thread; and

responsive to detecting the first instance of the programming idiom during execution of the thread, storing thread state information for the thread and initiating speculative execution from the recorded instruction address.

2. The method of claim 1, further comprising:

responsive to an event that modifies the first target address associated with the first instance of the programming idiom, determining whether to end speculative execution.

3. The method of claim 2, wherein determining whether to end speculative execution comprises determining whether a data value being written to the first target address associated with the first instance of the programming idiom is the data value for which the thread is waiting in the first instance of the programming idiom.

4. The method of claim 1, further comprising responsive to the event that modifies the first target address associated with the first instance of the programming idiom reloading the state information for the thread.

5. The method of claim 1, wherein the event is an asynchronous event caused by a device outside a processor running the thread.

6. The method of claim 1, wherein the wake-and-go storage array is a content addressable memory and an address appearing on an address bus is used to address the content addressable memory.

7. The method of claim 1, wherein the programming idiom comprises an instruction sequence comprising a load command, a compare command, and a branch command.

8. A data processing system, comprising:

a hardware wake-and-go mechanism;

a wake-and-go storage array; and

a thread state storage,

wherein the hardware wake-and-go mechanism is configured to;

examine an instruction stream being pre-fetched for a thread for instances of a programming idiom that causes the thread to wait for an event associated with a target address;

in response to detecting a first instance of the programming idiom in the instruction stream, perform a first look-ahead polling operation to determine whether an event associated with the first instance of the programming idiom has already occurred;

in response to the first look-ahead polling operation resulting in a determination that the event associated with the first instance of the programming idiom has not already occurred, store a first entry in the wake-and-go storage array, wherein the first entry comprises a first target address associated with the first instance of the programming idiom;

in response to detecting a second instance of the programming idiom in the instruction stream, perform a second look-ahead polling operation to determine whether an event associated with the second instance of the programming, idiom has already occurred;

in response to the second look-ahead polling operation resulting in a determination that the event associated with the second instance of the programming idiom has already occurred, record an instruction address for speculative execution of instructions following the second instance of the programming idiom in the instruction stream of the thread; and

responsive to detecting the first instance of the programming idiom during execution of the thread, store thread state information for the thread in the thread state storage and initiate speculative execution from the recorded instruction address.

9. The data processing system of claim 8, wherein the hardware wake-and-go mechanism is configured to determine whether to end speculative execution responsive to an event that modifies the first target address associated with the first instance of the programming idiom.

10. The data processing system of claim 9, wherein determining whether to end speculative execution comprises determining whether a data value being written to the first target address associated with the first instance of the programming idiom is the data value for which the thread is waiting in the first instance of the programming idiom.

11. The data processing system of claim 8, wherein the hardware wake-and-go mechanism is configured to reload the state information for the thread from the thread state storage responsive to the event that modifies the first target address associated with the first instance of the programming idiom.

12. The data processing system of claim 8, wherein the event is an asynchronous event caused by a device outside a processor running the thread.

13. The data processing system of claim 8, wherein the wake-and-go storage array is a content addressable memory and an address appearing on an address bus is used to address the content addressable memory.

14. The data processing system of claim 8, wherein the programming idiom comprises an instruction sequence comprising a load command, a compare command, and a branch command.

15. A computer program product comprising a computer storage medium having a computer readable program stored thereon, wherein the computer readable program, when executed on a computing device, causes the computing device to:

examine an instruction stream being pre-fetched for a thread for instances of a programming idiom that causes the thread to wait for an event associated with a target address;

in response to detecting a first instance of the programming idiom in the instruction stream, perform a first look-ahead polling operation to determine whether an event associated with the first instance of the programming idiom has already occurred;

in response to the first look-ahead polling operation resulting in a determination that the event associated with the first instance of the programming idiom has not already occurred, store a first entry in a wake-and-go storage array wherein the first entry comprises a first target address associated with the first instance of the programming idiom;

in response to detecting a second instance of the programming idiom in the instruction stream, perform a second look-ahead polling operation to determine whether an event associated with the second instance of the programming idiom has already occurred;

in response to the second look-ahead polling operation resulting in a determination that the event associated with the second instance of the programming idiom has already occurred record an instruction address for speculative execution of instructions following the second instance of the programming idiom in the instruction stream of the thread; and

responsive to detecting the first instance of the programming idiom during execution of the thread, store thread state information for the thread and initiate speculative execution from the recorded instruction address.

16. The computer program product of claim 15, wherein the event is an asynchronous event caused by a device outside a processor running the thread.

17. The computer program product of claim 15, wherein the programming idiom comprises an instruction sequence comprising a load command, a compare command, and a branch command.

18. The computer program product of claim 15, wherein the computer readable program further causes the computing device to:

responsive to an event that modifies the first target address associated with the first instance of the programming idiom, determine whether to end speculative execution.

19. The computer program product of claim 18, wherein determining whether to end speculative execution comprises determining whether a data value being written to the first target address associated with the first instance of the programming idiom is the data value for which the thread is waiting in the first instance of the programming idiom.

20. The computer program product of claim 15, wherein the computer readable program, when executed on a computing device, causes the computing device to:

reload the state information for the thread responsive to the event that modifies the first target address associated with the first instance of the programming idiom.