FIFO with random re-read support and its application

Details FIFO with random re-read support and its application FIFO with random re-read support and its application

1999-12-21

2002-08-13

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Control technique

C711S104000, C710S052000

Reexamination Certificate

active

06434676

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of data processing and data communication. More specifically, the present invention relates to the design of storage structures used in data processing and data communication devices.
2. Background Information
FIG. 1
illustrates a prior art storage structure equipped to support random read and write of its storage locations. Storage structure
50
includes memory array
52
having a number of memory locations, write enable control signal pin
54
, address input pins
56
a
-
56
b,
and data in and out pins
58
a
-
58
b.
By setting write enable control signal
54
to denote a “write” operation, and applying the appropriate address information to address input pins
56
a,
write data applied to data in pins
58
a
may be written into any memory location of memory array
52
. Similarly, by applying the appropriate address information to address input pins
56
b,
previously written data stored in any memory location of memory array
52
may be retrieved and made available at data out pins
58
b.
While storage structure is designed to facilitate random read/write, of course a host process may elect to write to and read from its storage locations sequentially, by shouldering the responsibility of ensuring that all successive write/read addresses issued are sequential in nature. [The term host process, as used herein in this application, in intended to include hardware and/or software.]
FIG. 2
illustrates a prior art first in, first out storage structure (FIFO) designed to support sequential write and read, without requiring a host process to shoulder the responsibility of ensuring the successive write/read addresses issued are sequential in nature. Storage structure
60
includes dual port memory array
62
having a number of memory locations, write counter
64
, read counter
66
and full/empty logic
68
, coupled to each other as shown. Write data may be sequentially written into memory locations of memory array
62
by applying a write signal to increment write counter
64
, whose output is applied to the write address inputs of memory array
62
. Likewise, read data may be sequentially read from memory locations of memory array
62
by applying a read signal to increment read counter
66
, whose output is applied to the read address inputs of memory array
62
. A host process need not be concerned with maintaining the sequential nature of the write/read addresses. By monitoring the output of write and read counters
64
and
66
, full/empty logic
68
is able to set a “full” control signal to “true” to inform a host process that RAM array
62
is full (accordingly, should not be further written into) and set an “empty” control signal to “false” to inform the host process that RAM array
62
is non-empty (accordingly, should be read to process the written data).
In a number of applications, while the basic write and read operations are fundamentally sequential in nature, nevertheless it may be desirable to be able to perform random re-reads in addition to the fundamental sequential write/read operations. An example of such applications is one where data are sequentially queued, and multiple sets of the queued data are to be sequentially examined and processed concurrently in a pipelined multi-stage fashion. To facilitate the multi-set pipelined multi-stage fashion of processing, earlier queued data must be “popped off” to make the later queued data visible, and yet all “popped off” data must remain available until all stages of processing are completed. One obvious approach, if a storage structure similar to the one illustrated in
FIG. 2
is continued to be used, is to provide additional hardware to store the “popped off” data, making the stored data available until all processing is completed. Another approach is to revert to the use of a storage structure similar to the one illustrated by FIG.
1
. Under such approach, the “popped off” data will still be re-accessible, until they are discarded. However, as alluded to earlier, the burden of maintaining the sequential nature of the fundamental writes and reads will be reverted back to the host process. Neither approach is desirable.
A specific application where such situations occur is in networking switch and router applications. Network switches/routers receive continuous streams of packets, and the included IP or MAC addresses are queued and examined to determine where the packets should be switched or routed. The determination typically involves data look ups. For performance reasons, it is desirable to be able to perform the look up for multiples of these IP/MAC addresses concurrently in a pipelined multi-stage fashion. However, as alluded to earlier, it is desirable if the concurrent processing can be made possible without having to resort to the use of RAM or registers to “queue” up the IP/MAC addresses (and shifting the burden of maintaining the sequential nature of the fundamental writes and reads to the host process) nor having to pay the price of replicating the hardware required to carry the “context” information of each IP/MAC address being concurrently processed.
Thus, a novel storage structure that can better accommodate this type of processing is desired.
SUMMARY OF THE INVENTION
The present invention includes a novel FIFO storage structure. The FIFO storage structure is provided with a RAM array including a number of memory locations, and control circuitry coupled to the RAM array. The control circuitry facilitates sequential write and read accesses of the memory locations, as well as non-sequential re-read of memory locations previously read in sequence. In particular, the control circuitry includes circuit elements for facilitating variably deferred release and reclaiming of sequentially read in-use ones of the memory locations.


REFERENCES:
patent: 4447873 (1984-05-01), Price et al.
patent: 5074420 (1991-12-01), Cappel, lll
patent: 5666494 (1997-09-01), Mote, Jr.
patent: 5687316 (1997-11-01), Graziano et al.
patent: 5708779 (1998-01-01), Graziano et al.
patent: 5758075 (1998-05-01), Graziano et al.
patent: 5784649 (1998-07-01), Holm
patent: 5809557 (1998-09-01), Shelma et al.
patent: 6055616 (2000-04-01), Panwar
patent: 6115387 (2000-09-01), Egbert et al.
patent: 6301264 (2001-10-01), Holm
patent: 6304924 (2001-10-01), Varma
patent: 6330626 (2001-12-01), Dennin et al.
Hobson et al., “A Parallel Embedded-Processor Architecture for ATM Reassembly,” IEEE, pp. 23-37, Feb. 1999.

Affiliated with

Also associated with

Rating

FIFO with random re-read support and its application does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with FIFO with random re-read support and its application, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and FIFO with random re-read support and its application will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2969159