Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2001-07-13
2004-02-10
Shin, Christopher B. (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S062000, C710S072000, C370S389000, C370S423000, C370S412000
Reexamination Certificate
active
06691185
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to I/O devices. More specifically, the present invention relates to a novel apparatus that merges a plurality of data streams into a single data stream.
BACKGROUND
In an effort to increase I/O bandwidth in high performance processor based systems, a number of companies have developed the HyperTransport (“HT”) I/O interconnect structure. Briefly, the HT I/O bus structure is a scalable device level architecture that provides a significant increase in transaction throughput over existing I/O bus architectures such as Peripheral Component Interconnect (“PCI”) and Advanced Graphics Port (“AGP”).
The foundation of the HT I/O bus is dual point-to-point unidirectional links consisting of a data path, control signals, and clock signals. The HT I/O bus can provide both point-to-point links and a scalable network topology using HT I/O switching fabrics. Thus, an HT based system can be expanded using HT switches to support multilevel, highly complex systems.
Communications between multiple HT I/O devices are known as data streams. Each data stream contains one or more packets of information. Each packet of information contains a packet ID and a data payload. The packet ID is also commonly referred to as a unit ID. Because all packets are transferred to or from a host bridge, the packet ID provides information that can be utilized to determine the source or destination of the packet. A more detailed description of the HT I/O bus structure is presented in Appendix A.
FIG. 1
presents an HT I/O device
100
that interfaces with a first unidirectional link
110
and a second unidirectional link
120
. Thus, the HT I/O device
100
can receive input data streams and transmit output data streams via unidirectional links
110
and
120
. The HT I/O device
100
contains input ports
130
and
150
for receiving data streams and output ports
140
and
160
for transmitting data streams. The HT device
100
may also contain circuitry for generating packets that can be transmitted as output data streams via the output ports
140
and
160
.
HT I/O devices may also be daisy chained as shown in FIG.
2
.
FIG. 2
presents a portion of a single unidirectional link in an HT I/O bus. The unidirectional link shown contains three HT I/O devices
210
,
220
, and
230
. If the first HT I/O device
210
receives a data stream with a destination ID that is equal to the ID of the first HT I/O device
210
, then the first HT I/O device
210
will receive and internally process the data stream. However, if the destination ID is not equal to the ID of the first HT I/O device
210
, then the first HT I/O device
210
will forward the data stream to the second HT I/O device
220
.
As the first HT I/O device
210
may also have the capability to generate packets, the output data stream of the first HT I/O device
210
is a composite of the input packet stream received by the first HT I/O device
210
and the internally generated packets. These internally generated packets will be referred to as an internal data stream.
The data stream received by the first HT I/O device
210
and the device's internal data stream may vary with time. For example, the input data stream for the first HT I/O device
210
may contain no packets over a given time interval. Thus, all packets in the internal data stream generated during that time interval by the first HT I/O device
210
may be transmitted through the first HT I/O device's output port. Alternately, if the data stream received by the first HT I/O device
210
and the device's internal data stream both contain a large number of packets, the HT I/O device may be required to choose between forwarding the received data stream or outputting the internally generated packets. The process by which such a choice is made is known in the art as a forwarding fairness algorithm.
Prior art systems allow an HT I/O device to insert internally generated packets into an output data stream freely if the output data stream is empty. However, if the output data stream contains a large number of packets, the prior art systems only allow the HT I/O device to insert internally generated packets into the output data stream at a rate that is not greater than the rate that the HT I/O device is receiving and forwarding packets from another HT I/O device. Such prior art systems are not optimal. Thus, a more optimal apparatus for merging two data streams into a single data stream is needed.
SUMMARY OF INVENTION
One embodiment of the invention is an I/O device that includes: an input port; an input buffer coupled to the input port; an internal port operable to store packets generated by the I/O device; an internal buffer coupled to the internal port; a plurality of packet ID arrival registers coupled to the input port and the internal port; autocorrelation logic coupled to the plurality of packet ID arrival registers; an arbiter coupled to the autocorrelation logic; a packet selector coupled to the arbiter, the input buffer and the internal buffer; and an output port coupled to the packet selector.
In another embodiment of the invention, the arbiter includes an autocorrelation magnitude table.
In another embodiment of the invention, the arbiter includes a maximum autocorrelation magnitude table.
In another embodiment of the invention, the arbiter is operable to command the packet selector to select a packet from one of the plurality of input buffers based upon the output of the autocorrelation logic.
Another embodiment of the invention is an I/O device that includes: a first input port; a first input buffer coupled to the first input port; a second input port; a second input buffer coupled to the second input port; a plurality of packet ID arrival registers coupled to the first input port and the second input port; autocorrelation logic coupled to the plurality of packet ID arrival registers; an arbiter coupled to the autocorrelation logic; a packet selector coupled to the arbiter, the first input buffer and the second input buffer; and an output port coupled to the packet selector.
Another embodiment of the invention is an I/O device that includes: a first internal port operable to store packets generated by the I/O device; a first internal buffer coupled to the first internal port; a second internal port operable to store packets generated by the I/O device; a second internal buffer coupled to the second internal port; a plurality of packet ID arrival registers coupled to the first internal port and the second internal port; autocorrelation logic coupled to the plurality of packet ID arrival registers; an arbiter coupled to the autocorrelation logic; a packet selector coupled to the arbiter, the first internal buffer and the second internal buffer; and an output port coupled to the packet selector.
Another embodiment of the invention is an HT I/O device that includes: an input port; an input buffer coupled to the input port; an internal port for storing packets generated by the HT I/O device; an internal buffer coupled to the internal port; and a plurality of packet ID arrival registers coupled to the input port and the internal port.
REFERENCES:
patent: 4677616 (1987-06-01), Franklin
patent: 4860357 (1989-08-01), Avery
patent: 4926418 (1990-05-01), Cidon
patent: 5245609 (1993-09-01), Ofek
patent: 5687325 (1997-11-01), Chang
patent: 5889776 (1999-03-01), Liang
patent: 6058436 (2000-05-01), Kosco
patent: 6118788 (2000-09-01), Kermani
patent: 6247058 (2001-06-01), Miller et al.
patent: 6363077 (2002-03-01), Wong et al.
patent: 6483841 (2002-11-01), Chang et al.
patent: 6571321 (2003-05-01), Rowlands et al.
patent: 6574708 (2003-06-01), Hayter et al.
patent: 2003/0012187 (2003-01-01), Avery
U.S. patent application Ser. No. 09/905,483, Avery, Method for Merging a Plurality of Data Steams into a Single Data Stream, Jul. 13, 2001.
API NetWorks, Inc., The Lightning Data Transport I/O Bus Architecture, Revision 1001, 2000.
API NetWorks, Inc., HyperTransport: Universal Interconnect Solution for I/O, Mar. 7, 2001.
API NetWorks, Inc
Park Vaughan & Fleming LLP
Shin Christopher B.
Sun Microsystems Inc.
LandOfFree
Apparatus for merging a plurality of data streams into a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for merging a plurality of data streams into a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for merging a plurality of data streams into a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3354610