Recording performance metrics to predict future execution of large instruction sequences on either high or low performance execution circuitry

• US 9,965,279 B2
• Filed: 11/29/2013
• Issued: 05/08/2018
• Est. Priority Date: 11/29/2013
• Status: Active Grant

• Current Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Original Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Inventors: Padmanabha, Shruti, Lukefahr, Andrew, Das, Reetuparna, Mahlke, Scott
• Primary Examiner(s): Petranek, Jacob A
• Application Number:
  US14/093,042
• Publication Number:
  US 20150154021A1
• Time in Patent Office: 1,621 Days
• Field of Search: None
• CPC Class Codes: G06F 1/329 by task scheduling
• CPC Class Codes: G06F 1/3293 by switching to a less power-consuming processor, e.g. sub-CPU
• CPC Class Codes: G06F 9/30058 Conditional branch instructions
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

An apparatus for processing data includes first execution circuitry, such as an out-of-order processor, and second execution circuitry, such as an in-order processor. The first execution circuitry is of higher performance but uses more energy than the second execution circuitry. Control circuitry switches between the first execution circuitry being active and the second execution circuitry being active. The control circuitry includes prediction circuitry which is configured to predict a predicted identity of a next sequence of program instructions to be executed in dependence upon a most recently executed sequence of program instructions and then in dependence upon this predicted identity to predict a predicted execution target corresponding to whether the next sequence of program instructions should be executed by the first execution circuitry or the second execution circuitry.

Claims

1. Apparatus for processing data under control of program instructions, said apparatus comprising:

first execution circuitry configured to execute program instructions;

second execution circuitry configured to execute said program instructions, said second execution circuitry having a lower energy consumption when executing said program instruction than said first execution circuitry, and said second execution circuitry requiring a longer time to execute said program instructions than said first execution circuitry; and

control circuitry configured to control whether said program instructions are executed by said first execution circuitry or said second execution circuitry, wherein

said control circuitry comprises prediction circuitry configured;

(i) to predict a predicted identity of a next sequence of program instructions to be executed in dependence upon a most recently executed sequence of program instructions; and

(ii) in dependence upon said predicted identity, to predict a predicted execution target corresponding to whether said next sequence of program instructions should be executed with said first execution circuitry or said second execution circuitry; and

said control circuitry is configured to select either said first execution circuitry or said second execution circuitry to execute said next sequence of program instructions in dependence upon said predicted execution target.

2. Apparatus as claimed in claim 1, wherein said program instruction have associated addresses and default program flow executes instructions in an order corresponding to advancing sequentially through said addresses in a default direction, and said prediction circuitry divides said program instructions into sequences of program instructions, said sequences of program instructions including said next sequence of program instructions and said most recently executed sequence of program instructions, in accordance with:

(i) said sequences of program instructions contain more than a threshold number of program instructions; and

(ii) said sequences of program instructions are bounded by non-sequential instructions at which program flow moves in a direction opposite to said default direction.

3. Apparatus as claimed in claim 2, wherein said non-sequential instructions comprise one or more of:

a branch instruction, a call instruction and a return instruction.

4. Apparatus as claimed inn claim 2, wherein said default direction corresponds to sequentially increasing addresses associated with said program instructions.

5. Apparatus as claimed in claim 2, wherein said sequences of program instructions are free to contain one or more non-sequential instructions between said non-sequential instructions that bound said sequences of program instructions.

6. Apparatus as claimed in claim 2, wherein said sequences of program instructions are bounded at their execution start by a non-sequential instruction within an immediately preceding sequence of program instructions within said program flow.

7. Apparatus as claimed in claim 2, wherein said prediction circuitry comprises hash generating circuitry configured to generate a hash value used as at least part of an identifier value for a sequence of program instructions in dependence upon addresses values of at least some of said non-sequential instruction within said sequence of program instructions.

8. Apparatus as claimed in claim 7, wherein hash generating circuitry is configured to generate said hash value using a hashing function that gives greater weight to address values of non-sequential program instructions disposed later in program flow order within said sequence of program instructions.

9. Apparatus as claimed in claim 7, wherein hash generating circuitry is configured to generate said hash value using a hashing function that is dependent upon a latest N non-sequential program instructions in program flow order disposed within said sequence of program instructions, wherein N is an integer value equal to 15.

10. Apparatus as claimed in claim 7, wherein said prediction circuitry is configured to use at least part of a target address value of program instruction to be executed following a non-sequential program terminating a sequence of program instructions as at least part of said identifier value for said sequence of program instructions.

11. Apparatus as claimed in claim 2, wherein said threshold number is between 100 and 10000.

12. Apparatus as claimed in claim 2, wherein said threshold number is 300.

13. Apparatus as claimed in claim 1, wherein said prediction circuitry is configured to generate an identifier value for said most recently executed sequence of program instructions and said prediction circuitry comprises identifier prediction table circuitry configured to use said identifier value for said most recently executed sequence of program instructions as an index to said identifier prediction table circuitry to predict an identifier value for said next sequence of program instructions.

14. Apparatus as claimed in claim 13, wherein said prediction circuitry comprises target prediction table circuitry configured to use said identifier for said next sequence of program as an index to said target prediction table circuitry to predict said predicted execution target.

15. Apparatus as claimed in claim 1, wherein said first execution circuitry and said second execution circuitry share one or more of:

instruction fetch circuitry, instruction decoder circuitry, cache memory circuitry;

branch predictor circuitry, memory management circuitry and translation lookaside buffer circuitry.

16. Apparatus as claimed in claim 1, wherein said first execution circuitry comprises first register file circuitry and said second execution circuitry comprises second register file circuitry and wherein said control circuitry is configured to transfer as a hardware driven operation state data between said first register circuitry and said second register circuitry when there is a change in which of said first execution circuitry and said second execution circuitry is selected to execute said program instructions.

17. Apparatus as claimed in claim 1, wherein said prediction circuitry divides said program instructions into sequences of program instructions, said sequences of program instructions including said next sequence of program instructions and said most recently executed sequence of program instructions, said control circuitry is configured to determine for each sequence of program instruction performance data indicative of at least one of a time taken to execute said sequence of program instructions and energy consumed when executing said sequence of program instructions by each of said first execution circuitry and said second execution circuitry and said prediction circuitry to configured to select which of said first execution circuitry and said second execution circuitry should serve as said predicted execution target in dependence upon said performance data.

18. Apparatus as claimed in claim 17, wherein said control circuitry determines said performance data based upon at least one of:

(i) detected performance indicative state captured during execution of said sequence of program instructions by at least one of said first execution circuitry and said second execution circuitry; and

(ii) modelled execution of said sequence of program instructions by at least one of said first execution circuitry and said second execution circuitry.

19. Apparatus for processing data under control of program instructions, said apparatus comprising:

first execution means for executing program instructions;

second execution means for executing said program instructions, said second execution means having a lower energy consumption when executing said program instruction than said first execution means, and said second execution means requiring a longer time to execute said program instructions than said first execution means; and

control means for controlling whether said program instructions are executed by said first execution means or said second execution means, wherein

said control means comprises prediction means for;

(i) predicting a predicted identity of a next sequence of program instructions to be executed in dependence upon a most recently executed sequence of program instructions; and

(ii) in dependence upon said predicted identity, predicting a predicted execution target corresponding to whether said next sequence of program instructions should be executed with said first execution means or said second execution means; and

said control means selects either said first execution means or said second execution means to execute said next sequence of program instructions in dependence upon said predicted execution target.

20. A method of processing data under control of program instructions, said method comprising the steps of:

executing program instructions with first execution circuitry;

executing said program instructions with second execution circuitry, said second execution circuitry having a lower energy consumption when executing said program instruction than said first execution circuitry, and said second execution circuitry requiring a longer time to execute said program instructions than said first execution circuitry; and

controlling whether said program instructions are executed by said first execution means or said second execution means, wherein

said step of controlling comprises;

(i) predicting a predicted identity of a next sequence of program instructions to be executed in dependence upon a most recently executed sequence of program instructions; and

(ii) in dependence upon said predicted identity, predicting a predicted execution target corresponding to whether said next sequence of program instructions should be executed with said first execution circuitry or said second execution circuitry; and

(iii) selecting either said first execution circuitry or said second execution circuitry to execute said next sequence of program instructions in dependence upon said predicted execution target.