Electrical computers and digital processing systems: processing – Instruction fetching – Prefetching
Reexamination Certificate
1998-10-26
2002-06-04
Follansbee, John A. (Department: 2154)
Electrical computers and digital processing systems: processing
Instruction fetching
Prefetching
Reexamination Certificate
active
06401193
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates generally to the prefetching of data for access by a processor. More particularly, the invention relates to predicting the next data fetch so that the predicted data can be prefetched to the lowest level cache before the predicted data is requested by the processor.
DESCRIPTION OF THE RELATED ART
Processor instruction execution speeds are much faster than the time required to access instructions from a computer's main memory. The slower main memory access time can create performance bottlenecks when a processor is forced to wait for fetched instructions to be transferred from the main memory to the processor. To minimize the gap between processor speed and main memory access time, higher speed cache memory is used to temporarily buffer instructions such that cached instructions are supplied to the processor with minimal time delay.
FIG. 1
is a depiction of a typical processor and memory arrangement that utilizes multilevel cache memory to supply a processor. In
FIG. 1
, the processor
10
is connected to a level zero (L
0
) cache
14
, a level one (L
1
) cache
16
, and a main memory
18
by a bus
22
. Other configurations are possible and may have, for example, the L
0
cache located on the same chip as the processor and connected to the processor by on-chip circuitry or the cache levels may be directly connected to the processor. The processor can be any processor, often referred to as a microprocessor or a central processing unit, that processes computer code such as assembly language code. The cache memory is often high speed memory, such as static random access memory (SRAM), and the main memory can be, for example, dynamic random access memory (DRAM), and/or flash memory. The cache memory is typically more expensive to build than the main memory and therefore, the cache memory is usually sized to store only a small portion of the main memory storage capacity.
In typical computer systems, assembly language instructions are delivered to the processor from memory and then executed by the processor. Referring to
FIG. 2
, a typical assembly language instruction
26
includes an opcode portion
28
and an operand portion
30
. The opcode, for operation code, informs the processor of what operation is to be performed. Opcode instructions include, for example, load instructions, add instructions, and subtract instructions. Referring to
FIG. 3
, a typical instruction
32
includes an opcode
38
that is referenced by a program counter (PC)
36
. The program counter is an instruction location indicator that identifies the address within the memory of the desired instruction and the instruction directs the performance of functions, such as loading data, adding data, or subtracting data. The operand includes the symbolic name for the memory address of the data that is to be operated on by the instruction or in some cases the memory addresses of another instruction. Referring to
FIG. 3
, the operand may include information on the source address
40
or addresses and the destination address
42
or addresses, where the source address is the location of the data that is to be operated on by the instruction, and where the destination address is the target location for data that is the result of the current operations. The source and destination addresses may include addressing modes, where the addressing modes are algorithms that determine the proper source or destination address for data stored within the memory. Data addressing modes can be categorized as random access addressing modes or deterministic addressing modes. Random access addressing modes include absolute addressing, register indirect addressing, and base plus offset addressing. Deterministic addressing modes include sequential addressing modes such as register indirect addressing with pre/post incrementing, circular addressing, and/or bit reverse addressing.
Referring back to
FIG. 1
, since cache memory cannot store the total volume of information that is stored in the main memory
18
, all of the information required by the processor
10
cannot be stored in the L
0
cache
14
at the same time and cache misses will result when the processor fetches data that is not stored in the L
0
cache. In order to increase the L
0
cache hit ratio, instructions and/or data can be prefetched from the main memory to the L
0
cache
14
or L
1
cache
16
in anticipation of a data fetch by the processor. Prefetching of instructions to the cache is made easier by the sequential nature of computer program instruction execution. That is, computer programs often run routines that utilize program instructions in sequential order and as a result, a string of instructions can be prefetched from the main memory to the cache with some degree of confidence that the instructions will soon be needed by the processor. Branch target buffers can be used for prefetching instructions that do not exhibit sequential characteristics.
In contrast to prefetching instructions, data is often accessed in more of a random nature, such that prefetching is more difficult to perform. One common technique used in prefetching data is that when a cache miss occurs, the current cache line is filled from the main memory with the desired prefetch data and a next cache line is filled with a block of data from the main memory that is spatially close to the missed data. Although the block caching approach may work well for some applications, it has disadvantages. Specifically, the block of supplemental data is prefetched from the main memory without any knowledge of the data access pattern of the current program and as a consequence, if the currently accessed data element is not part of a sequential data structure, the data prefetch may be filling the cache with unneeded data in the place of data that may soon be needed by the processor.
In addition to block data prefetching, other techniques for data prefetching involve recognizing access patterns that have developed from previous data accesses and then extrapolating the recognized pattern to generate new prefetch addresses. For example, a pattern recognition technique is disclosed in U.S. Pat. No. 5,694,568, entitled “Prefetch System Applicable to Complex Memory Access Schemes,” issued to Harrison, III et al. Although this technique may work well for its intended purpose, the technique relies on recognizing access patterns based on past data accesses where the past patterns may inaccurately predict future data access patterns.
In view of the shortcomings of the known prior art, what is needed is a method and apparatus for prefetching data that provide a high cache hit ratio.
SUMMARY OF THE INVENTION
A method and apparatus for prefetching data to a low level memory of a computer system utilize an instruction location indicator related to an upcoming instruction to identify a next data prefetch indicator and then utilize the next data prefetch indicator to locate the corresponding prefetch data within the main memory of the computer system. The prefetch data is located so that the prefetch data can be transferred to the low level memory, where the data can be quickly accessed by a processor before the upcoming instruction is executed. The next data prefetch indicator is generated by carrying out the addressing mode function that is embedded in an instruction only when the addressing mode of the instruction is a deterministic addressing mode such as a sequential addressing mode. The next data prefetch indicator is identified by the instruction location indicator by relating corresponding next data prefetch indicators to instruction location indicators in a searchable table.
In the preferred embodiment, a data prefetch prediction table is generated that enables the next data prefetch indicator to be identified based on the program counter of an instruction that is soon to be executed. Entries in the data prefetch prediction table are formed from instructions that utilize deterministic addressing modes for identifying the effective address of the source data. Th
Afsar Muhammad
Oberlaender Klaus
Fish & Richardson P.C.
Follansbee John A.
Infineon Technologies North America Corp.
LandOfFree
Dynamic data prefetching based on program counter and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic data prefetching based on program counter and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic data prefetching based on program counter and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2906354