Multiple branch analyzer for prefetching cache lines
First Claim
Patent Images
1. 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.
1 Assignment
0 Petitions
Accused Products
Abstract
Apparatus for fetching instructions in a computing system. A broadband branch history table is organized by cache line. The broadband branch history table determines from the history of branches the next cache line to be referenced and uses that information for prefetching lines into the cache.
-
Citations
9 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. 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. - View Dependent Claims (8, 9)
-
Specification