Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-11-04
2003-11-18
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S206000, C712S207000
Reexamination Certificate
active
06651162
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to data processing devices and systems, and in particular to circuits and methods for prefetching instructions and data processing systems using the same.
BACKGROUND INFORMATION
In many microprocessors, a branch target address cache (BTAC) is used to predict the target addresses of branch instructions, before those target addresses can be computed (or predicted by other, more accurate mechanisms). Generally, the BTAC is an associative memory which stores the addresses to a set of known branch instructions which is accessed with a portion of an instruction address. This may be understood by referring now to
FIG. 1
illustrating a BTAC
100
which may be used with the present invention. BTAC
100
includes a pair of arrays, array
102
having a plurality of entries
104
, each of which contains a branch instruction target address. Additionally, BTAC
100
includes array
106
having a plurality of entries
108
. Each entry
108
includes a field
110
containing an address tag, and a field
112
holding a validity tag, which in an embodiment of BTAC
100
may be one bit wide.
An n-bit instruction address
114
provides an index to address into each of arrays
102
and
106
. An m-bit portion
116
provides an index into each of arrays
102
and
106
. The target address in the entry
104
accessed thereby is held in latch
118
. Similarly, the address tag and validity tag from the corresponding entry
108
in array
106
is held in latch
120
. The address tag, which is n-m bits wide is compared with the n-m bit portion
122
of instruction address
114
in comparator
124
. The output of comparator
124
and the validity tag held in latch
120
are provided to each of a pair of inputs of AND gate
126
. A BTAC hit occurs when the output of AND gate
126
is asserted, or in its logically “true” state. That is, a BTAC hit occurs when both the n-m bit portion
122
of instruction address
114
is the same as the address tag
110
in the entry
108
indexed by the m-bit portion
116
of instruction address
114
, and that address tag is valid. Then, the corresponding target address which is held in latch
118
is loaded into an instruction fetch address register (IFAR) as the predicted address for the next instruction fetch cycle. This address is corrected with a better prediction within a few cycles, either by computing the correct address or by using a more accurate address prediction mechanism. BTAC
100
is a direct mapped cache, however, an artisan of ordinary skill would understand that other types of caches may be used, for example, set associative and fully associative caches, and such embodiments would be within the spirit and scope of the present invention.
When an instruction from the IFAR results in a miss to the low level (L1) instruction cache, the corresponding cache line must be reloaded from another level in the memory hierarchy. This requires a number of clock cycles. During this time, the address to the cache line causing the miss is transferred from the IFAR and stored in register such that the IFAR is available for prefetching instructions. For a high frequency superscalar processor, by the time the cache miss signal is received and processed by the IFAR control mechanism and the address where the cache miss occurred is restored in the IFAR, the BTAC has already been read for the next few successive cycles a corresponding number of addresses available for prefetching.
As a result, a need has arisen for circuits, systems and methods for efficiently prefetching instructions from a BTAC during an instruction cache miss. Such circuits, systems and methods should be capable of implementation with minimal structural or functional impact on the existing instruction processing architecture.
SUMMARY OF THE INVENTION
A method is disclosed for prefetching addresses which includes the step of accessing a stored instruction using a current address and at the same time, accessing a target address stored in a in a branch target address cache (BTAC). Instructions associated with the target address accessed from the BTAC are prefetched during the pendency of the line fill arising from the cache miss.
According to another embodiment of the present invention, a method is disclosed for prefetching instructions following an instruction cache miss by a current instruction address. The current address is used to access the BTAC. On a BTAC hit, the following substeps are performed. First, the target address from the BTAC is used to prefetch instructions into a prefetch buffer. A prefetch buffer is used to store prefetched instructions so that they may be quickly accessed without otherwise corrupting the instruction cache in the event the prefetch instructions are not used. If instructions in the prefetch buffer are used, they are also written to the instruction cache. If at the current address a miss in the instruction cache has occurred, the target address obtained from the BTAC is used to prefetch instructions during the pending instruction cache fill as before, and the target address is also used to recursively access the BTAC and prefetch instructions until the cache miss returns.
The present inventive principles are also embodied in circuits and systems. According to one such embodiment, instruction prefetching circuitry is disclosed which includes a BTAC. Control circuitry is included for accessing the BTAC and obtaining a target address therefrom in response to a hit in the BTAC. Additionally, circuitry is provided for prefetching instructions associated with the target address accessed from the BTAC. Circuitry is also provided for accessing the BTAC using the previously retrieved target address.
The present inventive principles are also directed to a data processing system which includes a memory for storing instructions and a microprocessor coupled to the memory. The microprocessor includes a BTAC for storing a plurality of target addresses to stored instructions. The instruction prefetch circuitry is operable to access the BTAC from a current address causing a miss to the instruction cache. In response to a hit in the BTAC a corresponding target address is obtained from the BTAC. Instructions are prefetched into a prefetch buffer a higher level from a selected one of instruction cache and system memory using the target address. A determination is made as to whether the instructions corresponding to the current address (giving rise to the cache miss) have been accessed from memory and, if the instructions corresponding to the current address have not been accessed from the memory, the target address previously obtained from the BTAC is used to access the BTAC for further prefetching.
The principles of the present invention provide an efficient means of prefetching instructions when a miss to the instruction cache occurs. While the instruction associated with the cache miss is retrieved from a higher level of memory in the memory architecture, the BTAC can be advantageously used to prefetch instructions which are predicted to follow from the execution of the current instruction. In other words, if the current instruction calls for a branch taken and the required instruction for the branch are already found in the prefetch buffer, a number of clock cycles can be saved.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention.
REFERENCES:
patent: 35794 (1862-07-01), Johnson
patent: 5168557 (1992-12-01), Shibuya
patent: 5265213 (1993-11-01), Weiser et al.
patent: 5619663 (1997-04-01), Mizrahi-Shalom et al.
patent: 5734881 (1998-03-01), White et al.
patent: 5809529 (1998-09-01), Mayfield
patent: 5987599 (1999-11-01), Poplingher et al.
patent: 5996056 (1999-11-01), Volkonsky
patent: 6279106 (2001-08-01), Roberts
patent: 6295600 (2001-09-01), Parady
Levitan David Stephen
Nemawarkar Shashank
Sinharoy Balaram
Starke William John
Ellis Richard L.
International Business Machines - Corporation
McBurney Mark E.
Meonske Tonia L.
Newberger Barry S.
LandOfFree
Recursively accessing a branch target address cache using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Recursively accessing a branch target address cache using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recursively accessing a branch target address cache using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3120244