US5809280A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive ahead FIFO with LRU replacement
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1995-10-13
•
Granted: 1998-09-15
•
Expires: 2015-10-13
Abstract
Abstract A plurality of read-ahead FIFOs, each with an LRU replacement policy, is provided for enhancing buffer performance. The FIFO contains a plurality of adaptive buffer replacement counters to monitor usage statistics of the FIFOs and to identify one of the FIFOs as a refill candidate buffer in the event of a miss which requires new data to be brought into one of the FIFOs. Each FIFO has a hit detector and a flush detector for comparing the address of a data request from the bus master with the address stored by each buffer for indicating FIFO hit or invalidate operations. Each FIFO also has a buffer selector to provide data from the buffer selected by the hit detector to the bus master if the selected FIFO buffer has not been invalidated by the invalidate address comparator. The buffer selector otherwise transferring the requested data from the memory to the refill candidate buffer and presenting new data from the refill candidate buffer to the bus master. The FIFO has an invalidate address comparator coupled to the memory and the FIFOs to compares write addresses to the memory with each address of each FIFO to invalidate the FIFO buffer whose address tag matches the invalidate address to ensure data coherency.
Inventors
- 👤 Gary F. Chard
- 👤 William C. Galloway
- 👤 Ryan A. Callison
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:31
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/76; G06F7/78; G06F12/00; G06F12/02; G06F12/08; G06F12/12; G06F12/121; G06F12/123; G06F12/125
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
375 words
A read-ahead buffer for buffering data requests from a consumer to a memory, said consumer having address outputs for issuing an address request and consumer data inputs to receive data responsive to said address request, said memory having memory read control inputs for reading from said memory, memory address inputs and memory data outputs, said read-ahead buffer comprising: a plurality of FIFO buffers, each of said FIFO buffers having data inputs coupled to said memory data outputs for storing data from said memory, data outputs coupled to said consumer data inputs for providing data to said consumer, address inputs coupled to said consumer address outputs for storing an address range, address outputs for presenting said address range, and having buffer control inputs for reading and writing data to said FIFO buffers; a hit detector having address inputs coupled to said FIFO buffer address outputs and to said consumer address outputs, said hit detector having control outputs coupled to said buffer control inputs and having a miss output, said hit detector comparing said address request from said consumer with said FIFO buffer address ranges, said hit detector asserting said buffer control inputs to provide data from said FIFO buffer whose address range matches said address request to said consumer and otherwise asserting said miss output; a flush detector coupled to said hit detector and said buffers, said flush detector causing the buffer selected by said hit detector to be flushed if the data in said buffer has been invalidated; and a miss controller having a miss input coupled to said miss output, buffer control outputs coupled to said FIFO buffer control inputs, address inputs coupled to said consumer address output, memory read control outputs coupled to said memory read control inputs, and memory address outputs coupled to said memory address inputs, said miss controller responding to said miss output assertion by selecting a candidate buffer from one of said FIFO buffers, providing said address request to said memory address input, asserting said memory read control outputs and said buffer control outputs to transfer data associated with said address request from said memory into said candidate buffer and to update said candidate buffer address range, and providing the requested data to said consumer from said candidate buffer.
Claim 2
Dependent Claim
375 words
A read-ahead buffer for buffering data requests from a consumer to a memory, said consumer having address outputs for issuing an address request and consumer data inputs to receive data responsive to said address request, said memory having memory read control inputs for reading from said memory, memory address inputs and memory data outputs, said read-ahead buffer comprising: a plurality of FIFO buffers, each of said FIFO buffers having data inputs coupled to said memory data outputs for storing data from said memory, data outputs coupled to said consumer data inputs for providing data to said consumer, address inputs coupled to said consumer address outputs for storing an address range, address outputs for presenting said address range, and having buffer control inputs for reading and writing data to said FIFO buffers; a hit detector having address inputs coupled to said FIFO buffer address outputs and to said consumer address outputs, said hit detector having control outputs coupled to said buffer control inputs and having a miss output, said hit detector comparing said address request from said consumer with said FIFO buffer address ranges, said hit detector asserting said buffer control inputs to provide data from said FIFO buffer whose address range matches said address request to said consumer and otherwise asserting said miss output; a flush detector coupled to said hit detector and said buffers, said flush detector causing the buffer selected by said hit detector to be flushed if the data in said buffer has been invalidated; and a miss controller having a miss input coupled to said miss output, buffer control outputs coupled to said FIFO buffer control inputs, address inputs coupled to said consumer address output, memory read control outputs coupled to said memory read control inputs, and memory address outputs coupled to said memory address inputs, said miss controller responding to said miss output assertion by selecting a candidate buffer from one of said FIFO buffers, providing said address request to said memory address input, asserting said memory read control outputs and said buffer control outputs to transfer data associated with said address request from said memory into said candidate buffer and to update said candidate buffer address range, and providing the requested data to said consumer from said candidate buffer.
Claim 3
Dependent Claim
231 words
The read-ahead buffer of claim 1, wherein each of said FIFO buffers includes: a data storage memory having a predetermined capacity, a write strobe input for receiving a write request, a write address input for receiving a write address value, a read strobe input for receiving a read request and a read address input for receiving a read address value; a write address generator having a write address output coupled to said write address input of said data storage memory, said write address generator incrementing said write address value after each write strobe assertion to said data storage memory; a read address generator having a read address output coupled to said read address input of said data storage memory, said read address generator incrementing said read address value after each read strobe assertion to said data storage memory; a difference counter having a read input coupled to said read strobe input, a write input coupled to said write strobe input, and a difference output for storing a difference value, said difference counter incrementing said difference value upon each write request to said data storage memory and decrementing said difference value upon each read request from said data storage memory; and a full indicator having an input coupled to said difference output of said difference counter, said full indicator being asserted when said difference value equals said predetermined capacity and deasserted otherwise.
Claim 4
Dependent Claim
66 words
The read-ahead buffer of claim 2, wherein said read address generator further includes: a register having an input for receiving a next read address value and an output for presenting said read address value; and an incrementer having an input coupled to said register output and an output coupled to said register input to increment said read address value upon a read of said FIFO buffer.
Claim 5
Dependent Claim
66 words
The read-ahead buffer of claim 2, wherein said write address generator further includes: a register having an input for receiving a next write address value and an output for presenting said write address value; and an incrementer having an input coupled to said register output and an output coupled to said register input to increment said write address value upon a write of said FIFO buffer.
Claim 6
Dependent Claim
13 words
The read-ahead buffer of claim 2, wherein said full indicator is a comparator.
Claim 7
Dependent Claim
31 words
The read-ahead buffer of claim 1, wherein said hit detector is a comparator having inputs respectively coupled to said address request and said address range of one of said FIFO buffers.
Claim 8
Dependent Claim
62 words
The read-ahead buffer of claim 1, wherein said miss controller further comprises a plurality of adaptive buffer replacement counters, each of said counters respectively coupled to each of said FIFO buffers, said counters monitoring usage statistics of said FIFO buffers and generating an active LRU value to identify said candidate buffer from one of said FIFO buffers based on said usage statistics.
Claim 9
Dependent Claim
29 words
The read-ahead buffer of claim 7, wherein each of said plurality of adaptive buffer replacement counters corresponding to each of said FIFO buffers is a least recently used counter.
Claim 10
Dependent Claim
65 words
The read-ahead buffer of claim 8, wherein said least recently used counter includes: a register having an output for holding a current LRU value; and a comparator having inputs coupled to said register output and said active LRU value, said comparator setting said register output to a predetermined maximum if said active LRU value equals said current LRU value and otherwise decrementing said register output.
Claim 11
Dependent Claim
35 words
The read-ahead buffer of claim 1, further comprising a bus snooper for monitoring bus write addresses of write operations to said memory and invalidating the FIFO buffer whose address range matches said bus write address.
Claim 12
Dependent Claim
31 words
The read-ahead buffer of claim 10, wherein said bus snooper includes a comparator having inputs respectively coupled to said address request and said address range of one of said FIFO buffers.
Claim 13
Dependent Claim
319 words
A read-ahead buffer comprising: a bus master; a main memory; a plurality of buffers coupled to said bus master and said memory, each of said buffers having a data block and an address associated with said data block, said data block mirroring said memory at said data block address; an invalidate address comparator coupled to said memory and said buffers, said invalidate address comparator receiving an invalidate address from said memory, said invalidate address comparator comparing the invalidate address with the address of each buffer and invalidating the buffer bearing the address matching the invalidate address; a plurality of adaptive buffer replacement counters, each of said counters respectively coupled to each of said buffers, said counters monitoring usage statistics of said buffers and identifying one of said buffers as a refill candidate buffer based on said usage statistics; a hit detector coupled to said buffers and said counters, said hit detector receiving the address of a data request from the bus master and comparing the address of each of said buffers with the address of the bus master data request, said hit detector asserting a hit output corresponding to one of said buffers if the request from the bus master is contained in said buffers; a flush detector coupled to said hit detector, to said buffers and to said counters, said flush detector causing the buffer selected by said hit detector to be flushed if said buffer has been invalidated by said invalidate address comparator; and a buffer selector coupled to said buffers, to said hit detector, to said flush detector and to said counters, said buffer selector coupling the buffer selected by said hit detector to said bus master if said selected buffer has not been invalidated by said invalidate address comparator, said buffer selector otherwise transferring the requested data from said memory to said refill candidate buffer and coupling said refill candidate buffer to said bus master.
Claim 14
Dependent Claim
319 words
A read-ahead buffer comprising: a bus master; a main memory; a plurality of buffers coupled to said bus master and said memory, each of said buffers having a data block and an address associated with said data block, said data block mirroring said memory at said data block address; an invalidate address comparator coupled to said memory and said buffers, said invalidate address comparator receiving an invalidate address from said memory, said invalidate address comparator comparing the invalidate address with the address of each buffer and invalidating the buffer bearing the address matching the invalidate address; a plurality of adaptive buffer replacement counters, each of said counters respectively coupled to each of said buffers, said counters monitoring usage statistics of said buffers and identifying one of said buffers as a refill candidate buffer based on said usage statistics; a hit detector coupled to said buffers and said counters, said hit detector receiving the address of a data request from the bus master and comparing the address of each of said buffers with the address of the bus master data request, said hit detector asserting a hit output corresponding to one of said buffers if the request from the bus master is contained in said buffers; a flush detector coupled to said hit detector, to said buffers and to said counters, said flush detector causing the buffer selected by said hit detector to be flushed if said buffer has been invalidated by said invalidate address comparator; and a buffer selector coupled to said buffers, to said hit detector, to said flush detector and to said counters, said buffer selector coupling the buffer selected by said hit detector to said bus master if said selected buffer has not been invalidated by said invalidate address comparator, said buffer selector otherwise transferring the requested data from said memory to said refill candidate buffer and coupling said refill candidate buffer to said bus master.
Claim 15
Dependent Claim
230 words
The read-ahead buffer of claim 12, wherein each of said buffers includes: a data storage memory having a predetermined capacity, a write strobe input for receiving a write request, a write address input for receiving a write address value, a read strobe input for receiving a read request and a read address input for receiving a read address value; a write address generator having a write address output coupled to said write address input of said data storage memory, said write address generator incrementing said write address value after each write strobe assertion to said data storage memory; a read address generator having a read address output coupled to said read address input of said data storage memory, said read address generator incrementing said read address value after each read strobe assertion to said data storage memory; a difference counter having a read input coupled to said read strobe input, a write input coupled to said write strobe input, and a difference output for storing a difference value, said difference counter incrementing said difference value upon each write request to said data storage memory and decrementing said difference value upon each read request from said data storage memory; and a full indicator having an input coupled to said difference output of said difference counter, said full indicator being asserted when said difference value equals said predetermined capacity and deasserted otherwise.
Claim 16
Dependent Claim
29 words
The read-ahead buffer of claim 12, wherein each of said plurality of adaptive buffer replacement counters corresponding to each of said FIFO buffers is a least recently used counter.
Claim 17
Dependent Claim
65 words
The read-ahead buffer of claim 14, wherein said least recently used counter includes: a register having an output for holding a current LRU value; and a comparator having inputs coupled to said register output and said active LRU value, said comparator setting said register output to a predetermined maximum if said active LRU value equals said current LRU value and otherwise decrementing said register output.
Claim 18
Dependent Claim
35 words
The read-ahead buffer of claim 12, further comprising a bus snooper for monitoring bus write addresses of write operations to said memory and invalidating the FIFO buffer whose address range matches said bus write address.
Claim 19
Dependent Claim
365 words
A computer system, comprising: a processor; a display coupled to said processor; a disk drive consumer having address outputs for issuing an address request and consumer data inputs to receive data responsive to said address request; a memory having memory read control inputs for reading from said memory, memory address inputs and memory data outputs for providing data responsive to said memory address inputs; and a read-ahead buffer for buffering data requests from said consumer to said memory, said read-ahead buffer including: a plurality of FIFO buffers, each of said FIFO buffers having data inputs coupled to said memory data outputs for storing data from said memory, data outputs coupled to said consumer data inputs for providing data to said consumer, address inputs coupled to said consumer address outputs for storing an address range, address outputs for presenting said address range, and having buffer control inputs for reading and writing data to said FIFO buffers; a hit detector having address inputs coupled to said FIFO buffer address outputs and to said consumer address outputs, said hit detector having control outputs coupled to said buffer control inputs and having a miss output, said hit detector comparing said address request from said consumer with said FIFO buffer address ranges, said hit detector asserting said buffer control inputs to provide data from said FIFO buffer whose address range matches said address request to said consumer and otherwise asserting said miss output; and a miss controller having a miss input coupled to said miss output, buffer control outputs coupled to said FIFO buffer control inputs, address inputs coupled to said consumer address output, memory read control outputs coupled to said memory read control inputs, and memory address outputs coupled to said memory address inputs, said miss controller responding to said miss output assertion by selecting a candidate buffer from one of said FIFO buffers, providing said address request to said memory address input, asserting said memory read control outputs and said buffer control outputs to transfer data associated with said address request from said memory into said candidate buffer and to update said candidate buffer address range, and providing the requested data to said consumer from said candidate buffer.
Claim 20
Dependent Claim
365 words
A computer system, comprising: a processor; a display coupled to said processor; a disk drive consumer having address outputs for issuing an address request and consumer data inputs to receive data responsive to said address request; a memory having memory read control inputs for reading from said memory, memory address inputs and memory data outputs for providing data responsive to said memory address inputs; and a read-ahead buffer for buffering data requests from said consumer to said memory, said read-ahead buffer including: a plurality of FIFO buffers, each of said FIFO buffers having data inputs coupled to said memory data outputs for storing data from said memory, data outputs coupled to said consumer data inputs for providing data to said consumer, address inputs coupled to said consumer address outputs for storing an address range, address outputs for presenting said address range, and having buffer control inputs for reading and writing data to said FIFO buffers; a hit detector having address inputs coupled to said FIFO buffer address outputs and to said consumer address outputs, said hit detector having control outputs coupled to said buffer control inputs and having a miss output, said hit detector comparing said address request from said consumer with said FIFO buffer address ranges, said hit detector asserting said buffer control inputs to provide data from said FIFO buffer whose address range matches said address request to said consumer and otherwise asserting said miss output; and a miss controller having a miss input coupled to said miss output, buffer control outputs coupled to said FIFO buffer control inputs, address inputs coupled to said consumer address output, memory read control outputs coupled to said memory read control inputs, and memory address outputs coupled to said memory address inputs, said miss controller responding to said miss output assertion by selecting a candidate buffer from one of said FIFO buffers, providing said address request to said memory address input, asserting said memory read control outputs and said buffer control outputs to transfer data associated with said address request from said memory into said candidate buffer and to update said candidate buffer address range, and providing the requested data to said consumer from said candidate buffer.
Claim 21
Dependent Claim
231 words
The computer system of claim 17, wherein each of said FIFO buffers includes: a data storage memory having a predetermined capacity, a write strobe input for receiving a write request, a write address input for receiving a write address value, a read strobe input for receiving a read request and a read address input for receiving a read address value; a write address generator having a write address output coupled to said write address input of said data storage memory, said write address generator incrementing said write address value after each write strobe assertion to said data storage memory; a read address generator having a read address output coupled to said read address input of said data storage memory, said read address generator incrementing said read address value after each read strobe assertion to said data storage memory; a difference counter having a read input coupled to said read strobe input, a write input coupled to said write strobe input, and a difference output for storing a difference value, said difference counter incrementing said difference value upon each write request to said data storage memory and decrementing said difference value upon each read request from said data storage memory; and a full indicator having an input coupled to said difference output of said difference counter, said full indicator being asserted when said difference value equals said predetermined capacity and deasserted otherwise.
Claim 22
Dependent Claim
66 words
The computer system of claim 18, wherein said read address generator further includes: a register having an input for receiving a next read address value and an output for presenting said read address value; and an incrementer having an input coupled to said register output and an output coupled to said register input to increment said read address value upon a read of said FIFO buffer.
Claim 23
Dependent Claim
66 words
The computer system of claim 18, wherein said write address generator further includes: a register having an input for receiving a next write address value and an output for presenting said write address value; and an incrementer having an input coupled to said register output and an output coupled to said register input to increment said write address value upon a write of said FIFO buffer.
Claim 24
Dependent Claim
13 words
The computer system of claim 18, wherein said full indicator is a comparator.
Claim 25
Dependent Claim
31 words
The computer system of claim 17, wherein said hit detector is a comparator having inputs respectively coupled to said address request and said address range of one of said FIFO buffers.
Claim 26
Dependent Claim
62 words
The computer system of claim 17, wherein said miss controller further comprises a plurality of adaptive buffer replacement counters, each of said counters respectively coupled to each of said FIFO buffers, said counters monitoring usage statistics of said FIFO buffers and generating an active LRU value to identify said candidate buffer from one of said FIFO buffers based on said usage statistics.
Claim 27
Dependent Claim
29 words
The computer system of claim 23, wherein each of said plurality of adaptive buffer replacement counters corresponding to each of said FIFO buffers is a least recently used counter.
Claim 28
Dependent Claim
65 words
The computer system of claim 24, wherein said least recently used counter includes: a register having an output for holding a current LRU value; and a comparator having inputs coupled to said register output and said active LRU value, said comparator setting said register output to a predetermined maximum if said active LRU value equals said current LRU value and otherwise decrementing said register output.
Claim 29
Dependent Claim
35 words
The computer system of claim 17, further comprising a bus snooper for monitoring bus write addresses of write operations to said memory and invalidating the FIFO buffer whose address range matches said bus write address.
Claim 30
Dependent Claim
31 words
The computer system of claim 26, wherein said bus snooper includes a comparator having inputs respectively coupled to said address request and said address range of one of said FIFO buffers.
Claim 31
Independent Claim
178 words
A method for buffering data requests from a consumer to a memory, said consumer issuing an address request to retrieve data stored in said memory, said data buffered in a plurality of FIFO buffers coupled to said consumer and said memory, each of said FIFO buffers storing data and an address range associated with said data, said method comprising the steps of: comparing said address request from said consumer with said FIFO buffer address ranges and providing data from said FIFO buffer whose address range matches said address request to said consumer; flushing the buffer with the matching address if the data in said buffer has been invalidated; and when none of said address ranges matches said address request or when the buffer with the matching address has been flushed, requesting data from said memory, further including the steps of: selecting a candidate buffer from one of said FIFO buffers; transferring data associated with said address request from said memory into said candidate buffer; updating said candidate buffer address range; and providing the requested data to said consumer.
Claim 32
Independent Claim
178 words
A method for buffering data requests from a consumer to a memory, said consumer issuing an address request to retrieve data stored in said memory, said data buffered in a plurality of FIFO buffers coupled to said consumer and said memory, each of said FIFO buffers storing data and an address range associated with said data, said method comprising the steps of: comparing said address request from said consumer with said FIFO buffer address ranges and providing data from said FIFO buffer whose address range matches said address request to said consumer; flushing the buffer with the matching address if the data in said buffer has been invalidated; and when none of said address ranges matches said address request or when the buffer with the matching address has been flushed, requesting data from said memory, further including the steps of: selecting a candidate buffer from one of said FIFO buffers; transferring data associated with said address request from said memory into said candidate buffer; updating said candidate buffer address range; and providing the requested data to said consumer.
Claim 33
Dependent Claim
30 words
The method of claim 28, wherein said comparing step further includes the steps of maintaining an active LRU value to identify an active buffer from one of said FIFO buffers.
Claim 34
Dependent Claim
20 words
The method of claim 28, wherein said selecting step includes the step of choosing the least recently used FIFO buffer.
Claim 35
Dependent Claim
57 words
The method of claim 30, further comprising the steps comparing said active LRU value to said current LRU value and setting said current LRU value to a predetermined maximum if said active LRU value equals said current LRU value and decrementing said current LRU value if said active LRU value is less than said current LRU value.
Claim 36
Dependent Claim
24 words
The method of claim 31, further comprising the step of selecting the FIFO buffer whose current LRU value equals one as the candidate buffer.
Claim 37
Dependent Claim
36 words
The method of claim 28, wherein said memory receives a write address, further comprising the steps of snooping said write address to said memory and invalidating the FIFO buffer whose address range matches said write address.
References Cited (Backward Citations)
US5469398A
Cited
US5333276A
Cited
US5450546A
Cited
US5371870A
Cited
US5519839A
Cited
US5586294A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-14 | 2002-03-16 | 2002-09-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-14 | 2006-03-16 | 2006-09-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-14 | 2010-03-16 | 2010-09-15 | $7700.00 | Window Closed / Lapsed |