System and method for employing a process identifier to minimize aliasing in a linear-addressed cache

Abstract

A system and method for reducing linear address aliasing is described. In one embodiment, a portion of a linear address is combined with a process identifier, e.g., a page directory base pointer to form an adjusted-linear address. The page directory base pointer is unique to a process and combining it with a portion of the linear address produces an adjusted-linear address that provides a high probability of no aliasing. A portion of the adjusted-linear address is used to search an adjusted-linear-addressed cache memory for a data block specified by the linear address. If the data block does not reside in the adjusted-linear-addressed cache memory, then a replacement policy selects one of the cache lines in the adjusted-linear-addressed cache memory and replaces the data block of the selected cache line with a data block located at a physical address produced from translating the linear address. The tag for the cache line selected is a portion of the adjusted linear address and the physical address produced from translating the linear address.

What is claimed is:  
     
         1 . A method for accessing a particular one of at least one cache line of an adjusted-linear-addressed cache memory, the particular one of the at least one cache line referenced by a linear address, comprising: 
 combining a process identifier unique to a process with the linear address to form an adjusted-linear address; and    comparing the adjusted-linear address with each of at least one tag, each of the at least one tag corresponding to each of the at least one cache line, to determine if the adjusted-linear address matches any of the at least one tag.    
     
     
         2 . The method of  claim 1 , further comprising, 
 transmitting a data block within the particular one of the at least one cache line to a processor if the adjusted-linear address matches a particular one of at least one tag corresponding to the particular one of the at least one cache line, and a first physical address stored within the particular one of the at least one tag matches a second physical address generated by translating the linear address.    
     
     
         3 . The method of  claim 1 , further comprising, 
 replacing a data block within a particular one of the at least one cache line that is selected by a replacement policy with a data block from a storage device as specified by the second physical address if at least one of the adjusted-linear address does not match any of the at least one tag, and the second physical address does not match the first physical address stored within a particular one of the at least one tag that matches the linear address,    wherein the tag corresponding to the particular one of the at least one cache line that is selected includes the adjusted-linear address and the second physical address.    
     
     
         4 . The method of  claim 1 , wherein combining the process identifier with the linear address includes hashing together the process identifier with the linear address.  
     
     
         5 . The method of  claim 1 , wherein combining the process identifier with the linear address includes concatenating together the process identifier with the linear address.  
     
     
         6 . The method of  claim 1 , wherein the process identifier is a page directory base pointer that is a physical address of a base of a page directory.  
     
     
         7 . The method of  claim 1 , wherein the process identifier resides in a register.  
     
     
         8 . The method of  claim 1 , wherein the adjusted-linear address is formed by combining the process identifier with a portion of the linear address.  
     
     
         9 . The method of  claim 8 , wherein the portion of the linear address that is combined is a directory field of the linear address.  
     
     
         10 . The method of  claim 1 , wherein a portion of the adjusted-linear address is compared with each of the at least one tag, each of the at least one tag includes a corresponding portion of the adjusted-linear address.  
     
     
         11 . A system, comprising: 
 an adjusted-linear address formed by an address combining device combining a process identifier with a linear address; and    a hit/miss determinator to determine if the adjusted-linear address matches any one of at least one tag, each of the at least one tag corresponds to each of at least one cache line in an adjusted-linear addressed cache memory.    
     
     
         12 . The system of  claim 11 , wherein if the adjusted-linear address matches any one of the at least one tag, the hit/miss determinator compares a first physical address within a particular one of the at least one tag that matches the adjusted-linear address with a second physical address generated by translating the linear address.  
     
     
         13 . The system of  claim 12 , wherein if the hit/miss determinator finds that the first physical address matches the second physical address, then a data block corresponding to the particular one of the at least one tag is transmitted to a processor for manipulation.  
     
     
         14 . The system of  claim 12 , wherein if the hit/miss determinator finds at least one of the adjusted-linear address does not match any of the at least one tag, and the second physical address does not match the first physical address, then using a replacement policy to select a particular one of the at least one cache line, a data block within the particular one of the at least one cache line is replaced with a data block located at the second physical address within a storage device at a higher level in a memory hierarchy, and a particular one of the at least one tag corresponding to the particular one of the at least one cache line is the adjusted-linear address and the second physical address.  
     
     
         15 . The system of  claim 11 , wherein the address combining device combines the process identifier with the linear address by concatenating together the process identifier with the linear address to form the adjusted-linear address.  
     
     
         16 . The system of  claim 11 , wherein the address combining device combines the process identifier with the linear address by hashing together the process identifier with the linear address to form the adjusted-linear address.  
     
     
         17 . The system of  claim 11 , wherein the process identifier is a page directory base pointer that is a physical address of a base of a page directory.  
     
     
         18 . The system of  claim 11 , wherein the process identifier resides in a register.  
     
     
         19 . The system of  claim 11 , wherein the adjusted-linear address is formed by combining the process identifier with a portion of the linear address.  
     
     
         20 . The system of  claim 19 , wherein the portion of the linear address that is combined is a directory field of the linear address.  
     
     
         21 . The system of  claim 11 , wherein the hit/miss determinator determines if a portion of the adjusted-linear address matches any of the at least one tag, each of the at least one tag includes a corresponding portion of the adjusted-linear address.  
     
     
         22 . A method for accessing a particular one of at least one cache line of an adjusted-linear-addressed cache memory, the particular one of the at least one cache line referenced by a linear address, comprising: 
 indexing a particular one of the at least one cache line referenced by the linear address;    combining a page table entry with the linear address to form an adjusted-linear address;    comparing the adjusted-linear address with a first portion of a tag corresponding to the particular one of the at least one cache line referenced to determine if the adjusted-linear address matches the first portion of the tag; and    if the adjusted-linear address matches the first portion of the tag, comparing a second portion of the tag with a first physical address generated by translating the linear address.    
     
     
         23 . The method of  claim 22 , further comprising, 
 transmitting a data block within the particular one of the at least one cache line to a processor if the adjusted-linear address matches the first portion of the tag and the second portion of the tag matches the first physical address.    
     
     
         24 . The method of  claim 23 , further comprising, 
 replacing a data block within a particular one of the at least one cache line that is selected by a replacement policy with a data block from a storage device as specified by the first physical address if at least one of the adjusted-linear address does not match the first portion of the tag, and the first physical address does not match the second portion of the tag,    wherein the first portion of the tag corresponding to the particular one of the at least one cache line that is selected is the adjusted-linear address and the second portion of the tag is a second physical address of the data block from the storage device.    
     
     
         25 . The method of  claim 22 , wherein combining the page table entry with the linear address includes hashing together the page table entry with the linear address.  
     
     
         26 . The method of  claim 22 , wherein combining the page table entry with the linear address includes concatenating together the page table entry with the linear address.  
     
     
         27 . The method of  claim 22 , wherein the particular one of the at least one cache line is indexed using a first portion of the linear address.  
     
     
         28 . The method of  claim 27 , wherein the first portion of the linear address is an offset field of the linear address.  
     
     
         29 . The method of  claim 22 , wherein the page table entry is combined with a second portion of the linear address to form the adjusted-linear address.  
     
     
         30 . The method of  claim 29 , wherein the second portion of the linear address is a directory field of the linear address.