Patent ID: 6301641
Filing Date: 2001-10-09
Classification: G06F,Y10S

Abstract:
A method of selecting memory locations for placing instructions into a main memory, the method comprising obtaining a sample of execution of a program containing the instructions, generating an optimized selection of locations using a local search, the optimized selection producing a minimized number of cache misses when the instructions are placed in the main memory connected to a cache memory according to the optimized selection for the sample of execution, wherein the method comprises:generating an original selection of locations for placing the instructions;computing for each respective one of a number of blocks having at least one of the instructions, a respective score indicating a number of cache misses caused by executions of the respective block during the obtaining of the sample of execution when the instructions are placed according to the original selection;comparing the respective scores for finding at least one selected one of the respective blocks for which the respective scores indicate that the at least one selected one of the respective blocks produces a higher number of cache misses than further ones of the respective blocks;defining a set of potential selections, wherein in each of the potential selections an order of the blocks in the main memory differs from the order of the blocks in the main memory of the original selection in that the instructions of the at least one selected one of the respective blocks have been moved relative to the instructions of the further ones of the respective blocks,testing whether for any particular one of the set of the potential selections, the particular potential selection produces fewer cache misses for the sample of execution when the instructions are placed according to the particular potential selection than when the instructions are placed according to the original selection;either taking a first action: repeating the comparing, the defining and the testing using the further ones of the respective blocks instead of the at least one selected block, or taking a second action: replacing the original selection by the particular potential selection and terminating the comparing, the defining and the testing, the first or second action being taken dependent on whether the potential selection produces fewer cache misses than the original selection; andrepeating the computing, the comparing the defining and the testing for the replaced original selection.