Why Your CPU Works So Hard

A surprisingly large abstraction gap with the physical world and why it matters

We’re in the middle of a sequence of posts thinking about how to approach performance of full computing stacks. Following the motto “intelligence depends on organizing computation correctly and efficiently,” the way we arrange our computations can have dramatic effects on how much automated intelligence we’re able to muster. Not only is it important to have enough hardware at our disposal (as we see in the current mania over datacenter buildout for AI), but it also really matters how we arrange that hardware and the software running on it. Furthermore, AI code generation must deal with meeting performance requirements of the programs it writes. Unifying the two concerns is recursive self-improvement, where one reason we care about efficiency of an intelligent system is to make it more effective at improving its own efficiency, supporting a virtuous cycle that can begin an intelligence explosion.

The last post covered low-level programming languages, the ones most-advertised as providing programmers maximum control over the performance of programs. I argued that the popular low-level languages are actually remarkably poorly suited to that task today, as hardware and software evolve together. Understanding the performance of a program in such a language requires thinking about aspects of hardware organization not at all represented explicitly in program syntax. I will use the current post first to go into more detail on the fundamental performance model that the laws of physics give us, and then I will primarily focus on the performance model that modern CPUs expose to software and the ways it makes performance tuning unnecessarily hard.

Computation in Space (Communication Dominates)

Let me start by repeating a figure from the last post.

Computation needs to be accomplished by configuring physical space. The parts of a computation coordinate through sending signals through space, and the speed of light is believed to be a limit on how quickly those signals can propagate. As a result, the distance between physical parts of a computation comes to limit performance. This diagram distinguished between computation and storage, though it is interesting to analyze both and notice that the same physical communication bottleneck limits them.

Take computation, which we can cast as circuits that break up the calculation work. I reviewed this model previously in discussion of inherent performance bottlenecks for deep learning. The key measurement limiting time to get the complete answer of a computation was critical-path length, or the length of the longest path through the diagram of a circuit. Interestingly, this length can be seen exactly as communication delay implied by the geometry and connectivity of a computation substrate. We’re just talking about communication across the regions of space that divide up the work of computation.

Perhaps less obvious is that performance of storage systems follows from essentially the same foundation. Software engineers are used to thinking about storage hierarchies, where computer systems are broken into different kinds of storage, including fast storage with relatively low capacity (storing fewer bits), slow storage with relatively high capacity, and different intermediate points. We can just accept storage hierarchies with this kind of trade-off as part of the facts of life today. Alternatively, we can see that storage is just another way of arranging matter in space, such that elements of the matter tend to preserve certain changes to their state. The more bits we want to represent, the more matter we’ll need to arrange in space, and thus the further-away some of those elements will be from each other. So we see that longer delays to return answers follow naturally from higher storage capacity. For this reason, it is often a good idea to avoid one gigantic storage system in favor of smaller ones spread throughout space, intermixed with the computation that will consult them.

In summary, we can go very far thinking about the fundamental limits of performance by considering only communication costs, in systems of nodes arranged spatially.

The Fiction of Flat Memory

My own career path kept me relatively confined to the software side of things until relatively late. I came (implicitly) to think of the interface that a CPU exposes to software as the fundamental definition of what is possible. Then, early in my time as faculty, a collaboration pulled me into learning about how memory systems actually work, as we did an especially comprehensive kind of formal verification of such implementations (and later work extracted out some of those ideas into a reusable implementation language). Here I’m talking about cache-coherence protocols, the canonical ways of implementing the fiction of memory as a flat sequence of numbered addresses, each accessible from every computation node. This abstraction is very far from fundamental, given the physical reality of computing, and it was eye-opening for me to see the complexity and computational cost that goes into providing it.

Let’s take a quick look at roughly how this kind of protocol works. We have the large and slow main memory at the top of a diagram, and we have individual CPU cores (our parallel compute nodes) at the bottom. In between are two additional levels of memory hierarchy. Each core has its own dedicated L1 (“level one”) cache, which stores memory addresses accessed recently by that core, keeping them accessible quickly. Groups of L1 caches share larger and slower L2 caches. The L2 caches finally connect to the main memory, through a directory that tracks the states of the different caches. Note that none of these ideas appear directly in low-level programming languages, providing the root of their disadvantage for modeling and tuning performance.

Protocol details won’t be too important for our main message. However, it is important to understand that different layers of the hierarchy can effectively lock (claim temporary exclusive ownership of) addresses, restricting the ability of other parts of the hierarchy to work with those addresses simultaneously. This diagram starts with the bottom-right CPU core holding a write lock on some address, meaning no other core is allowed to read or write that address, which saves the overhead of communicating with those other cores to coordinate accesses.

So now imagine what is an especially bad scenario for performance of this protocol. The bottom-right core took a write lock on some address, though now that core is done writing, but the system didn’t bother to release the lock. (After all, that core may return to writing the same address a millisecond later.) The bottom-left core, located furthest-away in space from the lock holder, wants to read the address. It has to route a message to the owning core through the whole hierarchy: up to the bottom-left L1, then to the L2 it connects to, to the directory, and then down a symmetrical path to the bottom-right L1. That L1 learns it has been asked to give up the lock and does so, and it also responds with the current value stored in the address. This response snakes back through the hierarchy, though now it moves in the reverse direction from the request.

We can see that quite a lot of communication has happened implicitly, which is trouble for giving programmers a performance model that is easy to reason about. Eyeballing this diagram as a literal spatial layout (which wouldn’t quite match any real CPU’s but is still illustrative), the total distance traversed by the path is roughly four times the actual physical distance between the two CPU cores involved – and the software code had no say in determining the path. There will be additional delay from the coordination logic that, as each signal is received, decides what further signals (and local state changes) to trigger based on it. As a storage system adds capacity, it often adds additional levels of hierarchy, which ironically can make worst-case communication delay worse, even as they may improve common cases.

The big point here is that important decisions highly relevant to communication overhead are entirely hidden from the programmer, who needs to apply a hardware model mentally to have a chance of predicting a program’s performance. Low-level languages generally don’t include direct abstractions of placement and neighbor-to-neighbor communication, but we need those abstractions if we are to do a good job performance-engineering.

Sequential Low-Level Code and Making CPUs Undo Translation Work

The last post emphasized two design weaknesses of low-level programming languages: sequentialized code and shared memory. We just saw how shared memory is very involved to implement in hardware with good performance. Let me now explain why sequentialized code is also problematic, in a way that applies just as well to programming languages C and Rust as it does to assembly and machine languages, the more direct bridges between software and CPUs.

Here’s a quick summary before we go into more detail. The laws of physics let us compute only with computation graphs arranged in space, with cost based on accumulated communication distances. Sequential programs are very far from this physical reality, yet we need to translate them into reality to run them. Good translation requires effective analysis of programs, which consumes computational resources if we perform it on-the-fly, as CPUs do. In fact, automated program understanding is so difficult that even the expensive translation in CPUs frequently makes (conservative) mistakes that hurt performance. Sometimes CPUs even make mistakes that create security problems.

OK, now back to more specifics. A CPU program is a sequence of instructions, which store intermediate state in registers, essentially parts of a core-local memory that is especially small but also especially fast; plus the shared, flat memory. Literally running such a program one-instruction-at-a-time can be punishingly slow, so the CPU makes an effort to extract latent parallelism and run many instructions at once, which corresponds to mapping parts of programs onto available computation graphs in space. We discussed before how long sequential dependency chains in computations create fundamental bottlenecks, so the CPU is motivated to notice which dependencies actually exist. Actually, it can overapproximate the dependencies and be sure to respect any dependency that it suspects may exist.

The trouble is that dependencies are indicated through the two types of state I mentioned, and they are both tricky to model.

1. Dependencies through registers are complicated by the fact that there are relatively few registers, which are fast but expensive to fabricate. Therefore, one register will often be reused for many different purposes throughout a computation, creating the potential for confusion. What appears to be a dependency may be an illusion, involving a register in two different lifecycle phases, serving different purposes. The extra work that a CPU does to extricate these false dependencies is register renaming.

2. Dependencies through memory are complicated by the fact that a given instruction may access an address computed by a complicated formula. Given two address formulas found in two parts of a program, it can be very challenging to decide if they might actually indicate the same address – and that analysis may even not be computable. As a result, CPUs are often very conservative about ruling out dependencies through memory.

Yet CPUs do a lot of work to best-effort approximate such dependency information. It is important to recognize that, alongside the “real work” of running a program, we constantly pay for the CPU to analyze a program as it runs to approximate its dependency structure. The CPU is repeatedly reconfiguring a physical graph of compute and storage nodes to stand for different parts of a program, minimizing the total communication distances that we focus on in this post. One trick is pipelining, where one instruction is broken up into several steps, which may reveal additional parallelism. Different steps of all of a large bag of instructions may be run simultaneously, so long as dependencies are respected.

The other big snag that arises in this delicate choreography is that sometimes the CPU is not even sure which instructions will be running in the near-term future, so it makes a best guess and prepares itself to undo work whenever a guess turns out to be wrong. This performance optimization can have nasty consequences, as the world learned through the Spectre and Meltdown attacks in 2018, which took advantage of the fact that CPUs don’t undo bad guesses completely enough to erase information (say, in L2 caches) that can later be used to leak program secrets. (See some past discussion here of effective reasoning about this risk from a software perspective.)

The irony of the situation is captured by this cartoon.

The CPU is reconstructing the information that often was already in the programmer’s head and maybe even written out directly in a program! Most clearly, if the original program was written out as a nice dataflow graph, then it is much easier for a CPU or anyone else to understand dependency structure. Yet we habitually use programming tools that translate nice high-level code into sequential, memory-access-heavy code that CPUs interpret natively, making bad decisions thanks to approximation and imposing run-time costs for the analysis that drives those decisions. Sometimes relevant analysis is much easier when performed with concrete values that appear at runtime (e.g. we may know when two formulas for computing memory addresses did or didn’t evaluate to equal values), but where ahead-of-time reasoning is possible, it can pay off significantly in alternative architectures.

Up Next

Some of these gripes can be addressed by smaller changes to existing low-level code formats. One I like is BasicBlocker, which uses compiler support to leave enough hints for CPUs that they don’t need to guess about where programs are headed. However, we should be able to reap bigger gains by making larger changes to standard abstractions.

So let’s think about what those changes should be. The next post will propose one principle for joint design of software and hardware abstractions: that each side should move closer to where the other has historically been, with more hardware-style software and more software-style hardware. We’ll discuss historical reasons why the community hasn’t moved as much in that direction as this post’s analysis may suggest it should. Not coincidentally, AI-champion GPUs already incorporate some of the principles we’ll cover, though we will discuss how they are less-suited to formal verification and related ingredients that will help us trust programs and automate programming more effectively.