Patent Publication Number: US-6990551-B2

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

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
   This application is a continuation of application Ser. No. 09/751,258 filed Dec. 29, 2000, the contents of which is incorporated herein in its entirety by reference thereto. 

   BACKGROUND OF THE INVENTION 
   I. Field of the Invention 
   This invention relates generally to computer technology, and more particularly, to improving processor performance in a computer system. 
   II. Background Information 
   The use of a cache memory with a processor facilitates the reduction of memory access time. The cache memory may be configured, among others, as an instruction cache, a data cache, or a translation lookaside buffer (cache that stores recently used page-directory and page-table entries). The fundamental idea of cache organization is that by keeping the most frequently accessed instructions and data in the fast cache memory, the average memory access time will approach the access time of the cache. It is generally understood that storage devices closer to the processor operate faster than storage devices farther away on the data path from the processor. However, there is a cost trade-off in utilizing faster storage devices. The faster the data access, the higher the cost to store a bit of data. Accordingly, a cache memory tends to be much smaller in storage capacity than main memory, but is faster in accessing the data. 
   In today&#39;s high-performance processor architectures, multi-level caches are employed to provide the most often referenced data to the execution units in a timely manner. For example, a two-level cache hierarchy is used so that the most often used data is stored in a small first-level cache that has a faster access time than a bigger second-level cache. The purpose of the bigger second-level cache is to capture the working set of an application in the cache and prevent the processor from having to access the slower main memory for data. 
   A virtual memory environment allows a large linear address space to be simulated with a small amount of physical memory (e.g., random access memory or read-only memory) and some disk storage. When a process references a logical address in memory, the processor translates the logical address into a linear address and then translates the linear address into a corresponding physical address. The physical address corresponds to a hardware memory location. A linear-to-physical address translation involves memory management hardware translating the linear address to the physical address. The linear-to-physical address translation is time consuming and waiting for this translation before performing an action (e.g., performing a cache lookup) increases the memory access time. 
   In order to decrease memory access time, a cache (e.g., the first-level cache in the above example) may be organized as a linear-addressed cache where the linear address of the memory request is used for the cache lookup rather than the physical address. The linear-addressed cache forgoes the linear-to-physical address translation before performing the cache lookup. Forgoing the linear-to-physical address translation decreases the memory access time. When using the linear-addressed cache, the linear-to-physical address translation is still performed because the physical address resulting from the translation is used to validate the data accessed in the cache using the linear address (i.e., check to ensure that the correct memory locations are accessed), but this linear-to-physical address translation is performed in parallel with the cache lookup. Performing the linear-to-physical address translation in parallel with the linear-addressed cache lookup improves the memory access time as the translation overhead is minimized due to the overlap with the cache lookup. 
   More than one process may execute on a processor. Typically, the linear-addressed cache is flushed when the processor switches from executing one process to executing another process. A cache flush occurs when the processor writes the valid and current data from its cache back into main memory. The cache flush diminishes processor performance as the processor may have to wait for completion of writes to the main memory. Moreover, data that would have been accessed after the cache flush that was in the cache before the flush, now has to be brought back into the cache. Therefore, cache flushes are avoided whenever possible in order to increase processor performance. 
   If a cache flush is not performed whenever a process switch occurs, then the linear-addressed cache may suffer from linear address aliasing. Linear address aliasing occurs when two separate processes running on the processor access the same cache line but those linear addresses map to different physical addresses (e.g., process one accesses linear address A and process two accesses linear address A but linear address A maps to different physical addresses). When linear address aliasing occurs, if the physical address, generated by performing a linear-to-physical address translation of the linear address, does not match a physical address within the tag of a cache line whose tag matches the linear address, then the data block provided (i.e., the data block within the cache line whose tag matches the linear address) is discarded, and the data block referenced by the linear address is brought into the linear-addressed cache from a storage device at a higher level in the memory hierarchy (e.g., main memory or the hard disk). This discarding of the provided data block and the resulting memory access (resulting from the linear address aliasing) to the slower storage device at the higher hierarchical level decreases processor performance. 
   For the foregoing reasons, there is a need to reduce the linear address aliasing problem between two or more processes, especially in a multi-threaded processor where these processes are run simultaneously. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  shows a linear-to-physical address translation in which a page table is not used to obtain the physical address. 
       FIG. 2  shows a linear-to-physical address translation in which a page table is used to obtain the physical address. 
       FIG. 3  shows a block diagram of an adjusted-linear-addressed cache memory system according to an embodiment of the present invention. 
       FIG. 4  shows a block diagram of an adjusted-linear-addressed cache memory replacing system according to an embodiment of the present invention. 
       FIG. 5  shows a flowchart describing the process for searching and populating the adjusted-linear-addressed cache memory according to an embodiment of the present invention. 
   

   DETAILED DESCRIPTION 
   In order to prevent linear address aliasing when using a linear-addressed cache memory (e.g., an instruction cache, a data cache, or a translation lookaside buffer), in an embodiment of the present invention, a process identifier that is unique to a process is combined with a portion or all of the linear address to form an adjusted-linear address. By combining the process identifier that is unique and a portion or all of the linear address, the resulting adjusted-linear address provides a high probability of no aliasing, and thus the possibility of linear address aliasing is reduced. The adjusted-linear address is used to search an adjusted-linear-addressed cache memory. The process identifier may be combined with the linear address by methods that include, among others, concatenating or hashing together the linear address and the process identifier. 
   The process identifier may be a page directory base pointer. Operating systems running on an Intel Architecture 32-bit (“IA-32”) architecture (i.e., architectures employing an 8086, 80286, 80386, 80486, or Pentium® processor by Intel Corporation) may assign a different page directory to each process and each of these page directories are uniquely identified by the page directory base pointer. Combining the page directory base pointer with the linear address is particularly beneficial for multi-threaded execution (i.e., executing several processes in rapid sequence). Multiple threads (a thread is a process that is part of a larger process or program) can share the adjusted-linear-addressed cache memory, and separating the cache lines between the threads results in less negative impact of a thread thinking that it is operating on the right data, but later having to be corrected (a linear-addressed cache includes the associated physical address for each cache line and there is a final check of the translated address to the stored physical address before the memory request is deemed valid). Moreover, if a process running as thread x is suspended and later is reactivated as thread y, the page directory base pointer for thread y remains the same as that for thread x and thus thread y can still access the cache lines that thread x fetched into the adjusted-linear-addressed cache memory. 
   Combining the page directory base pointer and the linear address by methods that include concatenating or hashing is a faster operation than performing a linear-to-physical address translation, as the page directory base pointer is quickly available in a register. Performing a linear-to-physical address translation, however, uses a memory access (e.g., the memory access may be to the cache or main memory; the memory accesses take longer than accessing the register) to obtain the linear address to physical address mapping. 
     FIG. 1  shows a linear-to-physical address translation in which a page table is not used to obtain the physical address. Here, a page directory base pointer  13  holds the base physical address for a page directory  16 . Each process has a unique page directory  16 . Each process also has a unique page directory base pointer  13 . Page directory base pointer  13  is used to access page directory  16 . The directory field of a linear address  10   a  provides an offset to a directory entry. The directory entry provides a base physical address for a page  22   a . The offset field of linear address  10   a  provides an offset to a physical address  25  within page  22   a.    
     FIG. 2  shows a linear-to-physical address translation in which a page table is used to obtain the physical address. Here, page directory base pointer  13  is used to access page directory  16 . A directory field of a linear address  10   b  provides an offset to a directory entry in page directory  16 . The directory entry provides a base physical address of a page table  19 . A table field of linear address  10   b  provides an offset to a page-table entry  31 . Page-table entry  31  provides a base physical address of a page  22   b . The offset field of linear address  10   b  provides an offset to physical address  25  within page  22   b.    
     FIG. 3  shows a block diagram of an adjusted-linear-addressed cache memory system according to an embodiment of the present invention. In this embodiment, address combining device  313  combines a portion of linear address  10   a , e.g., the portion of linear address  10   a  may be the directory field of linear address  10   a , with the process identifier, e.g., a page directory base pointer  13 , to produce a portion of an adjusted-linear address  325 . The offset field of linear address  10   a  provides the remaining portion of adjusted-linear address  325 . As stated earlier, page directory base pointer  13  is unique to a process and the resulting adjusted-linear address  325  provides a high probability of no aliasing. Address combining device  313  combines page directory base pointer  13  and the directory field of linear address  10   a  using methods that include hashing and concatenating. Adjusted-linear address  325  is used to search an adjusted-linear-addressed cache memory  310 . Adjusted-linear-addressed cache memory  310  includes cache lines and each of the cache lines has a tag and a data block. The tag for a particular cache line includes a portion of adjusted-linear address  325  and the physical address corresponding to adjusted-linear address  325 . 
   A hit/miss determinator  316  determines if the data block referenced by adjusted-linear address  325  resides in adjusted-linear address cache memory  310 . Hit/miss determinator  316  searches the tags of the cache lines to determine if any of the tags match a portion of adjusted-linear address  325  (e.g., the portion of adjusted-linear address  325  may be the address formed by address combining device  313  combining the directory field of linear address  10   a  with page directory base pointer  13 ). If a tag matches a portion of adjusted-linear address  325 , then hit/miss determinator  316  compares the physical address stored within that tag with physical address  25  generated from the linear-to-physical address translation of linear address  10   a  as described in FIG.  1 . This linear-to-physical address translation is performed in parallel with the searching of adjusted-linear-addressed cache memory  310 . If the physical address stored within that tag matches physical address  25 , then the data block referenced by linear address  10   a  resides in adjusted-linear-addressed cache memory  310  and can be accessed. If, however, none of the tags match a portion of adjusted-linear address  325  or the physical address stored within that tag does not match physical address  25 , then a replacement policy is used to replace the data block in one of the cache lines selected by the replacement policy with the data block referenced by linear address  10   a  and found in a storage device that is at a higher level in the memory hierarchy (e.g., main memory or the hard disk). The new tag for the cache line selected includes a portion of adjusted-linear address  325  and physical address  25 . 
     FIG. 4  shows a block diagram of an adjusted-linear-addressed cache memory replacing system according to an embodiment of the present invention. If the data block referenced by linear address  10   a  does not reside in adjusted-linear-addressed cache memory  310 , then one of the cache lines, as selected by a replacement policy, of adjusted-linear-addressed cache memory  310  is replaced with the data block that is referenced by linear address  10   a  and the tag for this cache line is set accordingly. In  FIG. 4 , assume that the data block referenced by linear address  10   a  does not reside in adjusted-linear-addressed cache memory  310  and a cache line  328  is selected by the replacement policy to hold the data block referenced by linear address  10   a . Cache line  328  includes a tag  319  and a data block  331 . Tag  319  includes physical address  25  which is found by performing the linear-to-physical address translation of linear address  10   a  as described earlier in FIG.  1 . Tag  319  also includes a portion of adjusted-linear address  325 . The portion of adjusted-linear address  325  included in tag  319  may be the address formed by address combining device  313  combining the directory field of linear address  10   a  with page directory base pointer  13 . Data block  331  is the data block referenced by linear address  10   a  and because this data block did not previously reside in adjusted-linear-addressed cache memory  310 , it was fetched, using physical address  25 , from a storage device at a higher level in the memory hierarchy. 
     FIG. 5  shows a flowchart describing the process for searching and populating adjusted-linear-addressed cache memory  310  according to an embodiment of the present invention. In this embodiment, in block  510 , address combining device  313  combines a directory field of linear address  10   a  with page directory base pointer  13  to form a portion of adjusted-linear address  325  and an offset field of linear address  10   a  is the remaining portion of adjusted-linear address  325 . The linear address and the page directory base pointer are combined by methods that include concatenating and hashing. In block  513 , hit/miss determinator  316  compares a portion of adjusted-linear address  325  with the tags of each of the cache lines of adjusted-linear-addressed cache memory  310  to determine if the portion of adjusted-linear address  325  matches any of these tags (i.e., to determine if a data block addressed by adjusted-linear address  325  resides in adjusted-linear-addressed cache memory  310 ). 
   In conditional block  519 , hit/miss determinator  316  determines if one of the tags matches a portion of adjusted-linear address  10   a . If one of the tags matches a portion of adjusted-linear address  325 , then in conditional block  520 , hit/miss determinator  316  determines if physical address  25 , generated by performing the linear-to-physical address translation of linear address  10   a  (as shown in FIG.  1 ), matches a second physical address stored within the particular one of the tags that matches a portion of adjusted-linear address  325 . If the two physical addresses match, then in block  522 , the data block within the particular one of the cache lines corresponding to the particular one of the tags that matches a portion of adjusted-linear address  325  is transmitted to a processor for manipulation. If none of the tags match a portion of adjusted-linear address  325 , or physical address  25  does not match the second physical address, then in block  525 , the data block within a particular one of the cache lines selected by a replacement policy is replaced with a data block located at physical address  25  within a storage device at a higher level in a memory hierarchy. In block  528 , the tag for the cache line that is selected by the replacement policy is set to a portion of adjusted-linear address  325  and physical address  25  generated by translating linear address  10   a.    
   Although unlikely, linear address aliasing may still exist when the process identifier is combined with the linear address, and therefore the replacement policy corrects data blocks in adjusted-linear-addressed cache memory  310  having the same adjusted-linear address but mapping to different physical addresses. This memory coherency may be done by, among others, the following strategies: (1) ensuring that only one copy of a data block is present in the cache at a given time (i.e., remove duplicate data blocks mapping to the same physical address); (2) invalidating duplicate copies of data blocks on a write (i.e., remove duplicate data blocks if one of the data blocks is modified); and (3) update all copies of data blocks when one of the data blocks is written. To assent to strategy (1), the number of translated bits (i.e., the bits in the portion of adjusted-linear address  325  formed by combining page directory base pointer  13  with the directory field of linear address  10   a ) used to index adjusted-linear-addressed cache memory  310  should be kept to a minimum in order to keep to a minimum the number of sets that are searched for duplicate data blocks. 
   In an alternative embodiment, page-table entry  31  is combined with linear address  10   b  to reduce linear address aliasing and also to allow multiple processes to share pages. In this embodiment, the corresponding page table entry  31  is combined with a first portion of the linear address (e.g., the first portion of the linear address may be the directory field of the linear address) to form a portion of the adjusted-linear address. The tag of each of the cache lines in the linear-addressed cache also includes the portion of the adjusted-linear address corresponding to that cache line. The linear-addressed cache is indexed using a second portion of the linear address (e.g., the second portion of the linear address may be the offset field of the linear address). Because page table entry  31  is obtained during the linear-to-physical address translation (i.e., page table entry  31  is not immediately available and a memory access (e.g., a cache access or main memory access) is used to obtain page table entry  31 ), page table entry  31  is not used to index the linear-addressed cache, but rather the second portion of the linear address is used to index the linear-addressed cache. 
   The portion of the adjusted-linear address stored within the tag for the cache line indexed is compared to the page table entry  31  combined with the first portion of the linear address. If these two addresses do not match, then the data block referenced by the linear address does not reside in the linear-addressed cache and thus must be fetched from the storage device at the higher level in the memory hierarchy. If the two addresses do match, however, then the physical address stored within the tag is compared to the physical address obtained from performing the linear-to-physical address translation. If these two addresses do not match, then the data block referenced by the linear address does not reside in the linear-addressed cache and thus must be fetched from the storage device at the higher level in the memory hierarchy. If the two addresses do match, however, then the data block referenced by the linear address does reside in the linear-addressed cache and is sent to the processor for processing. In this embodiment, by combining the linear address with page table entry  31 , linear address aliasing is reduced while still allowing different processes to share pages as those shared pages will have the same page table entry  31 . 
   In alternative embodiments, linear address  10   b  is used rather than linear address  10   a , and in this case, the directory field of linear address  10   b  is combined with page directory base pointer  13  to form a portion of adjusted-linear address  325 . The table field and the offset field of linear address  10   b  are the remaining portions of adjusted-linear address  325 . In other embodiments, fields, other than the directory field, or all of the linear address are combined with the process identifier to form the adjusted-linear address. Embodiments of the present invention are not limited to combining linear addresses having the format of linear address  10   a  or linear address  10   b , but rather, linear addresses of any format can be combined with the process identifier to form the adjusted-linear address. Also, the tag for each of the cache lines may include all or a portion of the linear address or the adjusted-linear address, and thus all or a portion of linear address or the adjusted-linear address is used for the tag matching. 
   Although embodiments are specifically illustrated and described herein, it will be appreciated that modifications and variations of the present invention are covered by the above teachings and within the purview of the appended claims without departing from the spirit and intended scope of the invention.