Control flow prediction with tree-like subgraphs for superscalar processors

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.