Ordering of high use program code segments using simulated annealing
First Claim
Patent Images
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
23 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
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.
-
Specification