1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ You might want to read up on Amdahl's law. $\endgroup$
    – ThreeFx
    Jun 18, 2017 at 19:04
  • 1
    $\begingroup$ lol at the "low level language"s ... $\endgroup$
    – WhatsUp
    Jun 19, 2017 at 13:44

1 Answer 1

5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ you understood my question correctly :-) $\endgroup$ Jun 18, 2017 at 21:59
  • $\begingroup$ I tested for my specific problem : bandwidth wall was definitely the bottleneck. Thanks a lot. $\endgroup$ Jun 19, 2017 at 14:47
  • $\begingroup$ Another issue is the thermal barrier. Even if your code runs entirely in the private cache of each core, an active core will dissipate more power than an idling CPU, and, in constrained environments such as laptops, phones, the frequency will be eventually reduced to prevent the CPU from frying. A single core running at its max frequency could execute its own task faster than when all cores are concurrently running this same program. (Intel "Turbo Boost" is also an illustration of this phenomenon) $\endgroup$
    – TEMLIB
    Jun 20, 2017 at 19:48
  • $\begingroup$ Great, less obvious scenario! $\endgroup$
    – Omar
    Jun 20, 2017 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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