Prioritizing instructions based on the number of delay cycles

• US 9,405,548 B2
• Filed: 12/07/2011
• Issued: 08/02/2016
• Est. Priority Date: 12/07/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mericas, Alexander E, Indukuru, Venkat R
• Primary Examiner(s): Caldwell, Andrew
• Assistant Examiner(s): Mehta, Jyoti
• Application Number:
  US13/314,052
• Publication Number:
  US 20130151816A1
• Time in Patent Office: 1,700 Days
• Field of Search: 712/215
• US Class Current: 1/1
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3853 of compound instructions
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory

Abstract

Methods, systems, and computer program products may provide delay-identification in data processing systems. An apparatus may include a delay-identification unit having a delay counter, a threshold register, a delay register, and a delay detector. The delay detector may be configured to start the delay counter in response to detecting that one group of instructions is delayed, and stop the delay counter in response to detecting that the one group of instructions is no longer delayed. The delay detector may additionally be configured to compare the number of cycles counted by the delay counter with a threshold number of cycles in the threshold register, and store at least one effective address of one of the instructions of the one group of instructions when the number of cycles counted by the delay counter is greater than the threshold number of cycles stored in the threshold register.

Claims

1. An apparatus, comprising:

an instruction-grouping circuit configured to organize a plurality of instructions for a computer processor into a plurality of instruction groups prior to execution;

a plurality of execution units configured to execute the plurality of instruction groups based upon cycles of a clock signal;

a delay-identification circuit including;

a delay counter that is configured to count a number of cycles occurring in a time period for a first group of instructions of the plurality of instruction groups, wherein the time period is an amount of time between when a group of instructions is ready to be dispatched to one or more execution units of the plurality of execution units and when the group of instructions has been completely executed by the one or more execution units;

a threshold register that is configured to store a threshold number of cycles that represents an undesired amount of delay within the time period;

a delay register that is configured to store at least one effective address of at least one instruction in the first group of instructions;

a delay detector circuit that is configured to;

detect when the first group of instructions is delayed in the time period;

in response to detecting that the first group of instructions is delayed, start the delay counter to count the number of cycles in the time period;

in response to detecting that the first group of instructions is no longer delayed, stop the delay counter;

compare the number of cycles counted with the threshold number of cycles; and

in response to determining the number of cycles counted is greater than the threshold number of cycles, store at least one effective address of at least one instruction of the first group of instructions; and

a group completion table that is configured to store data regarding the first group of instructions when the first group of instructions has been dispatched to the one or more execution units but has not been at least one of;

completely executed by the one or more execution units and flushed from the apparatus;

wherein the delay detector circuit is further configured to;

detect when the first group of instructions is delayed from being dispatched to the one or more execution units; and

detect when the group completion table is empty for one or more cycles; and

wherein the delay-identification circuit communicates a frequency, from among at least a first frequency and a second frequency, for processing the first group of instructions via the one or more execution units in response to anticipating a delay in the first group of instructions.

2. The apparatus of claim 1, wherein the delay detector circuit is further configured to:

reset the delay counter when the number of cycles counted by the delay counter is not greater than the threshold number of cycles;

detect when the first group of instructions is delayed from being completely executed by the one or more execution units;

detect when the first group of instructions has attained a next-to-complete status; and

in response to detecting that the first group of instructions has not attained a completed status within a number of cycles of attaining the next-to-complete status;

detect an oldest instruction in the one or more execution units that has not yet completed execution, wherein execution of the oldest instruction by one of the one or more execution units began before all other uncompleted instructions;

start the delay counter to count a number of cycles of the oldest instruction; and

stop the delay counter when execution of the oldest instruction completes.

3. The apparatus of claim 2, wherein the delay detector circuit is further configured to, in response to detecting that the first group of instructions has not attained a completed status within a number of cycles of attaining the next-to-complete status:

detect when the number of cycles of the oldest instruction is greater than the threshold number of cycles;

in response to detecting the number of cycles of the oldest instruction is greater than the threshold number of cycles, store one effective address of the oldest instruction; and

in response to execution of the oldest instruction completing;

reset the delay counter; and

detect, a next oldest instruction in the first group of instructions that has not yet completed execution, wherein execution of the next oldest instruction by one of the one or more execution units began before all other uncompleted instructions.

4. The apparatus of claim 1, wherein the delay detector circuit is further configured to:

in response to detecting the group completion table is empty for the one or more cycles, start the delay counter.

5. The apparatus of claim 4, wherein the delay detector circuit is further configured to:

in response to detecting the group completion table is no longer empty, stop the delay counter.

6. The apparatus of claim 1, further comprising:

a delay table that is configured to store data regarding the first group of instructions;

wherein the delay detector circuit is further configured to store, in the delay table, the number of cycles, the threshold number of cycles, and the at least one effective address.

7. The apparatus of claim 6, further comprising:

a prioritization circuit that is configured to;

order a group of incoming instructions prior to execution by the one or more execution units;

read the delay table;

identify, within the group of incoming instructions, one or more instructions that are identified within the delay table as previously causing a delay having an associated cycle count that is greater than the threshold number of cycles;

decrease a priority of the identified one or more instructions;

fetch data needed to avoid the delay when executing the identified one or more instructions; and

in response to fetching data needed to avoid the delay, increase the priority of the identified one or more instructions.

8. The apparatus of claim 6, further comprising a prioritization circuit that is configured to:

order a group of incoming instructions prior to execution;

read the delay table;

identify, within the group of incoming instructions, one or more instructions that are identified within the delay table as previously causing a delay having an associated cycle count that is greater than the threshold number of cycles; and

in response to identifying the one or more instructions, flush the identified one or more instructions from the apparatus.

9. The apparatus of claim 1, wherein the plurality of execution units are configured to operate at the first frequency when the first group of instructions does not include a delay in the time period, and the second frequency that is lower than the first frequency when the first group of instructions includes a delay in the time period.

10. A method, comprising:

in response to anticipating a delay in a group of instructions, communicating a frequency by a delay-identifying apparatus from among at least a first frequency and a second frequency, for processing the group of instructions via one or more execution units;

counting, by the delay-identifying apparatus, a number of cycles of a clock signal occurring in a time period in which the group of instructions is delayed, wherein the time period is the amount of time between when the group of instructions is ready to be dispatched for execution by the one or more execution units and when the group of instructions is completely executed by the one or more execution units and is thus no longer delayed;

detecting when the group of instructions is delayed in the time period;

comparing, by the delay-identifying apparatus, the counted number of cycles with a threshold number of cycles, wherein the threshold number of cycles represents an undesired amount of delay within the time period;

in response to determining the counted number of cycles is greater than the threshold number of cycles, storing, in a memory, an effective address of each instruction of the group of instructions;

detecting when the group of instructions is delayed from being dispatched to the one or more execution units;

storing, to a group completion table, data regarding the group of instructions when the group of instructions has been dispatched to the one or more execution units but has not been at least one of;

completely executed by the one or more execution units and flushed from the apparatus;

detecting when the group completion table is empty for one or more cycles;

in response to detecting the group completion table is empty for the one or more cycles, starting a delay counter; and

in response to detecting the group completion table is no longer empty, stopping the delay counter.

11. The method of claim 10, further comprising:

counting a second number of cycles between when the group of instructions is delayed from being completely executed and when the group of instructions is completely executed by the one or more execution units;

counting a third number of cycles between when the group of instructions has attained a next-to-complete status but has not yet attained a completed status and when an oldest instruction of the group of instructions has been completely executed by one of the one or more execution units; and

counting a fourth number of cycles between when the group of instructions is delayed from being dispatched to the one or more execution units and when the group of instructions is dispatched to the one or more execution units.

12. The method of claim 10, further comprising:

storing, to a delay table for the group of instructions, data regarding the number of cycles, the threshold number of cycles, and at least one effective address; and

ordering a group of incoming instructions prior to execution, the ordering of the group of incoming instructions further comprising;

reading a delay table;

identifying, within the group of incoming instructions, one or more instructions that are identified within the delay table as previously causing a delay having an associated cycle count that is greater than the threshold number of cycles;

decreasing a priority of the identified one or more instructions;

fetching data needed to avoid the delay when executing the identified one or more instructions; and

in response to fetching data needed to avoid the delay, increasing the priority of the identified one or more instructions.

13. The method of claim 10, further comprising:

storing, to a delay table for the group of instructions, data regarding the number of cycles, the threshold number of cycles, and at least one effective address; and

ordering a group of incoming instructions prior to execution, the ordering of the group of incoming instructions further comprising;

reading a delay table;

identifying, within the group of incoming instructions, one or more instructions that are identified within the delay table as previously causing a delay having an associated cycle count that is greater than the threshold number of cycles; and

in response to identifying the one or more instructions, flushing the identified one or more instructions from the delay-identifying apparatus.

14. A computer program product for identifying delays in a first computer processor having one or more execution units, the computer program product comprising at least one non-transitory computer readable storage medium having computer readable program instructions embodied therein that when executed by a second computer processor, enables the second computer processor to:

in response to anticipating a delay in a group of monitored program instructions, communicate a frequency, from among at least a first frequency and a second frequency, for processing the group of monitored program instructions via the one or more execution units;

count a number of cycles of a clock signal occurring in a time period in which the group of monitored program instructions is delayed, wherein the time period is an amount of time between when the group of monitored program instructions is ready to be dispatched for execution by the one or more execution units and when the group of monitored program instructions is completely executed by the one or more execution units, thus no longer delayed;

detect when the group of monitored program instructions is delayed in the time period;

compare the counted number of cycles with a threshold number of cycles, wherein the threshold number of cycles represents an undesired amount of delay within the time period;

in response to determining the counted number of cycles is greater than the threshold number of cycles, store, in a memory, an effective address of each instruction of the group of monitored program instructions;

detect when the group of monitored program instructions is delayed from being dispatched to the one or more execution units;

store, to a group completion table, data regarding the group of monitored program instructions when the group of monitored program instructions has been dispatched to the one or more execution units but has not been at least one of;

completely executed by the one or more execution units and flushed from the apparatus;

detect when the group completion table is empty for one or more cycles;

in response to detecting the group completion table is empty for the one or more cycles, start a delay counter; and

in response to detecting the group completion table is no longer empty, stop the delay counter.

15. The computer program product of claim 14, the computer readable program instructions further comprising instructions that enable the second computer processor to:

count a second number of cycles between when the group of monitored program instructions is delayed from being completely executed and when the group of monitored program instructions is completely executed by the one or more execution units;

count a third number of cycles between when the group of monitored program instructions has attained a next-to-complete status but has not yet attained a completed status and when an oldest instruction of the group of monitored program instructions has been completely executed by one of the one or more execution units; and

count a fourth number of cycles between when the group of monitored program instructions is delayed from being dispatched to the one or more execution units and when the group of monitored program instructions is dispatched to the one or more execution units.

16. The computer program product of claim 14, the computer readable program instructions further comprising instructions that enable the second computer processor to:

store, to a delay table for the group of monitored program instructions, data regarding the number of cycles, the threshold number of cycles, and at least one effective address; and

order a group of incoming instructions prior to execution, the ordering of the group of incoming instructions further comprising;

read the delay table;

identify, within the group of incoming instructions, one or more instructions that are identified within the delay table as previously causing a delay having an associated cycle count that is greater than the threshold number of cycles;

decrease a priority of the identified one or more instructions;

fetch data needed to avoid the delay when executing the identified one or more instructions; and

in response to fetching data needed to avoid the delay, increase the priority of the identified one or more instructions.

17. The computer program product of claim 14, the computer readable program instructions further comprising instructions that enable the second computer processor to:

store, to a delay table for the group of monitored program instructions, data regarding the number of cycles, the threshold number of cycles, and at least one effective address; and

order a group of incoming instructions prior to execution, the ordering of the group of incoming instructions further comprising;

read the delay table;

identify, within the group of incoming instructions, one or more instructions that are identified within the delay table as previously causing a delay having an associated cycle count that is greater than the threshold number of cycles; and

in response to identifying the one or more instructions, flush the identified one or more instructions from the first computer processor.