Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-12-23
2004-06-29
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S239000
Reexamination Certificate
active
06757815
ABSTRACT:
BACKGROUND
The present invention relates to processors. More particularly, the present invention relates to a single array banked branch target buffer for use in a processor.
Many processors, such as a microprocessor found in a computer, use an instruction pipeline to speed the processing of an instruction stream. The pipeline has multiple stages and an instruction is processed using early pipeline stages before a previous instruction is executed by later stages. Some instructions, such as a “conditional branch” instruction, however, must be executed before the processor can determine which instruction should be processed next. To increase efficiency, the processor “predicts” when a conditional branch is being processed and also predicts which instruction, or “branch,” should be placed into the early pipeline stages before that conditional branch instruction is executed.
To predict branch instructions within the instruction stream, a cache called a “branch target buffer” can be used to store information about branch instructions previously executed by the processor.
An instruction fetch unit may fetch upcoming instructions by fetching several bytes at the same time, such as by fetching sixteen-byte blocks of memory. A single block, however, may contain multiple branch instructions. In such a processor, the branch prediction mechanism must find the first taken branch instruction, if any, within the current sixteen-byte block to determine the next sixteen-byte block to fetch.
To efficiently find the first taken branch instruction, a “banked” branch target buffer may be used. U.S. Pat. No. 5,842,008 entitled “Method and Apparatus for Implementing a Branch Target Buffer Cache with Multiple BTB Banks” discloses such a banked branch target buffer. Each bank in the branch target buffer contains branch entries for branch instructions located in a different subset of the memory blocks. The branch target buffer banks are ordered such that when a branch prediction must be made, the branch entry “hits” produced by each branch target buffer bank are ordered, reducing the amount of time required to prioritize the branch instructions.
The banked branch target buffer uses a different, independent array for each bank, such that each array provides information about branches residing in the associated bank. The information is later prioritized. By way of example, a branch target buffer can use four banks to store information about a sixteen byte cache line. The branch target buffer may store information about a single branch in each bank, and therefore a maximum of four branches would be stored for each sixteen byte cache line.
FIG. 1
illustrates a known architecture for a single bank in such a banked branch target buffer. In other words, a branch target buffer having four banks would need four of the circuits shown in
FIG. 1
(one for each bank). For each bank, a lookup IP (Instruction Pointer) signal passes through a multiplexer
100
coupled to four buffer entries
200
, or “ways.” Note that the number of ways (four) does not have to be the same as the number of banks in the branch target buffer. The buffer entries
200
are mapped to cache data buffers
300
, and each buffer entry
200
is coupled to a comparator
400
. The lookup IP signal is also input to the comparators
400
, and the results from each comparator
400
are coupled to another multiplexer
500
that selects cache data stored in the cache data buffers
300
.
Each bank of the branch target buffer is addressed by the sixteen-byte line address. When a lookup to the branch target buffer occurs, each bank is addressed simultaneously and provides information for that particular bank and line. The result of each bank's search is then combined by a prioritizing and merging logic unit to produce the final branch target buffer prediction.
Assuming that each bank is organized in a classic four-way set associative fashion, a method for performing a look-up is illustrated in
FIG. 2
for one of the four branch target buffer banks. The lookup address, or Instruction Pointer (IP) is split into an “IP tag” field and an “IP set” field at step
10
. The IP set field corresponds to a specific bank in the branch target buffer. At step
20
, the IP set field is decoded and used to read out the four ways corresponding to that set (i.e., the four entries in the specific branch target buffer bank). The tag, valid and data fields are then read for each of the four ways or entries at step
30
. These four entry tags are compared to the IP tag in order to determine from which valid way, if any, there is a match at step
40
, and the chosen way is then used to select the data that represents that particular bank's information.
In a traditional four-way set associative organization (such as the one shown in FIG.
1
), it is forbidden to have the same valid tag in different ways of the same set. In other words, the match signals from the comparators and valid bit combined are mutually exclusive.
Providing independent arrays for each bank, however, creates routing problems, and increases area and design overhead related to the banked branch target buffer implementation. In particular, the use of multiple arrays implies costly routing from each array to the merging logic, which translates directly into timing problems.
Moreover, the utilization of the available entries is limited when multiple arrays are used. For example, branches may not be uniformly distributed between the banks. Suppose that most branches sit in bank
0
. In this case, there may be a lot of replacements in bank
0
while entries in banks
1
to
3
are less utilized.
SUMMARY
In accordance with an embodiment of the present invention, an Instruction Pointer (IP) signal is received comprising an IP tag field and an IP set field. A plurality of entries corresponding to the IP set field are read, each of the entries comprising an entry tag, an entry bank, and entry data. Each entry tag and entry bank is then compared with the IP tag and each of the plurality of banks.
REFERENCES:
patent: 5056002 (1991-10-01), Watanabe
patent: 5740415 (1998-04-01), Hara
patent: 5802602 (1998-09-01), Rahman et al.
patent: 5835948 (1998-11-01), Olarig et al.
patent: 5842008 (1998-11-01), Gochman et al.
patent: 6065091 (2000-05-01), Green
patent: 6304960 (2001-10-01), Yeh et al.
patent: 6385696 (2002-05-01), Doweck
Ellis Richard L.
Kenyon & Kenyon
Meonske Tonia L.
LandOfFree
Single array banked branch target buffer does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Single array banked branch target buffer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single array banked branch target buffer will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3320605