Thinking ahead - the joys and pitfalls of speculative execution

"Think ahead" is nearly always a good piece of advice for nearly all aspects in life and is something which we do - or at least should do! - regularly in our work. But the recent scares over Intel processor vulnerability (Meltdown and Spectre) means that it's not without its pitfalls. In this article, we'll talk about Speculative Execution, what it is, and in particular what it means for mathematical algorithms.

"Speculative Execution" is the technical term used in computer science to mean "thinking ahead" and its concept should already be familiar to anybody who plays chess at a half decent level. When making a move, you are constantly thinking "If I move *here* then what if my opponent moves *here*? Or *there*?"

And likewise, while your opponent is thinking about making his or her move, a good chess player doesn't sit there thinking about last night's Big Bang Theory episode until it's his/her turn to move again, he/she is also trying to work out in advance what to do next, depending on how the opponent responds. Speculative execution is a bit like that.

OK let's give an example. Note that like all analogies, this is massively, massively simplified and you shouldn't take the analogy too far. But let's have a go anyway. Suppose you are faced with the following problem :

1. Start facing North

2. Turn 90 degrees to the right

3. Turn about face

4. Turn 90 degrees to the left

5 If your current direction (in English) contains the letter 'S' then turn 90 degrees left otherwise turn right

6. Turn left 90 degrees a number of times equal to the number of vowels in your current direction

7. Turn about face if your current direction has an 'E' in it

I think (if I've worked it our correctly) that by this stage you should be facing West. To check my answer (here we go, P versus NP again!) I can't see any way of checking it other than following the steps through one by one from the start through to the end.

Now imagine there are a HUNDRED rather than just 7 steps to do. This could now take you an hour instead of a few minutes! However your luck is in! Your four best friends Alice, Bob, Cheryl and Dave all show up and they offer to help. They are all very reliable and diligent and you know you can trust their work to be totally accurate.

"I'm not sure how you can help" you say "It's literally a question of me ploughing through this set of instructions one at a time until I reach the end. You can help by making me cups of tea, fetching me some biscuits or even massaging my shoulders, but apart from that, I can't see how you can help other than just standing around while I work my way through this alone"

"Nonsense" says Alice. "I'm sure we can halve your time to solve the problem. That means we'll have plenty of time left this afternoon to all go for a beer to celebrate"

"How on earth are you going to do that?"

"Simple" says Alice. "Let's look at instruction number 50. We don't know in advance what direction you will be facing at that stage, but we do know it will either be North, East, South or West. So, I'll do steps 51 to 100 working on the assumption that step 50 lands you facing North. Bob can do steps 51 to 100 working on the basis that you'll be facing East at step 50, Cheryl, likewise based on the assumption you're facing South, and Dave can take West. You can do steps 1 to 50 and tell us the answer when you get there"

Working your way through, you get to step 50. "I'm facing South" you shout. "That's me!" shouts Cheryl. "I started at step 50 facing South and when I finished at step 100 I was facing East at the end"

"Oh well" smile Alice, Bob and Dave, screwing up their calculations and throwing them in the waste paper basket, "although our work was in vain, between us as a team we managed to halve the solution time with each of us doing the same amount of work and nobody idle"

Now, this is a little frivolous example on algorithm execution time and not on computer security, so I'll keep the technical details about MELTDOWN and SPECTRE to a minimum. There are plenty of resources on the web you can look up if you're interested further. But basically, before Alice, Bob and Dave threw their calculations in the bin, they existed for a brief moment. And in this little example, they just contained some worthless calculations, but in real-life examples on a computer processor, these calculations could contain sensitive passwords to bank websites etc. fetched out of memory.

The whole issue though, does raise interesting thoughts about the value of speculative execution and the realisation that faced with a problem which initially looks "linear", can be processed in part in "parallel", discounting along the way, the branches of the algorithm which don't work out. Which now takes us towards the theory of Non-deterministic Turing machines. But we'll look at those another time, that's enough for today! Enjoy!