Multi-core threading

The OS will manage the thread locations to spread the load across all processors in the system.
It will also tend to keep a thread running on the same core it ran on last time (to help with cache coherency).

But, consider the OS tends to be really good at shuffling around X CPU bound processes, where X is the number of cores.
But looking at something like Supreme Commander, it is still possible to confuse the OS's scheduling (thus the CoreMaxamizer tool for SupCom).

If you only have 2 cores, there is a chance the two sort threads sometimes run one per core, sometimes one of them fights with the main game thread for CPU time. If that is infact the case, you could call a Sleep(0) in the main thread just after you issue the sort jobs. You risk not getting control back as quickly as you might like, but you'd insure that the other threads have full access to the CPU.

Thanks for the reply. So consider the threadpool if i spawn two threads at the start of the application, will the location of the threads ever change?

WHen i assign jobs to either of these threads, i call wait immediately after which I think (sleeps) the main thread anyway. Isnt this the same idea as sleep(0)?

Thanks.
Ash.

Yes, the locations CAN change, but they may not, it depends on what else the OS needs to schedule on your CPU (you have lots of background tasks that might occasionally take some CPU time, causing things to rearrange)

Sleep(0) in windows drops the current thread, leaves it scheduled as normal, and schedules the current thread's remaining quantum. That time remaining in the quantum may go to another thread, or the current thread may immediately wake up.

Sleep(N) in windows drops the current thread, and flags it for reschedule after N milliseconds. Then a new scheduling cycle is kicked off and something else chosen to run. But, your thread that you called Sleep from will not have a chance to reschedule for at least 1 quantum. So, Sleep(1) could last 1ms, or more likely 15ms, or anything up to a few seconds.

There are some other thoughts, like this that you need to consider. But it might be an option.

Unless you must support very old Windows versions, don't use Sleep(0), use SwitchToThread(). It only schedules a thread that would be scheduled on the same core later, which is a good thing. Also, in case you need to know, you can tell from the return value whether a different thread has run in the mean time or not.

You've posted your problem description sure, that's good. However I haven't seen any details that could allow us to really help you yet. So far everyone will only be able to speculate about your problem. Here's a list of things you can provide that would enable you to get help quicker:

What platform is this on? Windows or Linux, or something else?
What language are you programming in?
What sorting algorithm have to implemented? Some algorithms have lots of room for parallelisation, and some cannot be parallelised at all. Some require more synchronisation than others.
What is your sorting routine up to 2x faster than? (The same algorithm on a single thread, or a different implementation e.g. std::sort if C++)
What are the items that you are actually sorting, and how many of them are there typically?
And most usefully, can you post the actual sorting algorithm routines?

It's worth knowing how to get the most out of threading in your environment, and assuming you're both talking about the same platform, KulSeran's advice should help you out there.
However that's only half of the story. At the end of the day it's all about speed right? You may find that there's a lot more room for optimisation of your algorithm implementation than you think. You may find some of my website useful (link below), but it would be best if you could post some of your own code.

Im im on windows vista 64 with a dual core. C++ for the implimentation. I havent implimented the sorting algorithm im using (std::sort), I have just segmented the data so I can process it concurrently using a median value to estimate at what point I can split the data up in, this way I dont have to merge the data after the two sorts are done I just iterate over it.

So, it should yield a 2x increase on the sort, or 4x or 8x depending on the number of cores. The sort might not be perfect but it will function as how I want it to.

Im sorting particles at the moment im testing with only 10k of them.

Somthing with threading is causing the program to slow down on some frames as If i disable it, it only jumps at most between 2fps. With my multithreaded app it jumps over 10fps, somtimes running slower than without threads, other times running much faster.

Ive tried using boost::threadpool now, still getting the same results as before so I dont believe it is anything to do with my locking, as I now dont actually perform any locking on any piece of data.

Quote:

Original post by Asheh Some frames it causes the application to run upto 2x faster but some frames it can slow the overall application down.

Quote:

Original post by Asheh So, it should yield a 2x increase on the sort, or 4x or 8x depending on the number of cores.

Quote:

Original post by Asheh Im sorting particles at the moment im testing with only 10k of them. Somthing with threading is causing the program to slow down on some frames as If i disable it, it only jumps at most between 2fps. With my multithreaded app it jumps over 10fps

So, to recap, you're switching between single- and multithreaded sorting modes, and using the resulting program FPS as a measure of how much of an improvement this is, and expecting a 2x difference? This is wrong in so many ways - you need to have better profiling methods rather than just blindly guessing what is going on. Rather than redoing all these profiling threads we have at gamedev already, I'll refer you to some earlier discussions for starters:
SDL + OpenGL Speed Question.
Speeding up particle effect.

Hope that helps to look in the right direction.

Quote:

Original post by Asheh Im im on windows vista 64 with a dual core. C++ for the implimentation. I havent implimented the sorting algorithm im using (std::sort), I have just segmented the data so I can process it concurrently using a median value to estimate at what point I can split the data up in

This would mean your threads aren't being sorted evenly. Use merge sort.

Quote:

So, it should yield a 2x increase on the sort, or 4x or 8x depending on the number of cores.

Nope. It will always be less than 2. And considerably less than 4, let alone 8. The only exception are superlinear algorithms, but those are somewhat hard to find in practice due to various overhead costs.

Naive paralellization typically results in 85-95% total CPU utilization on 2 core, and 75% on 4 cores. When you get to 8, other issues come into play as well.

Consider this: Main thread needs to either pre-partition the data, or perform final merge it. So linear time needed to perform is: Tmain + Tsort/N. As N increases, Tsort/N approaches 0, but Tmain doesn't change.

Of course, you might try increasing N particles to get more work done in each core, but this would also increase final pass cost.

Quote:

Ive tried using boost::threadpool now, still getting the same results as before so I dont believe it is anything to do with my locking, as I now dont actually perform any locking on any piece of data.

std::sort does not have guaranteed running time.

One possible solution to this is to add more granularity. Instead of splitting array into two, split it into 10 pieces. Then have 2 threads process each chunk, when done, perform the final pass.

In theory it is possible to have a 2x increase on two cores if you remove the overheads of creating the initial threads. Some frames this happens (i understand its not a total 2x increase, i believe it was around 1.8x).

Anyway... my main problem is I cannot get a consistant speed with the threads, 1 or 2fps differences is fine.

FWIW (as above) No i am not using the FPS as an indicator im using high resolution timers and averaging the time over a number of frames to get a good estimate. But every so often, the FPS jumps low for a second... (this is when the profiling shows that its actually slowing down the overall application and running slower than If i sort them on a single core).

It cant be the sorting because if I sort on 1 core, the fps/profiling results are steady. (the data is still segmented on a single core)

If i move it to two cores somthing is causing the fps to drop and be erratic, which changes my profiling results.

If i add granularity, will this help this problem? I have only managed to narrow this problem down to the threading causing this stalling/change in timing.

Quote:

Original post by Asheh In theory it is possible to have a 2x increase on two cores if you remove the overheads of creating the initial threads. Some frames this happens (i understand its not a total 2x increase, i believe it was around 1.8x).

And in theory, Pi equals 3. Note that I mentioned around 90% CPU utilization on 2 cores, which is consistent with 1.8. In practice, it's the very overhead that limits scalability. And while not very noticeable on 2 cores, as you increase the numbers, it becomes very problematic.

Theory is all fine and dandy, but practice refuses to play along.

Quote:

It cant be the sorting because if I sort on 1 core, the fps/profiling results are steady. (the data is still segmented on a single core) If i move it to two cores somthing is causing the fps to drop and be erratic, which changes my profiling results.

Let's say you get 40 FPS on single core, and 75 FPS on two cores. How much is the drop on two cores? Is it below 40?

If it only drops to 40-75 range, then the problem is very likely caused by degenerate data, which causes one half of sort to take considerably longer, thereby negating the performance increase.

// single core = 10 units// double core  = 5 units (+1 overhead) = 5 units (+1 overhead// degenerate case[L][EFTRIGHT] = 9 units

Or, you end up with one thread needing almost as much time as entire sort takes.

Quote:

If i add granularity, will this help this problem? I have only managed to narrow this problem down to the threading causing this stalling/change in timing.

It can help, since it avoids the degenerate case:

[L][TR][T] = 5 units (+3 overhead)[EF][IGH] = 5 units (+2 overhead)

But it may also increase the overhead, if granularity is too high.

Print out how long each half of sort takes in individual threads. If you notice both halfs are very uneven, then granularity is the problem.

But it could also be any random problem. Concurrency isn't easy, and sometimes the problem is completely elsewhere.

Quote:

Original post by Asheh I havent implimented the sorting algorithm im using (std::sort), I have just segmented the data so I can process it concurrently using a median value to estimate at what point I can split the data up in, this way I dont have to merge the data after the two sorts are done I just iterate over it. So, it should yield a 2x increase on the sort, or 4x or 8x depending on the number of cores. The sort might not be perfect but it will function as how I want it to. Im sorting particles at the moment im testing with only 10k of them.

Thanks for the info, that's great. Of coure you haven't actually implemented the sorting algorithm, you've merely used it.

I can appreciate that since you're sorting particles that an exact ordering usually isn't necessary, as they usually wont overlap one another, and any such overlap would only create a small, brief and barely-noticeable glitch.

I'm still not quite sure how you're doing it though, Are you copying the data to a seperate array for each thread or are they both operating on different sections of the same array? If the later, are you per-processing the array to split the data into non-overlapping ranges? You aren't overlapping iterators provided to std::sort for each thread are you?!
Without a merge step wouldn't you end up with two ascending sequences?
There should be other options for sorting that scale better to multiple cores without the need to add in additional merge steps etc. Fair enough starting off with std::sort though, rather than re-inventing the wheel before you need to.
Perhaps you could check whether the frame rate is affected by whether the particles are sorted correctly or not (seen that kind of thing happen before). If you don't sort them at all, is the frame rate smooth?

Not sure it has been said yet (and I'm assuming you're using win32 here), but you can "bind" your thread to a particular core using SetThreadAffinityMask...

Check your usage of system resources, memory allocation, especially if hidden (e.g. in stl containers). Read this interesting herb sutter article to get an idea of what I mean.
Hope this helps!