Electrical computers and digital processing systems: support – Clock control of data processing system – component – or data...
Reexamination Certificate
2001-06-05
2003-12-09
Lee, Thomas (Department: 2185)
Electrical computers and digital processing systems: support
Clock control of data processing system, component, or data...
C710S110000, C710S241000
Reexamination Certificate
active
06662306
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a new method and apparatus for flow control in a packet-switched microprocessor-based computer system (uniprocessor), a network of such computer systems, or a multiprocessor system. In particular, it relates to a new flow control design which provides efficient packet-switched control in a multiprocessor architecture, where slave requests from a processor to a slave on its local address bus are particularly efficiently processed.
The system in one embodiment is based upon that described in applicant's U.S. Pat. No. 5,907,485, “Method and Apparatus for Flow Control in a Packet-Switched Computer System” by Van Loo et al., filed Mar. 31, 1995, which is incorporated herein by reference.
The '485 patent presents solutions to many disadvantages found in prior systems by providing a new system for packet-switched flow control without negative feedback, handshakes, and other disadvantages as discussed therein. It presents an opportunity for further improvement and efficiency, however, in that in a multiprocessor environment, processor requests are for-warded to all the system controllers on the system, even those that are intended for a local slave, i.e. one on the sending processor's local address bus.
Thus, a need is presented for an improvement to the system of the '485 patent that increases the processing efficiency of processor requests sent to local slave devices.
SUMMARY OF THE INVENTION
The present invention employs a method and apparatus for centralizing the flow control decisions in a new system controller, which acts in conjunction with input and output queues of the masters and slaves in the system. The system controller determines the total queue sizes of all the queues in the system at initialization time, and permits a master (e.g. a processor) to send a number of transaction requests only to the extent of that total. The system of the invention classifies system interconnect queues as request queues, read-data queues, and write-data queues, and determines rules of transfer of both requests and data as loosely coupled events. An interconnect (system) controller is connected between one or more masters (e.g. microprocessors) and the slave devices, which may be I/O units, disk drives, memory, etc. The interconnect controller includes a queue for each master, and each master includes a transaction counter indicating the number of outstanding transaction requests from that master to the controller. The interconnect controller additionally includes both request and write data queues for each downstream slave, and a transaction counter indicating the number of outstanding requests from the controller to that slave and the outstanding write data transfers from some master to that slave.
The masters and the controller are prevented from issuing any transaction requests (or to initiate a write-data transfer requests) downstream when the respective counter indicates that the corresponding request or data queue downstream is full. When a transaction is complete (e.g. upon the receipt of requested data read or consumption of write data by the slave), the relevant counter is decremented to indicate the availability of a place in the transaction queue or write-data queue.
Queue overflow and congestion conditions are thus avoided by prohibiting the master or system controller from sending more transactions or data than the recipient has space for. A hardware handshake is used both to signal completion of a data transfer and to notify the master of one more available space in the downstream queue. The handshake is thus not an unsolicited signal, as in a credits-based scheme, and the signals are not based upon dynamic congestion.
The maximum queue sizes in the system are determined at initialization, and thus are known before execution of any applications by the master(s). The masters and controller thus have at all times information on the number of available spots in the queue immediately downstream—to be contrasted with a credits-based scheme, where the maximum queue sizes are not known a priori, and the sender can only keep track of the credits issued to it. The initialization sequence is software-driven (e.g. by a boot PROM), and the queue sizes and depths are determined by this sequence, which provides adaptability of the system to reconfigure it for different slaves (having different queue sizes) or to configure out nonfunctioning queue elements.
The elimination of (advance or overflow) feedback signals in the present flow control system reduces the interface latency, since there is no extra handshake, no rescheduling or rearbitrating for resources, and no retries by the master. Hence a simpler design is usable, which is easily scalable according to the number of processors, and the slave queues can be downsized as desired for price/performance considerations and desired bandwidth, without fear of losing any transactions due to smaller queue sizes. Furthermore, a variety of systems ranging from small/inexpensive to large/expensive can be designed from the same modular CPU and I/O interfaces by simply down- or up-scaling (sizing) the respective queues and buffers in the interconnect, as desired. Since the interconnect controller is custom-designed to accommodate a given set of masters and slaves with a given range of queue sizes, the masters and slaves needn't be redesigned at all. Because the system controller is relatively inexpensive, a number of different controller designs can be utilized without appreciably raising the cost of the system—which would not be the case if the processors and slave devices needed modification.
The overall system design and effort required to test and validate correct system behavior under saturation conditions (when flow control is important) is also greatly simplified.
This packet-switched mechanism, which heretofore is the same as that described in applicant's '485 patent (hereinafter referred to as the basic packet-switched system), is in the present invention enhanced such that transaction requests from a processor to a slave on the same address bus as the local system controller are automatically forwarded to the intended slave immediately. The system controller determines whether the proper criteria are met for that slave to receive such a request, such as that the slave's request receive queue is not full and that global ordering requirements are met, and if so then on a separately provided line connected to the slave validates the request for immediate reception by the slave. This saves several clock cycles over the basic packet-switched flow control system, in which the system controller otherwise has to consider the validity of the request, then request arbitration of the address bus to transmit the transaction request.
REFERENCES:
patent: 4459665 (1984-07-01), Miu et al.
patent: 4987529 (1991-01-01), Craft et al.
patent: 5168570 (1992-12-01), Eckert et al.
patent: 5210858 (1993-05-01), Jensen et al.
patent: 5269006 (1993-12-01), Dohse et al.
patent: 5303391 (1994-04-01), Simcoe et al.
patent: 5388232 (1995-02-01), Sullivan et al.
patent: 5396602 (1995-03-01), Amini et al.
patent: 5404137 (1995-04-01), Levien
patent: 5513327 (1996-04-01), Farmwald et al.
patent: 5548730 (1996-08-01), Young et al.
patent: 5555425 (1996-09-01), Zeller et al.
patent: 5559962 (1996-09-01), Okamura et al.
patent: 5564025 (1996-10-01), De Freese et al.
patent: 5606672 (1997-02-01), Wade
patent: 5841580 (1998-11-01), Farmwald et al.
patent: 5892957 (1999-04-01), Normoyle et al.
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Sun Microsystems Inc.
Wang Albert
LandOfFree
Fast forwarding slave requests in a packet-switched computer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast forwarding slave requests in a packet-switched computer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast forwarding slave requests in a packet-switched computer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3140988