Ordering of high use program code segments using simulated annealing

• US 7,308,683 B2
• Filed: 10/30/2003
• Issued: 12/11/2007
• Est. Priority Date: 10/30/2003
• Status: Active Grant

• Current Assignee: Trend Micro Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Johnson, Ross E.
• Primary Examiner(s): INGBERG, TODD D
• Application Number:
  US10/697,491
• Publication Number:
  US 20050097546A1
• Time in Patent Office: 1,503 Days
• Field of Search: 717/158, 717/159, 717/161, 717/156, 718/101, 718/100, 718/105, 711/147, 711/117, 719/316
• US Class Current: 717/158
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862

Abstract

An apparatus, program product and method utilize a heuristic-based algorithm such as simulated annealing to order program code segments in a computer memory to provide improved computer performance in terms of memory access, e.g., by minimizing cache misses or other memory-related performance penalties that may be present in a multi-level memory architecture. Program code is ordered in a computer memory by selecting an ordering from among a plurality of orderings for a plurality of program code segments using a heuristic algorithm, and ordering the plurality of program code segments in a memory of a computer using the selected ordering.

Claims

1. A method of ordering program code in a computer memory, the method comprising:

selecting an ordering from among a plurality of orderings for a plurality of program code segments using a heuristic algorithm, wherein the heuristic algorithm comprises a simulated annealing algorithm, wherein selecting the ordering using the heuristic algorithm includes testing a subset of the plurality of orderings, and wherein testing the subset of the plurality of orderings includes, for each ordering in the subset, calculating a cost for such ordering based upon cache miss rates for such ordering, and randomly selecting a different ordering after testing an ordering from the subset of orderings; and

ordering the plurality of program code segments in a memory of a computer using the selected ordering.

2. The method of claim 1, wherein the heuristic algorithm is configured to minimize cache misses in the computer.

3. The method of claim 1, wherein calculating the cost for each ordering comprises calculating a plurality of hits/reference values, misses/address values, and misses/entry values.

4. The method of claim 1, wherein randomly selecting the different ordering comprises swapping two program code segments in a previous ordering.

5. The method of claim 4, wherein the program code segments each comprise a module, and wherein randomly selecting the different ordering further comprises constraining selection of the two program code segments to modules in the same replaceable unit destination.

6. The method of claim 1, wherein selecting an ordering from among the plurality of orderings comprises testing a subset of orderings at each of a plurality of temperature values.

7. The method of claim 6, wherein selecting an ordering from among the plurality of orderings further comprises testing a subset of orderings at each temperature value.

8. The method of claim 7, wherein selecting an ordering from among the plurality of orderings further comprises accepting a change to an ordering if a calculated cost for such ordering is lower than that of a working ordering.

9. The method of claim 7, wherein selecting an ordering from among the plurality of orderings further comprises randomly accepting a change to an ordering even if the calculated cost for such ordering is not lower than that of the working ordering.

10. The method of claim 7, wherein selecting an ordering from among the plurality of orderings further comprises prematurely halting the testing of orderings based upon a halt criterion.

11. The method of claim 1, wherein the program code segments each comprise a module from an operating system kernel.

12. The method of claim 11, wherein each module comprises a high use module, and wherein selecting the ordering from among a plurality of orderings comprises generating a high use module list.

13. An apparatus, comprising:

a processor; and

first program code configured to be executed by the processor to optimize execution of second program code in a computer of the type including a multi-level memory architecture by using a heuristic algorithm to select an ordering from among a plurality of orderings for a plurality of program code segments in the second program code, wherein the heuristic algorithm comprises a simulated annealing algorithm, wherein the first program code is configured to select the ordering using the heuristic algorithm by testing a subset of the plurality of orderings, wherein the first program code is configured to test the subset of the plurality of orderings by, for each ordering in the subset, calculating a cost for such ordering based upon cache miss rates for such ordering, and wherein the first program code is configured to test the subset of orderings by randomly selecting a different ordering after testing an ordering from the subset of orderings.

14. The apparatus of claim 13, wherein the heuristic algorithm is configured to minimize cache misses in the computer.

15. The apparatus of claim 13, wherein the first program code is configured to randomly select the different ordering by swapping two program code segments in a previous ordering.

16. The apparatus of claim 15, wherein the program code segments each comprise a module, and wherein the first program code is configured to randomly select the different ordering by constraining selection of the two program code segments to modules in the same replaceable unit destination.

17. The apparatus of claim 13, wherein the first program code is configured to select an ordering from among the plurality of orderings by testing a subset of orderings at each of a plurality of temperature values, and testing a subset of orderings at each temperature value.

18. The apparatus of claim 17, wherein the first program code is configured to select an ordering from among the plurality of orderings by accepting a change to an ordering if a calculated cost for such ordering is lower than that of a working ordering.

19. The apparatus of claim 18, wherein the first program code is configured to select an ordering from among the plurality of orderings by randomly accepting a change to an ordering even if the calculated cost for such ordering is not lower than that of the working ordering.

20. The apparatus of claim 13, wherein the first program code is configured to select an ordering from among the plurality of orderings by prematurely halting the testing of orderings based upon a halt criterion.

21. The apparatus of claim 13, wherein the program code segments each comprise a module from an operating system kernel.

22. The apparatus of claim 21, wherein each module comprises a high use module, and wherein the first program code is configured to select the ordering from among a plurality of orderings by generating a high use module list.

23. A program product, comprising:

first program code configured to optimize execution of second program code in a computer of the type including a multi-level memory architecture by using a heuristic algorithm to select an ordering from among a plurality of orderings for a plurality of program code segments in the second program code, wherein the heuristic algorithm comprises a simulated annealing algorithm, wherein the first program code is configured to select the ordering using the heuristic algorithm by testing a subset of the plurality of orderings, wherein the first program code is configured to test the subset of the plurality of orderings by, for each ordering in the subset, calculating a cost for such ordering based upon cache miss rates for such ordering, and wherein the first program code is configured to test the subset of orderings by randomly selecting a different ordering after testing an ordering from the subset of orderings; and

a physical recordable computer readable medium bearing the first program code.