Compiler providing idiom to idiom accelerator

• US 8,732,683 B2
• Filed: 02/01/2008
• Issued: 05/20/2014
• Est. Priority Date: 02/01/2008
• Status: Expired due to Fees

• 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): Zhen, Li B
• Assistant Examiner(s): MACASIANO, JOANNE GONZALES
• Application Number:
  US12/024,347
• Publication Number:
  US 20110173593A1
• Time in Patent Office: 2,300 Days
• Field of Search: 717/154, 717/140, 717/129
• US Class Current: 717/143
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code

Abstract

A wake-and-go mechanism may be a programming idiom accelerator. As a processor fetches instructions, the programming idiom accelerator may look ahead to determine whether a programming idiom is coming up in the instruction stream. If the programming idiom accelerator recognizes a programming idiom, the programming idiom accelerator may perform an action to accelerate execution of the programming idiom. A compiler may recognize programming idioms and expose the programming idioms to the programming idiom accelerator within the resulting machine language instructions.

Claims

1. A method, in a compiler, for exposing programming idioms to a programming idiom accelerator, the method comprising:

receiving a portion of high level language program code;

examining a series of instructions in the portion of high level language program code;

determining whether the series of instructions comprises a recognized programming idiom from a plurality of predetermined programming idioms, wherein the set of predetermined programming idioms correspond to a plurality of programming idiom accelerators and wherein each of the plurality of programming idiom accelerators is a hardware device in the data processing system, wherein the plurality of programming idiom accelerators comprise a wake-and-go engine and a linked list acceleration engine;

compiling the high level language program code to machine code;

responsive to a determination that the series of instructions comprises a recognized programming idiom, inserting into the machine code a begin hint instruction that marks a beginning of the recognized programming idiom at a next instruction in the machine code and an end hint instruction that marks an end of the recognized programming idiom, wherein a given programming idiom accelerator that corresponds to the recognized programming idiom is configured to perform a look-ahead operation to examine the machine code being pre-fetched for a thread being executed by a processor and to detect the begin hint instruction, wherein during execution of the machine code by the processor, the given programming idiom accelerator performs at least one action to accelerate execution of the programming idiom, wherein the plurality of programming idiom accelerators are external to the processor;

detecting, by the wake-and-go engine, the begin hint instruction indicating a thread executing on the processor is waiting for an event that modifies a data value associated with a target address;

storing, by the wake-and-go engine, the target address in a wake-and-go entry of a content addressable memory in association with a thread identifier of the thread;

placing the thread in a sleep state; and

responsive to detecting a write to the target address, using the target address to address the content addressable memory and returning, by the content addressable memory, a storage address of the wake-and-go entry, placing the thread corresponding to the thread identifier in the wake-and-go entry in a non-sleep state, and determining whether the write to the target address is the event for which the thread is waiting.

2. The method of claim 1, further comprising:

determining whether the end of the high level language program code is reached; and

responsive to a determination that the end of the high level language program code is not reached, examining a next series of instructions in the portion of high level language program code.

3. The method of claim 1, wherein determining whether the write to the target address is the event for which the thread is waiting comprises:

determining, by the thread, whether the data value being written to the target address is a data value for which the thread is waiting.

4. The method of claim 3, further comprising:

responsive to the data value being written to the target address not being the data value for which the thread is waiting, storing the target address in a wake-and-go entry of a content addressable memory in association with a thread identifier of the thread and placing the thread in a sleep state.

5. The method of claim 1, wherein determining whether the write to the target address is the event for which the thread is waiting comprises determining, by logic associated with the content addressable memory, whether the data value being written to the target address is a data value for which the thread is waiting.

6. A data processing system, comprising:

a processor;

a plurality of programming idiom accelerators external to the processor; and

a memory coupled to the processor, the memory comprising instructions which, when executed by the processor, cause the processor to;

receive a portion of high level language program code;

examine a series of instructions in the portion of high level language program code;

determine whether the series of instructions comprises a recognized programming idiom from a plurality of predetermined programming idioms, wherein the set of predetermined programming idioms correspond to the plurality of programming idiom accelerators and wherein each of the plurality of programming idiom accelerators is a hardware device in the data processing system, wherein the plurality of programming idiom accelerators comprise a wake-and-go engine and a linked list acceleration engine;

compile the high level language program to machine code;

responsive to a determination that the series of instructions comprises a recognized programming idiom, insert into the machine code a begin hint instruction that marks a beginning of the recognized programming idiom at a next instruction in the machine code and an end hint instruction that marks an end of the recognized programming idiom, wherein a given programming idiom accelerator that corresponds to the recognized programming idiom is configured to perform a look-ahead operation to examine the machine code being pre-fetched for a thread being executed by a processor and to detect the begin hint instruction, wherein during execution of the machine code by the processor, the given programming idiom accelerator performs at least one action to accelerate execution of the programming idiom;

detect a thread that is waiting for an event that modifies a data value associated with a target address;

store the target address in a wake-and-go entry of a content addressable memory in association with a thread identifier of the thread;

place the thread in a sleep state; and

responsive to detecting a write to the target address, use the target address to address the content addressable memory and return, by the content addressable memory, a storage address of the wake-and-go entry, place the thread corresponding to the thread identifier in the wake-and-go entry in a non-sleep state, and determine whether the write to the target address is the event for which the thread is waiting.

7. The data processing system of claim 6, wherein the instructions further cause the processor to:

determine whether the end of the high level language program code is reached; and

responsive to a determination that the end of the high level language program code is not reached, examine a next series of instructions in the portion of high level language program code.

8. The data processing system of claim 6, wherein determining whether the write to the target address is the event for which the thread is waiting comprises:

determining, by the thread, whether the data value being written to the target address is a data value for which the thread is waiting.

9. The data processing system of claim 8, wherein responsive to the data value being written to the target address not being the data value for which the thread is waiting, the wake-and-go engine is configured to store the target address in a wake-and-go entry of the content addressable memory in association with the thread identifier of the thread and placing the thread in a sleep state.

10. The data processing system of claim 6, wherein determining whether the write to the target address is the event for which the thread is waiting comprises determining, by logic associated with the content addressable memory, whether the data value being written to the target address is a data value for which the thread is waiting.

11. A computer program product comprising a non-transitory computer useable medium having a computer readable program, wherein the computer readable program, when executed on a computing device, causes the computing device to:

receive a portion of high level language program code;

examine a series of instructions in the portion of high level language program code;

determine whether the series of instructions comprises a recognized programming idiom from a plurality of predetermined programming idioms, wherein the set of predetermined programming idioms correspond to a plurality of programming idiom accelerators and wherein each of the plurality of programming idiom accelerators is a hardware device in the data processing system, wherein the plurality of programming idiom accelerators comprise a wake-and-go engine and a linked list acceleration engine;

compile the high level language program code to machine code;

responsive to a determination that the series of instructions comprises a recognized programming idiom, insert into the machine code a begin hint instruction that marks a beginning of the recognized programming idiom at a next instruction in the machine code and an end hint instruction that marks an end of the recognized programming idiom, wherein a given programming idiom accelerator that corresponds to the recognized programming idiom is configured to perform a look-ahead operation to examine the machine code being pre-fetched for a thread being executed by a processor and to detect the begin hint instruction, wherein during execution of the machine code by the processor, the given programming idiom accelerator performs at least one action to accelerate execution of the programming idiom, wherein the plurality of programming idiom accelerators are external to the processor;

detect a thread that is waiting for an event that modifies a data value associated with a target address;

store the target address in a wake-and-go entry of a content addressable memory in association with a thread identifier of the thread;

place the thread in a sleep state; and

responsive to detecting a write to the target address, use the target address to address the content addressable memory and return, by the content addressable memory, a storage address of the wake-and-go entry, place the thread corresponding to the thread identifier in the wake-and-go entry in a non-sleep state, and determine whether the write to the target address is the event for which the thread is waiting.

12. The computer program product of claim 11, wherein determining whether the write to the target address is the event for which the thread is waiting comprises:

determining, by the thread, whether the data value being written to the target address is a data value for which the thread is waiting.

13. The computer program product of claim 12, wherein responsive to the data value being written to the target address not being the data value for which the thread is waiting, the wake-and-go engine is configured to store the target address in a wake-and-go entry of the content addressable memory in association with the thread identifier of the thread and placing the thread in a sleep state.

14. The computer program product of claim 11, wherein determining whether the write to the target address is the event for which the thread is waiting comprises determining, by logic associated with the content addressable memory, whether the data value being written to the target address is a data value for which the thread is waiting.