1. Field of the Invention
This invention relates generally to an improvement in cache memory management, and more specifically to tracking flushes of cache entries in a cache memory bridging a coherent memory domain (e.g., a data processing system) and non-coherent memory domain (e.g., input/output (I/O) devices).
2. Description of the Prior Art
Many data processing systems (e.g., computer systems, programmable electronic systems, telecommunication switching systems, control systems, and so forth) use one or more I/O devices for data transfers. Typically, an I/O bridge host (also called a primary hub), and multiple I/O bridge guests are connected in a hierarchy to facilitate data transfers between the data processing system and the I/O devices. The I/O bridge host is connected to the I/O bridge guests, which are connected to the I/O controllers, which are connected to the I/O devices.
FIG. 1 illustrates a typical prior art data processing system 100 that includes central processing unit (CPU) 102 connected by a common bus to main memory 104, and I/O bridge host 106. I/O bridge host 106 is connected to I/O bridge guests 108, 110, 112, and 114. I/O bridge guest 108 is connected to I/O devices 116 and 118. I/O bridge guest 110 is connected to I/O device 120. I/O bridge guest 112 is connected to I/O devices 122 and 124. I/O bridge guest 114 is connected to I/O device 126. The I/O controllers are not shown, but they are frequently incorporated in the I/O devices.
Many data processing systems use a cache memory (cache) in the I/O bridge host to improve the speed of communication with the I/O bridge guests (and ultimately the I/O devices). The cache management of the cache entries in the cache in the I/O bridge host is complex. One reason for this complexity is that the I/O bridge host and the cache are usually designed to be in the coherent memory domain (i.e., the location of the most up-to-date version of each cache entry is always identified), while the I/O devices are usually in the non-coherent memory domain.
One prior art solution for tracking the point in time to flush a cache entry (i.e., send data back to main memory or give up ownership of the cache entry) involves sending a cache entry address and a cache entry from the I/O bridge host to the I/O device. When the cache entry can be flushed, a message containing the cache entry address is sent back to the I/O bridge host from the I/O bridge guest. However, this prior art solution requires considerable bandwidth, and/or a large number of circuit packaging pins for communicating the cache entry address.
FIG. 2 illustrates such a prior art data processing system 200 which includes an I/O bridge host 106 that contains I/O control logic 202, I/O cache 204, and interface logic 206. I/O cache control logic 202 receives a cache entry address 220 and a flush command 230 from memory. I/O cache control logic 202 provides a cache entry address 210 to I/O cache 204 and interface logic 206. I/O cache 204 provides cache data 212 to interface logic 206. Interface logic 206 outputs cache entry address 210 and cache data 212 to interface logic 208 for the I/O bridge guest 108. I/O bridge guest 108 outputs cache data 212 to I/O device 116, and outputs cache entry address 210 and a flush signal 214 to I/O cache control logic 202. This requires considerable bandwidth, and a large number of circuit packaging pins for communicating the cache entry address, unless the I/O bridge host and I/O bridge guest are on the same integrated circuit chip or module.
A second prior art solution for tracking the time to flush cache entries in a cache in an I/O bridge host is to store cache entry addresses in a flush-cache-entry first-in-first-out (FIFO) memory. When an I/O device reads the last byte of a cache entry, it sends a message indicating that the I/O bridge host can flush the cache entry. When an I/O device sends a message to the I/O bridge host to flush the cache entry, the cache flushes the cache entry to main memory in the data processing system. The FIFO must be large enough to accommodate the maximum number of cache entries being transferred between the data processing system and the I/O device at a given point of time.
FIG. 3 illustrates one configuration of a prior art data processing system 300 that includes an I/O bridge host 106 containing I/O cache 204, which is connected by a common bus to interface logic and flush cache-entry-address (CEA) FIFOs 306, 308, 310, and 312. Flush CEA FIFO 306 is connected to I/O bridge guest 108. Flush CEA FIFO 308 is connected to I/O bridge guest 110. Flush CEA FIFO 310 is connected to 110 bridge guest 112. Flush CEA FIFO 312 is connected to I/O bridge guest 114.
FIG. 4 illustrates a prior art data processing system 400 in more detail that includes an I/O bridge host 106 that contains I/O cache control logic 402, I/O cache 204, and interface logic 306. I/O cache control logic 402 receives a cache entry address 220 and a flush command 230 from memory. I/O cache control logic 402 provides a cache entry address 210 to I/O cache 204 and to Flush CEA FIFO 406 (henceforth simply referred to as CEA FIFO 406) in interface logic 306. I/O cache 204 provides cache data 212 to interface logic 306. Interface logic 306 outputs cache data 212 to interface logic 404 for the I/O bridge guest 108. Interface logic 404 outputs flush signal 214 to I/O cache control logic 402 and CEA FIFO 406. I/O bridge guest 108 outputs cache data 212 to an I/O device (not shown).
The problem with this second prior art solution is that it does not take into account the fact that the cache could be required to flush or choose to flush the cache entry for other reasons, such as during the operation of a cache snoop algorithm or a cache replacement algorithm. The cache may re-use the cache entry for some other data. When the original I/O device sends a flush message, the cache controller will flush the new data. Because the cache is part of a coherent memory domain (i.e., architecture), this behavior does not cause data corruption, but it can cause performance degradation, because the data may need to be re-fetched (e.g., from main memory) for the second request that is being serviced by the cache.
It would be desirable to prevent the flushing of a re-allocated cache entry by keeping track of the flush status of the cache entry by using the CEA FIFO, and still maintain the order of the cache entries for the I/O responses. This avoids the cache tossing out new data destined for a different I/O device than the I/O device issuing the flush, and thereby prevents performance degradation caused by additional flush and re-request transactions for the cache.
An object of the invention is to prevent the flushing of a re-allocated cache entry by keeping track of the flush status of the cache entry by using the CEA FIFO, and still maintain the order of the cache entries for the I/O responses.
A first aspect of the invention is directed to a method for tracking at least one cache entry in a cache serving data transfers between a coherent memory domain and a non-coherent memory domain in a data processing system, including steps of storing an address corresponding to at least one cache entry in a plurality of memory cells, using at least one memory cell as a valid flag to indicate when at least one cache entry is still in the cache, and changing the valid flag based on one or more signals transmitted from the non-coherent memory domain.
A second aspect of the invention is directed to a data processing system or an I/O bridge host, having a cache and at least one cache entry, serving data transfers between a coherent memory domain and a non-coherent memory domain, including a plurality of memory cells, wherein the plurality of memory cells are configured to store an address corresponding to the cache entry, at least one memory cell, wherein the memory cell is configured as a valid flag to indicate when the cache entry is still in the cache, and the valid flag can be changed based on one or more signals transmitted from the non-coherent memory domain.
These and other objects and advantages of the invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.
USPTO Backgrounds
USPTO Backgrounds