Electrical Engineering

« first day (5215 days earlier) ← previous day next day → last day (15 days later) »

Nick Alexeev

02:10

@EzioMercer Let's say that each instruction takes 3 clock cycles to execute. During the 1st cycle the CPU loads the instruction from memory. During the 2nd clock cycle it executed the instruction. During the 3rd clock cycle it stores the result. If you predict [guess] what the next instruction is going to be, then you can load the instruction while the previous instruction is executing. You don't wait until the previous instruction executed, and that's how branch prediction speeds up the CPU.

Branch prediction in the CPU isn't perfect. Say you have a loop which iterates 100 times. There's a conditional jump at the end of the loop. Branch prediction will guess correctly 98 or 99 times, depending on predictor. It may mispredict at the end of the first iteration (depending how the prediction is wired). It will certainly mispredict at the end of the last iteration.

6 hours later…

Lundin

08:30

Pipelining and branch prediction are different though. What Nick described in the last message is pipelining, which can be present even in relatively simple CPUs with no cache. You just keep a number of instructions on standby and potentially flush the pipe if the execution path went in another direction.

Branch prediction is more about pre-loading instructions into instruction cache memory, so that the CPU can load them quicker from cache than by reading them from RAM. That's only relevant when you have a really fast CPU to the point where it can chew through instructions faster than the RAM access time.

Though in some embedded systems, instruction cache can also be used to compensate for the even slower flash memory, where it would otherwise have to use "wait states", essentially the CPU waiting for the flash to keep up.

I'd say the vast majority of embedded systems are Cortex M4 or lower, meaning they don't even have data cache let alone instruction cache. No instruction cache means no branch prediction. They could still have a pipeline though.

3 hours later…

bwDraco

11:47

@Lundin I would be extremely surprised for even embedded systems to not use a pipeline. Hell, AVR is two-stage.

Lundin

12:27

@bwDraco Yep that's what I'm saying, pipeline and branch prediction are similar but different features. I programmed a lot of HC12, tiny little 16 bitter. It had 5 stage iirc.

3 hours later…

Nick Alexeev

15:27

@bwDraco All ARM Cortex-Ms architectures are pipelined. Table here: en.wikipedia.org/wiki/ARM_Cortex-M#Instruction_sets

EzioMercer

16:14

@NickAlexeev @Lundin Thank you very much! So as I understand the `instructions` is not the direct command as I write in programming language

I understand it in that way:

Let's say I wrote something like this in code:

```
c = a + b;
c = c * c;
```

So the instructions are just the things which WILL happen and they are like this:

1. We will need A
2. We will need B
3. When we get A and B then we will need A + B
4. We will need store it in C
5. We will need multiply C by C
6. We will need store it in C

So if I'm correct the instructions don't necessary have actual values they are just future commands which will be executed. And the meaning of branch predictor is to PRELOAD the correct set of instructions

Am I right?

I just noticed this: @Lundin "Branch prediction is more about pre-loading instructions into instruction cache memory" So it seems that I'm on right way:)

Nick Alexeev

@EzioMercer "And then after some time..." Nope. The execution if the first instruction starts immediately. The branch predictor tries to guess [and it's an imperfect guesser] what the next instructions would be while while its already executing.

EzioMercer

@NickAlexeev When I said "After some time" I ment that when the actual values will come

So that means that in simple pipeline the most parallelled stages are Fetch, Decode and Execute but Memory and Writeback can do nothing. Is it correct?

Nick Alexeev

A branch predictor may be doing more than one thing. It may be guessing what the next instruction would be. (That's the branch predictors described in introductory textbooks about digital design and CPU architecture.) There may be another branch predictor which fetches instructions from slow DRAM into instruction cache. These aren't mutually exclusive.

@EzioMercer What books on digital design and CPU architecture have you read, or what courses have you taken?

EzioMercer

16:34

@NickAlexeev No one, I just read it by myself form the internet lectures, articles and SO answers. Sometimes I have to do some performance measurements so I have to take in account sometimes the branch predictor issue. And one day I was wondering how does really works under the hood so I started deep in dive as much as my little brain can understand on simple examples :)

I'm programmer on JS but I learned in university C/C++ and computer sciences so I have same basic understanding of how does things works under the hood

Wow! That is interesting. Didn't hear that there are several branch predictors with different stuff. Thanks!

I heard that some processors have a massive stuff to predict on the Decode stage which saves them 1 clock each time so they got a huge performance boost

Nick Alexeev

@EzioMercer Branch prediction is a cherry on top of a large corpus of CPU architecture knowledge. It's a tip of an iceberg.

I've got an undergraduate text "Digital design, intro to CPU architecture". It’s a good read by itself; it’s understandable without a class (without lectures, practicum, etc).

Branch prediction occupies maybe 6 pages in a 100-page chapter which introduces ARM architecture. That just scratches the surface. Preloading instruction flash based on branch prediction [what @Lundin described] is not even mentioned there.

EzioMercer

@NickAlexeev Did you mean this book amazon.com/Digital-Design-Computer-Architecture-Harris/dp/… ?

I couldn't find the book with exactly the same name as you suggested

Nick Alexeev

17:18

@EzioMercer Yes. I've got a slightly different edition, same authors: amazon.com/Digital-Design-Computer-Architecture-ARM/dp/…

EzioMercer

@NickAlexeev Thanks for exact link! I will try to read it)

github.com/last-genius/comp_arch_list/tree/master/books

May be someone also will need these books :)

Nick Alexeev

@EzioMercer There are also versions of this book for MIPS and RISC-V. Just as good to read.