METHOD FOR REDUCING THE FREQUENCY OF CACHE MISSES IN A COMPUTER

A score is computed of how many cache misses occur for the execution of each of a number of blocks. The score is used as a heuristic in a local search in which an original selection is iteratively replaced each time by a selection that differs from the original selection only by the movement of a single block and that has a lower number of cache misses for the sample of execution than the original selection. Thus a selection of locations for placing instructions of a program in main memory is found that minimizes the number of cache misses that occur for a sample of a typical execution of the program.