Predictive processor resource management

• US 20070050776A1
• Filed: 08/29/2005
• Published: 03/01/2007
• Est. Priority Date: 08/29/2005
• Status: Active Grant

• Current Assignee: The Invention Science Fund I, L.L.C. (Intellectual Ventures LLC)
• Original Assignee: Searete LLC (Intellectual Ventures LLC)
• Inventors: Ferren, Bran, Tegreene, Clarence, Myhrvold, Nathan, Wood, Lowell, Hillis, W., Mangione-Smith, William
• Granted Patent: US 7,877,584 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2209/507 Low-level
• CPC Class Codes: G06F 2212/6028 Prefetching based on hints or prefetch instructions
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3897 with adaptable data path
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

Embodiments include a device and a method. In an embodiment, a device includes a processor having an associated hardware resource and operable to execute an instruction group. The device also includes a resource manager operable to implement a resource management policy for the hardware resource with respect to an execution of the instruction group, the resource management policy responsive to a prediction of a future performance of the hardware resource based at least in part on a historical performance of the hardware resource.

Claims

1. A device comprising:

a processor having an associated hardware resource and operable to execute an instruction group; and

a resource manager operable to implement a resource management policy for the associated hardware resource with respect to an execution of the instruction group, the resource management policy responsive to a prediction of a future performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource.

2. The device of claim 1, wherein the processor and the associated hardware resource are formed on a single chip.

3. The device of claim 1, wherein the processor and the resource manager are formed on a single chip.

4. The device of claim 1, wherein the associated hardware resource includes a cache.

5. The device of claim 1, wherein the associated hardware resource includes a logical partition of a cache.

6. The device of claim 1, wherein the associated hardware resource includes a branch predictor.

7. The device of claim 1, wherein the associated hardware resource includes a dynamic branch predictor.

8. The device of claim 1, wherein the associated hardware resource includes a hardware resource logically associated with the processor.

9. The device of claim 1, wherein the associated hardware resource includes a hardware resource physically associated with the processor.

10. The device of claim 1, wherein the associated hardware resource associated with the processor includes a hardware resource controlled by the processor.

11. The device of claim 1, wherein the resource management policy responsive to a prediction of a future performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource includes a resource management policy responsive to a prediction of a future performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource during an execution of the instruction group.

12. The device of claim 1, wherein the resource management policy responsive to a prediction of a future performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource includes a resource management policy responsive to a prediction of a future performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource and a confidence indicia.

13. The device of claim 1, wherein the resource management policy responsive to a prediction of a performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource includes a resource management policy responsive to a prediction of a performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource and a saved indicia of confidence in the prediction of a performance of the associated hardware resource.

14. The device of claim 1, wherein the resource management policy formulated in response to a prediction of a performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource includes a resource management policy formulated in response to a prediction of a performance of the associated hardware resource as likely to provide a substantially optimum execution of the instruction group.

15. The device of claim 1, wherein the resource management policy formulated in response to a prediction of a performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource includes a resource management policy formulated in response to a prediction of a performance of the associated hardware resource as likely to provide a substantially optimum execution of the instruction group as measured by a preselected criterion.

16. The device of claim 15, wherein the preselected criterion includes at least one of a successful completion of the instruction group, an unsuccessful completion of the instruction group, an uncertain completion of the instruction group, an exception, a time to execute the instruction group, a successful hit, an unsuccessful hit, a hit ratio, correctly predicting a branch taken, incorrectly predicting a branch taken, correctly predicting a branch not taken, and/or incorrectly predicting a branch not taken.

17. The device of claim 1, wherein the resource management policy formulated in response to a prediction of a performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource includes a resource management policy formulated in response to a prediction of a performance of the associated hardware resource based at least in part on a Bayesian method.

18. The device of claim 1, wherein the resource management policy formulated in response to a prediction of a performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource includes a resource management policy formulated in response to a prediction of a performance of the associated hardware resource based at least in part on a heuristic algorithm.

19. The device of claim 1, wherein the resource management policy formulated in response to a prediction of a performance of the associated hardware resource based at least in part on a historical performance of the associated hardware resource includes a resource management policy formulated in response to a prediction of a performance of the associated hardware resource based at least in part on a learning algorithm.

20. The device of claim 1, wherein the resource manager includes a resource manager operable to recall historical data from a ghost page.

21. The device of claim 1, further comprising:

a storage device operable to save the historical performance of the associated hardware resource.

22. The device of claim 21, wherein the storage device operable to save the historical performance of the associated hardware resource includes a storage device operable to save the historical performance of the associated hardware resource and a measure of confidence in a prediction based on the historical performance.

23. A method comprising:

receiving a historical performance indicia of a hardware resource associated with a processor operable to execute an instruction group;

predicting a future performance of the hardware resource based at least in part on the historical performance indicia of the hardware resource;

picking a resource management policy responsive to the predicting a future performance of the hardware resource; and

implementing the resource management policy in the hardware resource for an execution of the instruction group by the processor.

24. The method of claim 23, wherein the predicting a future performance of the hardware resource at least in part based on the historical performance indicia of the hardware resource includes predicting a future performance of the hardware resource at least in part based on the historical performance indicia of the hardware resource corresponding to an execution of the instruction group.

25. The method of claim 23, wherein the predicting a future performance of the hardware resource based at least in part on the historical performance indicia of the hardware resource includes predicting a future performance of the hardware resource based at least in part on the historical performance of the hardware resource and a confidence indicia.

26. A device comprising:

a hardware hybrid branch predictor comprising at least two independent branch predictors, each branch predictor respectively predicting a branch instruction as taken or not taken, and a strength of the prediction; and

a branch chooser comprising

a confidence table including a respective confidence value in each of the at least two branch predictors; and

an operability to

respectively receive from each branch predictor a prediction of the branch instruction as taken or not taken, and the strength of the prediction; and

choose one branch prediction predicted by one of the at least two branch predictors in response to a function influenced by the respective strength of each prediction and the confidence value in each of the at least two branch predictor.

27. The device of claim 26, wherein the function influenced by the respective strength of each prediction and the confidence value in each of the at least two branch predictors includes a function employing an inferential methodology.

28. The device of claim 26, wherein the function influenced by the respective strength of each prediction and the confidence value in each of the at least two branch predictors includes a function employing a Bayesian methodology.

29. The device of claim 26, wherein the strength of a prediction is incremented for each successful prediction and de-incremented for each unsuccessful branch prediction, with no overflow or underflow.

30. A method comprising:

respectively receiving from at least two branch predictors of a hardware hybrid-branch predictor a prediction of a branch instruction as taken or not taken, and a strength of the prediction;

receiving a respective confidence value in each of the at least two branch predictors; and

choosing one branch prediction predicted by one of the at least two branch predictors in response to a function influenced by the respective strength of each prediction and the confidence value in each of the at least two branch predictor.