Branch-prediction driven instruction prefetch

Details Branch-prediction driven instruction prefetch Branch-prediction driven instruction prefetch

2000-02-29

2003-06-17

Nguyen, Than (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S118000, C711S122000, C711S213000, C712S234000, C712S237000, C712S238000, C712S239000

Reexamination Certificate

active

06581138

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method and an apparatus for instruction caching in computer processors.
2. Description of Related Art
Known instruction memory caching schemes for computer processors use cache memory to improve processor efficiency. Typically, when an instruction is fetched by the processor, an instruction cache is accessed to determine whether a copy of the memory holding the instruction is in the cache. If so, the instruction is provided to the processor from the instruction cache. If not, the main memory is accessed and a portion of the contents of the main memory that contains the instruction is copied to the instruction cache. The copied information is a cache line.
Because the instruction execution path is likely to continue sequentially and because instructions are often repeatedly executed, once the cache line is cached, the processor need not access main memory so long as the instructions being executed are from cache lines resident in the instruction cache. Thus, caching instructions reduces processor delays that would otherwise result from main memory fetches.
One problem which has arisen in the art is that instruction caching does not avoid all instruction memory access delays. One reason for this is that when sequential instruction execution reaches the end of a cache line, the subsequent cache line must be fetched from instruction memory if the subsequent cache line is not already in the instruction cache. Waiting for the subsequent cache line stalls the processor. Another reason for processor stalls is because branch instructions alter the sequential instruction fetch sequence within the instruction execution path. Thus, the cache line that contains the next instruction that is to be executed after a branch instruction may not be resident in the instruction cache. This requires that the prior art fetch the target instruction from main memory instead of from the instruction cache.
Both of these reasons invoke a main memory fetch that results in the processor incurring delays that are relatively much longer than delays incurred due to fetches from the instruction cache. The fetch to main memory thus delays the processing of the instruction execution path until the fetch for the cache line containing the needed instruction is completed.
One skilled in the art will understand that the main memory may itself be cached (for example a level 2 cache). However the main memory cache is relatively slower than the instruction cache.
Another problem is that only one cache line is read from memory into the instruction cache at a time and during the fetch the instruction cache can not be accessed to get instructions. Thus, if a subsequently accessed cache line would have required a linefill from main memory, the processor would incur an additional delay for a second cache linefill request from main memory, after it fetched all needed instructions from the first line resident in the instruction cache.
Accordingly, it would be desirable to provide a caching scheme that predicts and pre-fetches a number of cache lines that are expected to be needed in the future to overlap this process with other processor activities and thus minimize the amount of time the instruction cache is unavailable to the processor.
SUMMARY OF THE INVENTION
The invention provides a method and apparatus for optimizing instruction prefetch and caching in a processor. In the preferred embodiment, a path prediction circuit maintains information about which cache lines are likely to be executed in the future. This information is used to independently fetch the predicted cache lines, store them in a prefetch queue, and load them in to the instruction cache as instructions contained in these lines are about to be decoded by the processor.
The foregoing and many other aspects of the present invention will no doubt become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments that are illustrated in the various drawing figures.


REFERENCES:
patent: 4847753 (1989-07-01), Matsuo et al.
patent: 5317720 (1994-05-01), Stamm et al.
patent: 5333296 (1994-07-01), Bouchard et al.
patent: 5784711 (1998-07-01), Chi
patent: 6237074 (2001-05-01), Phillips et al.
patent: 6279107 (2001-08-01), Tran

Affiliated with

Also associated with

Rating

Branch-prediction driven instruction prefetch does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Branch-prediction driven instruction prefetch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Branch-prediction driven instruction prefetch will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3104366