Multi-access FIFO queue

Details Multi-access FIFO queue Multi-access FIFO queue

2001-08-20

2003-03-25

Le, Don (Department: 2819)

Electronic digital logic circuitry

Multifunctional or programmable

Having details of setting or programming of interconnections...

C365S189120

Reexamination Certificate

active

06538467

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to “First In First Out” (“FIFOs”) queues. More specifically, the present invention relates to FIFO queues that allow stored data to be read more than once.
BACKGROUND OF THE INVENTION
FIFO queues are well known in the art of computing. FIFO queues can be implemented in software or hardware. Typically, a hardware-implemented FIFO queue integrates a memory device with associated on-chip logic, which can be utilized in a wide variety of applications that may require data to be buffered.
A FIFO queue gets its name (that is, First In First Out) from the fact that the data buffered in the FIFO queue's memory is retrieved from the FIFO queue's memory in the same order that it was written to the FIFO queue's memory. That is, the First data element to be stored In the FIFO queue's memory is the First data element to be retrieved Out of the FIFO queue's memory. Similarly, the last data element to be stored in the FIFO queue is the last data element to be retrieved from the queue. The operation of storing a data element in the FIFO queue's memory is generally referred to as a “write” or a “push.” The operation of retrieving a data element from the FIFO queue's memory is generally referred to as a “read” or a “pop.”
A conventional FIFO queue typically comprises storage elements, a write pointer, a write signal, a read pointer, a read signal, a full signal, an empty signal, and a reset signal. The storage elements are used for storing data and can be thought of as memory locations where each memory location has an address. The data stored in the storage elements may be referred to herein as data elements. The write pointer contains the address of the storage element where the next data element is to be written. That is, the write pointer “points to” the storage element into which the next data element will be written. The write signal is an input signal that is asserted to cause a data element to be written into the FIFO queue's storage element pointed to by the write pointer. When the write signal is asserted a data element is written into the storage element pointed to by the write pointer. The read pointer contains the address of the storage element containing the next data element to be retrieved or read from the.FIFO queue's storage elements. That is, the read pointer points to the storage element containing the next data element to be read. The read signal is an input signal that is asserted to cause a data element to be read from one of the FIFO queue's storage elements. When the read signal is asserted the data element pointed to by the read pointer is retrieved or read. A full signal is an output signal that is asserted to indicate that the FIFO queue's storage elements are full and no more data can be written into the FIFO queue's storage elements. In other words, the full signal is asserted when the FIFO queue is full. An empty signal is an output signal that is asserted to indicate that the FIFO queue's storage elements are empty and that no data is available to be read from the FIFO queue's storage elements. In other words, the empty signal is asserted when the FIFO queue is empty. A reset signal is an input signal that causes the FIFO queue to become empty.
Conventional FIFO queues have the property that each data element stored in the FIFO queue can be read from the FIFO queue only once. This is because the read pointer is incremented every time a data element is read from the FIFO queue. Once the read pointer is incremented, the storage element just read from becomes available to be written to and the previous data element can then be overwritten and lost. However, in some applications it may be desirable to read some data elements more than once. This may happen, for example, while stepping through a loop construct in a computer program. Thus, in applications where it is desirable to read some data elements more than once conventional FIFO queues are not well suited.
SUMMARY OF THE INVENTION
The present invention addresses the issues above by providing FIFO queues that enable multiple accesses to data stored in the FIFO queue. According to the present invention, conventional FIFO queues can be augmented by the addition of one or more pointers, referred to herein as release pointers, one or more input signals, referred to herein as “repeat” signals, and one or more input signals, referred to herein as “release” signals. In one embodiment of the present invention, a release pointer points to a location in the queue (that is, one of the storage elements) containing a data element that has already been read. The release signal is an input signal that causes the release pointer to be incremented when the release signal is asserted. As long as the release signal is not asserted, the release pointer does not change while a read pointer is used to read data from the queue. The release pointer can be viewed as saving a location in the queue containing data that has already been read. In order to allow the read pointer to go back and reread previously read data, the repeat signal can be asserted. Asserting the repeat signal causes the read pointer to be set to the value of the release pointer. This allows the read pointer to be “rewound” to a location containing data already read (that is, the location pointed to by the release pointer) and start reading data that has already been read. The read pointer can be rewound as many times as desired. Once the data is no longer needed, the release signal can be asserted, causing the release pointer to be incremented along with the read pointer. Incrementing the release pointer frees up memory locations so that new data can be stored in them. Other embodiments may comprise multiple release pointers, multiple release signals, and multiple repeat signals.
Other embodiments of the present invention comprise an input signal, referred to herein as a switch signal. A switch signal causes the read pointer to switch values with a release pointer. That is, the read pointer takes on the value of the release pointer and the release pointer takes on the value of the read pointer. Switching values with a release pointer sets the read pointer to a location containing data already read and allows the read pointer to be utilized to reread the previously read data. In still other embodiments of the present invention, FIFO queues comprise multiple read pointers and an input signal for determining which read pointer is used to read data.
The present invention can be advantageously utilized, for example, in implementing certain programming constructs more efficiently than can be implemented using FIFO queues of the prior art. Looping constructs are an example of a programming construct that can be implemented efficiently using FIFO queues of the present invention.


REFERENCES:
patent: 5710943 (1998-01-01), Burton et al.
patent: 6172927 (2001-01-01), Taylor
patent: 6314478 (2001-11-01), Etcheverry

Affiliated with

Also associated with

Rating

Multi-access FIFO queue does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multi-access FIFO queue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-access FIFO queue will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3059387