Abstract:
The invention teaches how to reduce the traffic associated with handling cache lines containing useless data (i.e. cache lines corresponding to pages that have been invalidated). The invention makes it possible to evict such cache lines earlier, to avoid write backs of useless data from such cache lines to main memory, and to avoid transmitting useless data from such cache lines to the requesting remote coherence controller in a multiprocessor system. The present invention describes a mechanism for invalidating cache lines containing useless data transparently and without programmer&#39;s involvement. For efficiency, the content of a cache line containing useless data is invalidated only when the line is referenced or is about to be allocated for some new data.

Description:
RELATED APPLICATION 
     This application claims the benefit of provisional application No. 60/198,406, filed Apr. 19, 2000 and now abandoned. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention generally relates to the management of caches in a computer system. Namely, this invention relates to a method and an apparatus for reducing memory traffic between various components of a memory subsystem (e.g. between a write buffer and main memory, between a cache and main memory, and between processors in a multiprocessor system). More specifically, the present invention relates to a mechanism for avoiding unnecessary cache traffic related to handling cached data corresponding to pages marked as containing useless data (e.g. invalidated pages). 
     2. Discussion of the Prior Art 
     Frequently, a program generates and modifies data which at some point in time (even long before program completion) become absolutely “useless” for that program. In a memory constraint environment, it is not unlikely for a page containing such useless (modified) data to be swapped out from main memory to a disk. There exist several techniques (e.g. DIAGNOSE X‘214’ Pending Page Release call available on IBM s/390 and a mechanism described in copending application Ser. No. 09/636,049, filed Aug. 10, 2000, for “A Method and Apparatus for Efficient Virtual Memory Management”), the disclosure of which is herein, incorporated by reference) enabling a program to indicate to the OS whether the contents of certain pages (e.g. those containing only useless data) can be safely discarded (i.e. invalidated) should those pages be selected for eviction. The content of a page marked as invalid (useless) need not be written back to a disk even if the page is in a modified state. (The terms “modified” and “dirty” will be used interchangeably.) 
     However, when a page is invalidated, it is possible that some data (dirty or clean) associated with that page still resides in a processor cache (e.g. in a large write-back cache). This data is useless and occupies valuable cache resources. Moreover, handling this useless data (especially the data in a modified/dirty state) causes needless overhead: 
     a) Specifically, sooner or later, modified (dirty), useless data will be evicted from a cache (as a result of a cache line replacement while servicing a cache miss) and placed into a write buffer[2]. From a write buffer, the data is written back to memory. Writing this data to memory generates unnecessary traffic on a memory bus. Because write buffers tend to be small, they can easily get filled with useless data. 
     b) In addition, in a set associative cache, a cache line containing useful data (i.e. the data that will be used in the future) can be replaced before a cache line (from the same set) containing useless (dirty or clean) data (e.g. according to the least recently used replacement policy). If the useful data is in a modified state, it will have to be written back to memory. Later on, as a result of a cache miss, the useful data will have to be re-fetched from memory. Re-fetching that useful data generates unnecessary traffic on a memory bus. Hence, in a set-associative cache, a cache line containing useful data can sometimes be evicted before a cache line (in the same set) containing useless data. 
     c) Also, in a multiprocessor system (e.g. a shared memory multiprocessor, if some processor other than the one currently controlling the invalidated page (i.e. a page containing useless data) gets the control of the invalidated page and starts initializing that page with new data., some useless data (dirty or clean) may be sent across a bus (or some other interconnect), by a coherence controller to that requesting processor (i.e. the processor performing the initialization of that page and hereby requesting cached data from that page be transmitted to it). Hence, in a multiprocessor system (e.g. a shared memory multiprocessor), a coherence controller sometimes transmits useless data to a requesting processor. 
     The instruction sets of many microprocessors include instructions for managing on-chip (or local) instruction and data caches. Some of these instructions (privileged instructions) are only available to the supervisor-mode processes due to their destructive effect while others can be used-by user-level processes for effective cache management. For example, the following cache management instruction is implemented in PowerPC 604e: 
     DCBI (Data Cache Block Invalidate) is a supervisor-level (privileged) instruction due to the fact that it discards and invalidates the data stored in the cache block whether it is in clean (exclusive or shared) or in modified states. Once the data is invalidated, other processors on the same bus are instructed to invalidate the specified cache block. 
     Note that it is the responsibility of a programmer to invalidate cache lines containing useless data. A single instruction can invalidate at most one line. Hence, a number of such instructions must be issued to invalidate multiple cache lines (associated with a page). Finally, a supervisor-level (priviledged) instruction cannot be used by a user-level program. 
     SUMMARY OF THE INVENTION 
     From a correctness standpoint, cache lines containing useless data (i.e. cache lines corresponding to pages that have been invalidated) do not have to be kept around, written back to memory, or transmitted to a (remote) requesting processor upon request. 
     Therefore, an object of this invention is a method and an apparatus for reducing memory traffic between various components of a memory subsystem (e.g. between a write buffer and main memory, between a cache and main memory, and between processors in a multiprocessor system). 
     The invention reduces the traffic associated with handling cache lines containing useless data (i.e. cache lines corresponding to pages that have been invalidated). The invention makes it possible to do the following: to evict such cache lines earlier than when they would have been evicted according to an implemented replacement policy; to avoid write backs of useless data from such cache lines to main memory; and to avoid transmitting useless data from such cache lines to a requesting processor in a multiprocessor system. 
     The present invention describes a mechanism for invalidating cache lines containing useless data transparently and without programmer&#39;s involvement. For efficiency, the content of a cache line containing useless data is invalidated only when the line is referenced or is.about to be allocated for some new data. 
     One aspect of the present invention is an invalid page ID buffer. (IPIDB) containing the IDs of pages that have been invalidated (i.e. pages containing useless data). 
     Another aspect of this invention is a memory traffic saver device coupled with a write buffer. This device monitors a write buffer and uses the information from the invalid page ID buffer (IPIDB) to remove those entries from a write buffer that are associated with pages that have been invalidated (i.e. pages containing useless data) and not writing the data in those entries to main memory. 
     Another aspect of the present invention is a memory traffic saver device coupled with a cache controller. This device examines a set from which a cache line is about to be evicted and uses the information from the invalid page ID buffer (IPIDB) to evict those cache lines first that are associated with pages that have been invalidated (i.e. pages containing useless data). The content of evicted cache lines with useless data is discarded and not written to memory. 
     Another aspect of the present invention is a memory traffic saver device coupled with a coherence controller. This device examines requests received by a local coherence controller from a remote coherence controller for some data to be transmitted and uses the information from the invalid page ID buffer (IPIDB) to avoid transmitting to the requesting party the data from those cache lines that are associated with pages that have been invalidated (i.e. pages containing useless data) and, at the same time, invalidates those cache lines in a local cache. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a memory hierarchy in a typical computer system on which a preferred embodiment of the present invention operates. 
     FIG. 2 is a block diagram showing an Invalid Page ID Buffer (IPIDB) whose entries contain the identities (IDs) of some number of pages which have been invalidated (marked as containing useless data), and an apparatus controlling the buffer. 
     FIG. 3 is a block diagram showing a memory traffic saver apparatus and its interactions with a write buffer, a cache controller, a coherence controller, and an Invalid Page ID Buffer (IPIDB) through its buffer control. 
     FIG. 4 is a flow chart showing the logic of a memory traffic saver device coupled with a write buffer. 
     FIG. 5 is a flow chart showing the logic of a memory traffic saver device coupled with a cache controller. 
     FIG. 6 is a flow chart showing the logic of a memory traffic saver device coupled with a coherence controller. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 1 is a high-level block diagram showing a memory hierarchy in a typical multiprocessor computer system built of one ( 100 ) or more ( 102 ) computing nodes. Each node has one ( 104 ) or more processors ( 106 ) and some memory ( 126 ). Each processor has a CPU core ( 110 ). One ( 112 ) or more ( 116 ) levels of caches may be implemented. Caches are used to keep some recently and frequently referenced data locally (i.e. closer to the processor core). Caches are controlled by cache controllers ( 114 ). Caches ( 116 ) of different processors such as ( 104 ) and ( 106 ) are kept coherent by coherence controllers ( 120 ). Coherence controllers ( 120 ) are connected to a bus ( 122 ). 
     In addition, write buffers ( 118 ) may be implemented. In a system with multiple modes, nodes (e.g. ( 100 ) and ( 102 )) are connected to each other through internode coherence controllers ( 128 ) and some kind of interconnect ( 130 ). 
     The computer system shown in FIG. 1 illustrates the general architecture of a computer system to which this present invention is applicable but not limited to. It is understood that this invention applies to other architectures comprising a memory hierarchy (depicted in FIG. 1) as well as various controllers for attaching communication devices (e.g. terminals with keyboards, modems, networks, etc.), external storage devices (e.g. hard drives, CD-ROM drives, tape drives, flash memory cards, etc.), and other peripheral devices (printers, displays, etc.). 
     One aspect of the present invention is an invalid page ID buffer (IPIDB) (or simply a buffer) ( 200 ) (preferably in hardware) having a number of entries ( 202 ) and a buffer control ( 201 ). Each entry ( 202 ) in the buffer contains the identity of a page ( 204 ) (e.g. a physical page number and/or virtual page number) that has been invalidated (the content of such a page is useless). (In an alternate embodiment, in addition to a page ID, a buffer entry contains more information.) There exist several methods for indicating that the content of a page is useless and invalidating that page (e.g. the techniques proposed in) the above identified copending application Ser. No. 09/636,049 for “A Method and Apparatus For Efficient Virtual Memory Management. When a page is invalidated, an entry containing the identity of the corresponding page is passed ( 254 ) ( 260 ) to a buffer control ( 201 ) and is added ( 206 ) ( 240 ) to the buffer( 200 ). If all entries are full ( 220 ) (i.e. if no entry is available), one of the entries is removed ( 208 ) according to some policy (such as “first in, first out” or some other). (In an alternate embodiment, no entries are added once the buffer is full.) When a page whose identity is in a buffer becomes valid again, the corresponding entry is removed from a buffer and made available. This is accomplished via a Lookup-Remove ( 210 ) operation which attempts to find ( 244 ) an entry with page ID in question and if it is found ( 214 ), removes it ( 208 ). All entries in the buffer can be cleared (reset) ( 216 ) ( 246 ) when necessary. 
     In one embodiment, the buffer is memory mapped and is controlled with load and store instructions by a system software executing in a privileged mode. In another embodiment, the buffer is controlled by manipulating the content of special purpose registers. 
     In an alternate embodiment, other control signals are added to the buffer ( 200 ) and a buffer control ( 201 ). 
     In an alternate embodiment, more than one instance of a buffer ( 200 ) and a buffer control ( 201 ) can be implemented (e.g. to reduce contentions). 
     Another aspect of this invention is a memory traffic saver apparatus ( 302 ) (implemented preferably in hardware) which is connected to a buffer ( 200 ) via a buffer control ( 201 ). 
     In the preferred embodiment, a memory traffic saver apparatus ( 302 ) is coupled with a write buffer ( 118 ). The purpose of this apparatus is to observe the content of a write buffer ( 118 ) to detect whether a write buffer entry ( 306 ) (which contains the data copied from a modified cache line of a cache ( 116 )) to be written to memory, corresponds to a memory page ( 355 ) that has been invalidated. This is done whenever a new entry is added to a write buffer or a new entry is added to an invalid page ID buffer ( 400 ). A cache line ( 370 ) has a tag ( 324 ) associated with it. The tag along with a cache line index are transferred into a write buffer entry ( 306 ) when a cache line ( 370 ) is evicted from a cache ( 116 ). 
     The values of a tag ( 310 ) and an index ( 311 ) in a write buffer entry ( 306 ) are used to compute the address that the data will be written to. Similarly, they are used to compute ( 402 ) the identity of the page that the data will be written to. The apparatus ( 302 ) uses the computed identity of a page. (i.e. page ID) to try to find ( 230 ) an entry with the same page ID ( 254 ) in a buffer ( 200 ) in order to determine ( 404 ) whether that page has been invalidated. 
     If this is the case and such an entry is found ( 248 ), the data from such a write buffer entry ( 306 ) will not be written to main memory (and removed from a write buffer ( 118 )) ( 406 ). Otherwise, that write buffer entry ( 306 ) is written to a main memory page ( 355 ) as usual ( 408 ). 
     In the preferred embodiment, a memory traffic saver apparatus ( 302 ) is also coupled with a cache controller ( 114 ) managing a set associative cache ( 116 ) (i.e. a cache with several cache lines in a set). (A direct mapped cache is one-way set associative cache with only one line in a set.) On a cache miss ( 500 ), the apparatus ( 302 ) examines tags ( 324 ) of a set into which the new data will be placed. 
     A page identity is computed ( 502 ) from a cache line tag ( 324 ) and a cache set index. The apparatus ( 302 )uses the computed identity of a page (i.e. page ID) to try to find ( 230 ) an entry with the same page ID ( 254 ) in a buffer ( 200 ) in order to determine ( 504 ) whether a cache line is associated with a page that has been invalidated. 
     If one of the lines in a set is indeed associated with a page that has been invalidated (which is indicated by ( 248 )), such a line is immediately allocated for the new data (and its content is discarded even if it is in a modified state and not passed to a write buffer ( 118 ) and, hence, not written to memory) ( 506 ). The line containing useless data is allocated for the new data and the access history is updated (e.g. the line where the new data will be placed is marked as the most recently used) ( 508 ). If no such line is found, a standard replacement algorithm (e.g. the least recently used) is employed to find a cache line to be evicted and then allocated for the new data ( 510 ); then, the access history,is updated as described in the prior art ( 512 ). 
     In the preferred embodiment, a memory traffic saver apparatus ( 302 ) is also coupled with a cache coherence controller ( 120 ) managing a cache ( 116 ). In response to a request received by a local coherence controller ( 120 ) for some data to be transmitted to a remote coherence controller (e.g. this situation may arise as a result of Bus-Read or Bus-Read-Exclusive transactions in a multiprocessor system with the MESI protocol), the coherence controller ( 120 ) verifies whether the data in question is in a cache ( 116 ). If the data if found (i.e. on a cache hit ( 600 )), the apparatus ( 302 ) examines the value of the tag ( 324 ) of the cache line that contains the data. 
     A page identity is computed ( 602 ) from the values of a cache line tag ( 324 ) and a cache line index. The memory traffic saver apparatus ( 302 ) uses the computed identity of a page (i.e. page ID) to try to find ( 230 ) an entry with the same page ID ( 254 ) in a buffer ( 200 ) in order to determine ( 604 ) whether a requested cache line is associated with a page that has been invalidated (i.e. a page whose content is useless). 
     If the requested cache line is indeed associated with a page that has been invalidated (which is indicated by ( 248 )), such a line is immediately invalidated in a local cache and the data from that line are not sent (across the bus ( 122 ) or interconnect ( 130 ) to the processor requesting the data (e.g. the processor performing the initialization of that page,and hereby requesting cached data from that page be transmitted to it) ( 606 ). The requesting processor is notified that the requested data does not exist in a local cache ( 608 ). In the preferred embodiment, no explicit reply is sent to a requesting processor which, after some period of time, assumes that the data it needs cannot be found in caches of other processors. In an alternate embodiment, an explicit reply indicating that the requested data is not cached is sent to a requesting processor. 
     On the other hand, if the requested cache line is not associated with a page that has been invalidated, the request is processed and the data are sent to the requester as described in the prior art ( 610 ). 
     It is understood that the method for reducing the traffic between a cache and main memory (as described above) can also be used to reduce traffic between caches in a multi-level cache hierarchy e.g. L 1  ( 112 ) and L 2  ( 116 ) caches and, possibly, a write buffer between them). 
     It is also understood that one or more memory traffic saver devices mentioned above can be implemented in a system. A memory traffic saver device does not have to be coupled with all of the following devices: a write buffer, a cache controller, a coherence controller. It can be coupled with only a subset of them. 
     In addition, the buffer and a memory traffic saver device can be made multi-ported to perform more than one lookup at a time. 
     In an alternate embodiment, the entire cache is scanned periodically (or whenever a new entry is added to an invalid page ID buffer) and the content of a cache line containing useless data is invalidated immediately without waiting for that line to be referenced or allocated for some new data. 
     While it is apparent that the invention herein disclosed is well calculated to fulfill the objects stated above, it will be appreciated that numerous modifications and embodiments may be devised by those skilled in the art, and it, is intended that the appended claims cover all such modifications and embodiments as fall within the true spirit and scope of the present invention.