CPU Pipeline - Computerphile

How do CPUs make the most efficient use of their compute time? Matt Godbolt takes us through the pipeline - allowing the CPU to do work as many ticks of the system clock as possible!
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharanblog.com
Thank you to Jane Street for their support of this channel. Learn more: www.janestreet.com

[@pyromen321]

Somehow I missed that this guy is Matt Godbolt! Compiler explorer is without a doubt my favorite tool in software engineering as a whole!

[@londonbobby]

What? the guy who created the BBC micro emulator that runs in a browser? Wow, he's a genius 🤩

[@axelBr1]

I was going to comment about Compiler Explorer. I've only recently heard of it, and it's amazing. I recently used it to test my assumption about the declaration of a variable used in a loop. I'd always declared the variable outside the loop, (this is going back a few decades), to avoid the cost of it being repeatedly created inside the loop. The drawback of course is that inside the loop you have some "random" variable and have to go searching for its declaration, (of course not such a big issue with modern IDEs). It recently dawned on me that may be the compiler is smart enough to move the declaration outside the loop for me. I tested this out in Compiler Explorer and it's amazing to see what the compiler will do; declaring inside the loop creates smaller code (presumably faster) as the compiler knows the variable is going to be discarded and appears to even optimise away its creation and tidy up after use.

[@Functionviktor]

I use it always in my days now to see what my C++ code generates in assembly and now I'm dominating in reverse engineering using that knowledge 😅

[@crystalsoulslayer]

Shoutout to the people that design processors. This is hard enough to understand as an abstraction, much less when you try to de-abstract it. All of this is being done with _physical circuitry_ inside the computer. Utterly mind-boggling. Hats off.

[@unvergebeneid]

Also shout-out to the people discovering side-channel attacks. They have to understand the internal workings of these CPUs _at least_ as well as the engineers :D

[@thewhitefalcon8539]

Actually I think it's not so hard to design a 80s era non pipelined CPU if you know digital logic.

[@dascandy]

@@thewhitefalcon8539 The logic is the simple part. It's the clocking that makes it harder, and every year in progress beyond the most basic CPUs keeps adding to it.

[@rafa_br34]

@@unvergebeneid Honestly if you stop to think about it side channel attacks aren't hard to understand, the clever part is just using cache to test if the guess was correct or not.

[@meneldal]

It has been many years since people don't design the circuitry by hand, there's just nobody smart enough and with enough free time to do it by themselves. There are people who make software that converts your design into actual plans to send to the fab, people who design and simulate the cpu design and so on. People can only understand deeply a tiny part of the whole process.

[@MattGodbolt]

A huge shout out to Sean's fantastic animations! Thanks Sean! 🎉

[@Computerphile]

We'll shovel some more binary soon!

[@smoorej]

As a former IBM/370 Assembler programmer I approve of this presentation!

[@goldnutter412]

👏👏👏

[@NateEngle]

I always found the PDP 11 architecture very elegant, but of course C was the most productive way to write it so the closest I usually got to PDP assembly was designating some integers as register variables and then happily admiring what was written into the intermediate .a files being the System III C compiler I think the instruction set I spent the most time writing actual code for (and hence cursing over it's many flaws) was the i8031 (and its various later versions), but the internal operation of that thing made efficiency experts weep. It was kind of a learning environment for CPU designers whose ideas were inspired by the microcontroller that chose to do everything in the least intelligent manor.

[@easyactually]

Can't believe rollercoaster tycoon was made in assembly

[@TerrorTerros]

Performance was amazing though, it really showed 😮

[@georgeprout42]

I can. Chris Sawyer joined the European Coaster Club and came on a few trips to Europe with us. He went from "I have an idea for a game" to an adrenaline junkie with his first ride.

[@codycast]

yO mamma was made in assembly

[@casinatorzcraft]

I can. You can still abstract with subroutines and such

[@aaronbrown3820]

That guy is a real software engineer, unlike the react kiddies of today

[@trevinbeattie4888]

That last segment about parallel execution units where one might need to wait for the other to finish reminded me of the optimization options in gcc (at least a decade or two ago) where the compiler would figure out how to order the instructions to avoid such dependencies in the CPU pipeline without materially altering the results of the code. As I understand it, modern processors can do instruction re-ordering on the fly to get the same optimization results. It’s rather mind-boggling to me as I’ve just got a rudimentary understanding of microcode as a simple series of opening and closing logic gates (thanks to Ben Eater’s videos.)

[@SupaKoopaTroopa64]

Another interesting way the pipeline is kept busy is the uOP cache. Imagine the executor robot keeping a list of frequently accessed instruction addresses, and what instructions they contain. When the executor calculates the address of the next instruction, it can check it's address book, and if it finds a match, it can start executing that instruction without waiting for it to be fetched and decoded. Modern CPUs usually keep a book of ~5-7 thousand entries.

[@unvergebeneid]

Can't wait to see more from Matt!

[@stupossibleify]

Any podcast or video benefits from Matt Godbolt appearing

[@MattGodbolt]

Aww shucks :) Thank you very much!

[@jms019]

Some years back a particularly stupid agency didn’t get that my skills including assembly did in fact match a job requirement assembler.

[@kayakMike1000]

I am learning about CPU pipelines now. I am working on a RISC-V with a five stage pipeline.

[@lucidmoses]

As per your analogy, Having two sets of the fetch-decode lines per arithmetic unit would also work now that multiple threads are more common.

[@BoomBaaamBoom]

Thank you for making Compiler Explorer. It is very helpful to me!❤

[@CallousCoder]

This video should’ve be done 20 years ago when I tried to explain pipelining, super scaling and out of order processing to our intern in the context of pipeline poisoning due to unnecessary branching that I saw in a section of his code. Where actually making the code branchless with relative expensive multiplication instructions made it 5 times faster. It’s staggering how quickly the complexity branches out having to explain that to a CS that only works in theory and has no concepts of hardware layer. And soon you’re also touching out of order processing and super scaling 😂

[@avi12]

3:24 Mega-Hertz means millions of times per second, not thousands Thousands of times per second would be kilo-Hertz

[@NickEllis-nr6ot]

Absolutely brilliant explanation!

[@anton_verdi]

Beauty! Absolutely genius and interesting explanation!

[@KipIngram]

You can design your processor so that the branch "decision" is separated from the branch "action." Imagine having separate fetch and execute units. Between the two, there is a "flag" system - a flag can be empty, true, or false. Starts out empty. So you put the branch decision code as early as you can (you can't always separate them by much, but sometimes you can). As soon as that gets executed, the execute unit will post the result into the flag (so it's now either true or false). Meanwhile the fetch unit is "fetching ahead" - it will eventually see the branch action instruction, and will consult the flag. Hopefully the flag has been set - if so, the branch unit knows exactly what to do and can carry on. If the flag is still empty, though, then we have the problem you're discussing and we have to block until that flag value arrives. But by separating them like this we give ourselves "maximum opportunity" to avoid losing time.

[@Roarshark12]

Thanks so much for this video. Can you please also cover Tomasulo's algorithm?

[@MattGodbolt]

I hope to get there :) we're kinda heading in that direction...

[@Roarshark12]

@@MattGodbolt yeay!! It's something I really enjoyed learning about twenty-plus years ago in the CPU architecture class I took in computer engineering in college. I wonder what new innovations beyond that (and tournament predictors) have been made since I graduated in 2003. Also: I appreciated your lecture style, funneling from the most abstract ideas and intentions down into the nuts and bolts of how things get done inside a CPU.

[@vadrif-draco]

Very cool and informative animations! :)

[@TheUglyGnome]

This imaginary processor is not well suited for pipelining. Execute stage uses more than one clock cycle every time it needs to access memory. That's why pure RISC processors are load/store architectures. They don't need to access memory during execution stage. Their instruction sets are designed for pipelining from the start.

[@adingbatponder]

Have you got a link or further info on this. The difference seems important. Cheers.

[@TheUglyGnome]

@adingbatponder There's a great Wikipedia article "Classic RISC Pipeline". Also article "Load-store architecture" gives a bit of background info. For further reading, at least early editions of the book "Computer Architecture: A Quantitive Approach" by David Patterson & John Hennessy have great info about RISC vs. CISC pipelining.

[@FalcoGer]

And now superscalar, out-of-order, speculative execution with multiple execution units, register renaming and with multilevel cache, multicore and multiple memory channels, and of course virtual addressing. and how to avoid cache timing side channel attacks in such a setting.

[@noname2588o]

Requesting suggestions for some more reading/video resources to learn more on this and in general about computer architecture, compilers and os and kernel internals.

[@olafurw]

Matt! The best!

[@trevinbeattie4888]

Love Matt’s T-shirt

[@ACCPhil]

I could understand the 6502. I miss those days. But the conditional instructions in ARM, we down down before Sophie.

[@aaronr.9644]

OMG!! Godbolt!!! I didn't realise he contributed here.

[@kwazar6725]

Oh. Nice intro to instruction pipeline. Welcome to cpus

[@tlhIngan]

ARM is known for its conditionally executed instructions, except these days it's not done anymore. AArch32 (ARM 32 bit) still supports it, but AArch64 (64 bit ARM) does not support it. This is because conditional execution is incompatible with superscalar architectures (where you can execute more than one instruction simultaneously), so AArch64 code only allows conditionals in certain conditions. And on the very small end, Thumb never supported conditional execution at all. This was due to the limited length of a Thumb instruction.

[@meneldal]

Conditional execution for almost every instruction is also a bit a waste of space and limits the amount of instructions / size of literals you can have in the instructions. They were also not used as much as they could have, making them feel like even more of a waste.

[@j7ndominica051]

What's the LCD clock in the background scrolling names of programming languages and some number?

[@MattGodbolt]

It's a Tidbyt graphic display, showing the number of compilations by programming language of Compiler Explorer

[@jacejunk]

@3:24 "Megahertz - thousands of times per second" could have been rephrased as "Kilohertz", or "millions of times per second".

[@mytube001]

Well, it IS thousands of times per second, just thousands of thousands! :D

[@SeanHoulihane]

This was just starting to get interesting...

[@iNireus]

There needs to be more on micro coding, I do wonder now if they need to revisit microcoding

[@dj10schannel]

Cool

[@Lion_McLionhead]

Guess pipeline optimizations didn't hit PC's until the 486 but the marketing for the 586 was the 1st time public became widely aware of them. PGCC was just starting to bring delay slot optimizations & out of order instructions to the gcc series by 1997. Primitive, early microprocessors from the stone ages indeed.

[@Roxor128]

The original 8086 actually had some pipelining, except it wasn't for instructions, but for the microcode used to execute them. See Ken Shirriff's blog series on reverse-engineering the 8086 if you want some detail.

[@zxuiji]

Instead of branch prediction should just preload both via 2 data buses (adaptor circuit can be used for ensure only 1 fetch is passed onto the ram/hdd/ssd/etc at a time - ones designed for dual data buses can just use 2 slots which is easily detected by other hardware). While the CPU is waiting for the 2nd data bus to catch up with the 1st bus it sent a fetch along it can do it's comparison. Think about it, you have to fetch 2 values in some cases to compare already, then you have 2 branches to fetch for, just optimise for fetching both at once and ignore any data you wind up not using.

[@meneldal]

You can do that for the basic branches, but this doesn't work for indirect branches, as the destination could literally be anywhere.

[@zxuiji]

@@meneldalNot really, just delay fetching the values to compare for after fetching the addresses of the indirect branches. Then use those addresses after fetching the values to compare. Not rocket science.

[@meneldal]

@@zxuiji The problem is you don't know the addresses, that's the whole point. Like a switch written as "add pc, r5" (or various variations depending on architecture), while you can't predict r5 because it is the result of a computation just before.

[@zxuiji]

@@meneldal Ah, that one. Thought you were on about callback functions straught after if statements (or switch statements)

[@zxuiji]

@@meneldal Just thought of a partial fix for that problem. Build ALUs into memory devices like RAM. Doing so allows the CPU to offload the task to the source memory device which requires only 1 fetch, the fetch of the result. That is assuming the both values come from the same source anyways.

[@rafa_br34]

Excellent video, Quite disappointed it didn't touch into branchless programming much.

[@goldnutter412]

Perfect 🤣👏

[@dyretna681]

Ok ready for TIS-100

[@doge8530]

3:20 Megahertz, so thousands of times per second. Kilo is thousand, Mega is million. I don't mind mistakes, but it really takes away from the thought that Giga means literal billions of clock cycles per second in modern processors

[@mytech6779]

It is thousands. Thousands of thousands in fact.

[@tiredcaffeine]

@@mytech6779 The guy in the video said "thousands of times a second". "Thousands of times" doesn't mean "thousands of thousands of times".

[@mytech6779]

@@tiredcaffeine One is inclusive of the other. If you have 100 of something then you also have 10 of that same thing. My 3.8Ghz 8 core CPU is in fact capable of thousands of operations per second, many many thousands.

[@tiredcaffeine]

@@mytech6779 However in daily usage we say millions when we mean millions, not thousands.

[@mytech6779]

@@tiredcaffeine That's fine but it wasn't being used daily he just used it once.

[@gsestream]

maybe this tech pipe needs some unglogging. gpgpu with cpu compatibility.

[@Rowlesisgay]

Now somehow simplify superscaler out of order pipelined VLIW (I know VLIW is not out of order or even really superscaler) risc (I know risc and VLIW is mutually exclusive) multi-core cpus with 14 layers of cache.

[@jaydenritchie1992]

i cant remember if its il or 'e levore (i work) 'e (for) ono plata (one plate) munjari pasta (feed/eat pasta)

[@sudazima]

ive played enough factorio to know how CPUs work

[@FCHenchy]

The non-binary robot bit was adorable. Thank you.

[@KipIngram]

Yes - it. A robot is an it. And robots don't have minds. They're doing the same thing you're trying to model here - they just follow a set of instructions.

[@rumplstiltztinkerstein]

3:22 I know how stressful it is to give a lesson live correctly in the first shot. I'm just here to be that annoying guy with no friends that point out that MHz is "millions of times per second".

[@sumanalbargaw3108]

in GPU

[@mytube001]

I wish I had been born 20-30 years earlier. Assembly is so much more straightforward than modern languages. That stuff feels intuitive to me, while modern languages are very abstract. Sure, they're more powerful in most ways and the only way to do it on modern CPUs, but you've completely lost the connection to the hardware.

[@ArneChristianRosenfeldt]

I want to live in a world of zero-cost abstractions. A modern language which compiles to readable assembler code ( not x86 ). How do you optimize your hand-assembler for the pipeline? Optimization almost by definition is not straight forward. This is the reason why I don't understand that a greedy algorithm to allocate registers for local variables is an optimization. Yeah, spill over lands on the stack. Optimization is, when you hold back your greed, to keep some register free for later use. I guess that I talk about Sparc. On MIPS and x86 registers need to be assigned bottom up. Then for functions calling a lot of other functions, no registers are left. So they do everything on the stack. Thankfully, there still is block scope for your inner loops.

[@aryansingh7209]

6 minutes ago is crazy

[@MonochromeWench]

Delay slots, something completely irrelevant to any modern CPU architecture.

[@TheJimmyCartel]

Assembly is so much cooler then soydev unity bloat

[@habibie]

Shout out for all non binary robots 😂😅

[@JeremyP1]

second

[@zxcaaq]

clickbait