Memory stream buffer with variable-size prefetch depending on memory interleaving configuration

• US 5,659,713 A
• Filed: 12/07/1995
• Issued: 08/19/1997
• Est. Priority Date: 04/24/1992
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Goodwin, Paul M., Tatosian, David A., Smelser, Donald
• Primary Examiner(s): Tung, Kee M.
• Application Number:
  US08/568,520
• Time in Patent Office: 621 Days
• Field of Search: 395/416, 395/419, 395/421.08, 395/421.3, 395/484, 395/405, 395/487, 364/963.1, 364/960, 364/966.1, 364/243, 364/243.1, 364/263.1
• US Class Current: 711/157
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6022 Using a prefetch buffer or dedicated prefetch cache
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

A read buffering system and method employs a bank of FIFOs to hold sequential read data for a number of data streams being fetched by a computer. The FIFOs are located in the memory controller, so the system bus is not used in the memory accesses needed to fill the stream buffer. The buffer system stores addresses used for read requests made by a CPU, and if a next sequential address is then detected in a subsequent read request, this is designated to be a stream (i.e., sequential reads). When a stream is thus detected, data is fetched from DRAM memory for addresses following the sequential address, and this prefetched data is stored in one of the FIFOs. A FIFO is selected using a least-recently-used algorithm. When the CPU subsequently makes a read request for data in a FIFO, this data can be returned without making a memory access, and so the access time seen by the CPU is shorter. By taking advantage of page mode, access to the DRAM memory for the prefetch operations can be transparent to the CPU, resulting in substantial performance improvement if sequential accesses are frequent. One feature is appending page mode read cycles to a normal read, in order to fill the FIFO. The data is stored in the DRAMs with ECC check bits, and error detection and correction (EDC) is performed on the read data downstream of the stream buffer, so the data in the stream buffer is protected by EDC.

Claims

1. A method of buffering data read from a memory coupled to a CPU, wherein said memory is configured into one of a plurality of interleave patterns with other memories also coupled to said CPU, comprising the steps of:

storing an address sequentially following the address used for a read request made to said memory by said CPU;

detecting if a subsequent read request is made using an address which is equal to the stored sequential address, and, if so, generating a stream detect signal;

in response to said stream detect signal, fetching data from said memory at addresses following the stored sequential address and storing said data in a buffer, the maximum number of blocks of said data fetched from said memory and stored in said buffer being inversely proportional to the number of memories interleaved according to said interleave pattern; and

if said CPU sends a read request to said memory for data and said requested data is in said buffer, sending said data from said buffer to said CPU without accessing said memory for said requested data.

2. A method according to claim 1 wherein said step of fetching data from said memory includes the step of fetching a plurality of blocks from said memory at a plurality of addresses following said stored sequential address, if said memory is interleaved with either zero or one of said other memories.

3. A method according to claim 2 including the further steps of detecting a transaction on a system bus during said step of fetching, and terminating said step of fetching upon detecting said transaction.

4. A method according to claim 1 wherein said memory may only be interleaved with either zero, one or three other memories.

5. A method according to claim 1 wherein said memory contains dynamic random-access memory devices (DRAMs) capable of page mode operation, and further including the step of terminating said fetching before said maximum number of data blocks have been fetched if continuing said fetching would cause access to multiple pages of said DRAMs.

6. A system for reading data from a memory coupled to a CPU in response to read requests received from said CPU, wherein said memory is configured into one of a plurality of interleave patterns with other memories also coupled to said CPU, comprising:

a read buffer including a plurality of FIFOs, each FIFO having a plurality of entries;

an address queue for receiving and storing an address sequentially following the address of a read request sent by said CPU to said memory during a period of said requests;

a stream detect circuit for producing a stream detect signal in response to a read request having an address equal to the sequential address stored in said address queue;

means responsive to said stream detect signal for selecting one of said FIFOs of said read buffer for storing sequential data;

means for fetching data from said memory at addresses following the sequential address stored in said address queue and loading said fetched data into said selected FIFO, the maximum number of blocks of said data fetched from said memory and stored in said buffer being inversely proportional to the number of memories interleaved according to said interleave pattern;

means, responsive to a read request from said CPU for data in said memory, for sending said requested data from said selected FIFO to said CPU without accessing said memory if said requested data is in said selected FIFO.

7. A system according to claim 6 wherein said means for fetching data from said memory includes means for fetching a plurality of blocks of data from said memory at a plurality of addresses following the sequential address stored in said address queue, if said memory is interleaved with either zero or one of said other memories.

8. A system according to claim 7 including means for detecting a transaction on a system bus during said fetching and means for terminating said fetching upon detecting said transaction.

9. A system according to claim 6 wherein said memory may only be interleaved with either zero, one or three other memories.

10. A system according to claim 6 wherein said memory contains dynamic-random access memory devices (DRAMs) capable of page mode operation, and further including means for terminating said fetching before said maximum number of data blocks have been fetched if continuing said fetching would cause access to multiple pages of said DRAMs.

11. A computer system, comprising:

(a) a CPU coupled to a memory by a system bus, the CPU sending memory read requests to said memory by said system bus, wherein said memory is configured into one of a plurality of interleave patterns with other memories also coupled to said CPU by said system bus;

(b) a memory controller coupled between said memory and said system bus;

said memory controller including;

a read buffer, the read buffer having a plurality of FIFOs, each FIFO having a plurality of entries;

an address queue for receiving and storing the address of a read request sent by said CPU to said memory during a period of said requests;

a stream detector for producing a stream detect signal in response to a subsequent read request having an address following the sequential address stored in said address queue and loading said fetched data into said selected FIFO, the maximum number of blocks of said data fetched from said memory and stored in said buffer being inversely proportional to the number of memories interleaved according to said interleave pattern; and

means, responsive to a read request received from said CPU for data in said memory, for sending said requested data from said selected FIFO to said CPU without accessing said memory if said requested data is in said selected FIFO.

12. A computer system according to claim 11 wherein said means for fetching data from said memory includes means for fetching a plurality of blocks of data from said memory at a plurality of addresses following the stored sequential address, if said memory is interleaved with either zero or one of said other memories.

13. A computer system according to claim 12 including means for detecting a transaction on said system bus during said fetching and means for terminating said fetching upon detecting said transaction.

14. A computer system according to claim 12 wherein said memory contains dynamic-random access memory devices (DRAMs) capable of page mode operation, and said memory controller further includes means for terminating said fetching before said maximum number of data blocks have been fetched if continuing said fetching would cause access to multiple pages of said DRAMs.

15. A computer system according to claim 11 wherein said memory may only be interleaved with either zero, one, or three other memories.

16. A computer system according to claim 12 wherein said selecting means includes means for selecting the least recently used of said FIFOs for storing the data to be fetched from said memory.

17. A memory system, coupled to a central processor unit (CPU), for providing data to said CPU in response to a plurality of read requests from said CPU, said memory system comprising:

a memory interleaved with one or more other memories;

a stream buffer coupled to said memory;

means, responsive to said read requests from said CPU, for detecting a sequential relationship between addresses of successive read requests;

means, upon detecting said sequential relationship, for fetching one or more blocks of data from said memory from an address following said sequentially related addresses, a maximum number of blocks of data fetched from said memory being inversely proportional to the number of memories interleaved in said memory system;

means for storing said fetched data in said stream buffer;

means for detecting a transaction initiated by said CPU during said fetching; and

means for discontinuing said fetching upon detecting said transaction.

18. Apparatus according to claim 17, wherein the number of memories in said memory system is a power of two.

19. Apparatus according to claim 17, wherein a size of said stream buffer corresponds to said maximum number of data blocks fetched from said memory.

20. Apparatus according to claim 17 wherein said memory contains dynamic-random access memory devices (DRAMs) capable of page mode operation, and further including means for terminating said fetching before said maximum number of data blocks have been fetched if continuing said fetching would cause access to multiple pages of said DRAMs.