Patent Publication Number: US-9418011-B2

Title: Region based technique for accurately predicting memory accesses

Description:
BACKGROUND 
     In order to improve the performance and efficiency of computing systems, for example PC&#39;s, servers, etc., prefetching data and instructions that a processor may need at a later time is considered beneficial. However, conventional prefetching has not been able to accurately predict which cache lines should or should not be prefetched. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of an example processor and memory in accordance with one embodiment of the present invention. 
         FIG. 2  is a block diagram of an example page tracker buffer in accordance with an embodiment of the present invention. 
         FIG. 3  is a flow chart of an example method for utilizing an access signature in accordance with an embodiment of the present invention. 
         FIG. 4  is a flow chart of an example method for utilizing a reuse signature in accordance with an embodiment of the present invention. 
         FIG. 5  is a block diagram of an example system in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     In various embodiments, methods and apparatuses of predictive prefetching are presented. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the invention. It will be apparent, however, to one skilled in the art that embodiments of the invention can be practiced without these specific details. In other instances, structures and devices are shown in block diagram form in order to avoid obscuring the invention. 
     Reference throughout this specification to “one embodiment” or “an embodiment” means that a particular feature, structure or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, appearances of the phrases “in one embodiment” or “in an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures or characteristics may be combined in any suitable manner in one or more embodiments. 
     Referring now to  FIG. 1 , shown is a block diagram of an example processor and memory in accordance with one embodiment of the present invention. As shown in  FIG. 1 , system  100  may include processor  102  and memory  104 . Processor  102  may include core(s)  106 , level one cache  108 , translation lookaside buffer (TLB)  110 , page tracker buffer (PTB)  112 , level two cache  114  and PTB handler  116 . While shown as including level one cache  108  and level two cache  114 , processor  102  may include any number of cache levels. Also, while processor  102  is shown as including TLB  110 , which can store address translations from a virtual address to a physical address, the present invention may be practiced in a processor without a TLB. 
     PTB  112  may contain entries, as shown in greater detail in reference to  FIG. 2 , that indicate which portions of specific memory regions (for example, which cache lines of specific cache pages or other memory regions) have been accessed previously by core(s)  106 . In one embodiment, PTB  112  also contains entries that indicate which cache lines of specific cache pages have been accessed multiple times by core(s)  106 , potentially indicating those cache lines that may be most desirable to remain resident in cache. 
     PTB handler  116  may attempt to accurately predict the instructions and data that will be needed by core(s)  106 , as described in more detail hereinafter. In one embodiment, PTB handler  116  prefetches those cache lines of a cache page added to TLB  110  (for example after a TLB miss) that PTB  112  indicates were accessed during a prior instantiation. PTB handler  116  may read PTB  112  entries from, and write back PTB  112  entries to, page tracker memory table  118 . PTB handler  116  may also update entries in PTB  112 , for example as additional cache lines are accessed by core(s)  106 . PTB handler  116  may be implemented in other hardware, such as a prefetch module, or software or a combination of hardware and software. PTB handler  116  may be applied to data and instruction prefetching independently and may co-exist with other prefetchers. 
     Memory  104  may represent any type of memory, such as static or dynamic random access memory (RAM). In one embodiment, memory  104  represents double data rate synchronous dynamic RAM (DDR-SDRAM), however the present invention is not limited to any type of memory. Memory  104  may be logically divided into pages, such as page  120 , for caching and addressing. Each page  120  may contain a fixed number of lines  122 . In one embodiment, page  120  contains 64 lines  122 . In another embodiment, page  120  represents a memory region whose size may be configurable through firmware or software. 
     Referring now to  FIG. 2 , shown is a block diagram of an example page tracker buffer in accordance with an embodiment of the present invention. As shown in  FIG. 2 , page tracker buffer  112  may include any number of entries, accessible through index  208 , which each may include address  202 , access signature  204 , and reuse signature  206 . In one embodiment, PTB  112  may include a same number of entries as TLB  110 . In other embodiments, PTB  112  may include more or fewer entries than TLB  110 . In one embodiment, PTB  112  may include 64 entries. In another embodiment, PTB  112  may include 1024 entries. 
     While shown as including 28 bits, address  202  may contain more or fewer bits for identifying a page  120  (or another memory region). While shown as including 64 bits, access signature  204  and reuse signature  206  may contain more or fewer bits for identifying lines  122  of a page  120 . In one embodiment, set bits of access signature  204  indicate the lines  122  of page  120  that were accessed by core(s)  106  in a prior addressing of page  120  in TLB  110 . In one embodiment, set bits of reuse signature  206  indicate the lines  122  of page  120  that were accessed multiple times by core(s)  106  in a prior addressing of page  120  in TLB  110 . 
     Referring now to  FIG. 3 , shown is a flow chart of an example method for utilizing an access signature in accordance with an embodiment of the present invention. As shown in  FIG. 3 , the method begins with PTB handler  116  loading ( 302 ) access signature  204  associated with a cache page  120  into PTB  112  after writing back any evicted entry to page tracker memory table  118 . In one embodiment, PTB handler  116  loads access signature  204  after a TLB  110  miss and writes back any access signature being replaced. Next, PTB handler  116  may prefetch ( 304 ) lines  122 , into level two cache  114 , for example, indicated by access signature  204  as having been accessed by core(s)  106  previously. Lastly, PTB handler  116  may update ( 306 ) access signature  204 . In one embodiment, PTB handler  116  adds bits to the retrieved access signature  204  as any additional lines are requested and fetched. In another embodiment, PTB handler  116  may use the retrieved access signature  204  for prefetching and may regenerate the access signature for writing back to memory to be used on a subsequent page access. 
     Referring now to  FIG. 4 , shown is a flow chart of an example method for utilizing a reuse signature in accordance with an embodiment of the present invention. As shown in  FIG. 4 , the method begins with PTB handler  116  loading ( 402 ) reuse signature  206  associated with a cache page  120  into PTB  112  after writing back any evicted entry to page tracker memory table  118 . In one embodiment, PTB handler  116  loads reuse signature  206  after a TLB  110  miss. Next, PTB handler  116  may prioritize ( 404 ) replacement policy for those cache lines in level two cache  114  indicated by reuse signature  206  as having been accessed by multiple times by core(s)  106  previously. In one embodiment, PTB handler  116  may set as most recently used those cache lines with a bit set in reuse signature  206 . In another embodiment, PTB handler  116  may set as least recently used those cache lines without a bit set in reuse signature  206 . Lastly, PTB handler  116  may update ( 406 ) reuse signature  206  as any additional lines are requested multiple times. 
     Embodiments may be implemented in many different system types. Referring now to  FIG. 5 , shown is a block diagram of a system in accordance with an embodiment of the present invention. As shown in  FIG. 5 , multiprocessor system  500  is a point-to-point interconnect system, and includes a first processor  570  and a second processor  580  coupled via a point-to-point interconnect  550 . As shown in  FIG. 5 , each of processors  570  and  580  may be multicore processors, including first and second processor cores (i.e., processor cores  574   a  and  574   b  and processor cores  584   a  and  584   b ). Each processor may include PTB hardware, software, and firmware in accordance with an embodiment of the present invention. 
     Still referring to  FIG. 5 , first processor  570  further includes a memory controller hub (MCH)  572  and point-to-point (P-P) interfaces  576  and  578 . Similarly, second processor  580  includes a MCH  582  and P-P interfaces  586  and  588 . As shown in  FIG. 5 , MCH&#39;s  572  and  582  couple the processors to respective memories, namely a memory  532  and a memory  534 , which may be portions of main memory (e.g., a dynamic random access memory (DRAM)) locally attached to the respective processors, each of which may include page tracker memory tables in accordance with one embodiment of the present invention. First processor  570  and second processor  580  may be coupled to a chipset  590  via P-P interconnects  552  and  554 , respectively. As shown in  FIG. 5 , chipset  590  includes P-P interfaces  594  and  598 . 
     Furthermore, chipset  590  includes an interface  592  to couple chipset  590  with a high performance graphics engine  538 . In turn, chipset  590  may be coupled to a first bus  516  via an interface  596 . As shown in  FIG. 5 , various I/O devices  514  may be coupled to first bus  516 , along with a bus bridge  518  which couples first bus  516  to a second bus  520 . Various devices may be coupled to second bus  520  including, for example, a keyboard/mouse  522 , communication devices  526  and a data storage unit  528  such as a disk drive or other mass storage device which may include code  530 , in one embodiment. Further, an audio I/O  524  may be coupled to second bus  520 . 
     Embodiments may be implemented in code and may be stored on a storage medium having stored thereon instructions which can be used to program a system to perform the instructions. The storage medium may include, but is not limited to, any type of disk including floppy disks, optical disks, compact disk read-only memories (CD-ROMs), compact disk rewritables (CD-RWs), and magneto-optical disks, semiconductor devices such as read-only memories (ROMs), random access memories (RAMs) such as dynamic random access memories (DRAMs), static random access memories (SRAMs), erasable programmable read-only memories (EPROMs), flash memories, electrically erasable programmable read-only memories (EEPROMs), magnetic or optical cards, or any other type of media suitable for storing electronic instructions. 
     While the present invention has been described with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of this present invention.