Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-08-16
2002-09-10
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S234000, C712S236000, C712S237000, C712S238000, C712S239000, C711S125000, C711S131000, C711S137000, C711S213000
Reexamination Certificate
active
06449714
ABSTRACT:
This invention deals with a novel process and novel electronic circuits in a processor for significantly reducing the execution time of programs without increasing processor instruction execution rate. A fetch history table (FHT) stores recent branch history of program execution and is used by a processor to direct the path of future execution of the program. The invention enables any valid FHT entry to control the outgating for execution in any sequence or instructions in aligned sectors in an associated row of an instruction cache (AIC) without the conventional branch instruction overhead. This invention utilizes a novel “sector distribution table” (SDT) for quickly locating a next-to-be executed aligned segment of instructions in the associated AIC row for outgating to the processor's execution pipeline under control of novel FHT entries in novel types of FHT sets. The inventive process enables all FHT entries to have complete flexibility in specifying any sequence of the valid sectors in the associated AIC row.
PRIOR ART
The prior art is the same as cited in the incorporated specification Ser. No. 09/235,474.
CHARACTERISTICS OF THE INCORPORATED SPECIFICATION
The incorporated specification discloses novel circuits and novel processes for using the novel circuits. The novel circuits and processes include and use a fetch history table (FHT) containing novel FHT entries grouped into novel FHT sets for controlling the processor execution of instructions stored in aligned sectors of an Aligned Instruction Cache (AIC). Each row in the AIC includes a plurality of aligned sectors, each storing all, or a part of, a basic block of instructions ending in a branch instruction. Each valid FHT entry specifies a previously-executed sequence of sectors stored in an AIC row associated with the FHT set. The novel form of each valid FHT entry allows the FHT entry to be selected by a prediction vector during an FHT cycle, and to be used to control future re-execution of its represented sequence to avoid conventional branch instruction overhead and time loss previously occurring in the processor execution of branch instructions.
The incorporated specification provides “AIC cycles”. Each “AIC cycle” starts with a determination of an AIC hit or miss, and FHT entries are not allowed to control program execution during those AIC cycle which have an AIC miss. If an “AIC cycle” starts with an AIC miss, a FHT entry is generated during the “AIC cycle” using conventional branch instruction execution. On the other hand, the subject invention provides novel “FHT cycles” and does not use “AIC cycles”. Each “FHT cycle” having a FHT hit is used to control program execution, even when an AIC miss occurs within the “FHT cycle”.
An AIC miss occurs when no row in the AIC begins with an instruction currently predicted to be executed by the program. Then, one or more variable-length basic blocks of instructions are fetched from the storage hierarchy of the computer system, and all or part of the fetched basic block(s) are stored into fixed-size aligned sectors in the AIC row associated with the currently predicted instruction. The associated AIC row is selected by hashing the address of the currently predicted instruction to generate an AIC index which locates the associated AIC row in the AIC. The fetched blocks are stored in execution order in the left-to-right sequence of the aligned sectors in the associated AIC row. Since all aligned sectors in the AIC have the same size, any sector may store an entire basic block if the block size does not exceed the storage space in the sector. If a basic block exceeding the size of a sector will fill the sector and its remaining part is stored into the next one or more sectors in the same AIC. When a fetched block overflows the remaining sector(s) in the associated AIC row, the block overflow may be stored into one or more sectors in another AIC row selected by hashing the address of the first instruction to be stored in the first sector overflowing into that AIC row. The branch instruction ending the basic block is stored in the last sector of the block, and the sectors storing any prior part(s) of the block do not contain any branch instruction. Thus at any time, any AIC sector may store a branch instruction ending a basic block, and at any other time the same AIC sector may not be storing any branch instruction.
The incorporated specification groups the FHT entries into FHT sets, and each FHT set is associated with a respective AIC row by being located in the FHT at an FHT index directly calculated from the AIC index. Each of the valid FHT entries in any FHT set specifies a different execution sequences of the sectors in the associated AIC row. However in the incorporated specification, each valid FHT entry in each FHT set specifies an execution sequence starting with the first (leftmost) sector in the associated AIC row (which is not done in the subject specification.).
FHT cycles are used by the inventive process to control program execution. Each FHT cycle has either a FHT hit on a valid FHT entry in the associated FHT set, or an FHT miss when no valid FHT entry is found in the associated FHT set. A FHT hit uses the FHT entry having the hit to control outgating to the processor execution pipeline of a sequence of aligned sectors in the associated AIC row, and the outgated sequence may have any sector order as long as the first sector of the sequence is the first sector in the associated AIC row. A FHT miss does not find any FHT entry in the associated FHT set, and temporarily reverts to conventional branch instruction processing for the program during which a FHT entry is generated to represent the instruction sequence using conventional branch instruction processing. An AIC miss causes a FHT miss, but an AIC hit may not prevent a FHT miss.
Each FHT cycle starts with a prediction operation using a “next instruction address” provided during the immediate prior FHT cycle either: in a hit FHT entry, or in a generated FHT entry provided in response to a FHT miss. The first FHT cycle for a program uses the program's entry instruction address. The prediction operation uses the “next instruction address” to provide a “prediction vector”. Bits in the “prediction vector” respectively predict a sequence of “taken” and/or “not taken” states occurring for the branch instructions in the sequence of aligned sectors,predicted for outgating during the current FHT cycle. The prediction vector may be obtained from a recording made of “m“number of branches states immediately following the last execution of the instruction at the same address as the “next instruction address” provided for the current FHT cycle.
The “next instruction address” (used in the current FHT cycle) is hashed to obtain an AIC index, which locates both an associated AIC row and an associated FHT set. The associated FHT set contains either the next hit FHT entry or the next generated FHT entry, depending on whether the current FHT cycle gets an FHT hit or miss. An AIC hit is obtained if the associated AIC row is located at the AIC index hashed from the “next instruction address” of the current FHT cycle. An AIC miss is obtained if the associated AIC row at the hashed AIC index does not begin with the instruction located at the “next instruction address” provided for the current FHT cycle.
In response to an AIC miss, the basic blocks of instructions (next needed for execution) are fetched from the computer storage hierarchy starting at the memory address of the “next instruction address” of the current prediction. The fetched basic blocks are loaded in execution order into the aligned sectors from left-to-right in the associated AIC row.
The hashed AIC index is used to locate and access the associated FHT set. (This use of the AIC index to associate a FHT set to an AIC row causes problems, which are avoided by the subject invention.) A FHT miss occurs when the “next memory address” field in any FHT entry of the associated FHT set does not match the currently predicted next instruction address. (The curren
Augspurger Lynn L.
Ehrlich Marc A.
Treat William M.
LandOfFree
Total flexibility of predicted fetching of multiple sectors... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Total flexibility of predicted fetching of multiple sectors..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Total flexibility of predicted fetching of multiple sectors... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2861620