Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2000-12-19
2004-08-03
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S052000, C710S056000, C711S170000, C709S234000
Reexamination Certificate
active
06772243
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to first-in-first-out (FIFO) data pipelines, and more particularly to techniques for monitoring and indicating partial fullness levels of the FIFO pipelines.
FIFOs are widely used in computer and telecommunication fields for buffering data and handling transfer of data items between producers which deliver data items to the FIFO and consumers which remove data items from the FIFO. FIFOs are typically used as buffers for transferring data items between systems which may be clocked or asynchronous. For clocked systems involved in the transfer of the data items, the clocks may be of different frequencies and/or phases. Such buffers are typically used in systems where data items are produced or consumed in bursts.
FIFO implementations are usually either RAM-based or flow-through designs. The present invention relates to flow-through FIFOs. A flow-through FIFO generally comprises a plurality of stages and has an input port and an output port. Data items enter the FIFO at the input port, progress from one stage of the FIFO to the next, and exit the FIFO at the output port after the last stage of the FIFO. Accordingly, as suggested by the name FIFO (first-in-first-out), the order in which data items exit a FIFO is the same as the order in which the data items entered the FIFO.
When using a FIFO, it is often useful to know the fullness level of a FIFO. For example, a producer of data items needs to know if a FIFO is “almost full” in order to stop sending data items to the FIFO before the FIFO overflows. Similarly, a consumer needs to know when the FIFO is “almost empty” so that the consumer can slow down or stop trying to remove data items from the FIFO. Accordingly, a FIFO generally has signals associated with it which monitor and indicate the fullness level of the FIFO. For example, the indicator signals may indicate if the FIFO is ¼ full, ½ full, ¾ full, or the like. Such fullness indicator signals are called partial fullness indicator signals. These signals are typically important for producer circuits and consumer circuits to facilitate efficient flow of data items through the FIFO while preventing data loss that can occur if data is delivered to a FIFO that is completely full. These signals can be used to also prevent the consumer from reading from an empty FIFO.
The FIFO partial fullness indicator signals may be implemented relatively easily in RAM-based FIFO designs by knowing the total capacity of the FIFO and by monitoring the difference in value between the read and write pointers of the FIFO. Additionally, RAM-based FIFOs generally have multiple full/empty indicator signals which indicate the precise fullness values of the FIFO when only approximate values are needed. However, implementing partial fullness indicator signals in linear flow-through FIFOs is more complex, because monitoring the fullness or emptiness of individual stages of a FIFO does not generally yield steady signals as the fullness of a particular stage can be transitory and changes from empty to full and then back to empty again as a data item passes through the stage.
FIG. 1A
depicts a conventional technique for producing partial fullness signals
24
for a linear FIFO
10
. Signals di and do represent the data input and data output of FIFO
10
respectively. Control signals request input ri, request output ro, acknowledge input ai, and acknowledge output ao facilitate the transfer of data items to and from FIFO
10
. Request input signal ri indicates to FIFO
10
that a data item appearing at input di is valid and available to be stored by the first stage of FIFO
10
. Request output signal ro indicates to a consumer that the data items appearing on output do is valid and available to be read from FIFO
10
. Acknowledgment input signal ai indicates that the data item appearing on data input di has been stored in FIFO
10
. Acknowledgment output signal ao informs FIFO
10
that the data item appearing on data output do has been read.
The embodiment shown in
FIG. 1A
uses an up-down counter
12
to measure the partial fullness of FIFO
10
. Counter
12
generally has a lower bound value of zero, indicating an empty FIFO, and a upper bound value equal to the maximum capacity of FIFO
10
, indicating a full FIFO. Counter
12
is incremented as data items are loaded into FIFO
10
via input port
14
, and decremented as data items are read from FIFO
10
via output port
16
. Although counter
12
is able to produce partial fullness signals, it suffers from several disadvantages. For example, counter
12
has to be carefully designed to accommodate independent count up
18
and count down
20
signals, and requires the use of an arbiter
22
to arbitrate the count up and count down requests as both these signals can be received at about the same time. Another disadvantage of such a counter is that the entry of a second data item into FIFO
10
must wait not just for the first data item to be stored in FIFO
10
, but also for the count value to be incremented. This adversely affects the efficiency of FIFO
10
. The C-elements and RGD Arbiter
22
are components well known to asynchronous circuit designers.
FIG. 1B
depicts another conventional technique for producing a partial fullness indicator signal
40
for a linear FIFO
30
. According to this technique, the fullness/emptiness of each individual stage of FIFO
30
is monitored to determine the partial fullness or partial emptiness of FIFO
30
. As shown in
FIG. 2
, a resistor
32
is coupled to each individual FIFO stage and to a common node
34
. A capacitor
36
is coupled between common node
34
and ground voltage
38
. The voltage across each resistor is at a first voltage level when the stage connected to the resistor is full, and at a different voltage level when the stage is empty. Since the fullness of any stage carries the same weight as the fullness of any other stage, the voltage on capacitor
36
indicates the proportion of full stages in FIFO
30
. FIFO partial fullness indicator signals
40
are obtained using voltage comparators
42
to compare the voltage on capacitor
36
with some reference voltages
44
. A variant of this scheme uses currents rather than voltages to produce the fullness signals. Although this technique produces partial fullness indicator signals for a linear FIFO, this technique is quite expensive to implement. Since the voltage for each stage has to be measured, this technique requires a significant amount of additional circuitry, for example resistors connected to each stage, capacitor, comparators, etc., to produce the partial fullness signals. For large FIFOs, this technique requires a large number of wires to convey the fullness of each stage, and these wires are generally the expensive item in a chip. Due to the need for increased circuitry, this technique also reduces the amount of real estate available on a chip.
Thus, there is a need for techniques which can efficiently and accurately provide partial fullness indicator signals for a FIFO using minimal circuitry. It is desired that these techniques be able to generate fullness signals without having to monitor the fullness/emptiness of each individual stage of the FIFO.
SUMMARY OF THE INVENTION
The present invention relates to techniques for indicating partial fullness levels of a FIFO comprising a plurality of stages. A partial fullness detector is coupled to a subset of the plurality of stages of the FIFO, and is configured to output a signal indicating a partial fullness level of the FIFO.
According to an embodiment of the present invention, a m-out-of-n (where m≦n) detector is used to output signals indicating the partial fullness level of a FIFO. The m-out-of-n detector is coupled to “n” stages of the FIFO and configured to output partial fullness indicator signals based on the full/empty states of the stages coupled to the m-out-of-n detector. The fullness levels indicated by embodiments of the present invention may include ½ full, ¼ full, ⅓ full, &
Ebergen Josephus C.
Jones Ian W.
Casiano Angel L.
Gaffin Jeffrey
Sun Microsystems Inc.
Townsend and Townsend / and Crew LLP
LandOfFree
Apparatus and method for generating a partial fullness... 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 and method for generating a partial fullness..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for generating a partial fullness... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3343325