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).