Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-04-30
2001-03-20
Eng, David Y. (Department: 2155)
Electrical computers and digital processing systems: processing
Processing control
Branching
Reexamination Certificate
active
06205545
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the execution of computer instructions in a computer system. More specifically, the present invention relates to a method and apparatus wherein a trace picker identifies traces of program code in a native code pool, and translates the traces for native execution, with static branch prediction hints encoded in branch instruction in the translated traces.
DESCRIPTION OF THE RELATED ART
Early computer systems serially executed one computer instruction at a time, and did not start executing an instruction until the previous instruction had completed. As the art of computer design progressed, computer designers began to incorporate various types of parallelism into computer systems.
One type of parallelism is pipelining. Pipelining breaks down the execution of a computer instruction into various steps, and processes multiple instructions simultaneously by overlapping these steps. Another type of parallelism is superscaling. Superscaling uses multiple execution units to process separate instructions simultaneously.
Branch instructions can limit the advantages provided by parallel design techniques. Often, when a branch instruction is executed, the condition that the branch instruction must test has not yet been determined. Early computer systems simply halted execution of the branch instruction (and subsequent instructions) until the condition was determined. However, this negatively affects performance. For example, in a pipelined computer often the pipeline must be emptied before the condition can be determined, which limits the benefits achieved by pipelining.
To address this problem, computer designers started to include mechanisms that predict branch behavior. When a branch instruction is encountered, the branch behavior of the branch instruction is predicted. Later, when the condition can be evaluated, the prediction is also evaluated to determine if it is correct. If the prediction is correct, execution continues and the advantages achieved by parallel execution are preserved. If the prediction is incorrect, instructions that were provisionally executed must be purged from the pipeline and the instructions from the correct branch must be executed. However, the penalty for an incorrect branch is typically not any worse than halting execution and waiting for the condition to be determined.
The performance gains achieved by branch prediction are, of course, strongly related to the accuracy of the prediction. Accordingly, many techniques have been developed to provide accurate branch predictions. One of the earliest techniques was to simply predict that a branch is always taken. Statistically, most branches are taken, so this technique proved somewhat successful. A similar technique predicts that backward branches are always taken, and forward branches are never taken.
Another technique uses an address table of addresses to which branch instructions recently branched. Typically, the table consists of an associative memory having 4 to 8 entries. If an address in a branch instruction also appeared in the table, then that address is used as the predicted execution path.
A more sophisticated approach was disclosed by James E. Smith in U.S. Pat. No. 4,370,711. Smith disclosed a random access memory (RAM) having, for example, 16 entries, each containing a two bit count capable of assuming the values +1, 0, −1, and −2. A hash mechanism transforms the branch instruction address into a four bit address that accesses the RAM. If the value stored in an entry associated with a branch instruction is +1 or 0, then the branch is predicted as taken. Otherwise, the prediction is that the branch is not taken. After the branch instruction is executed, if it is taken, the count memory entry is incremented up to a limit of +1. If it is not taken, the count memory address is decremented down to a limit of −2. The prediction scheme disclosed by Smith incorporates branch history in the formulation of the branch prediction. For example, if the branch has been taken several times, it must be not taken twice in a row to change the prediction. Many computer systems use some variation of this scheme, with a table that stores a prediction and a hash function that associates a branch instruction with a prediction.
Another approach is disclosed by Hanan Potash in U.S. Pat. No. 4,435,756. Potash discloses encoding a branch prediction in each branch instruction based on whether it is probable that the branch condition will be evaluated as being true or false. In another embodiment, Potash discloses encoding branch history and a branch prediction in a branch instruction. In this embodiment, if the prediction proves to be incorrect two times in a row, the prediction is changed, which requires encoding a new prediction into the branch instruction and writing the branch instruction back to memory. Note that the branch instruction must also be written back to memory whenever branch history changes, even if the prediction does not change. This creates a large amount of write data, which lowers I/O throughput. For example, a branch instruction that alternates between two branch paths must be written back to memory every time it is executed.
Certain computer systems manufactured by Hewlett-Packard Company have used two types of branch prediction; a hardware-based branch prediction scheme that uses a prediction table to store dynamically generated branch predictions close to the CPU, and a software-based branch prediction scheme that encodes static branch predictions into each branch instruction when a computer program is compiled. With software-based branch prediction, the prediction is encoded in the branch instruction based on the order of the operands in the compare function. Specifically, if the first register number is lower than the second register number, backward branches will be predicted as taken and forward branches will be predicted as not taken. On the other hand, if the first register number is equal to or higher than the second register number, backward branches will be predicted as not taken and forward branches will be predicted as taken. For example, consider the following compare and branch (COMB) instructions, and assume that both instructions branch forward:
COMB,<R5, R3, Address,
and
COMB,>=R3, R5, Address.
A branch prediction of “taken” will be encoded in the first instruction and a branch prediction of “not taken” will be encoded in the second instruction, even though the instructions are logically identical.
To generate effective predictions, it is necessary to perform a “profile-based optimization” (PBO) run, wherein branching behavior is observed while an application is executing in a typical computing environment. After the PBO run is complete, the user's application is recompiled to incorporate updated branch predictions based on branching behavior observed during the PBO run.
An advantage provided by prior art software-based branch prediction techniques it that the prediction can be based on behavior observed over an extended period, not just the last branch or two. Also, software-based branch prediction requires less complex, less expensive hardware. It is much simpler to design hardware that only implements a branch prediction, compared to hardware that must also judge the accuracy of predictions and update predictions accordingly.
A disadvantage of software-based branch prediction techniques is that the prediction is static and does not adapt to changes in program data or the computing environment. Once the prediction is compiled into the branch instruction, it is not changed.
An advantage provided by hardware-based branch prediction techniques is that the prediction mechanism is completely transparent to the user of the computer system. In addition, predictions adapt dynamically to changes in the computing environments that may affect branching (such as changes in information stored in databases). Also, predictions tend to be very accurate when the prediction table is large or a pr
Buzbee William B.
Mattson, Jr. James S.
Shah Lacky V.
Eng David Y.
Hewlett--Packard Company
Plettner David A.
LandOfFree
Method and apparatus for using static branch predictions... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for using static branch predictions..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for using static branch predictions... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452056