17

You see this phrase or similar kicked around from time to time, generally referring to a program that claims they were not designed to take full advantage of multi-core processors. This is common especially with video game programming. (of course a lot of programs have no concurrency and do not need it, such as basic scripts, etc).

How can this be? A lot of programs (especially games) inherently use concurrency, and since the OS is in charge of task scheduling on the CPU, then are these programs not inherently taking advantage of the multiple cores available? What would it mean in this context to "take advantage of multiple cores"? Are these developers actually forbidding OS task scheduling and forcing affinity or their own scheduling? (Sounds like a major stability issue).

I'm a Java programmer, so maybe I have not had to deal with this due to abstractions or whatnot.

Improve this question
4
  • 11
    A big possibility is that shortcuts were taken in the synchronization, which work for a single-processor/core system but break with the true concurrency of multiple processors/cores.
    – Bart van Ingen Schenau
    Commented Feb 27, 2014 at 20:19
  • @BartvanIngenSchenau: This is correct. You should expand this and post it as an answer. I think all the others missed the point.
    – kevin cline
    Commented Feb 27, 2014 at 21:55
  • 1
    I think that @Bart is really close. However, s/work/ appear to work / and it will be closer to the mark.
    – Ben Voigt
    Commented Feb 28, 2014 at 0:21
  • as an aside - I've had experience of this as a user rather than a programmer - Ground Control 2 on windows XP. I needed to set core affinity to only one core on a multicore system for it to run properly, otherwise all the animations (infact the entire game) would run at 10x speed, which while being more of a challenge did get slightly annoying after a while. I've not done any work on games but to my mind, some part of the game seemed to be relying on the processor only doing a certain amount of work at the same time.
    – jammypeach
    Commented Feb 28, 2014 at 10:25

4 Answers 4

Reset to default
28

Good concurrency requires a lot more than throwing a few threads in an application and hoping for the best. There's a range in how concurrent a program can be going from embarrassingly parallel to pure sequential. Any given program can use Amdahl's law to express how scalable a problem or algorithm is. A couple qualifications for a embarrassingly parallel application would be:

  • No shared state, every function only depends on the parameters passed in
  • No access to physical devices (graphic cards, hard drives, etc)

There are other qualifications, but with just these two we can understand why games in particular are not as easy as you might think to take advantage of multiple cores. For one, the model of the world that will be rendered has to be shared as different functions calculate physics, movement, apply artificial intelligence etc. Second, each frame of this game model has to be rendered on screen with a graphics card.

To be fair, many game makers use game engines that are produced by third parties. It took a while, but these third party game engines are now much more parallel than they used to be.

There are bigger architectural challenges in dealing with effective concurrency

Concurrency can take many forms, from running tasks in the background to a full architectural support for concurrency. Some languages give you very powerful concurrency features such as ERLANG, but it requires you to think very differently about how you construct your application.

Not every program really needs the complexity of full multicore support. One such example is tax software, or any form driven application. When most of your time is spent waiting on the user to do something, the complexity of multithreaded applications are just not that useful.

Some applications lend themselves to a more embarrassingly parallel solution, such as web applications. In this case, the platform starts out embarrassingly parallel and it's up to you not have to impose thread contention.

The bottom line:

Not all applications are really hurt by not taking advantage of multiple threads (and thus, cores). For the ones that are hurt by that, sometimes the computations are not friendly to parallel processing or the overhead to coordinate it would make the application more fragile. Unfortunately, parallel processing is still not as easy as it should be to do well.

Improve this answer
3
  • This is a great analysis. One thing that bugs me though is your point about real-world programs often not being embarrassingly parallel and thus hard to parallelize: While it may be impossible to do the same thing in parallel, it may be very easy to do different things in parallel (e.g. in a pipeline architecture, or with a separate UI thread).
    – amon
    Commented Feb 27, 2014 at 20:49
  • 8
    The real point is that you need to design for parallel execution, and if you don't you are constrained by your lack of design. I agree that it can be very easy to do different things in parallel, but not if it's an existing application with high user expectations. In that case it very well may need a rewrite to make it possible. Rewrites are inherently risky, but occasionally you can make a good argument for them. I've done a couple such rewrites which maximized parallel processing while preserving as much code as possible. There's a lot of hidden factors.
    – Berin Loritsch
    Commented Feb 27, 2014 at 21:58
  • Great answer. It may be worth emphasizing that not only might there be diminishing returns in parallelizing some systems, but some may in fact become slower due to the overhead necessary to make them parallel. In particular, lots of semaphores/locks and context-switching may have adverse effects on runtime. Context-switching in particular could reduce the effectiveness of the cache, which is a non-trivial concern if you're at the point of optimizing your system. OP's example of game engines in particular leads me to recall hearing much more about optimizing caching than parallel access.
    – Gankro
    Commented Feb 28, 2014 at 22:38
35

A lot of programs (especially games) inherently use concurrency,

No, actually it's the reverse. Most apps are written in a single threaded mindset, and the developer(s) never made the necessary changes to support concurrency.

In C, C++, and C# you need to explicitly tell the application to start new threads and / or processes.

I think you're focusing too much on the scheduling of the threads and not enough on the data handling within the potential threads. Sharing data across threads and / or processes requires some form of synchronization. If you change an application to use multiple threads but fail to have that synchronization in place then you're likely going to see a lot of hard to track down bugs in the code.

For the multi-threaded applications I have worked on, I have generally never worried about dispatch and only about data synchronization. The only times I had to worry about dispatch was when I was chasing race conditions due to incorrect data synchronization.

Generally, when an application says it can't use multiple cores then it means they don't have the synchronization in place to protect the data manipulation.

Improve this answer
4
  • This is true even for new modern programs from big developer/publishers? When I sit down and write a program, one of the first things in the design stage I think about is, do I need concurrency? Because it can result in a drastically different design. Games in particular must have some level of concurrency, otherwise the game would freeze when one of the thousand on-screen models tried to do something... ?
    – SnakeDoc
    Commented Feb 27, 2014 at 20:23
  • 5
    @SnakeDoc - I think you're confusing your domains there. Big Game companies most certainly write with concurrency in mind, but I have yet to see a game from a Big Game co not support concurrency. The apps & games I have seen that can't support concurrency are generally from smaller shops / individual devs where they wouldn't have started with that mindset. And at some point in the evolution of the application, it becomes impossible to bolt in concurrency after the fact. And some apps were never intended to do enough to justify being concurrent.
    – user53019
    Commented Feb 27, 2014 at 20:27
  • And also some games thrive on new content (graphics and gameplay), without having to update the game engine (code implementation). Thus, the game engine could be years behind in technology.
    – rwong
    Commented Feb 28, 2014 at 6:32
  • 6
    @SnakeDoc: You don't need concurrency to deal with thousands of on-screen models. It's not like every object in your game needs its own thread to simulate it; one thread can handle the updates to everything on screen on every timestep.
    – user2357112
    Commented Feb 28, 2014 at 10:40
13

This is not so much about multiple cores as it is about multiple threads. The OS may schedule a thread to run on whatever core it likes, and this scheduling is transparent for the program being scheduled. However, many programs are not written using multiple threads, so they can only run on one core at once.

Why would I write a single-threaded program? They are easier to write and easier to debug: one things happens after another (instead of multiple things happening at once and possible getting in each others ways). Or your program may not be targeting multi-core machines (as was the case with old games). In some cases, a multi-threaded program could even run slower than a single-threaded version if the overhead from context-switches and communication between threads outweighs the speed gained by parallel execution (some parts of the program may not be parallelizable).

Improve this answer
7

This is not a full answer. It is a cautionary tale.

One day I thought I would show the students in my concurrent programming course a parallel quicksort. Quicksort ought to parallelize well, I thought. I used two threads. Ran it on my single core computer. The results were:

  • 14 seconds for a single-threaded version.
  • 15 seconds for the 2-threaded version.

This was about what I expected.

Then I tried it on a newer, dual-core machine.

  • 11 seconds for the single-threaded version.
  • 20 seconds for the 2-threaded version.

The two threads shared a queue of remaining tasks. It seems the fields of the queue object were being shuffled back and forth between one core's cache and the other's.

Improve this answer
9
  • 2
    How many array elements did you test with? Perhaps mergesort would be more suitable since multi-core programming would have necessitated the copying of data to avoid cache-line conflicts?
    – rwong
    Commented Feb 28, 2014 at 6:30
  • 2
    @rwong There were 10,000,000 array elements. Certainly mergesort would parallelize well. Had I used merge sort I probably would not have learned a useful lesson.
    – Theodore Norvell
    Commented Feb 28, 2014 at 19:40
  • 1
    @ArlaudPierre I will consider parallelizing any algorithm. Quicksort is interesting as you can use the bag-of-tasks approach for it. As the tasks are independent, my intuition was that it should be an example of embarrassing parallelism. I should mention that, after a bit of tuning, it actually got a speedup of close to 2.
    – Theodore Norvell
    Commented Feb 28, 2014 at 19:47
  • 1
    @Jules The answer is load balancing. Also I wanted to write it in a way that makes the number of threads easy to change. Your approach generalizes nicely to powers of 2, but not so well to other numbers of threads.
    – Theodore Norvell
    Commented Feb 28, 2014 at 19:51
  • 2
    @MaciejPiechotka The morals are pretty much all the things that you suggest. But coming back to the OP, I think the most relevant moral is that a multithreaded programs may actually run (much) slower on a multi-core architecture than on a single core processor, unless effort has been expended to ensure otherwise.
    – Theodore Norvell
    Commented Mar 1, 2014 at 16:26

Your Answer

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

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