Control Flow Prediction with Tree-Like Subgraphs for Superscalar Processors

Simonjit Dutta, Manoj Franklin

Abstract

Changes in control flow, caused primarily by conditional branches, are a prime impediment to the performance of wide-issue superscalar processors. This paper investigates a control flow prediction scheme that mitigates the effects of control flow changes caused by conditional branches. 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 processor 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.

Keywords

Branch prediction, Control flow prediction, Instruction-level parallelism, Speculative execution, Superscalar

Talk Overheads (74440 bytes)