Multiprocessor resource optimization

• US 7,774,558 B2
• Filed: 08/29/2005
• Issued: 08/10/2010
• Est. Priority Date: 08/29/2005
• Status: Expired due to Fees

• 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: Hillis, W. Daniel, Tegreene, Clarence T., Ferren, Bran, Wood, JR., Lowell L., Myhrvold, Nathan P.
• Primary Examiner(s): Peugh, Brian R
• Assistant Examiner(s): Bertram, Ryan
• Application Number:
  US11/214,458
• Publication Number:
  US 20070050555A1
• Time in Patent Office: 1,807 Days
• Field of Search: 711/141, 711/154
• US Class Current: 711/154
• 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 method applies a first resource management strategy to a first resource associated with a first processor and executes an instruction block in a first processor. The method also applies a second resource management strategy to a second resource of a similar type as the first resource and executes the instruction block in a second processor. The method further selects a resource management strategy likely to provide a substantially optimum execution of the instruction group from the first resource management strategy and the second resource management strategy.

Claims

1. A device comprising:

a first processor having an associated first cache and a second processor having an associated second cache; and

a cache manager implemented in a hardware-logic and operable to;

compare an execution of a given instruction group by the first processor while a first cache management policy is applied to the associated first cache and an execution of the given instruction group by the second processor while a second cache management policy is applied to the associated second cache, the execution of the given instruction group by the second processor initiated independently of the execution of the given instruction group by the first processor, wherein the first cache management policy assumes based on at least one of predicted information or historical information that the given instruction group will execute in a substantially optimal manner such that less than a preselected level of at least one error will occur during execution of the given instruction group and the second cache management policy assumes based on at least one of predicted information or historical information that the given 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 given instruction group;

select from the first cache management policy and the second cache management policy a cache management policy likely to provide a substantially optimum execution of the given instruction group according to a preselected criterion; and

associate in a recordable-type signal bearing medium the selected cache management policy with the given instruction group.

2. The device of claim 1, wherein the first processor and the second processor are implemented on a single chip.

3. The device of claim 1, wherein the associated first cache and the associated second cache are a logical partition of a physical memory.

4. The device of claim 1, wherein the associated first cache and the associated second cache are accessible by both the first and second processor.

5. The device of claim 1, wherein the associated first cache includes an L2 cache and the associated second cache includes an L2 cache.

6. The device of claim 1, wherein the first processor and the cache manager are formed on a single chip.

7. The device of claim 1, wherein the cache manager operable to associate in a recordable-type signal bearing medium the selected cache management policy with the given instruction group includes a cache manager operable to associate in a recordable-type signal bearing medium a ghost page indicative of the selected management policy with the given instruction group.

8. The device of claim 1, wherein the cache manager operable to compare includes a cache manager operable to compare according to the preselected criterion.

9. The device of claim 1, wherein the cache manager operable to select from the first cache management policy and the second cache management policy a cache management policy likely to provide a substantially optimum execution of the given instruction group according to a preselected criterion, such that less than a preselected level of at least one error will occur during execution of the given instruction group, includes a cache manager operable to select a management policy predicted as likely to provide a substantially optimum execution of the given instruction group, such that less than a preselected level of at least one error will occur during execution of the given instruction group.

10. The device of claim 1, wherein the cache manager operable to select from the first cache management policy and the second cache management policy a cache management policy likely to provide a substantially optimum execution of the given instruction group according to a preselected criterion, such that less than a preselected level of at least one error will occur during execution of the given instruction group, includes a cache manager operable to select a management policy predicted by a Bayesian method as likely to provide a substantially optimum execution of the given instruction group, such that less than a preselected level of at least one error will occur during execution of the given instruction group.

11. The device of claim 1, wherein the cache manager operable to select from the first cache management policy and the second cache management policy a cache management policy likely to provide a substantially optimum execution of the given instruction group according to a preselected criterion, such that less than a preselected level of at least one error will occur during execution of the given instruction group, includes a cache manager operable to select a management policy predicted by a heuristic as likely to provide a substantially optimum execution of the given instruction group, such that less than a preselected level of at least one error will occur during execution of the given instruction group.

12. The device of claim 1, wherein the cache manager operable to select from the first cache management policy and the second cache management policy a cache management policy likely to provide a substantially optimum execution of the given instruction group according to a preselected criterion, such that less than a preselected level of at least one error will occur during execution of the given instruction group, includes a cache manager operable to select a management policy predicted by a learning algorithm as likely to provide a substantially optimum execution of the given instruction group, such that less than a preselected level of at least one error will occur during execution of the given instruction group.

13. A device comprising:

a first processor having an associated first hardware resource and a second processor having an associated second hardware resource; and

a resource manager implemented in a hardware-logic and operable to;

compare an execution of a given instruction group by the first processor while a first resource management policy is applied to the associated first hardware resource and an execution of the given instruction group by the second processor while a second resource management policy is applied to the associated second hardware resource, wherein the first resource management policy assumes based on at least one of predicted information or historical information that the given instruction group will execute in a substantially optimal manner such that less than a preselected level of at least one error will occur during execution of the given instruction group and the second resource management policy assumes based on at least one of predicted information or historical information that the given 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 given instruction group;

select from the first resource management policy and the second resource management policy a resource management policy likely to provide a substantially optimum execution of the given instruction group according to a preselected criterion; and

associate the selected resource management policy with the given instruction group.

14. The device of claim 13, wherein the resource manager is associated with the first processor.

15. The device of claim 13, wherein the resource manager is associated with the first processor and the second processor.

16. The device of claim 13, wherein the associated first hardware resource includes a first branch predictor.

17. The device of claim 13, wherein the associated first hardware resource includes a first branch predictor and the associated second hardware resource includes a second branch predictor.

18. The device of claim 13, wherein the associated first hardware resource includes a first off-processor-chip cache and the associated second hardware resource includes a second off-processor-chip cache.

19. A method comprising:

applying a first resource management strategy to a first resource associated with a first processor and executing a given instruction group in the first processor, wherein the applying of the first resource management strategy to the first resource includes applying an optimistic resource management strategy to the first resource, the optimistic resource management strategy assuming based on at least one of predicted information or historical information that the given instruction group will execute in a substantially optimal manner such that less than a preselected level of at least one error will occur during execution of the given instruction group;

independently of the execution of the given instruction group in the first processor, applying a second resource management strategy to a second resource of a similar type as the first resource and executing the given instruction group in a second processor, wherein the applying of the second resource management strategy to the second resource includes applying a pessimistic resource management strategy to the second resource, the pessimistic resource management strategy assuming based on at least one of predicted information or historical information that the given 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 given instruction group;

selecting a resource management strategy likely to provide a substantially optimum execution of the given instruction group from the first resource management strategy and the second resource management strategy according to a preselected criterion, the resource management strategy selected in response to a characteristic of the executing the given instruction group in the first processor and in response to a characteristic of the executing the given instruction group in the second processor; and

associating in a recordable-type signal bearing medium the selected resource management strategy with the given instruction group.

20. The method of claim 19, wherein the applying a first resource management strategy to a first resource associated with a first processor includes applying a first resource management strategy to a cache associated with a first processor.

21. The method of claim 19, wherein the applying a first resource management strategy to a first resource associated with a first processor includes applying a first resource management strategy to a register associated with a first processor.

22. The method of claim 19, wherein the applying a first resource management strategy to a first resource associated with a first processor includes applying a first resource management strategy to a functional unit associated with a first processor.

23. The method of claim 19, wherein the applying a first resource management strategy to a first resource associated with a first processor includes applying a first resource management strategy to a branch predictor associated with a first processor.

24. The method of claim 19, wherein the associating in a recordable-type signal bearing medium the selected resource management policy with the given instruction group further comprising:

associating in a recordable-type signal bearing medium a ghost page indicative of the selected resource management strategy with the given instruction group.

25. A device comprising:

a given processor having an associated hardware resource and a present context; and

a control unit associated with the given processor and operable to;

fetch a given instruction for execution by the given processor;

receive a previously selected resource management policy associated with the given instruction, the previously selected resource management policy selected according to a preselected criterion as likely to provide a substantially optimum execution by the given processor of an instruction group that includes the given instruction, and further selected from an optimistic resource management policy and a pessimistic resource management policy, the optimistic resource management policy assuming based on at least one of predicted information or historical information that the instruction group will execute in a substantially optimal manner such that less than a preselected level of at least one error will occur during execution of the instruction group, and the pessimistic resource management policy assuming based on at least one of predicted information or historical information 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;

apply the previously selected resource management policy to the hardware resource if a predetermined similarity exists between the present context of the given processor and a runtime context of the given processor when the previously selected resource management policy was selected;

otherwise

do not apply the previously selected resource management policy to the hardware resource; and

cause the given processor to execute the given instruction.

26. A method comprising:

fetching a given instruction to be executed by a processor core of a chip having at least two processor cores that each have access to a resource;

receiving a previously selected resource management policy associated in a recordable-type signal bearing medium with an instruction group that includes the given instruction, the resource management policy having been selected according to a preselected criterion in response to a previous runtime execution of the instruction group, and as likely to provide a substantially optimum execution of the instruction group that includes the given instruction, and having further been selected from an optimistic resource management policy and a pessimistic resource management policy, the optimistic resource management policy assuming based on at least one of predicted information or historical information that the instruction group will execute in a substantially optimal manner such that less than a preselected level of at least one error will occur during execution of the instruction group, and the pessimistic resource management policy assuming based on at least one of predicted information or historical information 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;

applying the previously selected resource management policy to the resource; and

executing the given instruction by the processor core.

27. The method of claim 26, wherein the fetching a given instruction to be executed by a processor core of a chip having at least two processor cores that each have access to a resource includes

fetching a given instruction to be executed by a processor core of a chip having at least two processor cores that each have access to a cache resource.

28. The method of claim 26, wherein the fetching a given instruction to be executed by a processor core of a chip having at least two processor cores that each have access to a resource includes

fetching a given instruction to be executed by a processor core of a chip having at least two processor cores that each have access to a branch predictor.

29. A method comprising:

applying a first hardware resource management strategy to a first hardware resource associated with a first processor, and implementing a first test of possible substantially optimum execution of a given instruction group in the first processor, wherein the first hardware resource management strategy assumes based on at least one of predicted information or historical information that the given instruction group will execute in a substantially optimal manner such that less than a preselected level of at least one error will occur during execution of the given instruction group;

separately from and independently of the first test of possible substantially optimum execution of the given instruction group in the first processor, applying a second hardware resource management strategy to a second hardware resource associated with a second processor, and implementing a second test of possible substantially non-optimum execution of the given instruction group in the second processor, wherein the second hardware resource management strategy assumes based on at least one of predicted information or historical information that the given 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 given instruction group;

selecting a hardware resource management strategy likely to provide a substantially optimum execution of the given instruction group from the first hardware resource management strategy and the second hardware resource management strategy according to a preselected criterion; and

saving an association of the given instruction group and the selected hardware resource management strategy in a storage device.

30. The method of claim 29, wherein the saving of an association of the given instruction group and the selected hardware resource management strategy in a storage device includes:

saving an association of the given instruction group and the selected hardware resource management strategy in a recordable-type signal bearing medium.