Predictive processor resource management

• US 7,877,584 B2
• Filed: 08/29/2005
• Issued: 01/25/2011
• Est. Priority Date: 08/29/2005
• Status: Active Grant

• Current Assignee: The Invention Science Fund I, L.L.C. (Intellectual Ventures LLC)
• Original Assignee: The Invention Science Fund I, L.L.C. (Intellectual Ventures LLC)
• Inventors: Ferren, Bran, Hillis, W. Daniel, Mangione-Smith, William Henry, Myhrvold, Nathan P., Tegreene, Clarence T., Wood, JR., Lowell L.
• Primary Examiner(s): Chan, Eddie P
• Assistant Examiner(s): Faherty, Corey
• Application Number:
  US11/214,459
• Publication Number:
  US 20070050776A1
• Time in Patent Office: 1,975 Days
• Field of Search: 712/220, 712/239, 712/229
• US Class Current: 712/229
• 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 selected from an optimistic policy that assumes that the instruction group will execute in a substantially optimal manner by executing correct branches and a pessimistic policy that assumes that the instruction group will execute in a substantially sub-optimal manner such that greater than a preselected level of at least one error will occur during execution of the instruction group, the resource management policy selected after a first execution of the instruction group applying the optimistic policy and a second execution of the instruction group applying the pessimistic policy, the resource management policy associated together with the instruction group in a common storage hierarchy and responsive to a confidence value, the confidence value indicating 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 with respect to a prior execution of the instruction group.

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 optimistic policy assumes that less than a preselected level of at least one error will occur during execution of the instruction group.

8. The device of claim 1, wherein the pessimistic policy assumes that greater than a preselected level of at least one branch prediction error will occur during execution of the instruction group.

9. The device of claim 1, wherein at least one of the optimistic policy or the pessimistic policy comprises a policy based on at least one of theoretical information or historical information.

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 includes

a resource management policy associated together with the instruction group in a common storage hierarchy and 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 with respect to a prior execution of the instruction group.

12. The device of claim 1, wherein the resource management policy associated together with the instruction group in a common storage hierarchy and 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 with respect to a prior execution of the instruction group includes a resource management policy associated together with the instruction group in a common storage hierarchy and 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 with respect to a prior execution of the instruction group and a confidence indicia.

13. The device of claim 1, wherein the resource management policy associated together with the instruction group in a common storage hierarchy and 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 with respect to a prior execution of the instruction group includes a resource management policy associated together with the instruction group in a common storage hierarchy and 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 with respect to a prior execution of the instruction group.

14. The device of claim 1, wherein the resource management policy associated together with the instruction group in a common storage hierarchy and 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 with respect to a prior execution of the instruction group resource includes

a resource management policy associated together with the instruction group in a common storage hierarchy and responsive to a prediction of a performance of the associated hardware resource with respect to a prior execution of the instruction group as likely to provide a substantially optimum execution of the instruction group.

15. The device of claim 1, wherein the resource management policy associated together with the instruction group in a common storage hierarchy and 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 with respect to a prior execution of the instruction group includes

a resource management policy associated together with the instruction group in a common storage hierarchy and responsive to a prediction of a performance of the associated hardware resource with respect to a prior execution of the instruction group 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 associated together with the instruction group in a common storage hierarchy and 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 with respect to a prior execution of the instruction group includes a resource management policy associated together with the instruction group in a common storage hierarchy and responsive to a prediction of a performance with respect to a prior execution of the instruction group 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 with respect to a prior execution of the instruction group includes a resource management policy formulated in response to a prediction of a performance with respect to an execution of the instruction group 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 with respect to a prior execution of the instruction group includes a resource management policy formulated in response to a prediction of a performance with respect to an execution of the instruction group 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, the hardware resource including a branch predictor;

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, the resource management policy being picked from an optimistic policy that assumes that the instruction group will execute in a substantially optimal manner and a pessimistic policy that assumes that the instruction group will execute in a substantially sub-optimal manner such that greater than a preselected level of at least one error will occur during execution of the instruction group, the resource management policy being picked after a first execution of the instruction group applying the optimistic policy and a second execution of the instruction group applying the pessimistic policy; 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 optimistic policy assumes that less than a preselected level of at least one error will occur during execution of the instruction group and the pessimistic policy assumes that greater than a preselected level of at least one branch prediction error will occur during execution of the instruction group, and wherein at least one of the optimistic policy or the pessimistic policy comprises a policy based on at least one of theoretical information or historical information.

26. The method of claim 23, wherein the pessimistic policy assumes that the instruction group will execute in a substantially sub-optimal manner such that greater than a preselected level of at least one branch prediction error will occur during the second execution of the instruction group.