Multi-threading : N cores = N times one core?

Question

This question is about modern CPU architectures and multi-threading. I'm mainly interested in personal computers or servers having 2, 4, 8, 16... cores like for example an Intel core i7. I mean not a NASA supercomputer or GPU vector processing.

You have N cores.

You write an algorithm in a low level language such as C, C++, Java, C#... using essentially arithmetic (+/x/and/or...), basic for loops, floating point and arrays. It is mono threaded and your algorithm takes say 1 minute to complete.

Now you start N threads, and run the same algorithm on each of these threads INDEPENDENTLY : no lock (semaphores) or write access to common objects. Does each thread take 1 minute to complete, so that the total running time is 1 minute ?

What prevents this from being as good as it ? I know for example that if the threads write on the same parts of the memory (even without needing locks), the CPU caches of each processor need to refresh and the whole thing can be slowed down a lot.

Do you know some of the classical cases where the situation might be significantly different from "each thread one minute" and explain what about the architecture causes this ?

Note : Intel (for example) often uses hyperthreading so that 4 cores appear to be 8 logical processors. I don't want to focus on hyperthreading and I would like to simplify my question as if hyperthreading didn't exist. Imagine that each core can process the instructions of a single thread at a time.

I'm of course interested by things I might not be aware of in modern CPU architecture.

Answer 1

If I understood your question correctly, you are essentially asking:

Given a piece of sequential code, if we run N instances of it in parallel on N cores (on real, modern, typical, and not-particularly-high-end CPU models), should we expect any slowdown versus running only a single instance of that program on a single core?

As usual, the answer is: it depends. However, the answer will often be yes indeed, you should expect a slowdown. It will often take more than "one minute" per instance.

How and why? Intuitively, since you've got shared (and limited) resources, your threads will naturally compete for them.

For instance, main memory will be shared. Thus, if your program is bandwidth-bound (which is very common across many applications), few threads can easily fully saturate your limited memory bandwidth (essentially, they can request data from memory at a faster pace than your hardware can support) and you may notice degradation in performance (given your "one minute" measure) beyond that limit. You may want to look up the bandwidth-wall problem.

For another similar instance, many modern CPU models will have a shared last-level cache per chip/socket. These (typically L3) caches will often provide significantly higher bandwidth and lower latency for any thread (on the chip) accessing any cached data, in comparison to directly accessing main memory. Once threads start competing for this shared resource, the total working set size of all thread may exceed the cache capacity -- even though a single thread was running within cache. They effectively thrash the cache for each other.

You may want to contrast these cases to the case where the program is compute-bound and CPU-intensive yet can work with high locality in the smaller, private (i.e., not shared) caches. There are probably non-memory-hierarchy reasons as well (unlike the two above), although the reasons above are perhaps among the most obvious and most significant (or, at least, that is what I would expect).

Answer 2

There are many aspects making a difference, and it can go both ways.

Temperature: Many processors are temperature limited. If you have 16 cores at the same clock speed, you can expect them to produce 16 times more heat than one core. If that heat drives the temperature up too much, the clock speed may have to be reduced. That may be fine for a short time, but not for long running tasks.

An example is various MacBooks with different numbers of cores and different cooling. There is one model with four cores and passive cooling (no fan). You can run all cores on top speed for a shott time, but eventually speed will go down. Other models have 16 cores and no heat limitation at all.

Memory access: You may have lots of cores, but only one interface to memory. If you have 50 GByte/second band width, and your task uses 20 GByte/second, then from 3 cores up this will limit your speed.

Cache sizes: Most cores have L1 cache per core, but L2 cache is shared. For example, an eight core MacBook Pro has 24 MB of L2 cache; the cores are divided into two groups each with 12 MB of L2 cache. So 1 core has 12 MB. 2 cores have 12 MB each. With 3 cores, two share 12 MB and the third has 12 MB for itself. With eight cores used, you have two groups of four each sharing 12 MB per group. Now it depends on your algorithm. If your algorithm switches between using lots of memories followed by lots of calculations then the cache might "move" between cores and still be optimal.

If you split your work into multiple not identical tasks, you can have interesting effects. Some tasks interfere with each other, others don't.