Cache line replacement using cache status to bias way selection

摘要

A method for determining which way of an N-way set associative cache should be filled with replacement data upon generation of a cache miss when all of the ways contain valid data. A first choice for way selection and at least one additional choice for way selection are generated. If the status of the way corresponding to the first choice differs from a bias status, a way corresponding to one of the additional choices is designated as the way to be filled with replacement data. Otherwise, the way corresponding to the first choice is designated as the way to be filled with replacement data. Status information for a given way may include any data which is maintained on a cache line by cache line basis, but is preferably data which is maintained for purposes other than way selection. For example, status information might include indications as to whether a cache line is shared or private, clean or dirty. The algorithm for generating the first choice for way selection is preferably a random or round robin approach, but may be any other algorithm. Any algorithm may also be used for generating the additional choices for way selection. However, the additional choices are preferably generated as functions of the first (e.g., the first choice plus different constants). The bias status which is used to select between the first and at least one additional choices can be programmed to yield different results in different systems.