Static information storage and retrieval – Read/write circuit – Serial read/write
Reexamination Certificate
2000-09-29
2004-03-02
Lebentritt, Michael S. (Department: 2824)
Static information storage and retrieval
Read/write circuit
Serial read/write
C365S239000
Reexamination Certificate
active
06700825
ABSTRACT:
BACKGROUND
This invention relates to first-in, first-out (FIFO) data structures, and in particular to multidimensional, nonlinear FIFO structures.
FIG. 1
shows a conventional flow-through FIFO circuit
50
. In circuit
50
, a data item is received on an input node
55
, where a first stage
60
(
1
) accepts the data item and passes it to a second stage
60
(
2
), and so on to a third stage
60
(
3
) and a fourth stage
60
(
4
), or more, until the data item is output on output node
56
in the order in which it was received. An interconnect
58
in the form of wires or other type of data connection links pairs of successive stages.
Usually, FIFO circuits use some form of control mechanism to control the sequential transition of data items from one stage to another.
FIG. 2
is a simplified circuit diagram that illustrates a conventional linear first-in, first-out (FIFO) data structure
100
with control circuitry. FIFO data structure
100
includes a data path
101
, on which data items are sequentially moved, and a control path
102
. A data item can be any type of information signal and can comprise of any number of bits, words, etc. Control signals are digital signals or other signals that reflect the state of data path
101
, and direct the data path structures to move data items according to a predetermined protocol.
In the data path structure shown in
FIG. 2
, a plurality of data path cells
105
are interconnected in series. A first data item is received at an input to a first data path cell
105
(
1
), where the first data item is processed and output to a next data path cell
105
(
2
). The data item is processed in the next data path cell and the routine is repeated again as the data item is again output to a next data path cell
105
(
3
). The state of each data path cell
105
is monitored and controlled by a corresponding control cell
110
. In a simplistic example, control cell
110
(
1
) detects when data path cell
105
(
1
) has received a data item, and then directs data path cell
105
(
1
) to process the data item and send it to the next data path cell
105
(
2
). Control cell
110
(
1
) sends command and status information to the next control cell
110
(
2
) in the series, so that cell
110
(
2
) is able to detect when the data item is received in the next data path cell
105
(
2
).
One problem that arises in linear FIFO data structures is a high latency from first input to final output. As each processing stage must wait for the output of a stage before it, delays in each stage are cumulative. Thus, more stages in the FIFO leads to a higher latency. Another problem with linear FIFO data structures is high energy consumption. For a linear flow-through FIFO, the energy consumption per data item that flows through the FIFO is approximately proportional to the total number of stages in the FIFO. More stages in a FIFO leads to more energy consumption.
SUMMARY
Generally, the present invention provides a method and apparatus for a multi-dimensional, low-latency, energy efficient and high throughput data structure that exhibits FIFO behavior.
In a first aspect of the invention, a data structure includes an N-row-by-M-column array of data path cells, where N and M are integers greater than one. A first cell of a first row of the array is configured to receive an ordered stream of data items. A control circuit is coupled to the array and configured to sequentially move individual data items to particular cells in the array. In one sequence, data items flow sequentially into the first row of the array (with M cells per row), flow separately down the M columns of the array, and then flow sequentially through the M cells of the Nth row to an output from the Mth cell of the Nth row in the array.
In a second aspect of the invention, a nonlinear FIFO data structure includes an input data path cell configured to receive an ordered stream of data items via an input interconnect; an output data path cell configured to receive the ordered stream of data via an output interconnect; a plurality of intermediate data path cells connected between the input data path cell and the output data path cell in an array of rows and columns, wherein a first row is coupled to the input data cell and a last row is coupled to the output data path cell; a plurality of intermediate interconnects connecting each intermediate cell with intermediate cells adjacent to it; and control circuitry coupled to the input, output and intermediate interconnects configured to sequentially move individual data items from the input cell to particular data path cells in the first row, separately down columns of the data path cells, and then sequentially from particular data path cells of the last row to the output cell, such that the individual data items are output to the output cell in the order received at the input cell.
In a third aspect of the invention, a FIFO data structure includes an input pass gate configured to receive an ordered stream of data items from an input cell; an N-row-by-M-column array of data path cells, where N is greater than one and M is greater than one, the array of data path cells having an input row coupled to the input cell; a plurality of pass gates, each pass gate interconnecting adjacent cells in the input row, adjacent cells in an output row, and cells adjacent to the remaining cells in the array, each pass gate configured to receive a data item from a previous cell and sequentially pass the received data item to a next cell according to a predetermined sequence; a control circuit that controls the individual movement of data items through the plurality of pass gates, first through successive pass gates of the input row cells, from selected input-row cells through successive pass gates of columns comprising, in part, the remaining cells, and then through successive pass gates of the output row; and an output pass gate coupled to the Mth-row, Nth-column cell, configured to output the processed data items, wherein the control circuit follows the predetermined sequence such that the data items are output in the order received at the input pass gate.
In a fourth aspect of the invention, a data structure having an N-row-by-M-column array of communication cells includes a data path circuit having a plurality of sticky buffers, one to each cell, and a plurality of pass gates, configured to communicatively couple adjacent cells in an input row of the array, adjacent cells in an output row of the array, and any cell adjacent to other cells in the array; and a control circuit that controls movement of data items in the data path circuit from one sticky buffer to a next sticky buffer, by making a pass gate therebetween transparent.
In a fifth aspect of the invention, a two-dimensional first-in, first-out (FIFO) data structure includes an N-row-by-M-column array of individual FIFO cells having a data path, including a data buffer within each FIFO cell, and a pass gate between adjacent cells; and a control circuit in communication with the data path and configured to control data propagation along various predefined routes in the data path.
In a sixth aspect of the invention, an asynchronous pipeline module for use in a multi-dimensional FIFO data structure includes a NAND logic gate having a first input configured to receive a first control signal, a second input configured to receive an inverse of a second control signal and an output; a first inverter coupled between the output of the NAND logic gate and an associated pass gate so that the pass gate receives the inverse of the output of the NAND logic gate; a first transistor having a gate coupled to the inverse of the output of the NAND logic gate, a drain coupled to the first control signal and a source coupled to ground; a second transistor having a gate coupled to the output of the NAND logic gate, a drain coupled to the second control signal and a source coupled to a power supply; and at least one drive transistor having a gate coupled to the gate of either the first or second transistor, a source coupled to either ground or th
Lebentritt Michael S.
Nguyen Tuan T.
Park, Vaughn & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Implementation of a multi-dimensional, low latency, first-in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Implementation of a multi-dimensional, low latency, first-in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementation of a multi-dimensional, low latency, first-in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3191615