[Lecture] Computer Memory Hierarchy

[Wander Away]

As a senior in university studying computer engineering , I like how Linus doesn't pretend to know all the technical details about computers, unlike some other channels (*cough* Jayz2CentsMakesMeCringeSometimes). 

However, I thought It'd be interesting to give a lecture on what I've learned in my computer architecture class (and study for finals :D.....). 

 

I chose memory hierarchy as the topic because in this video Linus some did real world testing of different RAM speeds had on computers. I've had an issue with what Linus said between 0:57 -1:36 not being technically correct (Yes, I know I'm nitpicking, but hey, Linus does that all the time).  So here goes. 

 

_{If you can stand me going on an aside every other sentence that is.} 

 

NOTE: everything here will be a gross simplification of the actual architecture used by intel/amd/arm etc. 

 

Background:

Spoiler

In reality, the speed at which signals can propagate through a transistor is NOT instantaneous nor is it the speed of light, contrary to popular belief. It is actually on the order of a few to tens of picoseconds (1ps=1x10^-12s).

Be aware that in order for a processor to run at say for example, 3GHz, all combinational logic (implemented using many transistors) must be completed within 333 picoseconds. Due to the complex nature of instructions, each requires multiple clock cycles to execute at this speed. (Pipelining may be a topic that I will cover in the future if there is enough interest. It is the process of breaking instructions into stages, effectively executing multiple instructions in a single clock cycle. Intel used a 14 stage pipeline couple years ago, e.g. core i7 920)

For example, one of the simplest two-input NAND gate requires four transistors in CMOS logic, or less in domino, or pseudo logic. Beginning from the two inputs given to the NAND gate, it might take somewhere between 5-20 ps to get an output, depending on transistor sizing.

(Yes, wider transistors will make the switching speed faster, while the channel length (14nm on the current generation) stays the same)  

 

Signal propagation through interconnects (aka wires) also take time. In fact, sometimes it may be faster to insert buffers (made of transistors) in the middle interconnects. This is due to the inherent resistance and capacitance of the wires, and the delay here is significant. A few dozen micrometers of wire can cause hundreds of picoseconds of delay. 

 

With all these information in mind, and considering how far the RAM modules are from the CPU physically, it might not be a surprise anymore to know that it takes hundreds of CPU cycles for a read or write operation directly from RAM (main memory). 

Solution:

Spoiler

In order to make it so that the CPU doesn't have to wait for memory access every time it needs new data, cache's were built into the CPUs. On current Intel CPU's there are three levels of cache: L1, L2, L3.

L1 cache is on the order of tens of kilobytes, L2 hundreds of KB, and L3 a few MegaBytes. 

Cache is constructed using static RAM (SRAM technology, with 500ps ~ 2500ps delay, and costs $2000~$5000 US per GB), as opposed to the dynamic RAM that main memory (RAM) is built out of (DRAM, 50ns~70ns delay, with $20-$75 per GB). 

A reasonable access time for L1, L2, and L3 cache are around 1~2, ~20, ~50 CPU clock cycles respectively, with main memory taking ~200 cycles. 

Considering the prices of the different types of memory cells, it is pretty clear why so little amount of cache is present. 

 

The cache is used to store commonly used instructions and data within a program. All programmers are aware that most of a program execution is within a loop. As such, a running program will often use the same data and instructions, and such instructions can be stored within a cache for fast access. 

 

This is where branch prediction comes in, and you might have heard companies such as AMD speaking about their improved branch prediction algorithms. Branch is a cpu instruction to fetch an instruction that is not the one immediately after. This occurs when using if-else statements, loops, etc. Branches usually have a pattern associated with them, so it is possible to predict what the next instruction is going to be with reasonable accuracy of over 95%. This means at least 95% of the time when the CPU needs a new instruction, it will already be there waiting for the CPU to access quickly (a "hit"). 

 

If the information that the CPU requires for execution is not within L1 cache, this is called a "miss". Then it will try to access L2 cache (which is slower, in case you missed it) to find it. If it is not in L2 cache then it will move onto L3, and then to main memory. Each level will have a high hit rate, and of course a lower miss rate. 

 

Conclusion: 

Spoiler

So, the only time that the CPU will need to access the main memory (RAM) is when the information it is looking for is not present in the different level of cache. This only occurs less than 0.005% of the time. As such, the speed increases of main memory only matters (theoretically) 0.005% of the time. 

 

Higher RAM speeds will never be too fast for the CPU, but will be ever so slightly faster when the CPU does need data from it. Take that Linus!

 

[Mykie]

Should make it visual, like a video perhaps  

[Beskamir]

So correct me if I'm wrong but if something's in RAM it has to access L1, then L2, then L3, meaning around 72 cycles before it can even start searching RAM? Sure the "best case" is much quicker but you could end up with 72 extra cycles if predition doesn't work. And how does this work when there's way more data that could be branched to than can fit in the caches...

 

Anyway this explains a bunch of the stuff (namely branch predition and cacheing) I was doing with my Raspberry Pi 2 when I was making Mario without an OS. So thanks for that! Also hints that I may not have done it correctly...

[Mira Yurizaki]

11 minutes ago, ElfFriend said:

So correct me if I'm wrong but if something's in RAM it has to access L1, then L2, then L3, meaning around 72 cycles before it can even start searching RAM? Sure the "best case" is much quicker but you could end up with 72 extra cycles if predition doesn't work. And how does this work when there's way more data that could be branched to than can fit in the caches...

That's just something you may have to deal with. However, you could probably prep the memory controller for RAM access ahead of time.

[Wander Away]

1 hour ago, ElfFriend said:

So correct me if I'm wrong but if something's in RAM it has to access L1, then L2, then L3, meaning around 72 cycles before it can even start searching RAM? Sure the "best case" is much quicker but you could end up with 72 extra cycles if predition doesn't work. And how does this work when there's way more data that could be branched to than can fit in the caches...

No, if the CPU wants to access something that is in RAM, but not found in the multiple levels of cache, it is a "miss" and therefore will directly access the memory, while stalling the CPU. One thing with digital logic is that everything can be run in parallel, so while the CPU is trying to access L1 Cache, it is also trying to access L2, L3, and main memory at the same time. 

 

In addition, the cost of implementing the prediction algorithm is that 1. you need more transistors to do it, and 2. When the prediction is wrong, there are going to be an associated penalty. However, keep in mind that the "hit" rate and accuracy of the architecture makes it so that the benefits of such an architecture far outweighs the penalties on incorrect predictions. 

 

The branch prediction algorithms can range from very simple state machines to extremely complicated ones. I may do another writeup on it later. 

[BuckGup]

Moar plz. About everything

[themctipers]

I did not think of cache being used quite frequently, probably only for the OS and maybe the main execution code for a game (don't roast me if I got that wrong) because it was so small (200kb, then 512kb, then 4-8MB, and then you have 16gb+)

 

how does gpu vram compare to this in terms of access speed (faster than dram but slower than l3 cache?)

[BingoFishy]

This was really interesting! I don't know much about anything in-depth in computer architecture, etc., so keep it coming! Also, I like the "wall of text" style, not interested in a video or whatever like a few others are.