Byte-writable two-dimensional FIFO buffer having storage locations with fields indicating storage location availability and data ordering

• US 5,974,516 A
• Filed: 10/18/1996
• Issued: 10/26/1999
• Est. Priority Date: 10/18/1996
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Qureshi, Amjad Z.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Lee, Felix B.
• Application Number:
  US08/733,510
• Time in Patent Office: 1,103 Days
• Field of Search: 711/171, 711/172, 711/156, 711/170, 711/154, 711/158, 395/872, 395/873, 395/874, 395/875, 395/876
• US Class Current: 711/171
• CPC Class Codes: G06F 5/065 Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's

Abstract

A FIFO storage circuit stores data transferred over a data bus in data groups having of one or more data units. The FIFO buffer includes a number of storage locations each configured to store a single unit of data. Each data groups on the data bus is accompanied by data-size information. A storage-location availability decoder receives the data-size information and allocates a number of consecutive storage locations in the FIFO storage circuit to allow for storage of the incoming data group. The FIFO then stores each unit of the data group, along with a data tag common to each unit, in consecutive storage locations. The next stored data group is then assigned a new data tag. The FIFO storage circuit reads from the storage locations in order of data tag. Checking consecutive storage locations for equivalent data tags enables the FIFO storage circuit to output the appropriate number of units for each data group. Further, assigning unique sequential data tags to each data group allows the FIFO storage circuit to read the contents of FIFO buffer 200 in the appropriate order.

Claims

1. A first-in-first-out (FIFO) buffer for storing data received over a data bus, wherein the data are transferred in data groups including at least one unit of data, the FIFO buffer comprising:

a plurality of storage locations, each of the storage locations being connected the data bus and configured to store one data unit, wherein each of the storage location comprises a first storage area for an associated data unit, a second storage area for a valid flag indicating whether the storage location contains valid data, and a third storage area for a data tag indicating an order of storage of the associated data unit relative to other data units in the storage locations; and

a write control circuit comprising;

a data-group size decoder connected to receive information indicating a number of data units in a data group to be written to the storage locations during a write operation; and

a write pointer generator connected to the storage locations and to the data-group size decoder, the write pointer generator selecting a group of one or more the storage locations to which the data group is written during the write operation, wherein the write pointer generator selects the group according to valid flags in the storage locations and permits selection of the storage locations having address that do not reflect an order of storage of the data group relative to other data groups in the FIFO buffer.

2. The FIFO buffer of claim 1, wherein:

the write control circuit further comprises a data-tag generator that generates a data tag for the write operation; and

the write control circuit writes the data tag to the third storage area of each storage location to which a data unit of the data group is written.

3. The FIFO buffer of claim 2, wherein the data-tag generator comprises a counter that counts each time the write control circuit writes a data group, a count from the counter being the data tag from the data-tag generator.

4. The FIFO buffer of claim 1, wherein the write pointer generator selects as the group of storage locations, a first encountered set of consecutive storage locations that is sufficient to store a data group of the number of data units indicated to the a data-group size decoder.

5. The FIFO buffer of claim 1, wherein the write control circuit further comprises logic that decodes valid flags from the storage locations to determine whether the FIFO buffer is full and asserts a full flag if all of the storage location contain valid data.

6. The FIFO buffer of claim 1, further comprising a read control circuit connected to the storage locations, the read control circuit being configured to locate the storage locations which contains a demanded data group and to read the storage location located, wherein the read control circuit locates the storage locations by comparing data tags of storage locations containing valid data to a data tag for a preceding read operation.

7. The FIFO buffer of claim 6, wherein the read control circuit locates and reads the data group by performing a read operation including the sequential steps of:

(a) checking a storage location that a read pointer identifies;

(b) if the checked storage location contains invalid data or a data tag that does not immediately follow a data tag for a preceding read operation, incrementing the read pointer and returning to step (a);

(c) if the checked storage location contains valid data and a data tag that immediately follows the data tag for the preceding read operation, reading the data from the checked storage location and incrementing the read pointer;

(d) checking a storage location that the read pointer identifies;

(e) if the checked storage location contains valid data and a data tag that immediately follows the data tag for the preceding read operation, reading the data from the checked storage location, incrementing the read pointer, and returning to step (d); and

(f) if the checked storage location contains invalid data or a data tag that does not immediately follow the data tag for the preceding read operation, outputting a data group containing the data read during preceding steps of the read operation.

8. A first-in-first-out (FIFO) buffer comprising:

a plurality of storage locations, each of the storage locations comprising a first field for storage of a unit of data, a second field for a valid flag indicating whether the first field contains valid data, and a third field for a tag indicating when data was stored in the first field;

a write control circuit coupled to use the valid flags from the second fields of the storage locations when selecting storage locations for a write operation; and

a read control circuit coupled to use the tags from the third fields of the storage locations when selecting storage locations for a read operation.

9. The FIFO buffer of claim 8, wherein the write control circuit includes a counter that provides a count that the write control circuit writes to the second fields of the storage locations selected for a write operation, the counter incrementing the count after each write operation.

10. The FIFO buffer of claim 8, wherein the write control circuit is capable of selecting storage locations for a write even when addresses of the storage locations selected do not indicate a relative order in which data was written.

11. A method for operating a first-in-first-out (FIFO) buffer, comprising:

providing in the buffer a plurality of storage locations, each of the storage locations comprising a first field for storage of a data unit, a second field for a valid flag indicating whether the first field contains valid data, and a third field for a tag indicating when data was stored in the first field;

receiving a data group to be written to the buffer;

determining a number of storage locations required for storage of the data group;

checking the second fields of storage locations in the buffer to identify storage locations for storage of the data group, wherein the valid flag in the second field of each identified storage location indicates that the first field of the identified storage location does not store valid data;

writing data units from data group in the first fields of the identified storage locations;

setting the valid flags in the second fields of the identified storage locations to indicate the first fields of the identified storage locations contain valid data; and

writing a tag value to all of the third fields of the identified storage locations.

12. The method of claim 11, wherein determining the number of storage locations required comprises inspecting a group size of an incoming data group to determine whether the incoming data group is one, two or four data units long.