Cache coherency: Threads vs Cores

Question

I am currently studying concurrent systems, and I've become a little confused with the concept of cache coherency when working with multiple threads and multiple cores at the same time.

Some assumptions as I understand:

• Cores have caches
• Cores may have multiple threads at one time (if hyperthreaded)
• A thread is a single line of commands that are getting processed
• Thus, threads are not physical hardware and threads don't have caches and use the core's cache

Suppose a core has we have two threads and x is a shared variable with value five. Both want to execute:

my_y = x;

Where my_y is a private variable defined by both threads. Now suppose thread 0 executes:

x++;

Finally, suppose that thread 1 now executes:

my_z = x;

Where my_z is another private variable.

My book says the following:

What's the value in my_z? Is it five? Or is it six? The problem is that there are (at least) three copies of x: the one in main memory, the one in thread 0's cache, and the one in thread 1's cache.

How does this work? How are there at least three copies of x and why does the book specify that each thread has its own cache? To me, it would make sense that the core which is running the two threads has the value of x in its cache and thus both threads have the value in "their" (shared) cache.

In other words, when x++ is updated, the value in the core's cache would be updated. Then, thread 1 would execute my_z = x; which is still in the core's cache and it is up to date. Thus, there would be no coherency issue because the two threads basically share the cache.

It could be that the book assumes that each core has only one thread, but the book did previously mention something about "if there are more threads than cores". Does "if there are more threads than cores" imply that a core has more than one thread (hyperthreading) or is there some sort of thread scheduling happening so that each core only has one thread at a time?

Even if this is the case (the scheduling of cores and that a core can only have one thread at a time), if a core owns thread 0, executes x++ and then obtains thread 1 who is trying to execute my_z = x; the value of x would still exist in that core's cache, if I'm not mistaken.

Bonus question: how are the private variables of threads stored in memory? Are they stored in the same way as any variable where they get copied in a core's cache when used? If this is the case, will it be a problem to have a private variable in the core's cache if multiple threads are using the cache - whether simultaneously or scheduled?

As per @biziclop 's request, the book states the following assumptions:

• We use MIMD systems, that is, the nodes have the same architecture. (The book doesn't specifically state which architecture this is, though)
• Our programs are SPMD. Thus, we'll write a single program that can use branching to have multiple behaviours.
• We assume cores are identical but operate asynchronously.
• We program in the C language and in this section we focused on Pthreads.

Any help would be appreciated!

Answer 1

why does the book specify that each thread has its own cache?

The author is being sloppy. Threads don't have caches. The processor cores on which the threads run have caches.

the book did previously [say,] "if there are more threads than cores". Does [that] imply that a core has more than one thread (hyperthreading) or is there some sort of thread scheduling happening so that each core only has one thread at a time?

Either one of those things could be true. We've already established that the author is a bit sloppy with language, so taking that quote out of its context, there's no way to tell whether it's talking about more hardware threads than cores or more software threads.

how are the private variables of threads stored in memory?

All of the threads in a process see the same exact virtual address space. In the broadest sense, "private" simply describes a memory location that is only used by one thread, and it doesn't matter why the location is only used by one thread.

In a more narrow sense, each thread has a stack of function activation records (a.k.a., the "call stack") containing the arguments and the local variables of all of the active function calls. In many programming languages it is impossible for one thread to share its args or locals with any other thread, so those memory locations are automatically "private." In other programming languages, it is possible to share an arg or a local, but the programmer has to write explicit code to share it, and in any case, it's probably a bad idea.

will it be a problem to have a private variable in the core's cache if multiple threads are using the cache - whether simultaneously or scheduled?

When two different memory locations both hash to the same cache location, that's called a collision. And yeah! collisions happen some times. If a certain cache line contains variable X, and thread T wants to access variable Y which happens to use the same cache line, then the memory system will make thread T wait while it fetches the data from the main memory.

The phenomenon also is called "false sharing" (typically when it becomes a problem,) and you can Google for strategies to avoid it if and when you determine that it actually brings down the performance of your program.