Branch prediction instructions having mask values involving unloading and loading branch history data

A method for branch prediction, the method comprising, receiving a load instruction including a first data location in a first memory area, retrieving data including a branch address and a target address from the first data location, and saving the data in a branch prediction memory, or receiving an unload instruction including the first data location in the first memory area, retrieving data including a branch address and a target address from the branch prediction memory, and saving the data in the first data location.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates generally to computer processing techniques and, more particularly, to methods involving branch prediction in computer processing.

2. Description of Background

Branch prediction is used to improve the performance of processors. When a processor detects a conditional branch, an uncertainty is temporarily introduced into the processor pipeline. If the branch is taken, the next instruction is fetched from an address usually specified in the branch instruction. If the branch is not taken, execution proceeds to the instruction following the branch.

Large amounts of chip area are dedicated to the processor branch prediction mechanism. In practice, the branch address and target address of each branch encountered by the processor are saved in a table, called a Branch History Table (BHT). During the instruction fetch phase of a processor pipeline, the BHT is searched for a matching branch address, and if found, the target address is fetched, and the instruction located at the target address becomes the next instruction decoded. If no matching branch address is found in the instruction fetch segment, instruction fetching and decoding continue down the sequential path. Branch prediction errors occur when the table is incorrect. If the BHT predicted the branch to be taken and the predicted branch is not taken, the BHT entry is deleted or updated to record the correct branch action pattern. If a branch predicted not taken is taken, typically a new entry is made in the BHT, or the new branch pattern is updated. If the predicted target address is wrong, the correct address is saved in the BHT.

The prediction accuracy of the branch prediction mechanism (BHT) is proportional to the size of the BHT. Branch prediction accuracy may reach 80 to 90 percent, but there is a severe penalty when the BHT is incorrect. Prediction errors may cause the processor pipeline to be flushed, causing pipeline drain. A single prediction error may introduce a pipeline bubble (idle cycles) of 10 to 20 cycles or longer, depending on the pipeline length.

Increasing the size of the BHT reduces the penalty caused by prediction errors. The BHT may contain 4K to 16K entries, and with each entry approximately 8 bytes, (4 bytes for the branch address and 4 bytes for the target address) the overall size of the BHT may be 32K to 128K bytes. Although a larger BHT would reduce the percentage of wrong predictions and resultant penalties, the table hardware must be packaged in the speed critical instruction fetch and decode regions of the processor. The location of the table hardware limits the size of the BHT.

It is desirable to reduce the table hardware associated with the BHT without sacrificing prediction accuracy.

SUMMARY OF THE INVENTION

The shortcomings of the prior art are overcome and additional advantages are achieved through an exemplary method for branch prediction, the method comprising, receiving a load instruction including a first data location in a first memory area, retrieving data including a branch address and a target address from the first data location data location, and saving the data in a branch prediction memory.

An alternate exemplary method for branch prediction, the method comprising, receiving an unload instruction including a first data location in a first memory area, retrieving data including a branch address and a target address from the branch prediction memory, and saving the data in the first data location data location.

DETAILED DESCRIPTION OF THE INVENTION

Methods involving prefetching into a branch prediction mechanism are provided.

In this regard, it is desirable to reduce the size of a branch history table (BHT) size while improving branch prediction accuracy and processor performance. To accomplish this, a mechanism is described that allows future branch information to be prefetched into the BHT.

Prefetching future branch information into a prefetched branch history table (PBHT) allows a designer to reduce the size of the BHT without sacrificing branch prediction accuracy or performance. The branch information used to process the upcoming (future) instructions and branches of a program is held in the speed critical area (PBHT), while the full program and branch information are maintained in program save areas or main memory. The full size of the branch prediction mechanism is no longer limited in size by the hardware or cycle time considerations. The size of the PBHT need only by limited to the amount of branch information needed to capture the imminent working set of a program and the ability of the processor to stage (prefetch) the upcoming information into the PBHT on a timely basis.

Prefetching will improve processor performance if the items prefetched are used during branch prediction, and are fetched far enough in advance of their use.

It is desirable to provide a mechanism to determine that the entries prefetched into the BHT are actually used by the processor. This further increases the prefetching accuracy for the items prefetched. This is achieved by providing each entry prefetched with a confirmation (used) bit as part of the BHT entry. The bit is initially unset (equals 0) when a prefetch occurs and reset (equals 1) if the prefetch is used during branch prediction. If the processor does not use the prefetched entry, the confirmation bit associated with that entry would prevent that entry from being prefetched in the future.

The above mechanisms are achieved by providing two new instructions: unload BHT (UBHT) and load BHT (LBHT). The unload BHT instruction takes the most recent (youngest) BHT entries and saves them (writes them) in a branch information save area, while the load BHT instruction reverses the direction that information is transferred. The load BHT instruction takes information from the branch information save area and writes it into the BHT. Since program execution patterns are repetitive, reloading the BHT with information collected during a previous execution phase of a program will produce a higher prefetch accuracy (prefetch to used ratio) than allowing the compiler to statically generate prefetches at compile time.

The contents of the PBHT are not based on the spatial and temporal referencing patterns, but on a relative certainty of future use as specified in the repetitive execution flow of a program. The PBHT control mechanism dynamically captures (saves) the branch information of a program and then prefetches (reloads) the relevant information back into the PBHT ahead of its use. Thus the processor requires fast access only to the branch information which is in close (logical) proximity to the current instructions being processed. This represents only a small subset of the information that would be contained in a full BHT. The information contained in a full BHT can be prefetched from main memory (collected in program save areas or compiler analysis) and prefetched into the PBHT, ahead of its use, to maintain a high prediction accuracy.

FIG. 1illustrates a prior art example of a processor100. The processor100includes an instruction pointer generator102communicatively connected to a decode module104. The decode module104is communicatively connected to an address generation unit106. A data cache108is communicatively connected to the address generation unit106and an execution unit110. A branch prediction unit116including a branch history table (BHT)120is communicatively connected to an instruction cache118. An instruction fetch address112is communicatively connected to an instruction fetch generator114. The instruction fetch generator114is communicatively connected to the branch prediction unit116and the instruction cache118.

In operation, instructions requiring operands are sent to the address generation unit106via the decode module104. The operands are fetched from the data cache108and the instructions are processed in the execution unit110. Stores are sent from the execution unit110to the data cache108.

The instruction fetch, and branch prediction mechanism processes occur in parallel to the decode, cache access, and execution flow described above. An instruction fetch address112is sent to the instruction fetch generator114. The instruction fetch generator114generates a next instruction fetch address and saves the next instruction fetch address in the instruction fetch address112. The instruction fetch generator114also sends the instruction fetch address to the instruction cache118. The instruction cache118sends the contents of the instruction fetch address the decode module104. Branch prediction occurs in parallel. The address of the instruction fetch is sent to the branch predict unit116.

The branch prediction unit116includes the BHT120that saves the branch address and target address of the most recently executed branches encountered by the processor100. The address from the instruction fetch generator114is compared with each branch address saved in the BHT. If a match occurs (a branch is contained in the most recent instruction fetch) the next instruction fetch address will be the predicted target address of the matching branch. This address then becomes the next instruction fetch and is sent back to the instruction fetch address112and instruction fetch generator114. If no match occurs, the next instruction fetch is the next-sequential address from the current instruction fetch address. Finally, BHT updates are sent from the execution unit110to the BHT120.

A prior art example of the BHT120format is illustrated inFIG. 2. The BHT120is represented as an array of entries where each entry contains a branch address202of a previously executed branch, a corresponding target address204, and branch tag information206. The branch tag information206contains information identifying the branch as conditional or unconditional, taken/not taken history patterns, changing target patterns, thread or process identifiers, and other prediction hints and instruction prefetch and execution information.

FIGS. 3aand3billustrate an exemplary embodiment of a high level block diagram of a program executed by a processor.FIG. 3aincludes a program consisting of 5 blocks. The first block302(A) represents program entry. In block302, the program begins execution and program linkage is established. Block302includes many instructions and branches, and branches to one of two subsections, blocks304B and C. Each block304may include many additional instructions and branches. These blocks304B and C merge into block304D. The program exit is shown in block306E.

FIG. 3bfurther illustrates an exemplary embodiment of a block diagram showing the prefetching of information into the branch predictor (loading a BHT entry) and the saving of information that was recently in the branch predictor (unloading a BHT entry). The BHT entry loaded includes a branch address and a target address of an upcoming branch.FIG. 3bincludes the program logic instructions and branches block304and a branch information save area (BISA)308. The BISA308represents a section of memory where branch prediction information (BHT information) is written and read. Two instructions are employed in the program logic instructions to prefetch BHT entries and save BHT entries-Load BHT (LBHT) and Unload BHT (UBHT). During a load operation, BHT information is read from the BISA308. During an unload operation, BHT information is written to the BISA308. The Unload BHT instruction allows a programmer to identify BHT entries that have been previously used for branch prediction and develop a run-time prediction mechanism to prefetch these entries back into the BHT120for future use.

New BHT updates are staged (prefetched) into the BHT320when a BHT load operation is added to the entry to each program logic instruction304. The BHT load operation avoids initial branch prediction errors caused by new (first time) taken branches. Initially the information contained in the BISA308is generated by a compiler, however future executions of the program will prefetch BHT entries that have been written to the BISA308by a previously executed unload BHT instruction. The prefetched BHT entries represent dynamically collected BHT entries that were saved the last time the program was executed. Dynamically collecting branch information and subsequent reloading of the branch information improves branch prediction accuracy while allowing the BHT320to be reduced in size.

FIG. 4illustrates an exemplary embodiment of a processor400including a branch prediction unit416having the BHT320memory, a new entry buffer402memory, and a new entry count404memory. The processor400includes a branch information save area308memory. The processor400also includes similar components that operate similarly to the processor100illustrated inFIG. 1.

FIG. 5illustrates an exemplary embodiment of the new entry buffer (NEB)402. The NEB contains entries having a branch address202, a target address204, tag information206, and a confirmation bit502. In operation, BHT updates (entries) are sent simultaneously to the BHT320and the NEB402. The tag information206corresponds to the BHT entry. The confirmation bit502may be, for example, a 1 or a 0. The confirmation bit502may be set to 0 when a BHT entry is prefetched into the BHT320and set to 1 if the BHT entry is used for branch prediction. An entry is used if it matches an instruction fetch address generated during instruction fetching. However, all BHT updates (sent from the execution unit110) that are entered into the NEB402have the confirmation bit502set to 1, indicating they are used and should be prefetched. Whereas a BHT may contain branch information on 4K to 16K difference branches, the size of the new entry buffer may be relatively small, for example, 8 to 32 entries. Its function is to hold branch information of the most recently executed branches. There are many management schemes that may be used for the entries in the NEB402, for example, first-in-first-out (FIFO) or least-recently-used (LRU).

The value in the new entry count (NEC)404register (ofFIG. 4) equals the number of entries made to the BHT320since the last Unload BHT instruction was executed. The NEC404register is incremented by one each time a new entry is made to the BHT320. Incrementing the NEC404stops when the value in the NEC404reaches the size of the NEB402. The NEC404register is set to zero when a Unload BHT instruction is executed. (The Unload instruction empties (copies) the contents of the NEB402into the BISA308.) The two paths link the branch prediction unit416to the BISA308. The paths are used to write information to the BISA308when an Unload BHT instruction is encountered.

FIG. 6illustrates an exemplary embodiment of the BISA308. The BISA308represents a section of memory that contains branch prediction information that is written to and read from the branch predictor. BISA308memory can be part of system or program save areas or part of the memory used to specify a Load or Unload BHT instruction. The BISA308includes a load length602equal to the number of entries written into the BISA308. Tag information606identifies information such as, for example, branch type (conditional, unconditional), program or thread ID, past taken/not-taken branch patterns, opcode information, or branch guess information. A target address604is also included in the BISA308.

The simplest form of a LBHT instruction prefetches a single BHT entry. The instruction consists of an opcode and branch/target address pair, where the branch/target address pair specifies the branch and target address for the upcoming branch. These addresses may be expressed as a relative distance from the LBHT instruction, base/displacement encoding of each address, register value plus offset, or represent the actual BHT entry settings (branch and target address values).

FIGS. 7a-cillustrate exemplary embodiments of Load BHT instructions.FIG. 7a, includes an opcode field702, a length field704, and an address identifier706. The length field704specifies the numbers of entries to load from the BISA308to the BHT320. The length field704may be expressed as a binary encoding in the instruction, or a register, where the value in the register indicates the number of entries to load. The address identifier706identifies the BISA308address that contains the branch prediction information (BHT320entries) to load. Opcode702allows simultaneous loading of the BHT320and NEB402, or independent loading of the BHT320. All entries loaded into the NEB402have a confirmation bit set to zero. The confirmation bit will determine if the entry is written into the BISA308when an unload BHT instruction is encountered.

FIG. 7billustrates an alternative exemplary embodiment of an encoding for the Load BHT instruction. The opcode field702, the length field704, and the address identifier706are similar to the fields described above regardingFIG. 7a. The load BHT instruction includes a mask value708that allows the load instruction to selectively load branch information according to, for example, address range, thread or program IDs, and branch types. For example, one mask value708may specify that only branch information (branch address602values found in the BISA) within n bytes of the Load BHT are to be loaded from the BISA308into the BHT320. In this example, the distance between the Load BHT instruction and the branch address602is determined by calculating the difference (in absolute value) between the address of the Load BHT instruction and each branch address602found in the BISA. The branch prediction information with branch addresses less than n bytes from the Load BHT instruction are then loaded to the branch prediction memory. The value of n may be, for example, from 16 to 4K.

Other examples of mask values708may specify a thread or program space identifier where only entries with matching tag information606(from the BISA308) will be loaded into the BHT320. Finally, other mask values708may select BHT entries according to an opcode type, or branch type (conditional, unconditional). All entries loaded into the NEB402have the confirmation bit set to zero. The confirmation bit will determine if the entry is unloaded into the BISA308when an unload BHT instruction is encountered.

FIG. 7cillustrates another alternative exemplary embodiment of an encoding for the Load BHT instruction. The opcode field702and the address identifier706are similar to the fields described above regardingFIG. 7a. The length field704is not included, however the length field704is specified as a value in the BISA308.

The formats for the Unload BHT instructions are illustrated inFIGS. 8a-cand9a-b. There are two types of unload instructions: an unload BHT instruction (UBHT) shown inFIGS. 8a-c, and an unload-with-confirmation BHT (UCBHT) shown inFIGS. 9a-b. The unload BHT instruction unloads all entries in the NEB402and writes the entries into the BISA308, while the unload-with-confirmation instruction only unloads entries in the NEB that have a confirmation bit set to 1, indicating that the entries are recently used. With UCBHT a programmer has a certain degree of confidence that prefetching the entries back into the BHT320will be beneficial since the entries were used the last time the entries were in the BHT320.

Referring toFIG. 8a, an exemplary embodiment of an unload BHT instruction is shown. Though the format of the unload BHT instruction is similar to the Load BHT instructions described above, the instructions operate differently.FIG. 8aincludes an opcode field802, a length filed804, and a BISA address806. The length field804may be used for two types of data. First, the length field804may specify the number of BHT entries to unload, and is specified as a part of the instruction. Second, the length field804may identify a register, where a value in the register denotes the number of BHT entries unloaded into the BISA308. (The unload instruction copies BHT entries contained in the new-entry-buffer NEB402and writes them into the BISA308.)

FIG. 8billustrates an alternate exemplary embodiment of an unload BHT instruction similar to the instruction ofFIG. 8a, further including a mask value808. The mask field808is similar to the mask value708illustrated inFIG. 7b, and identifies the information to unload. The mask value808may specify an address range, thread or program ID, or branch type. For example, one example of a mask value808specifies that only NEB entries with branch address values within n bytes of the unload instruction will be unloaded into the BISA308. The range of n may be, for example, from 16 to 4K. Other mask value808settings may specify a thread or program space identifier. Only entries with matching tag information (in the NEB402) are unloaded into the BISA308. Other mask value808may select NEB entries according to the opcode802, or branch type (conditional, unconditional). Since the number of entries unloaded into the BISA302may vary and depends on the actual contents of the NEB402at the time of the instruction execution, the length field804identifies a register, and the value in the register at the end of execution identifies the number of entries unloaded (written).

FIG. 8cillustrates another exemplary embodiment of an encoding of the unload BHT instruction. The mask808, and BISA address806are similar to the fields described above regardingFIG. 8b. The length field804is omitted but is specified as a value in the BISA308. The number of entries unloaded into the BISA308is written into a header portion of the BISA308.

FIGS. 9aand9billustrate exemplary embodiments of the Unload-with-Confirmation BHT (UCBHT) instruction. In operation, only NEB402entries that have a confirmation bit set to 1 will be unloaded into the BISA308.FIG. 9aincludes an opcode field902, a length field904, a BISA address906, and a mask value908. The length field904identifies a register, and the value in the register denotes the number of BHT entries unloaded into the BISA308at the end of execution.

The mask field908is similar to the mask value908illustrated inFIG. 8band identifies the information to unload. The mask value908may specify all entries, an address range, thread or program ID, or branch type. For example, if the mask value908is ‘all’, then all entries in the NEB402with a confirmation bit set to 1 are unloaded into the BISA308. If the mask value908denotes an address range, then only NEB402entries with branch address values within n bytes of the unload instruction, and their confirmation bit on, will be unloaded into the BISA308. Other mask value908may specify a thread or program space identifier. Entries with matching tag information (in the NEB402) will be unloaded into the BISA308. Other mask values908may select NEB entries according to the opcode, or branch type (conditional, unconditional). Since the number of entries unloaded into the BISA308can vary and depends on the actual contents of the NEB at the time of the instruction execution, the length field904identifies a register, and the value in the register at the end of execution identifies the number of entries unloaded (written).

FIG. 9billustrates an alternate exemplary embodiment of the Unload BHT instruction. The mask value908, and BISA address906shown are similar to the fields described inFIG. 9a. The length field904is omitted but is specified as a value in the BISA308. The number of entries unloaded into the BISA308is written into a header portion of the BISA308.

The technical effects and benefits of the above described embodiments provide a method and system for accurate branch prediction with a reduced amount of hardware.