Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2001-05-10
2004-06-22
Perveen, Rehana (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S033000, C710S035000, C710S054000, C710S056000
Reexamination Certificate
active
06754741
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is generally related to memory storage techniques and more particularly to a logical FIFO storage method and apparatus.
Physical layer devices frequently involve complex FIFO buffering requirements. Such buffers may have to support multiple channels of data, with different bandwidths and physical datapath widths. The number of channels may be different on the input and output sides of the FIFO, and may further have to be configurable depending on the application of the device. For efficiency, it may be desirable to use a single block of RAM—e.g., when the number of channels can vary between wide limits—and create multiple logical FIFOs within this RAM. Finally, the FIFOs may have to run at high speeds (10 Gb/s or more) to support the requirements of the physical layer interfaces.
Several different ways have been employed in the past to solve the data width conversion and merging problems in various applications, usually at lower data rates. Considered below are some approaches to solving this problem.
The most obvious means of solving the problem is to use a data RAM of width equal to the highest common factor among all the different datapath widths that are to be supported. For example, if the various FIFO interface widths required are 8, 16, 32 and 128 bits, an 8-bit-wide RAM would be used. The wider datapath widths would be supported via multiplexing and demultiplexing logic. This “brute-force” approach is commonly used when data rates are low. It is, however, not feasible when the speeds increase. For example, supporting a 10 Gb/s data rate for the above combination of widths would require an 8-bit RAM capable of operating at 1.25 GHz. Such RAMs are very difficult to obtain using present CMOS technology. In addition, the solution is not scalable—a 40 Gb/s data rate requires a 5 GHz RAM, which is not possible at all in the near future.
Another possibility is to use several RAMs to construct the FIFO. Each FIFO would have a width corresponding to a particular datapath width. Circuitry would be provided to select the appropriate RAM based on the current configuration. This approach, however, is significantly more resource-intensive than using a single RAM. It is less efficient as well because most of the RAMs would not be used at any given time. In addition, it does not solve the issue of different input and output widths.
Other approaches using shift register networks on the input and output sides of the RAM have also been proposed and implemented. These architectures are relatively flexible. Typically, multi-stage shifting networks are used to shift and align incoming data from narrower streams to various positions in a wider stream. The wider stream feeds into a multiplexer, register, and buffer logic to merge the various narrow data words together into the desired wide output. The reverse operation is used on the output side. However, this approach suffers from the difficulty that its complexity grows by N
2
, where N is the number of channels to be supported. Thus, if the number of channels is large (e.g., 64), the resulting shift register network becomes enormous. In addition, these approaches are difficult to deal with at high speeds and/or large data widths due to the large number of interconnections. A 40 Gb/s FIFO supporting 64 datapath channels of 8 bits each, using typical 160 MHz RAMs, would require 16,384 register bits and 32,768 crossing wires, which is quite expensive to implement. Higher numbers would reach the limits of design rules in the circuit layout of the integrated circuit device. Attempting to support configurable channelizations (e.g., 1 channel of 256 bits, 16 channels of 32 bits each, or 64 channels of 8 bits each, or some combination of these) vastly complicates the problem.
Yet another general approach is to split up the RAM into a number of fixed-width, fixed-size units. A striping or interleaving scheme is then applied to distribute data across logical FIFOs built within the RAM. The striping is done to eliminate conflicts and wasted bandwidth that would otherwise occur due to the differences between the widths of the data ports and the width of the RAM. However, the use of such mechanisms results in very complex data steering, addressing and buffer management logic, and thus are not easily extensible to higher data rates.
The apparatus described in U.S. Pat. Nos. 3,812,467 and 3,800,289 hint at a possible solution to the above problem. The patents detail a multi-stage network used in conjunction with a memory and addressing scheme to transform a CPU's view of a single block of memory from a bit-wise organization to a word-wise organization, or vice-versa. Multi-stage networks are well known as having very desirable properties from a space and speed standpoint, especially when scaled up to large dimensions. The specific multi-dimensional memory addressed by the referenced patents, however, is not suitable for our purposes, because it does not support the concept of multiple independent streams being directed into and out of multiple logical buffers within a single physical memory, possibly with different widths on the input and output sides. In addition, the memory requires the use of 2
n
individual memory modules and a complex addressing and module selection scheme, which is undesirable from the perspective of implementation convenience and efficiency.
There is a need for a FIFO approach which exhibits high efficiency usage and high utilization capability. The FIFO mechanism and method should be regular and simple. The FIFO must be able to receive variable-sized input streams and output to variable-sized output streams.
SUMMARY OF THE INVENTION
In accordance with an embodiment of the invention, a FIFO storage method includes receiving one or more data streams at an input. Internal data comprising combinations of the incoming data are produced and stored in a memory store. Internal data obtained from a data stream are stored in and accessed from the memory store in first-in-first-out (FIFO) fashion. Internal data accessed from the memory store are processed to produce outgoing data. Each output datum comprises one or more of the constituent incoming data which constitute the accessed internal data.
In accordance with another embodiment of the invention, an incoming data stream is stored in a memory store in FIFO order. The data are read out of the memory store in FIFO order. Outgoing data are produced and output on one or more output ports. Each outgoing datum comprises a combination of one or more data read from the memory store.
In accordance with yet another embodiment of the invention, plural incoming data streams are processed to produce internal words. Each internal word comprises one or more data read in from one of the incoming data streams. Each internal word is stored in a memory store and is associated with a logical FIFO. The internal words are read out of the memory store and output on an output port.
The remainder of this document sets forth a description of an embodiment of the present invention.
REFERENCES:
patent: 3686640 (1972-08-01), Andersen et al.
patent: 3800289 (1974-03-01), Batcher
patent: 3812467 (1974-05-01), Batcher
patent: 4747070 (1988-05-01), Trottier et al.
patent: 5008852 (1991-04-01), Mizoguchi
patent: 5111389 (1992-05-01), McAuliffe et al.
patent: 5807245 (1998-09-01), Aldestam et al.
patent: 6091707 (2000-07-01), Egbert et al.
patent: 6092128 (2000-07-01), Maas et al.
patent: 6226338 (2001-05-01), Earnest
patent: 6311161 (2001-10-01), Anderson et al.
patent: 6333935 (2001-12-01), Carr et al.
patent: 6490324 (2002-12-01), McDade et al.
Alexander Thomas
Wong David
Allen Kenneth R.
Perveen Rehana
PMC-Sierra Inc.
Townsend and Townsend / and Crew LLP
LandOfFree
Flexible FIFO system for interfacing between datapaths of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flexible FIFO system for interfacing between datapaths of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flexible FIFO system for interfacing between datapaths of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3322314