4 ms·

I think the Pentium is more or less the first microprocessor with branch prediction. Certainly the most mainstream. PowerPC 601 arrived at more or less the sam

by phire 2mo ago

I think the Pentium is more or less the first microprocessor with branch prediction. Certainly the most mainstream. PowerPC 601 arrived at more or less the same time, and the Alpha 21064 was a year earlier. There were a few minicomputers and mainframes before that with branch predictors. Arguably the 486 could have done with a branch predictor (even a single entry loop predictor would have helped), and maybe the 386 too. But microcoded CISC designs didn't benefit much from predictors because they have multiple cycles to work it out. And RISC cpus were in their "branch delay slots are awesome" phase throughout most of the 80s. With a bit of trickery (very simple branch conditions and a 2 phase clock), your classic 5-stage MIPS design can fully hide all branches with just a single branch delay slot, so they were a little slow to adopt predictors. I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.

toast0 2mo ago
> I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be. It's got a lot to do with how cpu clock speeds were getting way faster, but ram wasn't. That's what makes deeper pipelines attractive, and if you give a cpu a deeper pipeline, it's gonna want a good branch predictor.
- phire 2mo ago
  I'm more thinking about how MIPS were quite late to branch predictors. They were shipping the high-performance R4000 and R4400 with 8 stage pipelines and no branch predictors. They could have really done with a branch predictor, each branch took three cycles (and the branch delay slot could fill only one instruction, often a useless NOP). The Pentium only had a 5 stage pipeline and massively benefited from its branch predictor. IBM was slapping branch predictors on PowerPC designs with 4 stage integer pipelines. You simply don't need a long pipeline to justify the benefits of a branch predictor.
adrian_b 2mo ago
Pentium was the first CPU with a branch predictor that many people could afford to buy. Before dynamic branch prediction, where the prediction for every branch is updated after each branch execution, depending on its history, static branch prediction had been used for decades, since around 1960, typically using the rule that forwards branches are unlikely to be taken, but backwards branches are likely to be taken. An alternative was to have an instruction bit where the compiler stored its prediction about the probability of a branch being taken. Dynamic branch predictors began to be used since the mid seventies. I do not remember now if any notable monolithic CPU had a dynamic branch predictor before Pentium, but prior multi-chip CPUs certainly existed.
- phire 2mo ago
  > Before dynamic branch prediction... static branch prediction had been used for decades. I'm not sure that's true. At least not the "predict backwards branches are taken" part. Many RISC cpus did kind of have "predict forwards as not taken", but really thats just speculative execution with the complete absence of any branch prediction at all. IMO "All branches are not taken" is not a prediction. Actual Static Branch prediction is something that seems to have shown up at the exact same time as dynamic branch prediction (ie Pentium and PowerPC 601). Seems to be more of a "well do speculative execution now, what do we do when there is no dynamic prediction?" thing. Maybe there is a multi-chip CPU out there that has proper static prediction but not dynamic? But I checked the likely candidate (The RS/6000 aka POWER1) and it doesn't have any prediction at all (just a hole where the static prediction bits will go later). Probably because static prediction requires support for speculative execution, which it doesn't do.

by phire 2mo ago

toast0 2mo ago

> I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be. It's got a lot to do with how cpu clock speeds were getting way faster, but ram wasn't. That's what makes deeper pipelines attractive, and if you give a cpu a deeper pipeline, it's gonna want a good branch predictor.

phire 2mo ago
I'm more thinking about how MIPS were quite late to branch predictors. They were shipping the high-performance R4000 and R4400 with 8 stage pipelines and no branch predictors. They could have really done with a branch predictor, each branch took three cycles (and the branch delay slot could fill only one instruction, often a useless NOP). The Pentium only had a 5 stage pipeline and massively benefited from its branch predictor. IBM was slapping branch predictors on PowerPC designs with 4 stage integer pipelines. You simply don't need a long pipeline to justify the benefits of a branch predictor.

adrian_b 2mo ago

Pentium was the first CPU with a branch predictor that many people could afford to buy. Before dynamic branch prediction, where the prediction for every branch is updated after each branch execution, depending on its history, static branch prediction had been used for decades, since around 1960, typically using the rule that forwards branches are unlikely to be taken, but backwards branches are likely to be taken. An alternative was to have an instruction bit where the compiler stored its prediction about the probability of a branch being taken. Dynamic branch predictors began to be used since the mid seventies. I do not remember now if any notable monolithic CPU had a dynamic branch predictor before Pentium, but prior multi-chip CPUs certainly existed.

phire 2mo ago
> Before dynamic branch prediction... static branch prediction had been used for decades. I'm not sure that's true. At least not the "predict backwards branches are taken" part. Many RISC cpus did kind of have "predict forwards as not taken", but really thats just speculative execution with the complete absence of any branch prediction at all. IMO "All branches are not taken" is not a prediction. Actual Static Branch prediction is something that seems to have shown up at the exact same time as dynamic branch prediction (ie Pentium and PowerPC 601). Seems to be more of a "well do speculative execution now, what do we do when there is no dynamic prediction?" thing. Maybe there is a multi-chip CPU out there that has proper static prediction but not dynamic? But I checked the likely candidate (The RS/6000 aka POWER1) and it doesn't have any prediction at all (just a hole where the static prediction bits will go later). Probably because static prediction requires support for speculative execution, which it doesn't do.