Research On Kev Techniques Of Conditional Branch Processing

With the increasing demand for complex embedded applications, techniques such as superscalar, deep pipelines and speculate execution are employed in modern microprocessors to explore great degrees of instruction parallelism. On the other hand, conditional branch instructions with the characteristic of conditional execution and flow control bring a deleterious effect on the instruction level parallelism. Consequently, techniques mentioned above rely on accurate conditional branch processing in order to develop their potential. This thesis focuses on key techniques of high performance conditional branch processing. The original contributions of this thesis are as follows:1. Branch prediction based on dynamic polarity transformation. By study and analysis of the temporal locality property of branch misprediction, a new branch prediction strategy is proposed, which based on dynamic polarity transformation. This approach monitors original branch misprediction rate whose polarity has not been transformed, and detects the periods with original branch misprediction rate higher than a threshold. These periods are called as peaks of misprediction. The polarity of original prediction results will be transformed to make the final prediction during peaks of misprediction, which keeps the final branch misprediction rate at a low level. This scheme can solve problems which traditional branch alias branch predictor cannot solve.2. Multi-layered filter (MLF) branch prediction. By study and analysis of the spatial locality property of branch misprediction, a new branch prediction strategy is proposed, which is called multi-layered filter (MLF) branch prediction scheme. The MLF prediction divides the prediction space of branch into multiple layers, and monitors the misprediction rate of each layer. In MLF prediction, only few difficultly predictable branches of each layer are filtered to next layer, and the sub-predictor of next layer can be dedicated to these difficultly predictable branches, improving the prediction accuracy and hardware efficiency. The filtering mechanism can solve the problem of low hardware resource utilization efficiency which traditional multiple-bank based branch predictors suffer.3. Multiple-level buffered parallel branch prediction and adaptive prediction granularity parallel branch prediction. A multiple-level buffered parallel (MLBP) branch prediction is proposed at first. The MLBP prediction accesses the predictor continuously in cycles when there is no conditional branch, and prefetch the prediction results of future branches. The prediction results prefetched are buffered at different levels. When multiple conditional branches are fetched at the same time, the prediction results buffered before will be allocated to these branches synchronously. This scheme can get a good performance in processors with an instruction fetch bandwidth less than or equal to eight. Then we further propose a new branch prediction scheme which based on adaptive prediction granularity. The new scheme adaptively changes the prediction granularity according to the bandwidth of instruction fetch and the behavior characteristics of branches. More specifically, different numbers of branches constitute an instruction package, and the branch histories are maintained in packages. As a result, this prediction scheme can process any number of branches in a single package. This prediction scheme can get high prediction accuracy in processors with any instruction fetch bandwidth.4. Loop accelerating scheme based on reuse of decode buffer and PC transmission across pipelines. By study and analysis of the characteristics of loop body, a new loop accelerating scheme is proposed, which is based on reuse of decode buffer and PC transmission across pipelines. The new scheme reduces the information needed in decode buffer by transferring PC related information across pipelines, which makes the design of decode buffer with many entries possible. Moreover, the new scheme reuse the decode buffer to process loops in program. That is, a loop body area will be created in decode buffer when a loop conditional branch turns up. Then during the loop execution time, the loop body instructions will be provided by the decode buffer, which improves the efficiency of loop execution. The new cheme further adopts the self-circulation wide issue mechanism to make up the performance losses caused by the loop body alignment problem, loop joining problem and cache output bandwidth problem.Techniques proposed in this thesis facilitate the high performance processing of conditional branch, and have positive effects on both theoretical researches and practical applications.