Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
1998-10-30
2001-07-31
Lee, Thomas (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S029000, C710S036000, C710S039000, C710S040000, C710S041000, C710S053000, C710S056000, C710S057000, C711S001000, C711S100000, C711S147000, C711S150000, C711S151000
Reexamination Certificate
active
06269413
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to FIFO buffers. More particularly, the invention relates to a buffer system wherein multiple independent logical FIFOs share a single memory structure, and wherein the storage capacity of the single memory structure may be allocated dynamically among each of the logical FIFOs as needed during operation.
BACKGROUND
A first-in-first-out or “FIFO” buffer is a well-known memory tool often used to transfer data from a source system to a destination system wherein the rate of output from the source system is not always the same as the rate of input of the destination system.
In certain applications, it is desirable to implement numerous independent FIFO buffers at the same time. For example, when multiple data streams must be coupled from one or more source systems to one or more destination systems, multiple FIFO buffers are required, one for each data stream. Clearly however, implementing multiple independent FIFO buffers requires redundant hardware and results in an increase in system cost as well as circuit space. Moreover, such a redundant hardware solution may represent waste for applications wherein it is not possible for all of the independent FIFOs to be full simultaneously, but wherein it is not possible to predict which FIFO will require maximum storage capacity at any given moment.
It is therefore an object of the invention to allow multiple independent FIFO buffers to share a single memory structure, thereby avoiding hardware redundancy.
It is a further object of the invention to avoid wasted storage capacity by allowing the maximum storage capacity of the single memory structure to be allocated dynamically among the multiple independent FIFOs during system operation according to the needs of the independent data streams being buffered.
SUMMARY OF THE INVENTION
The invention includes numerous aspects, each of which contributes to achieving the above-recited objectives.
In one aspect, a multiple logical FIFO system uses a single main register file to store payload data in association with link data so as to form one linked list data structure for each logical FIFO in the system. A write pointer register file stores one write pointer for each logical FIFO. A read pointer register file stores one read pointer for each logical FIFO. A free register identifier indicates a free register address at all times unless the overall system is full. The free register address corresponds to one free register within the main register file
When a word of write data is to be enqueued into a logical FIFO, the following actions occur: An active write pointer register is selected within the write pointer register file responsive to a write FIFO number input. A destination register is selected within the main register file responsive to the contents of the active write pointer register. The word of write data is loaded into a payload data field of the destination register. And the free register address is loaded into both the active write pointer register and the link data field of the destination register. Thus, after the word of write data has been enqueued into a logical FIFO, it is stored in the main register file in association with a pointer to a new register in the main register file. The new register will be used to store the next data word for that logical FIFO. In order to ensure this result, the address of the new register has been loaded into the write pointer register corresponding to that logical FIFO.
When a word of read data is to be dequeued from a logical FIFO, the following actions occur: An active read pointer register is selected within the read pointer register file responsive to a read FIFO number input. A source register is selected within the main register file responsive to the contents of the active read pointer register. The word of read data is routed from the payload data field of the source register to the read data output. And the contents of the link data field of the source register are loaded into the active read pointer register. Thus, after the word has been dequeued, the read pointer for that logical FIFO has been updated to point to the next entry in that logical FIFO.
In another aspect, the free register identifier may contain an array of storage cells, wherein each storage cell of the array corresponds to one of the registers within the main register file. The state of each storage cell is maintained to indicate whether the corresponding register in the main register file is free. In this context, a free register means a register that is not currently storing payload data for one of the logical FIFOs, and that has not been reserved for use in storing the next entry to be enqueued into one of the logical FIFOs. The collective states of the storage cells may be applied to a priority encoder as an input word. The output of the priority encoder may be used to indicate the free register address.
In another aspect, the free register identifier may be implemented as a conventional FIFO buffer. In such an embodiment, the conventional FIFO buffer is operable to enqueue, as a new element of its contents, the address of the source register each time a word of read data is dequeued from a logical FIFO. And the conventional FIFO buffer is operable to dequeue one element of its contents each time a word of write data is enqueued into a logical FIFO. In this manner, the conventional FIFO buffer may be used to store addresses of free registers within the main register file. The free register address may be taken from the output of the conventional FIFO buffer.
In yet another aspect, the free register identifier may be implemented as an additional logical FIFO buffer within the multiple logical FIFO system. In such an embodiment the additional logical FIFO buffer is operable to enqueue, as a new element of its contents, the address of the source register each time a word of read data is dequeued from a logical FIFO. And the additional logical FIFO buffer is operable to dequeue one element of its contents each time a word of write data is enqueued into a logical FIFO. The free register address is taken from the output of the additional logical FIFO buffer.
A chief advantage of the inventive multiple logical FIFO buffer system is the fact that the entire payload storage capacity of the main register file may be allocated dynamically among the logical FIFOs as needed during the operation of the system. Wasted memory space and redundant hardware can therefore be avoided.
REFERENCES:
patent: 4757440 (1988-07-01), Scheuneman
patent: 4949301 (1990-08-01), Joshi et al.
patent: 5014265 (1991-05-01), Hahne et al.
patent: 5043981 (1991-08-01), Firoozmand et al.
patent: 5133062 (1992-07-01), Joshi et al.
patent: 5163046 (1992-11-01), Hahne et al.
patent: 5210749 (1993-05-01), Firoozmand
patent: 5247626 (1993-09-01), Firoozmand
patent: 5414455 (1995-05-01), Hooper et al.
patent: 5442390 (1995-08-01), Hooper et al.
patent: 5471583 (1995-11-01), Au et al.
patent: 5487061 (1996-01-01), Bray
patent: 5488724 (1996-01-01), Firoozmand
patent: 5519701 (1996-05-01), Colmant et al.
patent: 5521916 (1996-05-01), Choudhury et al.
patent: 5553061 (1996-09-01), Waggener, Jr. et al.
patent: 5604742 (1997-02-01), Colmant et al.
patent: 5625625 (1997-04-01), Oskouy et al.
patent: 5649230 (1997-07-01), Lentz
patent: 5687316 (1997-11-01), Graziano et al.
patent: 5765041 (1998-06-01), Cherichetti et al.
patent: 5797043 (1998-08-01), Lewis et al.
patent: 5850568 (1998-12-01), Hawkins et al.
patent: 5937205 (1999-08-01), Mattson et al.
patent: 5948080 (1999-09-01), Baker
patent: 5974483 (1999-10-01), Ray et al.
patent: 5974516 (1999-10-01), Qureshi
patent: 5983301 (1999-11-01), Baker et al.
patent: 5987590 (1999-11-01), Wing So
patent: 5996032 (1999-11-01), Baker
patent: 6006286 (1999-12-01), Baker et al.
patent: 6044225 (2000-03-01), Spencer et al.
patent: 6049802 (2000-04-01), Waggener, Jr. et al.
patent: 6081852 (2000-06-01), Baker
patent: 6134625 (2000-10-01), Abramson
patent: 6137807 (2000-10-01), Rusu et al.
patent: 6141744 (2000-10-01), Wing So
p
Hart Kevin M.
Hewlett -Packard Company
Lee Thomas
Nguyen Tanh
LandOfFree
System with multiple dynamically-sized logical FIFOs sharing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System with multiple dynamically-sized logical FIFOs sharing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System with multiple dynamically-sized logical FIFOs sharing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2434936