Next: Speculation with Branch Up: Limits of Control Previous: Introduction

Relaxing Control Flow Constraints

The perfect branch prediction of an oracle machine is an upper bound of all other techniques to relax control flow constraints. Unfortunately, it is also an unrealistic upper bound. Because branch outcomes are known in advance on an oracle machine, no instructions have to wait for branches to be resolved. To achieve the same performance, a machine must speculatively execute all possible paths through a program. This requires hardware resources exponential in the number of outstanding conditional branches. Since perfect branch prediction is not realistic, more practical techniques are required to handle control flow. This section examines three techniques: speculation with branch prediction, control dependence analysis, and following multiple flows of control.




Next: Speculation with Branch Up: Limits of Control Previous: Introduction


Bob Wilson