Efficient pseudo-LRU for colliding accesses

A computer program product encoded in at least one non-transitory computer readable medium for use with a computing device, the computer program product comprising:

• computer readable program code embodied in said medium, for specifying an apparatus for allocating entries in a set associative cache memory, the computer readable program code comprising:
• first program code for specifying an array, configured to provide a first pseudo-least-recently-used (PLRU) vector in response to a first allocation request from a first functional unit, wherein the first PLRU vector specifies a first entry from a set of the cache memory specified by the first allocation request, wherein the first PLRU vector is a tree of bits comprising a plurality of levels;
• and
• second program code for specifying toggling logic, configured to receive the first PLRU vector and to toggle predetermined bits thereof to generate a second PLRU vector in response to a second allocation request from a second functional unit generated concurrently with the first allocation request and specifying the same set of the cache memory specified by the first allocation request, wherein the second PLRU vector specifies a second entry different from the first entry from the same set, wherein the predetermined bits comprise bits of a predetermined one of the plurality of levels of the tree.