Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output command process
Reexamination Certificate
2000-06-02
2003-06-17
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output command process
C710S054000, C710S112000, C711S001000, C711S100000
Reexamination Certificate
active
06581111
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This application relates to maintaining cache coherency in a computer system and more particularly to utilization of probe responses.
2. Description of the Related Art
In current processor implementations, a processor issues requests to a memory controller for such transactions as, e.g., read or write commands, or probe responses. In one implementation for a stand-alone processor, a command channel is provided over which the processor issues requests to another integrated circuit incorporating the memory controller. In such systems, data may be transmitted to and from the processor over a data channel that is separate from the command channel. In a typical computer system incorporating such a processor, an integrated circuit interfaces to the processor to provide both a memory control function and a bridge function between the host bus (the command and data channel) and other system buses. One of the bridge functions typically provided is a bridge between the host bus and a Peripheral Component Interconnect (PCI) bus. Such integrated circuits have been described in the art as “north bridges”.
One of the functions performed by memory controller logic on a north bridge is to probe the cache memory located on the processor in order to maintain coherence between the various memory components when another device, e.g., an I/O device on the PCI bus, accesses memory. The probe determines whether the cache memory on the processor has a copy of the memory location (typically a cache line containing that memory location) about to be accessed by the I/O device. The processor responds through the command channel with a probe response indicating whether or not that particular cache line is located in the cache memory and its status.
In general, system requests from the processor can be handled in-order by a north bridge with, e.g., a single request FIFO buffer that stores the received requests and issues the requests in the order received. That applies even to systems that handle speculatively pipelined requests. The in-order approach allows designers to implement a simple and inexpensive design. However, when another bus master, e.g., another integrated circuit on an input/output bus such as the Peripheral Component Interconnect (PCI) bus, accesses system memory resulting in probe traffic to the processor, such probe traffic requires immediate attention to avoid a system deadlock or stall condition.
That deadlock situation can occur when, for example, a PCI input/output (I/O) command cycle targeted at a device on the PCI bus (e.g. a south bridge integrated circuit providing interfaces to other I/O devices and legacy functions) is at the top of the request FIFO (also referred to as the command queue) and the south bridge is granted the PCI bus for a bus mastering cycle to main memory for a direct memory access (DMA) transfer. Many PCI bus masters, once they start a master cycle cannot be interrupted until the cycle completes, even if backed-off the bus. So, if a probe response is handled in-order like all other commands, the north bridge can lock because the I/O cycle at the top of the command queue will never complete because the south bridge cannot handle the I/O cycle until its DMA cycle completes. But its DMA cycle cannot complete until the probe response is processed. If the probe response is stuck in the command queue behind the PCI I/O command, the deadlock situation has occurred.
Thus, probe traffic requires attention at a higher priority than other types of traffic. One way to provide a higher priority for probe traffic is to provide the capability for out-of-order processing for all requests. However, that approach can be very complex resulting in additional logic as well as additional design and validation time.
It would be desirable to solve the need for out-of-order processing of probe responses to avoid deadlock situations while maintaining the benefits of the simplicity of in-order execution.
SUMMARY OF THE INVENTION
Accordingly, a combination in-order and out-of-order implementation is utilized that provides the simplicity of in-order design but also the capability of executing probe responses ahead of normal commands.
In one embodiment, the invention provides a method of processing commands that includes receiving commands into an integrated circuit and determining when one of the received commands is a probe response. If it is, the probe response is stored in a location other than a command queue. Others types of processor-to-system commands are stored into the command queue, which is implemented for simplicity as a first-in, first out (FIFO) structure. Thus, the commands in the command queue are removed from the command queue for processing in-order. A probe response, on the other hand, is processed out-of-order ahead of commands previously received and stored in the command queue. Data movements associated with a memory modifying command awaiting execution in the command queue affecting the cache line that is subject of the probe response are also handled out-of-order. The memory modifying command is discarded when it is removed in-order from the command queue.
In another embodiment the invention provides an integrated circuit that includes a plurality of receive elements coupled to receive processor requests, including command information. A command filter circuit, coupled to the receive elements, is responsive to the command information to selectively forward the received requests. A command queue is coupled to the command filter circuit to store the forwarded received requests. The command queue is unloaded for processing in a command interpreter in a first in first out (FIFO) order. The command filter is responsive to a received probe response to forward the probe response to a storage location other than the command queue. The received probe response is processed by the command interpreter ahead of requests previously stored in the command queue.
REFERENCES:
patent: 5544051 (1996-08-01), Senn et al.
patent: 5931920 (1999-08-01), Ghaffari et al.
patent: 6088740 (2000-07-01), Ghaffari et al.
patent: 6112265 (2000-08-01), Harriman et al.
patent: 6275905 (2001-08-01), Keller et al.
patent: 6370621 (2002-04-01), Keller
patent: 6393529 (2002-05-01), Keller
AMD Athlon™ Processor Technical Brief, Publication No. 22054, Dec. 1999, pp. 1-7.
AMD Athlon™ Processor Data Sheet, Publication No. 21016-D, Aug., 1999, pp. 1-58.
Lakhanpal Sanjiv K.
Nicol Mark D.
Pandya Chandrakant
Pencis Jennifer
Advanced Micro Devices , Inc.
Gaffin Jeffrey
Mai Rijue
Zagorin O'Brien & Graham LLP
LandOfFree
Out-of-order probing in an in-order system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Out-of-order probing in an in-order system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Out-of-order probing in an in-order system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3151044