Abstract:
A method for reducing cache memory pollution including fetching an instruction stream from a cache line, preventing a fetching for the instruction stream from a sequential cache line, searching for a next predicted taken branch instruction, determining whether a length of the instruction stream extends beyond a length of the cache line based on the next predicted taken branch instruction, continuing preventing the fetching for the instruction stream from the sequential cache line if the length of the instruction stream does not extend beyond the length of the cache line, and allowing the fetching for the instruction stream from the sequential cache line if the length of the instruction stream extends beyond the length of the cache line, whereby the fetching from the sequential cache line and a resulting polluting of a cache memory that stores the instruction stream is minimized. A corresponding system and computer program product.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    This invention relates generally to computer processor operation, and more particularly to providing a method, system, and computer program product for reducing cache memory pollution. 
         [0002]    In order to reduce or avoid the time delay (or “latency”) of accessing data stored in the main memory of a computer, modem computer processors include a cache memory (or “cache”) that stores recently accessed data so that it can be quickly accessed again by the processor. Data that is stored in a cache can be quickly accessed by a processor without the need to access the main memory (or “memory”), thereby increasing the performance of the processor and the computer overall. However, if the data needed by the processor does not exist (i.e., is not currently stored) in the cache, which is known as a “miss”, then the processor is subject to the latency of accessing the memory for the needed data. A miss can also occur in cache memory designs that include a low level cache (e.g., an “L1 cache”) and one or more higher level caches (e.g., an “L2 cache”, “L3 cache”, etc.) when the data needed by the processor does not exist in the L1 cache and the processor has to access a higher level cache, which also results in latency. 
         [0003]    To reduce or avoid the latency of accessing data from the main memory or a higher level cache when there is a miss, data is often preloaded (or “prefetched”) into the cache (or the L1 cache in the case of a multiple level cache) before it is needed by the processor. Thus, when the needed data is referenced by the processor, the resulting latency (or “miss penalty”) is avoided if the data was prefetched or reduced if a prefetch of the data from the memory or a higher level cache is already in progress. However, prefetches of data are typically speculative, so it is not assured that prefetched data will be used by the processor. Since a cache memory (whether L1, L2, etc) is usually a fraction of the size of a main memory, a limited amount of data can be stored in the cache, and existing data is removed (or evicted) from the cache to provide space for newly prefetched data when the cache is full. Therefore, prefetched data that is not used by the processor can negatively affect performance by causing useful data to be evicted from the cache (or the L1 cache in a multi-level cache design), thereby requiring the processor to access the memory (or a higher level cache) to reference the useful data when it is needed. This eviction of useful data as a result of prefetching unneeded data is known as cache pollution, and it is desirable to reduce cache pollution. 
       BRIEF SUMMARY OF THE INVENTION 
       [0004]    A method, system, and computer program product for reducing cache memory pollution is provided. An exemplary method embodiment includes fetching an instruction stream from a cache line, preventing a fetching for the instruction stream from a sequential cache line, searching for a next predicted taken branch instruction, determining whether a length of the instruction stream extends beyond a length of the cache line based on the next predicted taken branch instruction, continuing preventing the fetching for the instruction stream from the sequential cache line if the length of the instruction stream does not extend beyond the length of the cache line, and allowing the fetching for the instruction stream from the sequential cache line if the length of the instruction stream extends beyond the length of the cache line, whereby the fetching from the sequential cache line and a resulting polluting of a cache memory that stores the instruction stream is minimized. 
         [0005]    An exemplary system embodiment includes an instruction fetch control configured to: fetch an instruction stream from a cache line, prevent a fetch for the instruction stream from a sequential cache line, determine whether a length of the instruction stream extends beyond a length of the cache line based on a next predicted taken branch instruction, continue preventing the fetch for the instruction stream from the sequential cache line if the length of the instruction stream does not extend beyond the length of the cache line, and allow the fetch for the instruction stream from the sequential cache line if the length of the instruction stream extends beyond the length of the cache line; and a branch prediction logic in communication with the instruction fetch control and configured to search for the next predicted taken branch instruction and communicate it to the instruction fetch control; whereby the fetch from the sequential cache line by the instruction fetch control and a resulting polluting of a cache memory that stores the instruction stream is minimized. 
         [0006]    An exemplary computer program product embodiment includes a computer usable medium having a computer readable program, wherein the computer readable program, when executed on a computer, causes the computer to fetch an instruction stream from a cache line, prevent a fetch for the instruction stream from a sequential cache line, search for a next predicted taken branch instruction, determine whether a length of the instruction stream extends beyond a length of the cache line based on the next predicted taken branch instruction, continue preventing the fetch for the instruction stream from the sequential cache line if the length of the instruction stream does not extend beyond the length of the cache line, and allow the fetch for the instruction stream from the sequential cache line if the length of the instruction stream extends beyond the length of the cache line, whereby the fetch from the sequential cache line and a resulting polluting of a cache memory that stores the instruction stream is minimized. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0007]    Referring now to the drawings wherein like elements are numbered alike in the several FIGURES: 
           [0008]      FIG. 1  is a block diagram illustrating an example of a computer system including an exemplary computing device configured for reducing cache memory pollution. 
           [0009]      FIG. 2  is a block diagram illustrating an example of a processor subsystem of the exemplary computing device of  FIG. 1  that is configured for reducing cache memory pollution. 
           [0010]      FIG. 3  is a flow diagram illustrating an example of a method for reducing cache memory pollution executable, for example, on the exemplary computing device of  FIG. 1 . 
           [0011]      FIG. 4A  is a block diagram illustrating an example of an instruction stream, fetched, for example, by the processor subsystem of  FIG. 2 , whose length does not extend beyond the length of a cache line in which it starts. 
           [0012]      FIG. 4B  is a block diagram illustrating an example of an instruction stream, fetched, for example, by the processor subsystem of  FIG. 2 , whose length extends beyond the length of a cache line in which it starts. 
       
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
       [0013]    Exemplary embodiments of the invention described herein provide a method, system, and computer program product for reducing cache memory pollution. In accordance with such exemplary embodiments, cache memory pollution, which results from the eviction of useful data from the cache when unneeded data is prefetched, is reduced. Furthermore, the resulting unnecessary usage of system resources to fetch unneeded data is reduced. 
         [0014]    Turning now to the drawings in greater detail, wherein like reference numerals indicate like elements,  FIG. 1  illustrates an example of a computer system  100  including an exemplary computing device (“computer”)  102  configured for reducing cache memory pollution. In addition to computer  102 , exemplary computer system  100  includes network  120  and other device(s)  130 . Network  120  connects computer  102  and other device(s)  130  and may include one or more wide area networks (WANs) and/or local area networks (LANs) such as the Internet, intranet(s), and/or wireless communication network(s). Other device(s)  130  may include one or more other devices, e.g., one or more other computers, storage devices, peripheral devices, etc. Computer  102  and other device(s)  130  are in communication via network  120 , e.g., to communicate data between them. 
         [0015]    Exemplary computer  102  includes processor  104 , main memory (“memory”)  106 , and input/output component(s)  108 , which are in communication via bus  103 . Processor  104  includes cache memory (“cache”)  110  and controls  112 , which include components configured for reducing cache memory pollution that will be described below. Cache  110  may include multiple cache levels (e.g., L1, L2, etc.) that are on or off-chip from processor  104  (e.g., an L1 cache may be on-chip, an L2 cache may be off-chip, etc.). Memory  106  may include various data stored therein, e.g., instructions, software, routines, etc., which, e.g., may be transferred to/from cache  110  by controls  112  for execution by processor  104 . Input/output component(s)  108  may include one or more components that facilitate local and/or remote input/output operations to/from computer  102 , such as a display, keyboard, modem, network adapter, etc. (not depicted). 
         [0016]      FIG. 2  illustrates an example of a processor subsystem  200  of exemplary computer  102  that is configured for reducing cache memory pollution. Exemplary subsystem  200  may, e.g., be part of controls  112 . Subsystem  200  includes branch prediction logic (“BPL”)  202  and instruction fetch control (“IFC”)  206 , which are in communication, e.g., via one or more buses, circuits, connections, etc. IFC  206  receives one or more predicted target addresses, one or more predicted branch addresses, and, in some embodiments, additional branch prediction data (collectively, “branch prediction information”) from BPL  202 . IFC  206  uses a predicted target address as a reference point to begin fetching instructions and uses a predicted branch address as a reference point to stop fetching instructions. Based on the branch prediction information, IFC  206  sends one or more instruction fetch addresses to a cache memory (e.g., cache  110 ) or, if the instruction fetch is missed in the cache, to a main memory (e.g., memory  106 ). Alternately, in a multi-level cache design, IFC  206  may send one or more instruction fetch addresses to an above-L1 level of the cache if the instruction fetch is missed in the L1 cache or, if the instruction fetch is missed in the cache (e.g., including one or more above-L1 cache levels), to the main memory. BPL  202  also receives one or more of the instruction fetch addresses from IFC  206 . BPL  202  uses one or more starting instruction fetch addresses (e.g., an address of a target instruction or “predicted target address”) as a starting search address to search for predicted taken branch instructions (i.e., instructions executed based on a fulfilled condition—“predicted taken branches” or “predicted branches”) when the execution of a program (e.g., software, routine, etc.) begins. BPL  202  also uses one or more predicted target addresses as a starting address for new searches for predicted branches. 
         [0017]    In an exemplary operation of subsystem  200 , when processor  104  begins executing a program, the starting instruction fetch address for the program is communicated to BPL  202  from IFC  206  to use as a starting search address. BPL  202  then searches for predicted branches. When a predicted branch is found, its address (i.e., predicted branch address) is communicated to IFC  206  from BPL  202 , which uses the predicted branch address as a reference point to stop fetching instructions. A predicted target address is also communicated to IFC  206  from BPL  202 , which is used as a reference point to start fetching instructions. BPL  202  also uses the predicted target address as the starting address for a new search for predicted branches. When IFC  206  receives the predicted target address to begin an instruction stream fetch, the length of the cache line is known (e.g., it is a preset parameter). However, it is not known whether the length of the instruction stream that begins at the predicted target address extends beyond the length of the cache line, e.g., into a sequential cache line. 
         [0018]    To avoid issuing fetches to cache lines that will not be used, IFC  206  is configured to presume that the instruction stream is contained within a single cache line and, therefore, prevent fetches to one or more sequential cache lines, e.g., using a fetch blocking mechanism (e.g., sets a “fetch block”). IFC  206  then determines the length of the instruction stream with respect to the length of the cache line, e.g., based on the search for the second (or next) predicted branch by BPL  202 . Examples of this determination will be discussed further below. If IFC  206  determines that the length of the instruction stream does not extend beyond the length of the cache line as presumed, IFC  206  continues to prevent fetches to one or more sequential cache lines (e.g., holds or maintains the fetch block). However, if IFC  206  determines that the length of the instruction stream extends beyond the length of the cache line, IFC  206  allows fetches to one or more sequential cache lines (e.g., by releasing the fetch block). In some embodiments, if BPL  202  does not find a second prediction branch within a (e.g., system dependent) functionally feasible amount of time, then IFC  206  allows fetches to one or more sequential cache lines (e.g., releases the fetch block), e.g., to avoid negatively impacting performance (e.g., of processor  104  and/or computer  102  in general). 
         [0019]      FIG. 3  is illustrates an example of a method  300  for reducing cache memory pollution executable, for example, on exemplary computer  102 . In block  302 , an instruction stream is fetched from a cache line (e.g., by IFC  206 ). For example, the instruction stream may be fetched from a cache memory  110  (including from one or more levels) or a main memory  106  of a computer  102 . The instruction stream may start at a predicted target address, e.g., of a previous predicted branch or other pipeline restarting condition, such as a processor serialization event. In step  304 , a fetch for the instruction stream from a sequential cache line is prevented (e.g., by IFC  206  setting a fetch block). In block  306 , a search is conducted for a next predicted branch (e.g., by BPL  202 ). 
         [0020]    In block  308 , the length of the instruction stream is determined with respect to the length of the cache line (e.g., by IFC  206 ). In some embodiments, the length of the instruction stream may be determined based on the number bytes searched (e.g., by BPL  202 ) to find the next predicted branch, and this length is added to a cache line byte identifying portion (e.g., the least significant 8 bits of a 64-bit address) of the predicted target address (i.e., the start point byte of the instruction stream) to determine whether the instruction stream extends beyond the length of the cache line in which it starts. For example, if the length of the cache line is 256 bytes, the instruction stream starts at the 208th byte of the cache line, the BPL search length is 16 bytes, it takes four BPL searches to find the next predicted branch, and the predicted branch is found in the 12th byte of the fourth BPL search, then the length of the instruction stream is 208+[(16*3)+12]=268 bytes. Since the 268-byte relative length of the instruction stream is greater than the 256-byte length of the cache line, the instruction stream is determined to extend beyond the length of the cache line. If, based on the foregoing example, the next predicted branch is found in two BPL searches instead of four searches, then the length of the instruction stream is 208+[(16*1)+12]=236 bytes, and since the 236-byte relative length of the instruction stream is less than the 256-byte length of the cache line, the instruction stream is determined not to extend beyond the length of the cache line. 
         [0021]    In other embodiments, the length of the instruction stream may be determined based on a comparison of the cache line address included within the predicted target address to the cache line address included within the next predicted branch address (i.e., the ending address of the instruction stream). For example, the cache line may be 256 bytes in length with each address of the cache line identified by a 64-bit address, where the most significant 56 bits of the address identify the cache line (i.e., in distinction from other cache lines in a cache or main memory) and the least significant 8 bits identify the start or end point byte of the instruction stream within the cache line (e.g., byte 0, 1, 2, . . . , or 255). If the 56-bit cache line identifying portion of the starting address of the instruction stream is different from the 56-bit cache line identifying portion of the ending address of the instruction stream, then the length of the instruction stream extends beyond the length of the cache line, e.g., into a sequential cache line. However, if the cache line identifying portion of the starting address of the instruction stream is the same as the cache line identifying portion of the ending address, then the length of the instruction stream does not extend beyond the length of the cache line. Other examples for the determination of the length of the instruction stream with respect to the length of the cache line are possible, which may be known or apparent in light of the disclosure herein. 
         [0022]    In block  310 , the condition of whether the length of the instruction stream extends beyond the length of the cache line (e.g., based on the determination in block  308 ) is determined (e.g., by IFC  206 ). If the length of the instruction stream does not extend beyond the length of the cache line, method  300  proceeds with block  312  in which the preventing of the fetch from the sequential cache line is continued (e.g., the fetch block is maintained by IFC  206 ). If the length of the instruction stream does extend beyond the length of the cache line, method  300  proceeds with block  314  in which fetches from the sequential cache line are allowed (e.g., the fetch block is released by IFC  206 ). 
         [0023]    In some embodiments, the performance of blocks  308 ,  310 ,  312 , and  314  is dependent on an additional block  316  in which the condition of whether a next predicted branch is found within a (e.g., system dependent) functionally feasible amount of time is determined (e.g., by IFC  206 ). If the next predicted branch is found within the functionally feasible amount of time, method  300  continues with blocks  308 ,  310 ,  312 , and  314  as described above, wherein fetching from the sequential cache line is continued to be prevented or is allowed dependent on the length of the instruction stream in comparison to the length of the cache line. If the next predicted branch is not found within the functionally feasible amount of time, method  300  continues with block  314  as described above in which fetching from the sequential cache line is allowed. 
         [0024]      FIG. 4A  is a block diagram illustrating an example  400  of an instruction stream  422 , fetched, for example, by processor subsystem  200 , whose length does not extend beyond the length of a cache line  412  in which it starts. Exemplary diagram  400  depicts cache line  412  with start point  413  and end point  414 . Cache line  412  includes instruction stream  422  that starts at start point  423  within cache line  412  and ends at end point  424  also within cache line  412 . Thus, the length of instruction stream  422  does not extend beyond the length of cache line  412 . 
         [0025]      FIG. 4B  is a block diagram illustrating an example  450  of an instruction stream  472 , fetched, for example, by the processor subsystem  200 , whose length extends beyond the length of a cache line  462  in which it starts. Exemplary diagram  450  depicts cache line  462  with start point  463  and boundary point  465  with sequential cache line  464 . Boundary point  465 , e.g., depicts a boundary between an end point of cache line  462  and a start point of cache line  464 . Cache line  462  includes a portion of instruction stream  472  that starts at start point  473  within cache line  462  but ends at end point  474  within sequential cache line  464 . Thus, the length of instruction stream  472  extends beyond the length of cache line  462  (i.e., into sequential cache line  464 ). 
         [0026]    Elements of exemplary computer system  100 , such as computer  102 , are illustrated and described with respect to various components, modules, etc. for exemplary purposes. It should be understood that other variations, combinations, or integrations of such elements that provide the same features, functions, etc. are included within the scope of embodiments of the invention. 
         [0027]    The flow diagram described herein is just an example. There may be many variations to this diagram or the blocks (or operations) thereof without departing from the spirit of embodiments of the invention. For instance, the blocks may be performed in a differing order, or blocks may be added, deleted or modified. All of these variations are considered a part of the claimed invention. Furthermore, although an exemplary execution of the flow diagram blocks is described with respect to elements of exemplary computer system  100  and exemplary subsystem  200 , execution of the flow diagram blocks may be implemented with respect to other systems, subsystems, etc. that provide the same features, functions, etc. in accordance with exemplary embodiments of the invention. 
         [0028]    As described above, embodiments of the invention may be embodied in the form of computer-implemented processes and apparatuses for practicing those processes. Embodiments of the invention may also be embodied in the form of computer program code containing instructions embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other computer-readable storage medium, wherein, when the computer program code is loaded into and executed by a computer, the computer becomes an apparatus for practicing the invention. The present invention can also be embodied in the form of computer program code, for example, whether stored in a storage medium, loaded into and/or executed by a computer, or transmitted over some transmission medium, such as over electrical wiring or cabling, through fiber optics, or via electromagnetic radiation, wherein, when the computer program code is loaded into and executed by a computer, the computer becomes an apparatus for practicing the invention. When implemented on a general-purpose microprocessor, the computer program code segments configure the microprocessor to create specific logic circuits. 
         [0029]    While the invention has been described with reference to exemplary embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted for elements thereof without departing from the scope of the invention. In addition, many modifications may be made to adapt a particular situation or material to the teachings of the invention without departing from the essential scope thereof. Therefore, it is intended that the invention not be limited to the particular embodiment disclosed as the best mode contemplated for carrying out this invention, but that the invention will include all embodiments falling within the scope of the appended claims. Moreover, the use of the terms first, second, etc. do not denote any order or importance, but rather the terms first, second, etc. are used to distinguish one element from another.