Queue having distributed multiplexing logic

Details Queue having distributed multiplexing logic Queue having distributed multiplexing logic

1998-06-15

2001-01-23

Lee, Thomas C. (Department: 2782)

Electrical computers and digital data processing systems: input/

Input/output data processing

Input/output data buffering

C365S189050, C365S221000

Reexamination Certificate

active

06178472

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to digital circuitry and, in particular, to a queue within a digital circuit. Still more particularly, the present invention relates to an improved queue design having distributed multiplexing logic.
2. Description of the Related Art
As illustrated in
FIG. 1
, one conventional realization of a first in, first out (FIFO) queue
10
within a field programmable gate array (FPGA) includes two or more entry latches
12
, one for each entry in FIFO queue
10
. Each entry latch
12
is implemented with a D-latch having an n-bit data input (D), an enable input (E), a clock input (CLK), and an n-bit data output (Q). To form FIFO queue
10
, entry latches
12
are cascaded, with the output of each entry latch
12
except the one forming the bottom entry being connected to the data input of the latch forming the subsequent entry and the data input of the latch forming the top entry receiving the n-bit Data_in value. The data output (Q) of each of entry latches
12
is also connected to a respective input of multiplexer
14
, which selects as an output value the n-bit input value specified by the select signal generated by mux control
16
in response to global Read and Write control signals. The n-bit output of multiplexer
14
is in turn connected to the data input of an output latch
18
, which latches in input values and latches out an n-bit data_out value in response to the clock input (CLK).
During operation, when mux control
16
senses that the Read control signal is asserted, mux control
16
generates a select signal that specifies the mux input corresponding to the oldest occupied entry in FIFO queue
10
. During the clock cycle in which the Read control signal is asserted, the input value present at the selected mux input is passed to output latch
18
, which latches in the input value. Then, during the next clock cycle, output latch
18
outputs the n-bit Data_out value.
Conversely, when the Write control signal is asserted, the Data_in value is latched into the entry latch
12
forming the top entry in FIFO queue
10
. Because the Write control signal is connected to the enable inputs of all entry latches
12
, each other entry latch
12
latches the value held by the preceding entry latch
12
during a write. The value, if any, held by the entry latch
12
forming the bottom entry in the queue is latched out and discarded (unless the Read control signal is also asserted).
The present invention includes a recognition that the conventional FIFO queue design for FPGAs depicted in
FIG. 1
suffers from a number of deficiencies. For example, the operation of output latch
18
introduces a cycle of latency in the output data path, as discussed above. In addition, as queue depth increases, multiplexer
14
becomes large and operates more slowly, which introduces additional latency in the output data path. Furthermore, the delay associated with the interconnect connecting entry latches
12
and multiplexer
14
can introduce significant latency in the operation of FIFO queue
10
. It would therefore be desirable to provide an improved queue design for that addresses these and other deficiencies of the conventional FIFO queue design shown in FIG.
1
.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide improved digital circuitry.
It is another object of the present invention to provide an improved queue within a digital circuit.
It is yet another object of the present invention to provide an improved queue having distributed multiplexing logic.
The foregoing objects are achieved as is now described. A queue includes a data multiplexer having an output and at least two inputs and a plurality of data latches. The data latches include at least a first data latch and a second data latch, which each have a data input and a data output. The data output of the first data latch is coupled to a first input of the data multiplexer, and the output of the data multiplexer is coupled to the data input of the second data latch. A data value to be stored in the queue is received at a second input to the data multiplexer. In response to one or more control signals, the data value is latched into at least one of the first and second data latches, thereby storing the data value in the queue. Depending upon the design of the control logic, the queue can implement either first in, first out (FIFO) or last in, first out (LIFO) behavior.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.


REFERENCES:
patent: 4833655 (1989-05-01), Wolf et al.
patent: 4979190 (1990-12-01), Sager et al.
patent: 5774475 (1998-06-01), Qureshi
patent: 5844844 (1998-12-01), Bauer et al.

Affiliated with

Also associated with

Rating

Queue having distributed multiplexing logic does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Queue having distributed multiplexing logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Queue having distributed multiplexing logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2510079