Cache replacement mechanism

Claim 1

An n-way set-associative cache (where n is an integer greater than 1), comprising: (a) a plurality n of cache RAMs, each of said cache RAMs containing a plurality of cache lines; (b) means for storing a plurality of priority tags, one for each of said cache lines, said priority tags defining respective individual user-defined priorities for each of said cache lines; (c) addressing means for addressing said cache RAMs in parallel to select a set of n cache lines, one line from each of the cache RAMs; (d) means for comparing the priority tags of said set of n cache lines with each other; (e) first selection means operative in the event that one of said set of n cache lines has a priority, as defined by its priority tag, that is lower than the priorities of all others of said set of n cache lines, as defined by their priority tags, for selecting said one of said set of n cache lines for replacement; and (f) second selection means operative in the event that at least two of said set of n cache lines have priorities, as defined by their priority tags, that are equal to each other but lower than the priorities of all others of said set of n cache lines, as defined by their priority tags, for selecting one of said at least two of said set of n cache lines for replacement.

Claim 4

A method of operating an n-way set-associative cache (where n is an integer greater than 1), said cache comprising a plurality n of cache RAMs, each of said cache RAMs containing a plurality of cache lines, the method comprising: (a) storing a plurality of priority tags, one for each of said cache lines, said priority tags defining respective individual user-defined priorities for each of said cache lines; (b) addressing said cache RAMs in parallel to select a set of n cache lines, one line from each of the cache RAMs; (c) comparing the priority tags of said set of n cache lines with each other; (d) in the event that one of said set of n cache lines has a priority, as defined by its priority tag, that is lower than the priorities of all others of said set of n cache lines, as defined by their priority tags, selecting said one of said set of n cache lines for replacement; and (e) in the event that at least two of said set of n cache lines have priorities, as defined by their priority tags, that are equal to each other but lower than the priorities of all others of said set of n cache lines, as defined by their priority tags, selecting one of said at least two of said set of n cache lines for replacement.

Claim 5

A method of operating an n-way set-associative cache (where n is an integer greater than 1), said cache comprising a plurality n of cache RAMs, each of said cache RAMs containing a plurality of cache lines, the method comprising: (a) storing a plurality of priority tags, one for each of said cache lines, said priority tags defining respective individual user-defined priorities for each of said cache lines; (b) addressing said cache RAMs in parallel to select a set of n cache lines, one line from each of the cache RAMs; (c) comparing the priority tags of said set of n cache lines with each other; (d) in the event that one of said set of n cache lines has a priority, as defined by its priority tag, that is lower than the priorities of all others of said set of n cache lines, as defined by their priority tags, selecting said one of said set of n cache lines for replacement; and (e) in the event that at least two of said set of n cache lines have priorities, as defined by their priority tags, that are equal to each other but lower than the priorities of all others of said set of n cache lines, as defined by their priority tags, selecting one of said at least two of said set of n cache lines for replacement.