Patent US5717954A successfully refreshed from Google Patents.
US5717954A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Locked exchange FIFO
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1995-10-13
•
Granted: 1998-02-10
•
Expires: 2015-10-13
Abstract
Abstract A FIFO with locked exchange capability is disclosed. The FIFO has a memory for storing and retrieving data submissions, a write address generator and a read address generator for sequentially addressing the memory. A difference counter maintains the difference between the number of writes to the queue and reads from the queue. The net difference, as tracked by the counter is a measure of the FIFO utilization. To detect the queue full condition, a comparator compares the maximum FIFO stack depth against the counter output. The result of this comparison is latched and provided to a write strobe generator so that, in a subsequent write operation, if the FIFO is full, the write strobe from the producer is blocked and the data will not be written to the FIFO. Otherwise, the write strobe from the producer is passed to the memory. Additionally, a remaining space count is maintained in a status register. During operation, a bus master performing the read-modify-write cycle to the FIFO reads the status register to find the available space in the FIFO and immediately writes the data to the FIFO. If the read returns a zero, indicating that the FIFO is full, the bus master requeues the data for another read- modify-write cycle as it knows that the data has not been stored in the FIFO.
Inventors
- 👤 Thomas W. Grieff
- 👤 William C. Galloway
- 👤 Jeff M. Carlson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 12:55
CPC Classifications
G; G06; G06F; G06F5/00; G06F5/06; G06F5/10; G06F5/12; G06F5/14; G06F2205/00; G06F2205/12; G06F2205/123
Claims Analysis
Total Claims: 48
Claim 1
Independent Claim
238 words
A queue for sequentially storing data from a producer and providing said data to a consumer, said producer generating a write strobe signal, said consumer generating a read strobe signal, said queue comprising: a memory having a memory write strobe input for receiving a memory write strobe signal and a read strobe input for receiving said read strobe signal from said consumer, said memory storing data upon receipt of said memory write strobe signal, said memory providing data to said consumer upon receipt of said read strobe signal, said memory having a memory capacity; a memory full detector having a read input and a write input respectively coupled to said read strobe signal from said consumer and said write strobe signal from said producer and having a full output, said memory full detector asserting said full output when the difference between the number of said read and write strobe signal assertions equals said memory capacity; and a write enable generator having a write strobe input for receiving said write strobe signal from said producer, a full input coupled to said full output, and a write strobe output providing a write strobe signal connected to said memory write strobe input, said write enable generator blocking the write strobe signal from said producer to said memory when said full output is asserted and passing the write strobe signal from said producer to said memory when said full output is negated.
Claim 2
Dependent Claim
238 words
A queue for sequentially storing data from a producer and providing said data to a consumer, said producer generating a write strobe signal, said consumer generating a read strobe signal, said queue comprising: a memory having a memory write strobe input for receiving a memory write strobe signal and a read strobe input for receiving said read strobe signal from said consumer, said memory storing data upon receipt of said memory write strobe signal, said memory providing data to said consumer upon receipt of said read strobe signal, said memory having a memory capacity; a memory full detector having a read input and a write input respectively coupled to said read strobe signal from said consumer and said write strobe signal from said producer and having a full output, said memory full detector asserting said full output when the difference between the number of said read and write strobe signal assertions equals said memory capacity; and a write enable generator having a write strobe input for receiving said write strobe signal from said producer, a full input coupled to said full output, and a write strobe output providing a write strobe signal connected to said memory write strobe input, said write enable generator blocking the write strobe signal from said producer to said memory when said full output is asserted and passing the write strobe signal from said producer to said memory when said full output is negated.
Claim 3
Dependent Claim
105 words
The queue of claim 1, wherein said memory full detector further comprises: a difference counter having a read input and a write input respectively coupled to said read and write strobe signals, said difference counter having difference outputs for storing a difference value, said difference counter decrementing the difference outputs on each assertion of said read strobe signal and incrementing the difference outputs on each assertion of said write strobe signal; and a comparator having an input coupled to said difference outputs and having an output coupled to said full output, said comparator asserting said full output when said difference value equals said memory capacity.
Claim 4
Dependent Claim
18 words
The queue of claim 2, wherein said difference counter includes an adder/subtractor having an input preset to one.
Claim 5
Dependent Claim
56 words
The queue of claim 2, wherein said difference counter includes a subtractor having first inputs coupled to said memory capacity and second inputs coupled to said difference outputs, said subtractor having remaining space outputs for providing a remaining space signal, said subtractor subtracting said difference outputs from said memory capacity to generate said remaining space signal.
Claim 6
Dependent Claim
61 words
The queue of claim 4, wherein said producer generates a read strobe signal, the queue further comprising: a status register having a producer read input strobe for receiving said read strobe signal from said producer and status outputs for presenting a status signal, said status register presenting said status signal to said producer upon receipt of said producer read input strobe.
Claim 7
Dependent Claim
16 words
The queue of claim 5, wherein said status signal reflects the remaining space in said queue.
Claim 8
Dependent Claim
40 words
The queue of claim 5, wherein said memory and said status register are responsive to an address value and wherein said address values for write operations to said memory and for read operations from said status register are the same.
Claim 9
Dependent Claim
39 words
The queue of claim 5, wherein said write enable generator blocks said write strobe signal from said producer to said memory when said full output is asserted after said status register has presented said status signal to said producer.
Claim 10
Dependent Claim
39 words
The queue of claim 5, wherein said write enable generator passes said write strobe signal from said producer to said memory when said full output is negated after said status register has presented said status signal to said producer.
Claim 11
Dependent Claim
77 words
The queue of claim 1, wherein said memory has write address inputs for receiving a write address signal, the queue further comprising a write address generator having a write strobe input for receiving said write strobe signal and having write address outputs coupled to said write address inputs for providing a write address signal to said memory, said write address generator incrementing the value of said write address signal upon receipt of said memory write strobe signal.
Claim 12
Dependent Claim
76 words
The queue of claim 1, wherein said memory has read address inputs for receiving a read address signal, the queue further comprising a read address generator having a read strobe input for receiving said read strobe signal and having read address outputs coupled to said read address inputs for providing a read address signal to said memory, said read address generator incrementing the value of said read address signal upon receipt of said read strobe signal.
Claim 13
Dependent Claim
256 words
A computer system comprising: a producer generating a write strobe signal when providing data; a consumer generating a read strobe signal when requesting data; and a queue connected to said producer and said consumer, said queue sequentially storing data from said producer and providing data to said consumer, said queue including: a memory having a memory write strobe input for receiving a memory write strobe signal and a read strobe input for receiving said read strobe signal from said consumer, said memory storing data upon receipt of said memory write strobe signal, said memory providing data to said consumer upon receipt of said read strobe signal, said memory having a memory capacity; a memory full detector having a read input and a write input respectively coupled to said read strobe signal from said consumer and said write strobe signal from said producer and having a full output, said memory full detector asserting said full output when the difference between the number of said read and write strobe signal assertions equals said memory capacity; and a write enable generator having a write strobe input for receiving said write strobe signal from said producer, a full input coupled to said full output, and a write strobe output providing a write strobe signal connected to said memory write strobe input, said write enable generator blocking the write strobe signal from said producer to said memory when said full output is asserted and passing the write strobe signal from said producer to said memory when said full output is negated.
Claim 14
Dependent Claim
256 words
A computer system comprising: a producer generating a write strobe signal when providing data; a consumer generating a read strobe signal when requesting data; and a queue connected to said producer and said consumer, said queue sequentially storing data from said producer and providing data to said consumer, said queue including: a memory having a memory write strobe input for receiving a memory write strobe signal and a read strobe input for receiving said read strobe signal from said consumer, said memory storing data upon receipt of said memory write strobe signal, said memory providing data to said consumer upon receipt of said read strobe signal, said memory having a memory capacity; a memory full detector having a read input and a write input respectively coupled to said read strobe signal from said consumer and said write strobe signal from said producer and having a full output, said memory full detector asserting said full output when the difference between the number of said read and write strobe signal assertions equals said memory capacity; and a write enable generator having a write strobe input for receiving said write strobe signal from said producer, a full input coupled to said full output, and a write strobe output providing a write strobe signal connected to said memory write strobe input, said write enable generator blocking the write strobe signal from said producer to said memory when said full output is asserted and passing the write strobe signal from said producer to said memory when said full output is negated.
Claim 15
Dependent Claim
106 words
The computer system of claim 12, wherein said memory full detector further comprises: a difference counter having a read input and a write input respectively coupled to said read and write strobe signals, said difference counter having difference outputs for storing a difference value, said difference counter decrementing the difference outputs on each assertion of said read strobe signal and incrementing the difference outputs on each assertion of said write strobe signal; and a comparator having an input coupled to said difference outputs and having an output coupled to said full output, said comparator asserting said full output when said difference value equals said memory capacity.
Claim 16
Dependent Claim
19 words
The computer system of claim 13, wherein said difference counter includes an adder/subtractor having an input preset to one.
Claim 17
Dependent Claim
57 words
The computer system of claim 13, wherein said difference counter includes a subtractor having first inputs coupled to said memory capacity and second inputs coupled to said difference outputs, said subtractor having remaining space outputs for providing a remaining space signal, said subtractor subtracting said difference outputs from said memory capacity to generate said remaining space signal.
Claim 18
Dependent Claim
62 words
The computer system of claim 15, wherein said producer generates a read strobe signal, the queue further comprising: a status register having a producer read input strobe for receiving said read strobe signal from said producer and status outputs for presenting a status signal, said status register presenting said status signal to said producer upon receipt of said producer read input strobe.
Claim 19
Dependent Claim
17 words
The computer system of claim 16, wherein said status signal reflects the remaining space in said queue.
Claim 20
Dependent Claim
41 words
The computer system of claim 16, wherein said memory and said status register are responsive to an address value and wherein said address values for write operations to said memory and for read operations from said status register are the same.
Claim 21
Dependent Claim
40 words
The computer system of claim 16, wherein said write enable generator blocks said write strobe signal from said producer to said memory when said full output is asserted after said status register has presented said status signal to said producer.
Claim 22
Dependent Claim
40 words
The computer system of claim 16, wherein said write enable generator passes said write strobe signal from said producer to said memory when said full output is negated after said status register has presented said status signal to said producer.
Claim 23
Dependent Claim
78 words
The computer system of claim 12, wherein said memory has write address inputs for receiving a write address signal, the queue further comprising a write address generator having a write strobe input for receiving said write strobe signal and having write address outputs coupled to said write address inputs for providing a write address signal to said memory, said write address generator incrementing the value of said write address signal upon receipt of said memory write strobe signal.
Claim 24
Dependent Claim
77 words
The computer system of claim 12, wherein said memory has read address inputs for receiving a read address signal, the queue further comprising a read address generator having a read strobe input for receiving said read strobe signal and having read address outputs coupled to said read address inputs for providing a read address signal to said memory, said read address generator incrementing the value of said read address signal upon receipt of said read strobe signal.
Claim 25
Dependent Claim
257 words
A disk controller comprising: a producer generating a write strobe signal when providing data; a consumer generating a read strobe signal when requesting data; and a queue connected to said producer and said consumer, said queue sequentially storing data from said producer and providing said data to said consumer, said queue including: a memory having a memory write strobe input for receiving a memory write strobe signal and a read strobe input for receiving said read strobe signal from said consumer, said memory storing data upon receipt of said memory write strobe signal, said memory providing data to said consumer upon receipt of said read strobe signal, said memory having a memory capacity; a memory full detector having a read input and a write input respectively coupled to said read strobe signal from said consumer and said write strobe signal from said producer and having a full output, said memory full detector asserting said full output when the difference between the number of said read and write strobe signal assertions equals said memory capacity; and a write enable generator having a write strobe input for receiving said write strobe signal from said producer, a full input coupled to said full output, and a write strobe output providing a write strobe signal connected to said memory write strobe input, said write enable generator blocking the write strobe signal from said producer to said memory when said full output is asserted and passing the write strobe signal from said producer to said memory when said full output is negated.
Claim 26
Dependent Claim
257 words
A disk controller comprising: a producer generating a write strobe signal when providing data; a consumer generating a read strobe signal when requesting data; and a queue connected to said producer and said consumer, said queue sequentially storing data from said producer and providing said data to said consumer, said queue including: a memory having a memory write strobe input for receiving a memory write strobe signal and a read strobe input for receiving said read strobe signal from said consumer, said memory storing data upon receipt of said memory write strobe signal, said memory providing data to said consumer upon receipt of said read strobe signal, said memory having a memory capacity; a memory full detector having a read input and a write input respectively coupled to said read strobe signal from said consumer and said write strobe signal from said producer and having a full output, said memory full detector asserting said full output when the difference between the number of said read and write strobe signal assertions equals said memory capacity; and a write enable generator having a write strobe input for receiving said write strobe signal from said producer, a full input coupled to said full output, and a write strobe output providing a write strobe signal connected to said memory write strobe input, said write enable generator blocking the write strobe signal from said producer to said memory when said full output is asserted and passing the write strobe signal from said producer to said memory when said full output is negated.
Claim 27
Dependent Claim
106 words
The disk controller of claim 23, wherein said memory full detector further comprises: a difference counter having a read input and a write input respectively coupled to said read and write strobe signals, said difference counter having difference outputs for storing a difference value, said difference counter decrementing the difference outputs on each assertion of said read strobe signal and incrementing the difference outputs on each assertion of said write strobe signal; and a comparator having an input coupled to said difference outputs and having an output coupled to said full output, said comparator asserting said full output when said difference value equals said memory capacity.
Claim 28
Dependent Claim
19 words
The disk controller of claim 24, wherein said difference counter includes an adder/subtractor having an input preset to one.
Claim 29
Dependent Claim
57 words
The disk controller of claim 24, wherein said difference counter includes a subtractor having first inputs coupled to said memory capacity and second inputs coupled to said difference outputs, said subtractor having remaining space outputs for providing a remaining space signal, said subtractor subtracting said difference outputs from said memory capacity to generate said remaining space signal.
Claim 30
Dependent Claim
62 words
The disk controller of claim 26, wherein said producer generates a read strobe signal, the queue further comprising: a status register having a producer read input strobe for receiving said read strobe signal from said producer and status outputs for presenting a status signal, said status register presenting said status signal to said producer upon receipt of said producer read input strobe.
Claim 31
Dependent Claim
17 words
The disk controller of claim 27, wherein said status signal reflects the remaining space in said queue.
Claim 32
Dependent Claim
41 words
The disk controller of claim 27, wherein said memory and said status register are responsive to an address value and wherein said address values for write operations to said memory and for read operations from said status register are the same.
Claim 33
Dependent Claim
40 words
The disk controller of claim 27, wherein said write enable generator blocks said write strobe signal from said producer to said memory when said full output is asserted after said status register has presented said status signal to said producer.
Claim 34
Dependent Claim
40 words
The disk controller of claim 27, wherein said write enable generator passes said write strobe signal from said producer to said memory when said full output is negated after said status register has presented said status signal to said producer.
Claim 35
Dependent Claim
78 words
The disk controller of claim 23, wherein said memory has write address inputs for receiving a write address signal, the queue further comprising a write address generator having a write strobe input for receiving said write strobe signal and having write address outputs coupled to said write address inputs for providing a write address signal to said memory, said write address generator incrementing the value of said write address signal upon receipt of said memory write strobe signal.
Claim 36
Dependent Claim
77 words
The disk controller of claim 23, wherein said memory has read address inputs for receiving a read address signal, the queue further comprising a read address generator having a read strobe input for receiving said read strobe signal and having read address outputs coupled to said read address inputs for providing a read address signal to said memory, said read address generator incrementing the value of said read address signal upon receipt of said read strobe signal.
Claim 37
Independent Claim
121 words
A method for sequentially storing data from a producer into a memory, said memory having a write strobe input for receiving a write strobe signal, said memory storing data upon receipt of said write strobe signal, said method comprising the steps of: receiving a status read from said producer to said memory; determining an available space count associated with said memory and providing said available space count to said producer in response to said status read; receiving write data and a write strobe signal from said producer; and blocking said write strobe signal from said memory when said available space count is zero and otherwise passing the write strobe signal from said producer to said memory to store said write data.
Claim 38
Independent Claim
121 words
A method for sequentially storing data from a producer into a memory, said memory having a write strobe input for receiving a write strobe signal, said memory storing data upon receipt of said write strobe signal, said method comprising the steps of: receiving a status read from said producer to said memory; determining an available space count associated with said memory and providing said available space count to said producer in response to said status read; receiving write data and a write strobe signal from said producer; and blocking said write strobe signal from said memory when said available space count is zero and otherwise passing the write strobe signal from said producer to said memory to store said write data.
Claim 39
Dependent Claim
19 words
The method of claim 34, wherein said determining step further comprises the step of latching said available space count.
Claim 40
Dependent Claim
41 words
The method of claim 34, wherein said receiving a status read step and said receiving write data and a write strobe signal step are responsive to an address value and wherein said address values for said receiving steps are the same.
Claim 41
Dependent Claim
45 words
The method of claim 34, wherein said memory has a read strobe input for receiving a read strobe signal, the method further comprising the step of providing said data from said memory to a consumer upon receipt of a read strobe signal from said consumer.
Claim 42
Dependent Claim
52 words
The method of claim 37, wherein said memory has a memory capacity and wherein said determining step further comprises the steps of: counting a difference between said read strobe signal assertion and said write strobe signal assertion; comparing said difference with said memory capacity; and latching the result of said comparing step.
Claim 43
Dependent Claim
27 words
The method of claim 38, wherein said determining step further comprises the step of subtracting said difference from said memory capacity to generate said available space count.
Claim 44
Dependent Claim
37 words
The method of claim 34, wherein said memory has write address inputs for receiving a write address signal, the method further comprising the step of incrementing said write address signal upon receipt of said write strobe signal.
Claim 45
Dependent Claim
37 words
The method of claim 34, wherein said memory has read address inputs for receiving a read address signal, the method further comprising the step of incrementing said read address signal upon receipt of said read strobe signal.
Claim 46
Independent Claim
78 words
A method for sequentially storing data from a producer into a locked exchange memory, said method comprising the steps of: reading an available space count from said locked exchange memory; immediately writing said data to said locked exchange memory; and determining whether said locked exchange memory has accepted said data, wherein said reading and immediately writing steps are responsive to an address value and wherein said address values for said reading and immediately writing steps are the same.
Claim 47
Independent Claim
78 words
A method for sequentially storing data from a producer into a locked exchange memory, said method comprising the steps of: reading an available space count from said locked exchange memory; immediately writing said data to said locked exchange memory; and determining whether said locked exchange memory has accepted said data, wherein said reading and immediately writing steps are responsive to an address value and wherein said address values for said reading and immediately writing steps are the same.
Claim 48
Dependent Claim
21 words
The method of claim 42, wherein said determining step further comprises the step of comparing said available space count with zero.
References Cited (Backward Citations)
US4298954A
Cited
US4449182A
Cited
US4449182B1
Cited
US4486854A
Cited
US4922437A
Cited
EP0312239A2
Cited
US4873666A
Cited
US4942553A
Cited
US5280584A
Cited
US5276847A
Cited
US5241630A
Cited
US5295246A
Cited
EP0537397A1
Cited
US5390299A
Cited
US5450546A
Cited
US5561823A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-02-09 | 2001-08-11 | 2002-02-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-02-09 | 2005-08-11 | 2006-02-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-02-09 | 2009-08-11 | 2010-02-10 | $7700.00 | Window Closed / Lapsed |