Search Microcontrollers

Friday, May 24, 2013

Puzzle, moving the solution to parallel

The puzzle problem illustrated here and for which I proposed a simple algorithm here, can probably be assigned to multiple CPUs at the same time in a way that the solution is found in parallel.

In my original post I already explained that the solution search process can be "initialized" using the "step" array which encodes the  list of "moves" executed in the first "n" steps.

This means that the problem can be visualized as follows :

Each level of this tree represents one step.
So, for step 1 (after root) there are 8 possible positions to be tested, each one of which has 8 possible destinations in step 2 etc.

"Slicing"the problem means, at any level, to restrict the search from move n>=1 to move m <=8.
Then slices of the problem may be distributed to different CPUs to be computed at the same time.

If we try to implement this concept in the example algorithm, we need to account for three things :

1) The initial part of the solution, consisting of a step array from 1 to i that locates the beginning of the search for the given process
2) The initial move to be tested at step i+1
3) The final move to be tested at step i+1

Technically this could be implemented by making step a 2 dimensional array initially set as :

{{0,8},{0.8},{0,8}....}  being 0 the last move attempted (none) and 8 the last to be attempted for that particular step.

When initializing the solution for a giving CPU, by transmitting the step array, we could use the last element in the array as the boundary of the solution to be searched.

Let's imagine a process P1 started to attempt a solution for the (5x5) puzzle and after 3 steps, it decides to call for reinforcements, asking a second cpu to take over part of the problem.

In our example the current situation is represented by the image below

this also means that the step array contains the following data :

Where the Last Move is the move that allowed us to move from A1 to C2 (Step 1), then from C2 to E1 (Step 2) etc according to the numbering visible below.

We know that the Max Move is 8 because the current process (P1) is asked to investigate the FULL solution (so, from 1 to 8 for every step).
At this point P1 wants to ask a new process P2 to address part of the problem starting from step 4.
Let's imagine that P1 decides to split the work from step 4 onward into two sets of moves S1= [1..4] and S2=[5..8].
It will run itself S1 and ask P2 to take care of S2.

P1 needs to prepare the initial step array for P2, basically telling it which part of the problem has already been taken care of.
The first 3 steps will need to be "locked", so the Max Move will be set equal to Last Move, plus the additional new step 4 will have Last Move = 4 (this si the last move defined in S1) and Max Move = 8

-> Step(P2) = {{3,3},{2,2},{5,5},{4,8}}

At the same time P1 needs to set a constraining Max Move for step 4

-> Step(P1) = {{3,8},{2,8},{5,8},{0,4}}

The example used only two different processes, but the concept stands for any number of processes that could be engaged at any step.

No comments: