Determining thresholds and wrap-around conditions in a first-in-first-out memory supporting a variety of read and write transaction sizes

• US 6,134,629 A
• Filed: 01/29/1998
• Issued: 10/17/2000
• Est. Priority Date: 01/29/1998
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: L'Ecuyer, Brian Peter
• Primary Examiner(s): Nguyen, Hiep T.
• Application Number:
  US09/015,415
• Time in Patent Office: 992 Days
• Field of Search: 711/110, 711/217, 711/218, 711/219, 710/52, 365/221
• US Class Current: 711/110
• CPC Class Codes: G06F 2205/126 Monitoring of intermediate fill level, i.e. with additional means for monitoring the fill level, e.g. half full flag, almost empty flag
• CPC Class Codes: G06F 5/12 Means for monitoring the fill level; Means for resolving contention, i.e. conflicts between simultaneous enqueue and dequeue operations
• CPC Class Codes: G06F 5/14 for overflow or underflow handling, e.g. full or empty flags

Abstract

Data is read from a first-in-first-out (FIFO) queue. A first condition flag is generated which indicates whether a read transaction of a first transaction size may be performed. When a write address for the FIFO queue is greater than a read address for the FIFO queue, the first condition flag is set to true when the read address plus the first transaction size is less than or equal to the write address. When the write address for the FIFO queue is less than the read address for the FIFO queue, the first condition flag is set to true when the read address plus the first transaction size is less than the write address plus a maximum depth of the FIFO queue. A first read transaction of the first transaction size from the FIFO queue is performed only when the first condition flag is true.

Claims

1. A method for transferring data in a first-in-first-out (FIFO) queue using a variety of transaction sizes, the method comprising the following steps:

(a) generating a plurality of condition flags, each condition flag indicating whether a read transaction of a particular transaction size may be performed, including the following substeps;

(a.1) generating a first condition flag that indicates when read transactions of a first transaction size may be performed, wherein the first transaction size does not equal zero, and,

(a.2) generating a second condition flag that indicates when read transactions of a second transaction size may be performed, wherein the second transaction size does not equal zero and does not equal the first transaction size; and

,

(b) implementing read transactions of the first transaction size to the FIFO queue but only when the first condition flag is true; and

,

(c) implementing read transactions of the second transaction size to the FIFO queue but only when the second condition flag is true.

2. A method as in claim 1 wherein step (a) additionally comprises the following substep:

(a.3) generating a third condition flag that indicates when read transactions of a third transaction size may be performed, wherein the third transaction size does not equal zero, does not equal the first transaction size and does not equal the second transaction size.

3. A method as in claim 2 additionally comprising the following step:

(d) implementing read transactions of the third transaction size to the FIFO queue but only when the third condition flag is true.

4. A method as in claim 1 wherein:

in substep (a.1);

when a write address for the FIFO queue is greater than a read address for the FIFO queue, setting the first condition flag to true when the read address plus the first transaction size is less than or equal to the write address, and

when the write address for the FIFO queue is less than the read address for the FIFO queue, setting the first condition flag to true when the read address plus the first transaction size is less than the write address plus a maximum depth of the FIFO queue; and

,

in substep (a.2)

when the write address for the FIFO queue is greater than the read address for the FIFO queue, setting the second condition flag to true when the read address plus the second transaction size is less than or equal to the write address, and

when the write address for the FIFO queue is less than the read address for the FIFO queue, setting the second condition flag to true when the read address plus the second transaction size is less than the write address plus the maximum depth of the FIFO queue.

5. A method for transferring data in a first-in-first-out (FIFO) queue using a variety of transaction sizes, the method comprising the following steps:

(a) generating a plurality of condition flags, each condition flag indicating whether a write transaction of a particular transaction size may be performed, including the following substeps;

(a.1) generating a first condition flag that indicates when write transactions of a first transaction size may be performed, wherein the first transaction size does not equal zero, and,

(a.2) generating a second condition flag that indicates when write transactions of a second transaction size may be performed, wherein the second transaction size does not equal zero and does not equal the first transaction size; and

,

(b) implementing write transactions of the first transaction size from the FIFO queue but only when the first condition flag is true; and

,

(c) implementing write transactions of the second transaction size from the FIFO queue but only when the second condition flag is true.

6. A method as in claim 5 wherein step (a) additionally comprises the following substep:

(a.3) generating a third condition flag that indicates when write transactions of a third transaction size may be performed, wherein the third transaction size does not equal zero, does not equal the first transaction size and does not equal the second transaction size.

7. A method as in claim 6 additionally comprising the following step:

(d) implementing write transactions of the third transaction size from the FIFO queue but only when the third condition flag is true.

8. A method as in claim 5 wherein:

in substep (a.1);

when a read address for the FIFO queue is greater than a write address for the FIFO queue, setting the first condition flag to true when the write address plus the first transaction size is less than or equal to the read address, and

when the read address for the FIFO queue is less than the write address for the FIFO queue, setting the first condition flag to true when the write address plus the first transaction size is less than the read address plus a maximum depth of the FIFO queue; and

,

in substep (a.2)

when the read address for the FIFO queue is greater than the write address for the FIFO queue, setting the second condition flag to true when the write address plus the second transaction size is less than or equal to the read address, and

when the read address for the FIFO queue is less than the write address for the FIFO queue, setting the second condition flag to true when the write address plus the second transaction size is less than the read address plus the maximum depth of the FIFO queue.

9. A method as in claim 5 additionally comprising the following steps:

(d) generating a plurality of read condition flags, each read condition flag indicating whether a read transaction of a particular transaction size may be performed, including the following substeps;

(d.1) generating the first read condition flag that indicates when read transactions of a first transaction size may be performed, wherein the first transaction size does not equal zero, and,

(d.2) generating a second read condition flag that indicates when read transactions of the second transaction size may be performed, wherein the second transaction size does not equal zero and does not equal the first transaction size; and

,

(e) implementing read transactions of the first transaction size to the FIFO queue but only when the first read condition flag is true; and

,

(f) implementing read transactions of the second transaction size to the FIFO queue but only when the second read condition flag is true.

10. A method as in claim 9 wherein step (d) additionally comprises the following substep:

(d.3) generating a third read condition flag that indicates when read transactions of a third transaction size may be performed, wherein the third transaction size does not equal zero, does not equal the first transaction size and does not equal the second transaction size.

11. A method as in claim 9 additionally comprising the following step:

(g) implementing read transactions of the third transaction size to the FIFO queue but only when the third read condition flag is true.