Full episode with Jim Keller (Feb 2020): https://www.youtube.com/watch?v=Nb2tebYAaOA
Clips channel (Lex Clips): https://www.youtube.com/lexclips
Main channel (Lex Fridman): https://www.youtube.com/lexfridman
(more links below)

Podcast full episodes playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOdP_8GztsuKi9nrraNbKKp4

Podcasts clips playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOeciFP3CBCIEElOJeitOr41

Podcast website:
https://lexfridman.com/ai

Podcast on Apple Podcasts (iTunes):
https://apple.co/2lwqZIr

Podcast on Spotify:
https://spoti.fi/2nEwCF8

Podcast RSS:
https://lexfridman.com/category/ai/feed/

Jim Keller is a legendary microprocessor engineer, having worked at AMD, Apple, Tesla, and now Intel. He's known for his work on the AMD K7, K8, K12 and Zen microarchitectures, Apple A4, A5 processors, and co-author of the specifications for the x86-64 instruction set and HyperTransport interconnect.

Subscribe to this YouTube channel or connect on:
- Twitter: https://twitter.com/lexfridman
- LinkedIn: https://www.linkedin.com/in/lexfridman
- Facebook: https://www.facebook.com/lexfridman
- Instagram: https://www.instagram.com/lexfridman
- Medium: https://medium.com/@lexfridman
- Support on Patreon: https://www.patreon.com/lexfridman

So let's get into the basics before we zoom back out.

How do you build a computer from scratch?

Maybe even as far back as what is a transistor?

So the special charm of computer engineering is there's a relatively good understanding of abstraction layers.

So down at the bottom you have atoms and atoms get put together in materials like silicon or dope silicon or metal, and we build transistors.

On top of that, we build logic gates, right, and then functional units, like an adder, a subtractor, an instruction parsing unit, and then we assemble those into, you know, processing elements.

Modern computers are built out of probably 10 to 20 locally, organic processing elements or coherent processing elements.

And then that runs computer programs, right?

So there's abstraction layers and then software, you know, there's an instruction set you run.

And then there's assembly language C, C++, Java, JavaScript, you know, there's abstraction layers, you know, essentially from the atom to the data center, right?

So when you build a computer, you know, first there's a target, like what's it for, like how fast does it have to be, which, you know, today there's a whole bunch of metrics about what that is.

And then in an organization of 1,000 people who build a computer, there's lots of different disciplines that you have to operate on.

So there's a bunch of levels of abstraction in organization like Intel and in your own vision, there's a lot of brilliance that comes in at every 1 of those layers.

Some of it is science, some of it is engineering, some of it is art.

What's the most, if you could pick favorites, what's the most important, your favorite layer on these layers of abstractions?

Where does the magic enter this hierarchy?

That's the fun, you know, I'm somewhat agnostic to that.

So I would say for relatively long periods of time, instruction sets are stable.

So the x86 instruction set, the ARM instruction set.

So it says, how do you encode the basic operations?

Load, store, multiply, add, subtract, conditional branch.

There aren't that many interesting instructions.

Like if you look at a program and it runs, 90% of the execution is on 25 opcodes, 25 instructions.

Intel architecture has been around for 25 years.

And that's because the basics are defined a long time ago, right?

Now, the way an old computer ran is you fetched instructions and you executed them in order.

The way a modern computer works is you fetch large numbers of instructions, say 500.

And then you find the dependency graph between the instructions.

And then you execute in independent units those little micrographs.

So a modern computer, like people like to say, computers should be simple and clean, but it turns out the market for simple, clean, slow computers is 0, right?

We don't sell any simple, clean computers.

Now, you can, there's, how you build it can be clean, but the computer people want to buy, that's say in a phone or a data center, fetches a large number of instructions, computes the dependency graph, and then executes it in a way that gets the right answers.

Yeah, they run deeply out of order, and then there's semantics around how memory ordering works and other things work.

So the computer sort of has a bunch of bookkeeping tables that says what order do these operations finish in or appear to finish in.

But to go fast, you have to fetch a lot of instructions and find all the parallelism.

Now there's a second kind of computer, which we call GPUs today, and I call it a difference.

There's found parallelism, like you have a program with a lot of dependent instructions, you fetch a bunch, and then you go figure out the dependency graph, and you issue instructions out of order That's because you have 1 serial narrative to execute, which in fact can be done out of order.

So yeah, so humans think in serial narrative.

There's a sentence after sentence after sentence, and there's paragraphs.

Imagine you diagrammed it properly, and you said, which sentences could be read in any order, any order without changing the meaning?

That's a fascinating question to ask of a book.

So some paragraphs could be reordered, some sentences can be reordered.

You could say, he is tall and smart and X, right?

And it doesn't matter the order of tall and smart.

But if you say the tall man is wearing a red shirt, what colors, you know, like you can create dependencies, right?

Right, And so GPUs on the other hand, run simple programs on pixels.

But you're given a million of them, and the first order, the screen you're looking at doesn't care which order you do it in.

Simple narratives around the large numbers of things where you can just say it's parallel because you told me it was.

the narrative is sequential but you discover little pockets of parallelism versus?

So once you crack the problem, you say, here's how you fetch 10 instructions at a time, Here's how you calculated the dependencies between them.

Here's how you describe the dependencies.

Here's, you know, these are pieces, right?

So, and once you describe the dependencies, then it's just a graph, sort of, it's an algorithm that finds, what is that, I'm sure there's a graph theory, theoretical answer here that's solvable.

In general, programs, modern programs, that human beings write, how much found parallelism is there in them?

You would get what's called cycles per instruction, and it would be about, you know, 3 instructions.

3 cycles per instruction, because of the latency of the operations and stuff.

And in a modern computer, executes it like 0.25 cycles per instruction.

1 is the found parallelism in the narrative, right?

And the other is the predictability of the narrative.

So certain operations, they do a bunch of calculations and if greater than 1, do this, else do that.

That decision is predicted in modern computers to high 90% accuracy.

So imagine you have a decision to make every 6 instructions, which is about the average.

But you want to fetch 500 instructions, figure out the graph and execute them all in parallel.

That means you have, let's say if you fix 600 instructions and it's every 6, you have to fetch, you have to predict 99 out of a hundred branches correctly for that window to be effective.

Okay, so parallelism, you can't parallelize branches.

So imagine you do a computation over and over.

And you go through that loop a million times.

So every time you look at the branch, you say it's probably still greater than 1.

And you're saying you could do that accurately.

20 years ago, you simply recorded which way the branch went last time and predicted the same thing.

So then somebody said, hey, let's keep a couple of bits and have a little counter so when it predicts 1 way, we count up and then pins.

So say you have a 3 bit counter, so you count up, and then you count down, and if it's, you know, you can use the top bit as the assigned bit, so you have a assigned 2 bit number.

So if it's greater than 1, you predict taken, and less than 1, you predict not taken, right?

This branch depends on how you got there.

So if you came down the code 1 way, you're talking about Bob and Jane, right?

It went 1 way, but if you're talking about Bob and Jill, does Bob like Jane?

That's cool, but that's not how anything works today.

They use something that looks a little like a neural network.

So modern, you take all the execution flows and then you do basically deep pattern recognition of how the program is executing.

And you do that multiple different ways, and you have something that chooses what the best result is.

There's a little super computer inside the computer.

So the effective window that is worth finding grass in gets bigger.

So this is 1 of those, to get the result, to get from a window of say 50 instructions to 500, it took 3 orders of magnitude or 4 orders of magnitude more bits.

Now if you get the prediction of a branch wrong, what happens then?

You flush the pipe, so it's just the performance cost.

So we're starting to look at stuff that says, so they executed down this path, and then you had 2 ways to go, but far, far away, there's something that doesn't matter which path you went.

So you took the wrong path, you executed a bunch of stuff.

Then you had the mispredicting, you backed it up, but you remembered all the results you already calculated.

Like if you read a book and you misunderstand a paragraph, your understanding of the next paragraph sometimes is invariant to that understanding.

And you can kind of anticipate that invariance.

Yeah, well, you can keep track of whether the data changed, and so when you come back to a piece of code, should you calculate it again or do the same thing?

Okay, how much of this is art and how much of it is science?

So imagine you come to a point in the road where you have to make a decision, right?

And you have a bunch of knowledge about which way to go, maybe you have a map.

So you wanna go the shortest way, or do you wanna go the fastest way, or do you wanna take the nicest road?

So imagine you're doing something complicated like building a computer and there's hundreds of decision points all with hundreds of possible ways to go And the ways you pick interact in a complicated way.

And then you have to pick the right spot.

You avoided the question, you just described the Robert Frost problem of road less taken.

That's what we do as computer designers, it's all poetry.

Yeah, I don't know how to describe that because some people are very good at making those intuitive leaps.

It seems like this combination of things.

Some people are less good at it, but they're really good at evaluating the alternatives.

Right, and everybody has a different way to do it.

And some people can't make those leaps, but they're really good at analyzing it.

So when you see computers are designed by teams of people who have very different skill sets, and a good team has lots of different kinds of people, I suspect you would describe some of them as artistic.

And the 1% inspiration is really important.

And then there are interesting things to do at every level of that stack.

At the end of the day, if you run the same program multiple times, does it always produce the same result?

So if you run a correct C program, the definition is every time you run it, you get the same answer.

But that's a language definitional statement.

So for years when people did, when we first did 3D acceleration of graphics, you could run the same scene multiple times and get different answers.

Right, And then some people thought that was okay and some people thought it was a bad idea.

And then when the HPC world used GPUs for calculations, they thought it was a really bad idea.

Now, in modern AI stuff, people are looking at networks where the precision of the data is low enough that the data is somewhat noisy.

And the observation is the input data is unbelievably noisy.

So why should the calculation be not noisy?

And people have experimented with algorithms that say can get faster answers by being noisy.

Like as a network starts to converge, if you look at the computation graph, it starts out really wide and then it gets narrower.

And you can say, is that last little bit that important, or should I start the graph on the next rev before we whittle it all the way down to the answer?

Right, so you can create algorithms that are noisy.

Now if you're developing something, and every time you run it you get a different answer, It's really annoying.

And so most people think, even today, every time you run the program, you get the same answer.

Now I know, but the question is, that's the formal definition of a programming language.

There is a definition of languages that don't get the same answer, but people who use those, you always want something because you get a bad answer and then you're wondering, is it because of something in the algorithm or because of this?

So everybody wants a little switch that says no matter what, do it deterministically.

And it's really weird, because almost everything going into modern calculations is noisy.

So why do the answers have to be so clear?

I design computers for people who run programs.

So if somebody says, I want a deterministic answer, like most people want that.

Can you deliver a deterministic answer, I guess is the question.

What people don't realize is you get a deterministic answer even though the execution flow is very undeterministic.


Speaker 0: So let's get into the basics before we zoom back out. How do you build a computer from scratch? What is a microprocessor? What is a microarchitecture? What's an instruction set architecture?

Maybe even as far back as what is a transistor?

Speaker 1: So the special charm of computer engineering is there's a relatively good understanding of abstraction layers. So down at the bottom you have atoms and atoms get put together in materials like silicon or dope silicon or metal, and we build transistors. On top of that, we build logic gates, right, and then functional units, like an adder, a subtractor, an instruction parsing unit, and then we assemble those into, you know, processing elements. Modern computers are built out of probably 10 to 20 locally, organic processing elements or coherent processing elements. And then that runs computer programs, right?

So there's abstraction layers and then software, you know, there's an instruction set you run. And then there's assembly language C, C++, Java, JavaScript, you know, there's abstraction layers, you know, essentially from the atom to the data center, right? So when you build a computer, you know, first there's a target, like what's it for, like how fast does it have to be, which, you know, today there's a whole bunch of metrics about what that is. And then in an organization of 1,000 people who build a computer, there's lots of different disciplines that you have to operate on. Does that make sense?

And so.

Speaker 0: So there's a bunch of levels of abstraction in organization like Intel and in your own vision, there's a lot of brilliance that comes in at every 1 of those layers. Some of it is science, some of it is engineering, some of it is art. What's the most, if you could pick favorites, what's the most important, your favorite layer on these layers of abstractions? Where does the magic enter this hierarchy?

Speaker 1: I don't really care. That's the fun, you know, I'm somewhat agnostic to that. So I would say for relatively long periods of time, instruction sets are stable. So the x86 instruction set, the ARM instruction set.

Speaker 0: What's an instruction set?

Speaker 1: So it says, how do you encode the basic operations? Load, store, multiply, add, subtract, conditional branch. There aren't that many interesting instructions. Like if you look at a program and it runs, 90% of the execution is on 25 opcodes, 25 instructions. And those are stable, right?

Speaker 0: What does it mean stable?

Speaker 1: Intel architecture has been around for 25 years. It works. It works. And that's because the basics are defined a long time ago, right? Now, the way an old computer ran is you fetched instructions and you executed them in order.

Do the load, do the add, do the compare. The way a modern computer works is you fetch large numbers of instructions, say 500. And then you find the dependency graph between the instructions. And then you execute in independent units those little micrographs. So a modern computer, like people like to say, computers should be simple and clean, but it turns out the market for simple, clean, slow computers is 0, right?

We don't sell any simple, clean computers. Now, you can, there's, how you build it can be clean, but the computer people want to buy, that's say in a phone or a data center, fetches a large number of instructions, computes the dependency graph, and then executes it in a way that gets the right answers.

Speaker 0: And optimize that graph somehow.

Speaker 1: Yeah, they run deeply out of order, and then there's semantics around how memory ordering works and other things work. So the computer sort of has a bunch of bookkeeping tables that says what order do these operations finish in or appear to finish in. But to go fast, you have to fetch a lot of instructions and find all the parallelism. Now there's a second kind of computer, which we call GPUs today, and I call it a difference. There's found parallelism, like you have a program with a lot of dependent instructions, you fetch a bunch, and then you go figure out the dependency graph, and you issue instructions out of order That's because you have 1 serial narrative to execute, which in fact can be done out of order.

Speaker 0: Did you call it a narrative?

Speaker 1: Yeah. Wow. So yeah, so humans think in serial narrative. So read a book, right? There's a sentence after sentence after sentence, and there's paragraphs.

Now you could diagram that. Imagine you diagrammed it properly, and you said, which sentences could be read in any order, any order without changing the meaning? Right?

Speaker 0: That's a fascinating question to ask of a book.

Speaker 1: Yeah. Yeah, you could do that. Right? So some paragraphs could be reordered, some sentences can be reordered. You could say, he is tall and smart and X, right?

And it doesn't matter the order of tall and smart. But if you say the tall man is wearing a red shirt, what colors, you know, like you can create dependencies, right? Right, And so GPUs on the other hand, run simple programs on pixels. But you're given a million of them, and the first order, the screen you're looking at doesn't care which order you do it in. So I call that given parallelism.

Simple narratives around the large numbers of things where you can just say it's parallel because you told me it was. So found parallelism where

Speaker 0: the narrative is sequential but you discover little pockets of parallelism versus?

Speaker 1: Turns out large pockets of parallelism.

Speaker 0: Large, so how hard is it to discover?

Speaker 1: Well, how hard is it? That's just transistor count, right? So once you crack the problem, you say, here's how you fetch 10 instructions at a time, Here's how you calculated the dependencies between them. Here's how you describe the dependencies. Here's, you know, these are pieces, right?

Speaker 0: So, and once you describe the dependencies, then it's just a graph, sort of, it's an algorithm that finds, what is that, I'm sure there's a graph theory, theoretical answer here that's solvable. In general, programs, modern programs, that human beings write, how much found parallelism is there in them? What does 10x mean?

Speaker 1: What? So if you execute it in order. Versus, yeah. You would get what's called cycles per instruction, and it would be about, you know, 3 instructions. 3 cycles per instruction, because of the latency of the operations and stuff.

And in a modern computer, executes it like 0.25 cycles per instruction. So it's about, we today find 10x. And there's 2 things. 1 is the found parallelism in the narrative, right? And the other is the predictability of the narrative.

Right? So certain operations, they do a bunch of calculations and if greater than 1, do this, else do that. That decision is predicted in modern computers to high 90% accuracy. So branches happen a lot. So imagine you have a decision to make every 6 instructions, which is about the average.

But you want to fetch 500 instructions, figure out the graph and execute them all in parallel. That means you have, let's say if you fix 600 instructions and it's every 6, you have to fetch, you have to predict 99 out of a hundred branches correctly for that window to be effective.

Speaker 0: Okay, so parallelism, you can't parallelize branches. Or you can.

Speaker 1: No, you can predict.

Speaker 0: What does predict a branch mean? Or what does predict a branch mean?

Speaker 1: So imagine you do a computation over and over. You're in a loop. So while n is greater than 1, do. And you go through that loop a million times. So every time you look at the branch, you say it's probably still greater than 1.

Speaker 0: And you're saying you could do that accurately.

Speaker 1: Very accurately.

Speaker 0: Modern computers. My mind is blown. How the heck do you do that? Wait a minute.

Speaker 1: Well you wanna know, this is really sad. 20 years ago, you simply recorded which way the branch went last time and predicted the same thing. Right. Okay.

Speaker 0: What's the accuracy of that?

Speaker 1: 85%. So then somebody said, hey, let's keep a couple of bits and have a little counter so when it predicts 1 way, we count up and then pins. So say you have a 3 bit counter, so you count up, and then you count down, and if it's, you know, you can use the top bit as the assigned bit, so you have a assigned 2 bit number. So if it's greater than 1, you predict taken, and less than 1, you predict not taken, right? Or less than 0, whatever the thing is.

And that got us to 92%. Oh. Okay, no, it's better. This branch depends on how you got there. So if you came down the code 1 way, you're talking about Bob and Jane, right?

And then said, is Bob like Jane? It went 1 way, but if you're talking about Bob and Jill, does Bob like Jane? You go a different way. So that's called history. So you take the history and a counter.

That's cool, but that's not how anything works today. They use something that looks a little like a neural network. So modern, you take all the execution flows and then you do basically deep pattern recognition of how the program is executing. And you do that multiple different ways, and you have something that chooses what the best result is. There's a little super computer inside the computer.

Speaker 0: That's trying to predict branching.

Speaker 1: That calculates which way branches go. So the effective window that is worth finding grass in gets bigger.

Speaker 0: Why was that gonna make me sad? Because that's amazing.

Speaker 1: It's amazingly complicated. Oh, well. Well, here's the funny thing. So to get to 85% took a thousand bits. To get to 99% takes tens of megabits.

So this is 1 of those, to get the result, to get from a window of say 50 instructions to 500, it took 3 orders of magnitude or 4 orders of magnitude more bits.

Speaker 0: Now if you get the prediction of a branch wrong, what happens then? You flush the pipe. You flush the pipe, so it's just the performance cost.

Speaker 1: But it gets even better. Yeah. So we're starting to look at stuff that says, so they executed down this path, and then you had 2 ways to go, but far, far away, there's something that doesn't matter which path you went. So you took the wrong path, you executed a bunch of stuff. Then you had the mispredicting, you backed it up, but you remembered all the results you already calculated.

Some of those are just fine. Like if you read a book and you misunderstand a paragraph, your understanding of the next paragraph sometimes is invariant to that understanding. Sometimes it depends on it.

Speaker 0: And you can kind of anticipate that invariance.

Speaker 1: Yeah, well, you can keep track of whether the data changed, and so when you come back to a piece of code, should you calculate it again or do the same thing?

Speaker 0: Okay, how much of this is art and how much of it is science? Because it sounds pretty complicated.

Speaker 1: So, how do you describe a situation? So imagine you come to a point in the road where you have to make a decision, right? And you have a bunch of knowledge about which way to go, maybe you have a map. So you wanna go the shortest way, or do you wanna go the fastest way, or do you wanna take the nicest road? So there's some set of data.

So imagine you're doing something complicated like building a computer and there's hundreds of decision points all with hundreds of possible ways to go And the ways you pick interact in a complicated way. And then you have to pick the right spot.

Speaker 0: So that's art or

Speaker 1: science, I don't know.

Speaker 0: You avoided the question, you just described the Robert Frost problem of road less taken.

Speaker 1: Describe the Robert Frost problem? That's what we do as computer designers, it's all poetry. Okay. Great. Yeah, I don't know how to describe that because some people are very good at making those intuitive leaps.

It seems like this combination of things. Some people are less good at it, but they're really good at evaluating the alternatives. Right, and everybody has a different way to do it. And some people can't make those leaps, but they're really good at analyzing it. So when you see computers are designed by teams of people who have very different skill sets, and a good team has lots of different kinds of people, I suspect you would describe some of them as artistic.

But not very many.

Speaker 0: Unfortunately, or fortunately.

Speaker 1: Fortunately. Well, you know, computer design's hard. It's 99% perspiration. And the 1% inspiration is really important.

Speaker 0: But you still need the 99.

Speaker 1: Yeah, you gotta do a lot of work. And then there are interesting things to do at every level of that stack.

Speaker 0: At the end of the day, if you run the same program multiple times, does it always produce the same result? Is there some room for fuzziness there?

Speaker 1: That's a math problem. So if you run a correct C program, the definition is every time you run it, you get the same answer.

Speaker 0: Yeah, well that's a math statement.

Speaker 1: But that's a language definitional statement. So for years when people did, when we first did 3D acceleration of graphics, you could run the same scene multiple times and get different answers. Right. Right, And then some people thought that was okay and some people thought it was a bad idea. And then when the HPC world used GPUs for calculations, they thought it was a really bad idea.

Now, in modern AI stuff, people are looking at networks where the precision of the data is low enough that the data is somewhat noisy. And the observation is the input data is unbelievably noisy. So why should the calculation be not noisy? And people have experimented with algorithms that say can get faster answers by being noisy. Like as a network starts to converge, if you look at the computation graph, it starts out really wide and then it gets narrower.

And you can say, is that last little bit that important, or should I start the graph on the next rev before we whittle it all the way down to the answer? Right, so you can create algorithms that are noisy. Now if you're developing something, and every time you run it you get a different answer, It's really annoying. And so most people think, even today, every time you run the program, you get the same answer.

Speaker 0: Now I know, but the question is, that's the formal definition of a programming language.

Speaker 1: There is a definition of languages that don't get the same answer, but people who use those, you always want something because you get a bad answer and then you're wondering, is it because of something in the algorithm or because of this? So everybody wants a little switch that says no matter what, do it deterministically. And it's really weird, because almost everything going into modern calculations is noisy. So why do the answers have to be so clear?

Speaker 0: Or so where do you stand?

Speaker 1: I design computers for people who run programs. So if somebody says, I want a deterministic answer, like most people want that.

Speaker 0: Can you deliver a deterministic answer, I guess is the question. Like when you,

Speaker 1: Yeah, hopefully, sure. What people don't realize is you get a deterministic answer even though the execution flow is very undeterministic. So

See all Lex Fridman transcripts on Youtube

Jim Keller: Abstraction Layers from the Atom to the Data Center | AI Podcast Clips