US 5,706,492 AGranted

Method and apparatus for implementing a set-associative branch target buffer

AssigneeIntel Corporation

InventorsBradley D. Hoyt, Glenn I. Hinton, David B. Papworth, Ashwani Kumar Gupta, Michael Alan Fetterman, Subramanian Natarajan, Sunil Shenoy, Reynold V. D'Sa

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

A Branch Target Buffer Circuit in a computer processor that predicts branch instructions with a stream of computer instructions is disclosed. The Branch Target Buffer Circuit uses a Branch Target Buffer Cache that stores branch information about previously executed branch instructions. The branch information stored in the Branch Target Buffer Cache is addressed by the last byte of each branch instruction. When an Instruction Fetch Unit in the computer processor fetches a block of instructions it sends the Branch Target Buffer Circuit an instruction pointer. Based on the instruction pointer, the Branch Target Buffer Circuit looks in the Branch Target Buffer Cache to see if any of the instructions in the block being fetched is a branch instruction. When the Branch Target Buffer Circuit finds an upcoming branch instruction in the Branch Target Buffer Cache, the Branch Target Buffer Circuit informs an Instruction Fetch Unit about the upcoming branch instruction.

Claims19

Dependent claims

A method for predicting a plurality of branch instructions within a stream of computer instructions utilizing a branch target buffer cache, said method comprising the steps of:

requesting information about upcoming branch instructions by having an instruction fetch unit pass an instruction pointer to a branch target buffer circuit, said instruction pointer identifying a branch instruction in a memory, said instruction pointer having a set of branch target buffer set address bits and a set of branch target buffer tag address bits;
indexing into said branch target buffer cache with said set of branch target buffer set address bits of said instruction pointer to select a branch set entry, said target buffer cache comprising a plurality of branch set entries, each said branch set entry comprising a set of branch instruction entries, each branch instruction entry storing information about an associated branch instruction including a position with a memory block, all branch instruction entries within a particular branch set entry storing branch instructions having identical branch target buffer set address bits;
reading out said selected branch set entries from said branch target buffer cache;
examining said selected branch set entries from said branch target buffer cache to determine if any of said selected branch set entries contain information about said branch instruction identified by said instruction pointer in said memory;
eliminating said branch set entries which do not match said branch instructions identified by said instruction pointer in said memory;
and
selecting at least one branch instruction entry in said branch set entries using said branch target buffer tag address bits of said instruction pointer.

4 more elements

A branch instruction prediction mechanism, said branch instruction prediction mechanism predicting a plurality of branch instructions within a stream of computer instructions, said branch instruction prediction mechanism comprising:

an instruction fetch unit, said instruction fetch unit utilizing an instruction pointer for maintaining a current fetch address, said instruction pointer identifying a branch instruction in a memory, said instruction pointer having a set of branch target buffer set address bits and a set of branch target buffer tag address bits;
a branch target buffer cache, said branch target buffer cache comprising a plurality of branch set entries, each of said branch set entries comprising a set of branch instruction entries, each branch instruction entry storing information about an associated branch instruction including a position with a memory block, all branch instruction entries within a particular branch set entry storing branch instructions having identical branch target buffer set address bits;
and
a branch target buffer circuit, said branch target buffer circuit receiving said instruction pointer, said branch target buffer circuit searching for a first upcoming branch instruction in said memory identified by said instruction pointer, said branch target buffer circuit indexing into said branch target buffer cache with said set of branch target buffer set address bits of said instruction pointer to select a branch set entry, said branch target buffer circuit selecting at least one branch instruction entry in said branch set entry using said branch target buffer tag address bits of said instruction pointer.

1 more element

Dependencies are inferred from the claim text.

Facts

Application: 08/687,975Filed 29 Jul 1996 · continuation
Priority: 4 Jan 1994
Granted: 6 Jan 1998
Term ends: Not estimatedThe source records don’t support an estimate.

Classification3 codes

G06F 9/3806
For branches, e.g. hedging, branch folding: using address prediction, e.g. return stack, branch history buffer
G06F 9/30054
To perform operations for flow control: unconditional branch instructions
G06F
Computing and data processing

Family

Serial177,155Parent of this continuation · filed 4 Jan 1994
US 5,574,871 AParent of this continuation
US 5,706,492 AThis patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key