Metaphor of the Branch Predict

"branch predict".

I was struck by that phrase in a meeting a few days ago. It was used by a software engineer describing what he thought the direction of a project management team would be regarding a new product. Rewording his statement: "My branch predict is that they will kill this program".

Of course, these type of metaphors are common. Body-based metaphors are the very common ("the leg of the table"). These are followed closely by metaphors using mechanical analogies arising from common occupations. These are generally used to describe one's internal thought processes and/or personal situation. I have a "sea of troubles", I'm "sailing against the wind", I've "got my nose to the grindstone", that really "fuels my fire" (its fun to think of these -- go ahead try it!).

And so you might expect our age of advanced computers to generate a number of such metaphors. It was interesting to hear this fairly hardware-bound metaphor move into the group think of the software folks..

Many enterprise codes, such as databases or ERP systems, experience lots of branches -- They are "branchy". The standard metric used in analysis is the average number of "instruction between branches". This is a measure on the dynamic instruction stream (tracking the instruction pointer) rather than based just on static analysis. For instance, running SAP SD's benchmark, R/3 executes on the average about 6 instructions before it hits a branch!

Because of the parallel nature of the way our microprocessors' internal architecture works, if we waited to branch our front end instruction decoder till all the conditional values that decide a branch were ready, we could not continue to fill the pipeline and the machine would stall. So we must predict with high accuracy which branch target is taken and start to work down that path. If we do this with high enough accuracy, then we can afford the occasional miss-predict, when we must re-steer the machine and throw away some temporary results.

To do this prediction, the hardware uses a number of heuristics. These are the "branch predict" of the hardware.

Some heuristics are clear. For instance, on x86, loops are written ending in a direct branch backward to the start of the loop. Since most loops actually loop in applications (isn't that nice), then on encountering a backward jump the first time, our best assumption is the take the branch. This is static branch prediction (Intel® 64 and IA-32 Architectures Optimization Reference Manual http://www.intel.com/design/processor/manuals/248966.pdf)

Other heuristics are more complicated to implement but, as you might imagine, attempt to remember the history of the branch. Nothing predicts the future as well as the past, or as Lord Byron (Letters/1821) said: "The best of prophets of the future is the past."

For the most part, the branch predictor in current hardware does a great job. For some floating point/numeric codes (SpecFP) the predictor can get 98%+ accuracy. SAP's R/3, which processes enterprise data from many users, the miss-predict rate is about 6%. (However, even at this rate, we lose 7-10% performance from what an oracle-type -- e.g. "perfect" -- predictor could delivery).

Using "branch predict" in the context that started this article has a certain natural simple charm. After all, its just a slightly geeky way of linking us to our hardware while saying the single word "predict". Which was what my colleague was doing here - simply predicting the future based on his best knowledge. He wanted to let the listener know he wasn't guessing about the future status of the program.

So, in these days, the Dilbert-ian static predict for a project is: "This project will be killed". Augmented with other dynamic knowledge (schedule slips, perceived value to the customer, etc.) my colleague was able to succulently state his informed opinion on the direction of the project he was describing to us.