Quote:
Originally Posted by RustyBrooks
It's probably something that would benefit from multi-threading, but not on a machine with just 1 CPU. If one thread already uses ~100% of a CPU there is nothing to be gained from a 2nd thread
Well, since it's still rolling around in my head, I might as well ask and learn something, even if I'm not going to implement it right away.
The program itself is pretty straight-forward. I've got the check process (the one that gets repeated over and over) broken down into 3 basic steps:
1) Generate a permutation to apply to the unsolved cube. This is done algorithmically, so that given any permutation has a well-defined "next" permutation. This generation is therefore a linear task and can't be multithreaded.
2) Apply the permutation to the unsolved cube. (We can make lots of copies of the cube, so the different threads won't need to be accessing the same information.)
3) Check whether the resulting cube configuration matches with something in a database of known configurations. (There's just one database, but the values are all fixed so data corruption can't happen there.)
The normal pattern is to loop around from 1-3 over and over again. There are two places where the multithreading seems to fit.
A) Multithread the calculation of the permutations
B) Multithread the checking step
I have three different conceptual pictures in my head.
P1) I have one line of workers and each of them are checking in after step 1. Each worker does steps 2 and 3 with their given permutation. (Each worker gets their own cube, twists it a few times, and then walks through the entire library to see if there's a match.)
P2) I have one line of workers and each of them are checking in after step 2. Each worker does step 3 but checks a different part of the list. (This is like giving copies of the cube to the workers, and each worker checks a different section of the library for a match.)
P3) I have two lines of workers. One checks in after step 1 and the checks in after step 2. So one group is constantly generating arrangements of cubes to check and the other group is running to the library to check. (There's one group that is constantly making a stack of cubes, and then a team of people taking one cube at a time and each one is checking a different part of the library)
The first and second pictures seem roughly identical conceptually. I already have the task written out and just branch out from that point forward. The third picture seems like it would require a much more sophisticated change to the programming because I'm now creating two distinct types of tasks and the latter is dependent upon the completion of the first. I assume that the third picture is possible, but maybe it's not? I don't even know if that's a good idea because unless it's perfectly tuned, there will always be a back-log. Either the workers will be waiting for more cubes to check, or the cubes will be piling up. But again, this is just the picture in my head.
In practice, is there a rule of thumb for deciding where/how to implement multi-threading? Here's what I believe about the program.
* I suspect the actual process involved in steps 1 and 2 are slow. But since Step 1 is linear, that can't be multithreaded.
--- Step 2: Each turn of the cube involves changing either 20 or 40 variables. Each permutation will have more and more steps as the search depth gets deeper. Even if the search is only 4-5 moves deep, there's already going to be about 100+ variable manipulations involved.
* The individual process of checking at step 3 is fast.
--- Step 3: If the cube is correctly solved, it will check 48 different positions. But the vast majority of the time it will check just a couple positions before finding it's not a match, and the program will immediately leave the check process and return a negative match. This part is only slow because there are tens of thousands of positions in the library.
My intuition is that the gain is likely better in the slower processes because of the overhead cost of just routing the workers. Is this a reasonable way of thinking about it?