Patent Number: 6,253,285

Title: Method and apparatus for minimizing dcache index match aliasing using hashing in synonym/subset processing

Abstract: A data caching system comprises a hashing function, a data store, a tag array, a page translator, a comparator and a duplicate tag array. The hashing function combines an index portion of a virtual address with a virtual page portion of the virtual address to form a cache index. The data store comprises a plurality of data blocks for holding data. The tag array comprises a plurality of tag entries corresponding to the data blocks, and both the data store and tag array are addressed with the cache index. The tag array provides a plurality of physical address tags corresponding to physical addresses of data resident within corresponding data blocks in the data store addressed by the cache index. The page translator translates a tag portion of the virtual address to a corresponding physical address tag. The comparator verifies a match between the physical address tag from the page translator and the plurality of physical address tags from the tag array, a match indicating that data addressed by the virtual address is resident within the data store. Finally, the duplicate tag array resolves synonym issues caused by hashing. The hashing function is such that addresses which are equivalent mod 2.sup.13 are pseudo-randomly displaced within the cache. The preferred hashing function maps VA<14, 15 XOR 13, 12:6> to bits <14:6> of the cache index.

Inventors: Razdan; Rahul (Princeton, MA), Kessler; Richard E. (Shrewsbury, MA), Keller; James B. (Waltham, MA)

Assignee: Compaq Computer Corporation

International Classification: G06F 12/10 (20060101); C06F 012/00 ()

Expiration Date: 06/26/2018