# US 8,751,751 B2 · Method and apparatus for minimizing cache conflict misses > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,751 B2 - Document ID: US8751751B2 - Status: Granted - Kind: B2 - Application number: 13/015,771 - Filed: 2011-01-28 - Published: 2012-08-02 - Granted: 2014-06-10 - Earliest claimed: 2011-01-28 - Assignees: International Business Machines Corporation - Applicants: Robert H. Bell, Jr.; Men-Chow Chiang; Hong L. Hua - Inventors: Robert H. Bell, Jr.; Men-Chow Chiang; Hong L. Hua - Web page: https://patentgrep.com/patent/US8751751B2 ## CPC - G06F 12/0864: using pseudo-associative means, e.g. set-associative or hashing - G06F 12/1018: involving hashing techniques, e.g. inverted page tables - G06F 12/1036: for multiple virtual address spaces, e.g. segmentation (G06F12/1045 takes precedence) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for minimizing cache conflict misses is disclosed. A translation table capable of facilitating the translation of a virtual address to a real address during a cache access is provided. The translation table includes multiple entries, and each entry of the translation table includes a page number field and a hash value field. A hash value is generated from a first group of bits within a virtual address, and the hash value is stored in the hash value field of an entry within the translation table. In response to a match on the entry within the translation table during a cache access, the hash value of the matched entry is retrieved from the translation table, and the hash value is concatenated with a second group of bits within the virtual address to form a set of indexing bits to index into a cache set. ## Claims ### Claim 1 A method for minimizing cache conflict misses, said method comprising: providing a translation table having a plurality of entries, wherein each entry includes a page number field and a hash value field; generating a hash value from a first group of bits within a virtual address; storing said hash value in said hash value field of an entry within said translation table; and in response to a match on said entry within said translation table during a cache access, retrieving said hash value of said matched entry from said translation table, and concatenating said hash value with a second group of bits within said virtual address to form a set of indexing bits to index into a cache set. ### Claim 2 (depends on 1) The method of claim 1, wherein said first group of bits is a plurality of most significant bits (MSBs). ### Claim 3 (depends on 1) The method of claim 1, wherein said second group of bits is a plurality of page bits within said virtual address. ### Claim 4 (depends on 3) The method of claim 3, wherein said second group of bits is the five most significant page bits. ### Claim 5 (depends on 1) The method of claim 1, wherein said hash value is represented by at least five bits. ### Claim 6 (depends on 1) The method of claim 1, wherein said translation table facilitates the translation of a virtual address to a real address during a cache access. ### Claim 7 A computer readable device having a computer program product for minimizing cache conflict misses, said computer readable device comprising: computer program code for providing a translation table having a plurality of entries, wherein each entry includes a page number field and a hash value field, wherein said translation table facilitates the translation of a virtual address to a real address during a cache access; computer program code for generating by a processor a hash value from a first group of bits within a virtual address; computer program code for storing said hash value in said hash value field of an entry within said translation table; and computer program code for, in response to a match on said entry within said translation table during a cache access, retrieving by said processor said hash value of said matched entry from said translation table, and concatenating by said processor said hash value with a second group of bits within said virtual address to form a set of indexing bits to index into a cache set. ### Claim 8 (depends on 7) The computer readable device of claim 7, wherein said first group of bits is a plurality of most significant bits (MSBs). ### Claim 9 (depends on 7) The computer readable device of claim 7, wherein said second group of bits is a plurality of page bits within said virtual address. ### Claim 10 (depends on 9) The computer readable device of claim 9, wherein said second group of bits is the five most significant page bits. ### Claim 11 (depends on 7) The computer readable device of claim 7, wherein said hash value is represented by at least five bits. ### Claim 12 (depends on 7) The computer readable device of claim 7, wherein said translation table facilitates the translation of a virtual address to a real address during a cache access. ### Claim 13 An apparatus for minimizing cache conflict misses, said apparatus comprising: a hash function module for generating a hash value from a first group of bits within a virtual address; a translation table having a plurality of entries, wherein each entry includes a page number field and a hash value field, wherein said translation table facilitates the translation of a virtual address to a real address during a cache access, wherein said hash value is stored in said hash value field of an entry within said translation table; means for, in response to a match on said entry within said translation table during a cache access, retrieving said hash value of said matched entry from said translation table; and a combine function module for concatenating said hash value with a second group of bits within said virtual address to form a set of indexing bits to index into a cache set. ### Claim 14 (depends on 13) The apparatus of claim 13, wherein said first group of bits is a plurality of most significant bits (MSBs). ### Claim 15 (depends on 13) The apparatus of claim 13, wherein said second group of bits is a plurality of page bits within said virtual address. ### Claim 16 (depends on 15) The apparatus of claim 15, wherein said second group of bits is the five most significant page bits. ### Claim 17 (depends on 13) The apparatus of claim 13, wherein said hash value is represented by at least five bits. ### Claim 18 (depends on 13) The apparatus of claim 13, wherein said translation table facilitates the translation of a virtual address to a real address during a cache access.