US4943908A — Multiple branch analyzer for prefetching cache li…

Claim 1

Independent Claim 404 words

In a computer with a processor, a main memory, said main memory storing a plurality of lines of instructions, and a cache, said cache temporarily storing instruction lines received from said main memory, apparatus for prefetching instruction lines from said main memory to said cache, comprising: a branch history table having a plurality of entries, each said entry corresponding to an instruction line in said main memory and comprising addresses of all branches predicted as taken in said corresponding line; means connected to said branch history table for determining from the branch history table entry for a current instruction line in use by, or in queue for use by, the processor and from an address of an entry point into said current line by the processor, a next instruction line to be used by the processor and an entry point into said next line; and means responsive to said determination of the next instruction line for prefetching said next line from said main memory into said cache in the event said next line is not already in said cache; said determining means comprising: entry register means for receiving and storing initially the entry point address for said current line; map table means receiving the current address stored in said entry register means and the taken branch addresses from the branch history table entry for said current line, and outputting (a) in the event there is no taken branch in said current line following the address stored in said entry register means, the address of the next sequential instruction line in said main memory, and (b) in the event the taken branch that follows the address stored in said entry register means has a target address in said current line, the address of the next taken branch that will be encountered in said current line after taking said taken branch which follows said stored address, or the address of the next sequential instruction line in said main memory if no other taken branches will be encountered in said current line after taking said taken branch which follows said stored address, and (c) in the event the taken branch that follows the address stored in said entry register means has a target address outside said current line, said target address; and means for updating the address stored in said entry register means in the event that said map table means outputs a next taken branch address.

Claim 2

Dependent Claim 404 words

In a computer with a processor, a main memory, said main memory storing a plurality of lines of instructions, and a cache, said cache temporarily storing instruction lines received from said main memory, apparatus for prefetching instruction lines from said main memory to said cache, comprising: a branch history table having a plurality of entries, each said entry corresponding to an instruction line in said main memory and comprising addresses of all branches predicted as taken in said corresponding line; means connected to said branch history table for determining from the branch history table entry for a current instruction line in use by, or in queue for use by, the processor and from an address of an entry point into said current line by the processor, a next instruction line to be used by the processor and an entry point into said next line; and means responsive to said determination of the next instruction line for prefetching said next line from said main memory into said cache in the event said next line is not already in said cache; said determining means comprising: entry register means for receiving and storing initially the entry point address for said current line; map table means receiving the current address stored in said entry register means and the taken branch addresses from the branch history table entry for said current line, and outputting (a) in the event there is no taken branch in said current line following the address stored in said entry register means, the address of the next sequential instruction line in said main memory, and (b) in the event the taken branch that follows the address stored in said entry register means has a target address in said current line, the address of the next taken branch that will be encountered in said current line after taking said taken branch which follows said stored address, or the address of the next sequential instruction line in said main memory if no other taken branches will be encountered in said current line after taking said taken branch which follows said stored address, and (c) in the event the taken branch that follows the address stored in said entry register means has a target address outside said current line, said target address; and means for updating the address stored in said entry register means in the event that said map table means outputs a next taken branch address.

Claim 3

Dependent Claim 83 words

Cache prefetching apparatus as defined in claim 1, wherein: said updating means stores in said entry register means said outputted next taken branch address when said outputted next taken branch address is first encountered as an outputted next taken branch address, and said updating means stores in said entry register means an address one position later than said outputted next taken branch address in the event said outputted next taken branch address has already been encountered as an outputted next taken branch address.

Claim 4

Dependent Claim 96 words

Cache prefetching apparatus as defined in claim 1, and further comprising: means for storing the addresses of next taken branches outputted by said map table means, said updating means storing in said entry register means said outputted next taken branch address in the event said outputted next taken branch address is not already stored in said storing means, and said updating means storing in said entry register means an address one position later than said outputted next taken branch address in the event said outputted next taken branch address is already stored in said storing means.

Claim 5

Dependent Claim 31 words

Cache prefetching apparatus as defined in claim 1 wherein said map table means is logic circuitry which products the output corresponding to the set of inputs within a single machine cycle.

Claim 6

Dependent Claim 42 words

Cache prefetching apparatus as defined in claim 4 wherein said updating means is logic circuitry which updates the address stored by said entry register means in the same machine cycle during which a new output is produced by said map table means.

Claim 7

Dependent Claim 46 words

Cache prefetching apparatus as defined in claim 1 wherein said map table means outputs an address other than a next taken branch address in no more machine cycles than the number of addresses of taken branches in the branch history table entry for the current line.

Claim 8

Dependent Claim 348 words

In a computer with a processor, a main memory, said main memory storing a plurality of line of instructions a cache said cache temporarily storing instruction lines received from said main memory and a branch history table, with branch information for an entire instruction line of said main memory forming a single entry in said branch history table, and where the branch history table entry for a current instruction line and an entry point into said current line is used to predict a next instruction line to be used by said processor and an entry point into said next line, said next line being prefetched from said main memory into said cache if it is not already there, the combination comprising: entry register means for receiving and storing initially the entry point address for a current line; map table means receiving the current address stored in said entry register means and the addresses of all taken branches for said current line from said branch history table entry for said current line, and outputting (a) in the event there is no taken branch in said current line following the address stored in said entry register means, the address of the next sequential instruction line in said main memory, and (b) in the event the taken branch that follows the address stored in said entry register means has a target address in said current line, the address of the next taken branch that will be encountered in said current line after taking said taken branch which follow said stored address, or the address of the next sequential instruction line in said main memory if no other taken branches will be encountered in said current line after taking said taken branch which follows said stored address, and (c) in the event the taken branch that follows the address stored in said entry register means has a target address outside said current line, said target address; and means for updating the address stored in said entry register means in the event that said map table means outputs a next taken branch address.

Claim 9

Dependent Claim 348 words

In a computer with a processor, a main memory, said main memory storing a plurality of line of instructions a cache said cache temporarily storing instruction lines received from said main memory and a branch history table, with branch information for an entire instruction line of said main memory forming a single entry in said branch history table, and where the branch history table entry for a current instruction line and an entry point into said current line is used to predict a next instruction line to be used by said processor and an entry point into said next line, said next line being prefetched from said main memory into said cache if it is not already there, the combination comprising: entry register means for receiving and storing initially the entry point address for a current line; map table means receiving the current address stored in said entry register means and the addresses of all taken branches for said current line from said branch history table entry for said current line, and outputting (a) in the event there is no taken branch in said current line following the address stored in said entry register means, the address of the next sequential instruction line in said main memory, and (b) in the event the taken branch that follows the address stored in said entry register means has a target address in said current line, the address of the next taken branch that will be encountered in said current line after taking said taken branch which follow said stored address, or the address of the next sequential instruction line in said main memory if no other taken branches will be encountered in said current line after taking said taken branch which follows said stored address, and (c) in the event the taken branch that follows the address stored in said entry register means has a target address outside said current line, said target address; and means for updating the address stored in said entry register means in the event that said map table means outputs a next taken branch address.

Claim 10

Dependent Claim 80 words

The combination in claim 7, wherein: said updating means stores in said entry register means said outputted next taken branch address when said outputted next taken branch address is first encountered as an outputted next taken branch address, and said updating means stores in said entry register means an address one position later than said outputted next taken branch address in the event said outputted next taken branch address has already been encountered as an outputted next taken branch address.

Claim 11

Dependent Claim 93 words

The combination of claim 7, and further comprising: means for storing the addresses of next taken branches outputted by said map table means, said updating means storing in said entry register means said outputted next taken branch address in the event said outputted next taken branch address is not already stored in said storing means, and said updating means storing in said entry register means an address one position later than said outputted next taken branch address in the event said outputted next taken branch address is already stored in said storing means.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1993-07-23	1994-01-22	1994-07-24	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1997-07-23	1998-01-22	1998-07-24	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2001-07-23	2002-01-22	2002-07-24	$7700.00	Window Closed / Lapsed

Multiple branch analyzer for prefetching cache lines

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag