6

I'm trying to understand in a general sense how L1/L2 (and now L3 caches) are updated and how the updates are propagated in a multi-core x86/x86-64 CPU to the other cores and eventually RAM.

Assuming an 4 core CPU and 2 pairs of L1/L2 caches, where pairs of cores share a common L1/L2 pair and there's an interconnect between the 2 L1/L2 pairs. And the cache lines are 64-bit wide. So we have:

  1. Core-0/Core-1 on (L1/L2)-0
  2. Core-2/Core-3 on (L1/L2)-1
  3. (L1/L2)-0 is connected to (L1/L2)-1

Let's say there is a thread T0 running on Core-0 that is writing to a 64-bit integer variable called X, and there's another thread T1 on Core-3 continually reading variable X's value - Please ignore the logical race conditions for a moment.

Question: Assuming X has been cached in Core-0's L1. When T0 writes a new value to X, Is the following sequence of events correct?

  1. X's value is pushed from register to L1-0
  2. X's value is pushed from L1-0 to L2-0
  3. X's value is pushed from L2-0 to L2-1
  4. X's value is pushed from L2-1 to L1-1
  5. X's value is pushed from L1-0 to RAM

Note: Steps 2 and 4 may happen concurrently.

  • 1
    In the Wikipedia article for Cache coherency (which is what this question is about, and which is typically way beyond the typical CS/CE/ECE undergraduate education), a number of protocols (MSI, MESI, MOESI...) are listed. OP's question requires one to state explicitly which protocol the answer is applicable for. Also, different vendors implementing the same architecture could choose different protocol. Sometimes desktop, mainframe and mobile devices could choose different protocols as well. – rwong Jan 4 '15 at 4:34
13

First if you are concerned about recent (last 5-10 years, since Nahalem?) Intel x86, then your architect is a little off. Each core has their own 128K L1 cache split (64K data / 64K code). Above that, each core has its own L2 cache which basically acts as a buffer between the L1 and L3 cache. Each socket has its own L3 cache (up to 20MB, I think). The L1 and L2 caches are small, simple, and quick. The L3 cache is much larger and more complex (it is divided into small segments that all sit on a ring with other other things like the memory controller and QPI bridge to other sockets). (Please ignore things like the load and store buffers that will make this even more complex.)

Also, cache lines are 64-bytes.

So it looks like this (on for example a dual socket machine, with 4 cores per CPU):

Core 0 (socket 0) -> L1-0 -> L2-0 -> L3-0 -> QPI link to socket 1
Core 1 (socket 0) -> L1-1 -> L2-1 -> ^
Core 2 (socket 0) -> L1-2 -> L2-2 -> |
Core 3 (socket 0) -> L1-3 -> L2-3 -> +

Core 4 (socket 1) -> L1-4 -> L2-4 -> L3-1 -> QPI link to socket 0
Core 5 (socket 1) -> L1-5 -> L2-5 -> ^
Core 6 (socket 1) -> L1-6 -> L2-6 -> |
Core 7 (socket 1) -> L1-7 -> L2-7 -> +

Pre Nahalem, L2 caches were shared among core pairs. I haven't had to do a lot of performance work on this in a while, so I'm not really sure of the subtleties there.

The L3 cache is fully inclusive of the L1 and L2 cache's below it. The cache contains the "correct" values for all memory address. More correct than main memory, since writes can sit in L3 for a while before going to memory (write-back caching). All caches are coherent. That is, you will never had two different values for the same memory location. This coherency is maintained by a version of the MESI protocol, called MESIF (for Intel, AMD has a different caching strategy and uses MEOSI and arranged their caching differently).

Since the L1 and L2 are private to the core, the coherence only has to be managed at the L3 level (I think, I've been unable to get a definite answer on this). The cache interconnects have four lanes: data, request, acknowledge, and snoop (to keep up to date on other memory operations).

Now, we can get down to your questions.

If a thread on Core 0 is reading an address, the address will reside in L1-0 and L3-0 in either the Exclusive, Shared, or Forward state (all three show that the address is unmodified and cached). Now, Core-4 wants to write to it. A Request/Read-For-Ownership will send the cache line from the other L3 cache (L3-0) and cause the other caches to mark their copies as Invalid. It will now be in L1-4 and L3-1 (marked as Exclusive).

(Here is where ignoring store buffers simplified a lot.)

Core-4 will write from a register to the L1-4 cache. Causing to transition the line to the Modified state. This gets propagated to the L3-1 cache (since it is fully inclusive).

Now, Core-0 wants to read again. The L1-0 cache is Invalid at that address, so it sends a read request that misses the L3-0 cache and causes the L3-1 to send the cache line back across. The L3-1 now states that address is Shared, and the L3-0 holds the line as Forward (the most recent requester gets the Forwarding responsibility).

Clear as mud? There might be a few edits to this to clean up some of the language that I might be too vague on.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.