Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2003-05-02
2004-03-02
Lane, Jack A. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
Reexamination Certificate
active
06701414
ABSTRACT:
FIELD OF THE INVENTION
Embodiments of the present invention relate to prefetching data from a memory. In particular, the present invention relates to methods and apparatus for prefetching data from a memory for use by a processor.
BACKGROUND
Instructions executed by a processor often use data that may be stored in a memory device such as a Random Access Memory (RAM). For example, a processor may execute a LOAD instruction to load a register with data that is stored at a particular memory address. In many systems, because the access time for the system memory is relatively slow, frequently used data elements are copied from the system memory into a faster memory device called a cache and, if possible, the processor uses the copy of the data element in the cache when it needs to access (i.e., read to or write from) that data element. If the memory location that is accessed by an instruction has not been copied into a cache, then the access to the memory location by the instruction is said to cause a “cache miss” because the data needed could not be obtained from the cache. Computer systems operate more efficiently if the number of cache misses is minimized.
One way to decrease the time spent waiting to access a RAM is to “prefetch” data from the RAM memory before it is needed and, thus, before the cache miss occurs. Many processors have an instruction cycle in which instructions to be executed are obtained from memory in one step (i.e., an instruction fetch) and executed in another step. If the instruction to be executed accesses a memory location (e.g., a memory LOAD), then the data at that location must be fetched into the appropriate section of the processor from a cache or, if a cache miss, from a system memory. A cache prefetcher attempts to anticipate which data addresses will be accessed by instructions in the future and prefetches the data to be accessed from the memory before the data is needed. This prefetched data may be stored in a cache or buffer for later use.
Prior prefetching schemes determine a “stride” for memory instructions such as LOAD's and then prefetch data using this stride. The stride for an instruction in a program may be defined as the distance between the memory addresses loaded by two consecutive executions of the instruction. As used herein, “instruction” refers to a particular instance of an instruction in the program, with each instruction being identified by a different instruction pointer (“IP”) value. Stride based prefetch schemes are premised on the theory that an instruction will access a series of memory locations that are the same distance apart from one another. This prediction is often accurate if, for example, the program is in a loop or nested loop or is stepping though a table.
REFERENCES:
patent: 5790823 (1998-08-01), Puzak et al.
patent: 6055622 (2000-04-01), Spillinger
patent: 6253306 (2001-06-01), Ben-Meier et al.
patent: 6574712 (2003-06-01), Kahle et al.
patent: 0 402 787 (1990-12-01), None
patent: 1 031 919 (2000-08-01), None
Abdallah Mohammad A.
Al-Dajani Khalid
LandOfFree
System and method for prefetching data into a cache based on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for prefetching data into a cache based on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for prefetching data into a cache based on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3251938