Method and apparatus for fetching instructions

Claim 2

Appratus for instruction prefetching in a computer having a cache and a memory, said cache providing temporary high-speed storage for lines of data, said lines of data being prefetched into said cache from said memory by said apparatus, characterized by means (14, 20) for generating addresses of said lines of data; broadband branch history table (21) for storing and providing entries pertaining to branches; local branch history table means (15) for receiving said entries provided by said broadband branch history table and for controlling instruction fetching from the cache (12); and prefetch engine means (22) for computing a next line address and prefetching a next line indicated by said next line address into the cache (12) from the memory (13) if said next line is not stored in the cache (12).

Claim 3

Apparatus according to claim 1 wherein said prefetch engine means is characterized by entry register means (20) for receiving an entry point into a new line, said entry point being the first instruction address within said new line that will be executed by the processor; and map table means (40) for associating said entry point with a finite sequence of taken branches to be encountered when said line is entered at said entry point, said finite sequence terminating when a branch is encountered that is taken to a new line or when no further branches are encountered.

Claim 4

Apparatus according to claim 2 wherein said entry register means (20) holds a queue of entries and further confirms prefetched lines by comparing the oldest entry in the queue to the address of a new line when it is entered.

Claim 5

Improved instruction fetching apparatus for a computing system, said computing system using a plurality of machine instructions normally identified by addresses, and said computing system including a processor (10), a main memory for storing said instructions and data, a cache for storing instructions and data from the main memory for access by the processor (10), and an instruction buffer (11) for transferring said instructions from said cache to said processor, wherein said instruct­ion fetching apparatus is characterized by a local branch history table for transferring said instructions from said cache to said instruction buffer; a broadband branch history table (15) organized on the basis of lines of data within said cache for directing the transfer of lines from the memory (13) to the cache (12); and means for transferring lines of branch entries from said broadband branch history table (21) to said local branch history table (15) to be used for local control of said instruction buffer (11).

Claim 6

Improved instruction fetching apparatus for a computing system, said computing system using a plurality of machine instructions normally identified by addresses, and said computing system including a processor (10), a main memory for storing said instructions and data, a cache for storing instructions and data from the main memory for access by the processor (10), and an instruction buffer (11) for transferring said instructions from said cache to said processor, wherein said instruct­ion fetching apparatus is characterized by a local branch history table for transferring said instructions from said cache to said instruction buffer; a broadband branch history table (15) organized on the basis of lines of data within said cache for directing the transfer of lines from the memory (13) to the cache (12); and means for transferring lines of branch entries from said broadband branch history table (21) to said local branch history table (15) to be used for local control of said instruction buffer (11).

Claim 7

Apparatus according to claim 4, characterized by means for analyzing said entries from said broadband branch history table (21) based on a projected entry point into said cache line; means for determining the order in which the individual branches within said line will be en­countered; means for determining which of said branches within said line exit said line, and if there is no branch that exits said line, determining that the next line to be referenced will be the next sequential line; means for recognizing loops within a line and identifying a branch that will eventually fall through to an exit point of said line; and means for initiating transfer of a new line into said cache if said new line is not already in said cache, and for initiating the transfer of said new line's branch information from said broadband branch history table into said local branch history table and for analyzing said branch information for said new line based on its predicted entry point.

Claim 8

Method for use in an apparatus according to one of the claims 1 to 5, characterized by transferring said instructions from the cache (12) to the instruction buffer (11) by a local branch history table (15); transferring lines of branch entries from the broadband branch history table (21) to the local branch history table (15) to be used for locally controlling the instruction buffer (11), said broadband branch history table being organized on the basis of lines of data within the cache; and directing the transfer of said lines from the memory (13) to the cache (12) based on analysis of entries in said broadband branch history table (21).

Claim 9

Method according to claim 6 further characterized by the steps of anticipating references to said lines that are not stored in said cache, and prefetching said lines of memory from said main memory into said cache, said steps of anticipating and prefetching including steps of analyzing said entries from said broadband branch history table (21) based on a projected entry point into said cache line; determining the order in which the individual branches within said line will be encountered subject to said projected entry point into said line; determining which of said branches within said line exit said line, and if there is no branch that exits said line, determining that the next line to be referenced will be the next sequential line; recognizing loops within a line and identifying a branch that will eventually fall through to an exit point of said line; and initiating transfer of a new line into said cache if said new line is not already in said cache (12), and initiating the transfer of said new line's branch information from the broadband branch history table (21) into the local branch history table (15) and analyzing the branch information for said new line based on its predicted entry point.