System for combining requests associated with one or more memory locations that are collectively associated with a single cache line to furnish a single memory operation

[0002] The invention relates to reducing bus loading due to snoop traffic.

[0003] Referring to FIG. 1, a typical computer system 10 may include a level one (L1) cache 14 to expedite transactions between a microprocessor 16 and a system memory 18, such as a dynamic random access (DRAM) memory. To accomplish this, the cache 14 typically includes a static random access memory (SRAM) that typically is more expensive and faster than the system memory 18. Usually, the cache 14 retains a copy of data in the most recently accessed (by the microprocessor 16) memory locations to make these locations “cached locations.” In this manner, when the microprocessor 16 executes a memory read operation, for example, to retrieve data from one of the cached locations, the cache 14, instead of the system memory 18, provides the data to the microprocessor 16. As a result, the read operation is accomplished in less time than if the data is retrieved from the slower system memory 18. Because of the cache 14, memory write operations by the microprocessor 16 may also be accomplished in less time, as the data may be stored in the cache 14 instead of in the system memory 18. The cache 14 typically is integrated with the microprocessor 16 and may be accessed by devices other than the microprocessor 16 via a local bus 22 that is coupled to the microprocessor 16.

[0004] Because devices other than the microprocessor 16 typically interact with the system memory 18, measures typically are in place to preserve coherency between data stored in the cache 14 and data stored in the system memory 18. For example, a bridge 23 may furnish a memory write operation to a cached location. In short, the cache 14 may implement a variety of different protocols to preserve data coherency.

[0005] For example, for a “write-through” protocol, the write operation furnished by the bridge 23 in the above example causes the cache 14 to invalidate a corresponding cache line in the cache 14. A cache line typically includes several bytes of data that are associated with contiguous memory locations. When the microprocessor 16 executes a memory write operation that targets a memory location that is associated with a cache line, then a “write hit” occurs. In general, to determine when a cache hit (i.e., a write or read (described below) hit) occurs, a bus operation called “snooping” occurs on the local bus 22. In response to this write hit, the cache 14 updates the corresponding cache line and the corresponding locations in the system memory 18 pursuant to the write-through policy. However, when a device other than the microprocessor 16 writes to a memory location that is associated with the cache line, then the cache 14 invalidates the cache line, as at least some of the data of the cache line has become “stale.” Read operations are handled in a slightly different manner. When the microprocessor 16 executes a memory read operation, the cache 14 determines if a “read hit” occurs. A read hit occurs if the read operation targets a memory location that is associated with a cache line that has not been invalidated. When a read hit occurs, the cache 14 (and not the slower system memory 18) provides the requested data. Otherwise, the system memory 18 provides the requested data.

[0006] The cache 14 may alternatively implement a “write-back” policy that improves the performance of memory write operations (versus the “write-through” policy described above) by eliminating the slower writes to system memory 18 every time the cache 14 is updated. Instead, the system memory 18 is updated when coherency problems arise. In this manner, when the microprocessor 16 writes data to a memory location associated with a cache line, a write hit occurs, and in response to this occurrence, the cache 14 updates the corresponding cache line without updating the system memory 18. When a device other than the microprocessor 16 performs a memory write operation to a memory location that is associated with the cache line, then the cache 14 does not invalidate the associated cache line, as some of the data in the cache line may have been modified by the microprocessor 16. Instead, the cache 14 halts, or “backs off,” the memory write operation and updates the memory locations in the system memory 18 that are associated with the cache line. After the system memory 18 is updated, the cache 14 permits the original write operation to proceed. For the write-back policy, a similar scenario occurs when a device other than the microprocessor 16 performs a read operation to read data from the system memory 18.

[0007] The memory write operations that are furnished by the bridge 23 may be, for example, in response to a stream of data that is produced by video camera 12. In this manner, the video camera 12 may continually provide signals indicative of frames of data to a serial bus 11 that is coupled to the bridge 23. In response, the bridge 23, in turn, may generate numerous write operations to store the data in predetermined contiguous regions of the system memory 18 where the data may be processed (decompressed, for example) by the microprocessor 16 before corresponding video images are formed on a display 20.

[0008] Unfortunately, the numerous write operations that are furnished by the bridge 23 may cause an extensive number of snooping operations on the local bus 22. The snooping operations, in turn, may consume a considerable amount of bandwidth of the local bus 22. As a result, the processing bandwidth of the microprocessor 16 may be effectively reduced.

[0009] Thus, there is a continuing need for a computer system to more efficiently handle a stream of data.

[0010] In one embodiment, a method for use with a computer system includes receiving requests to store data in one or more memory locations that are collectively associated with a cache line. The requests are combined to furnish a memory operation.

[0011] FIG. 1 is a schematic diagram of a computer system of the prior art.

[0012] FIG. 2 is a schematic diagram of a bridge according to an embodiment of the invention.

[0013] FIG. 3 is a schematic diagram of a computer system according to an embodiment of the invention.

[0014] FIG. 4 is a schematic diagram of a queue of the bridge of FIG. 2.

[0015] FIGS. 5 and 6 are state diagrams illustrating operations of logic of the queue of FIG. 4.

[0016] Referring to FIG. 2, an embodiment 84 of a bridge in accordance with the invention includes a transaction queue 44 with features to efficiently handle a stream of data that is received by the bridge 84. In particular, a hub link interface 38 of the bridge 84 may receive requests (read and/or write requests, as examples) that are attributable to a stream of incoming data, such as a stream of video data that originates with a camera or with a block oriented device (a hard disk drive, for example), as examples. Each request indicates information (memory locations, or addresses, for example) that may be used by a memory interface 30 to generate a memory operation (a write operation or a read operation, for example) on a memory bus 86. In this manner, each memory operation may cause a host interface 34 to execute a snoop operation on a local bus 85 to determine if a possible hit occurs with a level one (L1) cache 81 (see FIG. 3) (or a level two (L2) cache, as another example), and thus, numerous write operations may consume excessive bandwidth of the local bus 85. However, the queue 44 is adapted to minimize the number of memory operations that are attributable to the stream of data.

[0017] In particular, the queue 44 receives incoming requests and is adapted to combine multiple requests that are directed to memory locations that are associated with the same cache line to form a single request. As an example, the bridge 84 may receive eight, four byte write requests that all target memory locations that are associated with the same cache line. The write requests may be attributable to an incoming stream of video data, for example. Instead of causing the memory interface 30 to generate eight separate write operations in response to these requests (i.e., the conventional response), the queue 44 may, in some embodiments, combine the write requests into a single write request, an action which causes the memory interface 30 to generate one write operation (a block write operation, for example) to transfer all 32 bytes into a system memory 88 (see FIG. 3). Therefore, one snooping operation (instead of eight snooping operations) occurs. As a result, the processing bandwidth of a computer system 80 (see FIG. 3) that uses the bridge 84 may be enhanced.

[0018] Although the description refers to combining requests that are directed to a single cache line, the same principles apply to multiple cache lines. In this manner, the queue 44, in some embodiments, combines the requests that are directed to multiple cache lines. However, for purposes of clarity, only a single cache line is described with the understanding that the principles described in this application may extend to multiple cache lines.

[0019] In some embodiments, the queue 44 stores requests before the requests are passed to host interface 34. The bridge 84 may include other queues 40, 46 and 48 that are associated with the hub link interface 38, the memory interface 30 and an Accelerated Graphics Port (AGP) interface 32, respectively.

[0020] In some embodiments, the queue 44 may implement a first-in-first-out (FIFO) memory. In this manner, as each request propagates to the top of the FIFO memory, the request becomes available to the memory interface 30. Once available, the memory interface 30 may convert the request into the appropriate operation, such as a memory write operation, for example.

[0021] Referring to FIG. 3, in some embodiments, the bridge 84 may be a memory hub that is part of the computer system 80. In this context, the term “computer system” may refer to any system that includes a microprocessor, such as (but not limited to) a desktop computer or a laptop computer.

[0022] In some embodiments, the L1 cache 81 may be part of a microprocessor 82 (an X86 microprocessor, a Pentium® microprocessor or a microcontroller, as examples) that communicates with the rest of the computer system 80 via the local bus 85 and the bridge 84. In some embodiments, the computer system 80 may include multiple microprocessors that are also coupled to the local bus 85. The computer system 80 may include a video camera 89 that is coupled to another bridge, or input/output (I/O) hub 96, and the video camera 89 may furnish a stream of data that the I/O hub 96 converts into requests (write requests and/or read requests, as examples). In this manner, the video camera 89 may furnish a stream of video data to a serial bus 95. The serial bus 95, in turn, may propagate signals that indicate the stream to the I/O hub 96. The I/O hub 96 may forward the requests to the memory hub 84 via a hub link 91.

[0023] The bridge 84 may also be coupled to a memory bus 86, an AGP bus 90, a cache 83 and the hub link 91. The AGP is further described in detail in the Accelerated Graphics Port Interface Specification, Revision 1.0, published on Jul. 31, 1996 by Intel Corporation of Santa Clara, Calif. The bridge 84 may be coupled to the microprocessor(s) 82 via a host bus 85. A graphics accelerator 92 may be coupled to the AGP bus 90 and control a display 94 that, for example, displays images that are captured by the video camera 89. The system memory 88 may be coupled to a memory bus 86. The memory bus 86, the host bus 85, the AGP bus 90 and the cache 83 may be coupled to the memory interface 30, the host interface 34, the AGP interface 32, and a cache interface 36, respectively.

[0024] In some embodiments, the I/O hub 96 may provide interfaces to an I/O expansion bus 100 and a Peripheral Component Interconnect (PCI) bus 102, as examples. The PCI Specification is available from The PCI Special Interest Group, Portland, Oreg. 97214. Furthermore, the I/O hub 96 may provide interfaces to a hard disk drive 114 and a CD-ROM drive 112, as examples. The hard disk drive 114, or any other block oriented device, may, for example, produce requests that are handled by the queue 44, as described in this application. An I/O controller 98 may be coupled to the I/O expansion bus 100 and may control operations of a floppy drive 108. The I/O controller 98 may also receive input signals from a mouse 106 and a keyboard 104, as examples.

[0025] The above-described computer system is an exemplary system, and combinations of the above-described components may be integrated separately or fabricated together on the same die. Other computer systems are within the scope of the appended claims.

[0026] In the following description, writes requests may be specifically discussed. However, these types of requests illustrate features of some embodiments and should not be considered limiting. For example, the bridge 84 may handle read requests in a similar manner. The bridge 84 may also handle speculative prefetches on read, as described below.

[0027] Referring to FIG. 4, in some embodiments, the queue 44 may include a request FIFO memory 102 that may receive requests, such as write requests, from the hub link interface 38. In this manner, each deferred write request propagates from the bottom of the FIFO memory 102 in a first-in-first-out manner through the FIFO memory 102 until the request reaches the top of the FIFO memory 102 and becomes available to an interface, such as the memory interface 30, if the request is not reordered by inbound logic 106. As described below, the inbound logic 106 maintains a pointer to place an incoming request (a write request, as an example) in the FIFO memory 102 to be later removed and transferred to the memory interface 30.

[0028] As an example, for an incoming write request that targets a memory location, the inbound logic 106 may additionally determine if the request targets the same cache line as a deferred write request that is stored in the FIFO memory 102. If so, the inbound logic 106 may then combine the two write requests, as described below. In some embodiments, in response to one or more incoming write requests, the inbound logic 106 may further perform a speculative read operation to read one or more cache lines from the device that generated the write requests in an effort to further reduce the number of memory write operations and snooping of the local bus 85.

[0029] When the queue 44 receives each incoming request from the hub link interface 38, the inbound logic 106 determines if a request that is stored in the FIFO memory 102 targets memory locations associated with the same cache line. If so, the inbound logic 106 takes appropriate action to combine the requests. For example, the inbound logic 106 may combine two write requests or combine two read requests. In this combination, the inbound logic 106 may append the data and byte enable signals associated with the requests and may change the commands associated with the requests, such as changing a particular write command into a block write command, for example.

[0030] In some embodiments, the queue 40 may include outbound logic 104 that maintains a pointer for indicating the next request that is to be transferred from the FIFO memory 102 and into the appropriate interface. In this manner, in some embodiments, the outbound logic 104 traverses the memory locations (called slots) of the FIFO memory 102 in a circular, or “round robin,” fashion.

[0031] Besides the FIFO memory 102, the queue 44 may also include a data memory 100 that stores data for the associated requests that are stored in the FIFO memory 102. In this manner, each deferred request stored in the memory 102 may indicate an address, a command and a pointer that points to a portion of the data memory 100 that is associated with the request.

[0032] Referring to FIG. 5, in some embodiments, the inbound logic 106 may behave in the following manner. In the following description, the term “incoming request” generally refers to the most recent request that is received by the queue 44. In an IDLE state, the inbound logic 106 waits as the host interface 34 processes the request at the top of the FIFO memory 102 by snooping the cache 81. In this manner, if the snooped cache line(s) are valid, the host interface 34 may retrieve the cache line(s) and modify them in accordance with the request at the top of the FIFO memory 102. Next, the memory interface 30 may perform a memory operation to execute the request.

[0033] Subsequently, for incoming write requests, the inbound logic 106 may transition to a speculative read state called READ. In the READ state, the inbound logic 106 may interact with the hub link interface 38 to read one or more cache lines of data from the device that produced the incoming request. In this manner, the read cache line(s) include data from the incoming request and are based on the assumption that the device will furnish additional write requests that are associated with the entire cache line. Thus, as a result of this read ahead technique, the number of snoop operations that would otherwise occur on the local bus 85 are reduced. The speculative read feature of the bridge 84 may be configured (via configuration registers), for example, by driver software, such as driver software that is associated with block oriented devices (disk drives), for example.

[0034] The inbound logic 106 transitions either from the IDLE state or the READ state to a CHECK state in which the inbound logic 106 traverses the slots of the FIFO memory 102 in search of an empty slot. In some embodiments, the inbound logic 106 traverses the slots in a circular fashion and remains in the CHECK state until all slots have been checked. If during this check, the inbound logic 106 determines that the incoming request and one of the requests stored in the FIFO memory 120 target the same cache line, then the inbound logic 106 transitions to a COMBINE state.

[0035] In the COMBINE state, in some embodiments, the inbound logic 106 may combine the stored request with the incoming request by replacing the original stored deferred request with a new request that indicates the information in both the incoming and the original requests. Once the inbound logic 106 performs the combination, the inbound logic 106 transitions back to the IDLE state. If no match occurs during the CHECK state, the inbound logic 106 transitions to an IN state in which the inbound logic 106 stores the incoming deferred request in the next available slot. Afterwards, the inbound logic 106 transitions back to the IDLE state.

[0036] Referring to FIG. 6, in some embodiments, the outbound logic 104 may include at least two states: a IDLE state and an OUT state. The outbound logic 104 may enter the IDLE state when the computer system 80 comes out of a reset, such as after powerup of the computer system 80, for example. The outbound logic 104 transitions from the IDLE state to the OUT state when an interface of the bridge, such as the memory interface 30, requests the next request from the queue 44. The outbound logic 104 remains in the OUT state until the request is furnished to the requesting interface, and afterwards, the outbound logic 104 transitions back to the IDLE state.

[0037] Other embodiments are within the scope of the following claims. For example, the phrase “combining requests” refers generally to linking requests together to reduce the number of memory operations that would otherwise occur, and the combination may occur without reducing the number of requests that are otherwise stored in the queue 44. Therefore, in some embodiments, two or more requests that target memory locations that are associated with the same cache line may be stored in the FIFO memory 102. In this manner, in some embodiments, each request may indicate a tag that indicates whether the request should be combined with another request that is stored in the FIFO memory 102. In some embodiments, the inbound logic 106 may associate the appropriate tag with each incoming request before allowing the request to be stored in the FIFO memory 102.

[0038] While the invention has been disclosed 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 the invention.