US 5,809,280 AGranted

Adaptive ahead FIFO with LRU replacement

AssigneeCompaq Computer Corporation

InventorsGary F. Chard, William C. Galloway, Ryan A. Callison

Life of this patent

Estimating the term…

Loading patent…

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.

Claims33

Dependent claims

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.

2 more elements

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.

6 more elements

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.

7 more elements

Dependencies are inferred from the claim text.