In order to achieve high performance, wide-issue superscalar processors have to fetch a large number of instructions per cycle. Conditional branches are the primary impediment to increasing the fetch bandwidth because they can potentially alter the flow of control and are very frequent. To overcome this problem, these processors need to predict the outcome of multiple branches in a cycle. This paper investigates two control flow prediction schemes that predict the effective outcome of multiple branches with the help of a single prediction. Instead of considering branches as the basic units of prediction, these schemes consider subgraphs of the control flow graph of the executed program as the basic units of prediction and predict the target of an entire subgraph at a time, thereby allowing the superscalar fetch mechanism to go past multiple branches in a cycle. The first control flow prediction scheme investigated considers sequential block-like subgraphs and the second scheme considers tree-like subgraphs to make the control flow predictions. Both schemes do a 1-out-of-4 prediction as opposed to the 1-out-of-2 prediction done by branch-level prediction schemes. These two schemes are evaluated using a MIPS ISA-based 12-way superscalar microarchitecture. An improvement in effective fetch size of approximately 25 percent and 50 percent, respectively, is observed over identical microprocessors that use branch-level prediction. No appreciable difference in the prediction accuracy was observed, although the control flow prediction schemes predicted 1-out-of-4, outcomes.

In modern processors, deep pipelines couple with superscalar techniques to allow each pipe stage to process multiple instructions. When such a pipe must be pushed and refilled, as when predicted program flow beyond a branch is subsequently recognized as wrong, the temporary performance loss is significant. While modern branch target buffer (BTB) technology makes this flush/refill penalty fairly rare, the penalty that accrues from the remaining branch mispredictions is a serious impediment to even higher processor performance. Advanced mechanisms that can reduce this residual misprediction penalty can be of enormous value in future microprocessor designs. One promising new mechanism, the Misprediction Recovery Cache (MRC) is proposed previously. In this paper, we focus especially on MRC integration into existing pipelines.

In order to fetch a large number of instructions per cycle, wide-issue superscalar processors have to predict the outcome of multiple branches in a cycle, and fetch instruction blocks from multiple targets. This paper investigates a control flow prediction scheme that predicts the outcome of multiple branches by performing a single prediction. Instead of predicting the outcome of each individual conditional branch, this scheme considers a tree-like subgraph of the control flow graph of the executed program as a single prediction unit, and predicts the target of a subgraph at a time, thereby allowing the superscalar fetch mechanism to go past multiple branches per cycle. This approach is evaluated using the MIPS architecture, for a 12-way superscalar processor, and an improvement in effective fetch size of more than 50%, over an identical processor that uses branch prediction is observed for the SPEC integer benchmarks. No appreciable difference in the prediction accuracy was observed although the control flow prediction scheme predicted one out of four outcomes.