Thread: Optimizing for parallell execution... on linux

Originally Posted by CornedBee

- I find your names confusing. The BoardCoordinates class doesn't make sense to me.

I can only tell you its function. It contains valid coordinates in the board to examine to place a queen. This is because I remove rows and columns as I place queens.
When I think about it, it might have been better to just merge BoardCoordinates and Board into a single class, but... well, right now, it works, so I don't want to go there. In the future, if I reuse this, I might do it.

Neither does GetBoard (it gets a field).

Probably a bad name when you mention it...

- Why is GetBoard even a bound function? Why not make Board a proper class and give it an indexing call operator, so that you can write Board(x, y)? Boost.Bind can act as an optimization barrier (it holds a function pointer), and you definitely want the field access to be inlined.

Initially, I didn't use any function at all. I just indexed the board using the index operator directly. But then I wanted to test location and whether it could speed up the function (ie, x first or y first), so I made it into a lambda.
But gcc 4.4 doesn't support lambdas, so I just used a dirty hack to make it compile.

- Given that your work queue is pretty much known at compile time, static work division by index would be far more efficient than the work queue: no locking, no fetching elements from a stack.

I didn't want static division. One thread my run faster than another. So ideally, what I wanted to do is create n threads, wait until one of them finishes, schedule more work for it.
There is no WaitForMultipleObjects, so this is the best I figured I could do it.

- Whether you use a work queue or computed work division, a better choice as the basis of the implementation would be the Intel Threading Building Blocks (TBB) library. It has higher-level operations, such as a parallel for loop. You could model your problem very well with a parallel for loop, I think.

If it's free, then it's definitely something I would consider in the future.
However, there are requirements on this task. It must use threads, condition variables and locks. No abstraction mechanisms such as OpenMP.

Originally Posted by Elysia

I didn't want static division. One thread my run faster than another. So ideally, what I wanted to do is create n threads, wait until one of them finishes, schedule more work for it.
There is no WaitForMultipleObjects, so this is the best I figured I could do it.

You have absolutely the right idea there, the problem is you are working with monkey wrenches for tools. Sadly it is very hard to do scalable parallelism with threads using the commonly available primitives. As an example of doing it right look at Cilk Plus, Intel TBB or Microsoft PPL. In my opinion we are doing a huge disservice by forcing students to work at the stupidly low level of threads and mutexes. You will never write anything scalable that way, it's just too difficult. The solutions are out there, it's frustrating that people aren't using them.

Do not worry. This is just the basics to make sure proper understanding of the building blocks. It is not an absolute requirement for the future.
I just looked at Intel's Thread Building Blocks, and I must say I am disappointing. All there is is a commercial license for $100 (for students) or GPL v2, both of which sucks. Screw you Intel.

Originally Posted by Elysia

I just looked at Intel's Thread Building Blocks, and I must say I am disappointing. All there is is a commercial license for $100 (for students) or GPL v2, both of which sucks. Screw you Intel.

If you're doing cross-platform projects for college, GPLv2 isn't a problem. And if you're doing your own stuff, which I believe you're mostly doing for Windows, use the Microsoft PPL, which is 95% source compatible: just change the includes and recompile, and it usually just works.

Originally Posted by Elysia

Do not worry. This is just the basics to make sure proper understanding of the building blocks. It is not an absolute requirement for the future.
I just looked at Intel's Thread Building Blocks, and I must say I am disappointing. All there is is a commercial license for $100 (for students) or GPL v2, both of which sucks. Screw you Intel.

Can you give me idea why you think that? I can forward your concerns to some people I know on the TBB team. For what you're getting, I would think $100 a cheap price.

Compare it to the GPL version. It's free. So clearly they are interested in providing it for free to the community, and that is what the GPL version is for.
The commercial version is clearly targeted at corporations with lots of money to pay so they can keep their source code secret. I can understand they wanting $100 or so from corporations with commercial interests. But I am not a corporation, hence $100 is a lot.

The reasons I dislike GPL (from my limited knowledge of it) are:
- You are required to provide source code for the program. I don't like this. It means I cannot have control over the source of my own program. I am not entirely against giving out or making source public, but I like choice. GPL does not give me any choice.
- You are required to either provide source with the binary distribution, or provide access to source via physical media (v3 fixes this AFAIK, but this is v2 we're talking about).

EDIT: It's also a big concern how Intel's compiler cripples AMD processors with their compiler. AFAIK, this hasn't changed in any new version. With that in mind, who would pay $100+ when they have at least one (and intend to have more in the future) AMD processors?

Originally Posted by Elysia

You are required to provide source code for the program. I don't like this. It means I cannot have control over the source of my own program. I am not entirely against giving out or making source public, but I like choice. GPL does not give me any choice.

I think that's the point though, and also the reason why reciprocal licenses are often paired for such dual licensing schemes. You do have choice: use one license or the other, with different trade-offs. It just is just that you don't like both choices, but that's too bad because you're not the copyright holder... they could, after all, have offered just one license at full price for all users.

Originally Posted by Elysia

But I am not a corporation, hence $100 is a lot.

Consequently, it sounds like it is not that you dislike the GPL here, but that you dislike the price of the other license, e.g., maybe if they charged $20 instead, you would be happy.

Originally Posted by laserlight

Consequently, it sounds like it is not that you dislike the GPL here, but that you dislike the price of the other license, e.g., maybe if they charged $20 instead, you would be happy.

I dislike GPL, and I dislike the price other license too, and that is the problem.
*shrug* We all have a choice, though. If one doesn't like it, one doesn't have to use it. So that's precisely what I am going to do, at the moment.

Originally Posted by Elysia

The reasons I dislike GPL (from my limited knowledge of it) are:
- You are required to provide source code for the program. I don't like this. It means I cannot have control over the source of my own program. I am not entirely against giving out or making source public, but I like choice. GPL does not give me any choice.
- You are required to either provide source with the binary distribution, or provide access to source via physical media (v3 fixes this AFAIK, but this is v2 we're talking about).

I'm glad I asked, because I can assuage your fear. The TBB OSS license is GPLv2 with the libstdC++ runtime exception. This is the same exception which is used for the Linux kernel to allow binary works to link dynamically against the kernel (or in this case, TBB) without falling under the usual GPL restrictions. This means that as long as you use it in the form of a DLL and do not statically link it into your code, you are good to go. See here.

EDIT: It's also a big concern how Intel's compiler cripples AMD processors with their compiler. AFAIK, this hasn't changed in any new version. With that in mind, who would pay $100+ when they have at least one (and intend to have more in the future) AMD processors?

TBB is totally independent of the problem you are talking about. It is true that the Intel compiler as well as their IPP libraries have some broken CPU checks in them which cause the program to take the slow path on AMD CPUs, and that ticks me off just as much as it does you. But it has no bearing on TBB.

We all have a choice, though. If one doesn't like it, one doesn't have to use it. So that's precisely what I am going to do, at the moment.

Rolling your own isn't a realistic option (not if you want to do it right), so you're pretty much limited to either TBB (if you want to be portable) or PPL (if you're willing to stick with MS tools only). Obviously you can choose whatever you want, though.

Originally Posted by brewbuck

I'm glad I asked, because I can assuage your fear. The TBB OSS license is GPLv2 with the libstdC++ runtime exception. This is the same exception which is used for the Linux kernel to allow binary works to link dynamically against the kernel (or in this case, TBB) without falling under the usual GPL restrictions. This means that as long as you use it in the form of a DLL and do not statically link it into your code, you are good to go. See here.

I'm glad you asked. This changes things dramatically! This means I can use it incoming projects.
Obviously keeping track of these licenses and what exactly they mean is a chore.

Well, I have taken a look on the source files of TBB, and they mention that source that uses TBB is exempt from the license, which I interpret as I can use whatever license I want for my source/binaries.

Anyway, recently I have had to work with this a little more and this time with TBB.
This time, I get a speedup of roughly 1.8x on my dual core and 3.67x on the linux machine. However, seeing as it is supposed to have 24 cores, that is rather pitiful...

Did you ever find out if it's a NUMA box? Some links here: How to force two process to run on the same CPU

gg

Well, in case this means NUMA, then yes:

numactl --hardware
available: 2 nodes (0-1)
node 0 size: 22196 MB
node 0 free: 11574 MB
node 1 size: 22220 MB
node 1 free: 12449 MB
node distances:
node 0 1
0: 10 20
1: 20 10

But apart from changing to TBB, there isn't much changed since last. The threads are lock free and execute independently. There should be no reason why there is such a huge slowdown since they should access only local memory until the time comes to merge the solutions...

So I'm guessing that node 0 and 1 both have 12 cores at their disposal. Not sure how to confirm that, maybe "numactl --dump all"?

It would be interesting to see what happens if you compile with "NUM_THREADS=12", and run it with "numactl --cpubind=0 --membind=0 program". That should run like a normal 12 core SMP system (in theory).

gg