Browse Prior Art Database

Method to Determine Loop Lockdown Eligibility Based on Knowledge of Pattern History Table Branch Predictability Disclosure Number: IPCOM000199676D
Publication Date: 2010-Sep-14
Document File: 2 page(s) / 47K

Publishing Venue

The Prior Art Database


Computer software often includes sections of code called loops which are instructions that are repeatedly executed some number of times. The number of loop iterations is determined by how many times the branches within the loop (there must be at least 1) repeat the same outcomes. At some point one such conditional branch changes direction (taken vs. not-taken) or target address; and the loop is broken out of. Because the instructions within a loop repeat, it is wasteful to continually expend effort (power) to fetch the repeated instruction from the instruction cache and to predict the repeated branches from the branch prediction logic. Loops can be detected in hardware. And upon detection, parts of the front end of the normal microprocessor pipeline can be shut down. This saves power and can improve performance by eliminating any delays that are encountered in normal front-end pipeline processing of such loops. Loop stream detection is present in the prior art. Care must be taken to decide which loops are eligible for lockdown. Locking down short-iteration loops introduces branch misprediction penalties if such branches would have been predicted correctly if branch prediction had not been shut down. Loop locking in such cases is detrimental to performance. In a hybrid branch predictor with a Branch History Table (BHT) and one or more tagged Pattern History Tables (PHT), branches that are part of a loop may or may not be predictable by the PHT. It would be advantageous to identify whether branches within a loop are predictable by the PHT and use that determination to affect whether or not a loop qualifies for lockdown. A case for (partially) tagged geometric history length predictors. Such a hybrid branch predictor is also described in a related patent disclosure which further describes how to exclude branch occurrences encountered with unpredictable patterns from the PHT?s. We have not found in the prior art a method for determining loop lockdown eligibility from the perspective of PHT branch predictability.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Method to Determine Loop Lockdown Eligibility Based on Knowledge of Pattern History Table Branch Predictability

The following table shows the stages of a microprocessor pipeline including this invention. Each box represents one or more processor clock cycles. The number of cycles spent in each stage is not necessarily equal. This invention is included in the box labeled "Loop detection and lockdown eligibility determination".

Branch predictor, Instruction fetching

Front end of the pipeline

Loop detection and lockdown eligibility determination

Loop instruction buffer

Back end of the pipeline

    This invention is part of a hybrid BHT + tagged-PHT branch predictor similar to the TAGE predictor.

    In the disclosed predictor the BHT is accessed based on instruction address. The PHT is accessed as a function of the global path taken to get to the current occurrence of a branch. The PHT index can be a function of the global history of branch outcomes (taken, not-taken), the path of previous taken branches used to reach the current branch, and the address of the current branch itself.

    The first time a branch instruction is encountered it is added to the BHT. It includes an indication of whether the PHT can be used for that branch. This allow-PHT indication is initially set to 0.

    Upon mispredicting the direction (taken vs. not-taken) of a branch from the BHT, a determination is made as to whether or not this occurrence of the branch is predictable by the PHT (any PHT in a multi-PHT configuration). This determination is based on whether the mispredicted occurrence of the branch is distinguishable from previous occurrences of the branch by looking at the current state of the global history and vector of instruction addresses of the branches that are part of the global history. If it is determined to be PHT-predictable, then the allow-PHT indication in the BHT is set to 1 and the PHT is written. Otherwise the allow-PHT indication is not changed, and the PHT is not written.

    Loops are detected at some stage in the pipeline (this could be at some point prior to or some point after the decode stage). The detection is done by noticing that the same sequence of instructions (including branches) is repeating. Limi...