Theoretical speed gain of quad core vs. single core

Question

I first asked this question at cstheory, but they suggested to ask my question here, so here it goes ...

I'm working on my masters thesis and I need to have theoretical value of the (average) speed gain that a quadcore processor brings compared to a singlecore processor, when they both use the same frequency. So for example the speed gain of a 2 GHz singlecore vs. 2 Ghz quadcore.

Somewhere on the internet I've read that a quadcore is 2.6 times faster than singlecore, but the author didn't mention any source so I cannot use that in my thesis.

I've been trying to calculate some things myself, but didn't come to a conclusion. I tried like this:

threads | quad core | single core | ratio 
--------|-----------|-------------|-------
1       | 1         | 1           | 1
2       | 2         | 1/2         | 4
3       | 3         | 1/3         | 9
4       | 4         | 1/4         | 16
5       | 3+1/2     | 1/5         | 17.5
6       | 2+2(1/2)  | 1/5         | 15
7       | 1+3(1/2)  | 1/5         | 12.5
...

This table represents the timeslices available to execute a task (I've taken a fair 50/50 usage for each thread). For example when using a singlecore and a application uses 3 threads, each thread can work 1/3 of the time, while with a quadcore each thread can work 100% of the time, because 3 threads can be spread accross a separate core. After playing with some calculations in Excel, I could not come to any conclusion.

I'm a bit stuck and need some fresh ideas on how to get a theoretical number that represents how much faster a quad core is (on average) compared to a single core. Maybe some of you know some empirical numbers with a good reference to the source? Anyway, all the help is welcome, because I'm a bit stuck and this is the last part I need to cover in my thesis.

Thanks!

Answer 1

There is no absolute value of how much faster a quad-core would be compared to a single-core. As the comments have said, it very much depends on exactly what you are doing whether it will be faster or slower. Even live performance testing may not give a fair answer since it won't model exact runtime behaviour.

In any case, if you are looking for a theoretical model it certainly is possible, though, as you can quickly see, not practically possible.

First you need to understand the architecure of the chips of the involved. When you move from single-core to quad-core not all resources are actually quadrupled. In particular the memory is still a shared resource. This memory is then split between a series of caches, some of which are shared, and some of which are not shared. Each cache is connected to the other caches either by a dedicated bus, or a shared data bus. Each of these caches, and buses, has a real bandwidth and latency number. This is not likely published, but with some very focused tests can be obtained.

Second you need to understand how the application will be using memory. How this memory is shared and the order in which it is accessed. For a single thread you could, in theory, calculate the amount of time it spends loading data from the various cache levels. For a multi-core case a key value is how often you attempt to write to the same memory. In this case you will invoke the chips cache-coherency algorithm. This algorithm is usually documented (to some degree) and the time to synchronize can be reasonably well measured.

Combine these together and you'll see that with perfect knowledge of how the program behaves and how the processor behaves you would be able to calculate the theoretical gains of increasing the number of cores. In pratice this simply won't be possible for all but the simplest of programs (but even then the way the chips manage memory is complex enough to make the problem too difficult).

What you should get from this description is primarily that processor speed alone is not the only problem. Memory is often the key bottleneck. When svick says perfectly parallelized he means they don't share memory. In this case your threads will approach the maximum 4x speed gain as the memory contention is low. However, they still share some memory cache for reading (L3 and main memory on Intel) and thus could still be limited by the total memory bandwidth.

If you wish to look at a degenerate example lookup "false sharing". In such cases the total speed goes down as more processors are added.

Answer 2

In addition to the other answer: Today, the speed of a processor is to a large degree limited by heat. Processing produces heat, too much heat would destroy the processor or dramatically shorten its life, so when the processor gets close to being too hot, it's speed is slowed down so that it produces less heat.

For example, one curent Intel processor can be purchased with 4, 8, 10, 14, or 18 cores. The official clock speed is 4.3, 3.6, 3.3, 3.1 and 2.6 GHz. Because 18 cores produce more heat than 4, the clock speed must be reduced (if the 18 core processor only uses 4 cores, at can run at the same speed as the 4 core processor). Using a single core only, the processor can run at an even higher speed.

There is the consideration whether the code is aware of running on multiple processors or not. Lots of performance critical code is written to be aware of what caches are available. For example, if there is 2 MB of cache, you would try to cut up the work into chunks of 2 MB at a time. But if there are four threads on four CPUs, you may have only 0.5 MB per CPU, which may reduce performance somewhat if the code is aware of it, and may reduce performance dramatically if the code is not aware, and four cores try to access 8MB.

(In a comment, Raphael correctly suggested that you can gain more speed by sheer luck. If the code isn't aware of caches, but splits the work into four parts so that every core can do some work, it may happen by sheer luck that the code is now more cache friendly and runs more than four times faster).

There is the question which resources are duplicated. There are processors which are optimised for integer performance, and a floating-point or especially vector unit may be shared between cores. In that case, your gain will be a lot less if your code uses the resources that are not duplicated. (On such a processor, integer code would get the expected speedup).