Software branch prediction via inter-procedural path profiling

Abstract

The technique of predicting branch directions before execution is defined as branch prediction. Conditional branches pose a hazard to the instruction flow since the instruction that executes after the branch is not known. When a branch appears, the next instruction is not known till the branch is executed. Either instruction fetch has to be halted or the branch direction has to be predicted. With some degree of probability the latter method of predicting branch directions has yielded good results. Several authors have suggested ways of predicting the direction of conditional branches with hardware that uses the history of previous branches. The branches are predicted statically, which occurs during compile time, or dynamically, which occurs during run-time. Dynamic methods have shown the better performance over static schemes. They employ one or two levels of history information and prediction accuracy scales proportional to the history information. So employing larger branch tables, which store the branch histories, we get good performance With reducing chip area, larger tables would occupy a significant portion of chip area. We propose a technique called software branch prediction, where the branch tables reside in the physical memory along with the application. The branch tables no longer reside in the hardware and so chip area occupied by the tables is freed. Software branch prediction performs as well as hardware predictions in terms of prediction accuracy, but the execution time of the application is increased by 50 - 100 %. Since accessing software tables takes longer than hardware tables, the execution time is higher. We need to identify ways to reduce the execution time. We propose one such mechanism called pivot branches. Pivot branches are branches whose execution can determine the direction taken by a few or more branches. We could predict more than one branch direction by correctly predicting pivot branches at one time. Two different methods were attempted to determine the existence of pivot branches. They are code inspection and inter-procedural path profiling. Path profiling was done on two SPEC benchmarks. The results did not clearly indicate if pivot branches exist, but it shows that there are gains doing predictions this way.