Parallel Programming With Recursive Functions?

Question

Background of the Problem: I'm trying to write a puzzle solution algorithm that takes advantage of multi-core processors and parallel processing. However, the ideal/easiest solution is a simple recursive function.

What's the best way to break down the solution to both take advantage of parallel processing AND the recursive function?

The code below is a solution for a simple puzzle solving algorithm (it works correctly). The puzzle in this example is straightforward - there are 14 slots numbered 1-14. Each puzzle piece has a unique ID, a range that tells you where it can start and stop (e.g. 6-8 means it only fits in slots 6-8), and a price. The algorithm attempts to find the solution that maximizes the price of the solution. Only 1 piece can occupy a slot, and empty slots are acceptable. The solution would tell you which pieces are used and the total cost. (To keep things simple, assume also that slot 1 MUST be filled).

My attempted solution to combine parallelism and recursion is what is used below: create a Task for each piece that uses slot 1, then within the Task recursively look through the rest of the pieces, slotting them into the remaining spaces while maximizing the cost. Is this the best solution (probably not, which is why I'm here). How can it be improved? Any other good recommendations when using parallel/recursive solutions?

While the simple recursion would work well here, I'm picturing this running with a Puzzle that has 200 slots and 5000 pieces.

Here's the solution to this example as well:

ID=1 Price=10.0 Range=1-6
ID=12 Price=8.0 Range=9-14
ID=15 Price=3.0 Range=7-8


public class Puzzle
{

    public PuzzleSet calculateResults(PuzzleSet input) throws Exception
    {   
        System.out.println(System.currentTimeMillis());
        PuzzleSet results = getPriceMultithread((PuzzleSet)SerializationUtils.clone(input));
        System.out.println(System.currentTimeMillis());
        return results;
    }

    private PuzzleSet getPriceMultithread(PuzzleSet input) throws Exception
    {
        PuzzleSet initial = input.startsAtPoint(1);

        ExecutorService exec = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors()+1);
        Collection<Callable<PuzzleSet>> tasks = new ArrayList<Callable<PuzzleSet>>();

        for (int i=0; i<initial.size(); i++)
        {
            final PuzzleData d = initial.get(i);
            final PuzzleSet start = input.higherThan(initial.get(i).rangeUpper);
            tasks.add(new Callable<PuzzleSet>() {
                public PuzzleSet call() {
                    PuzzleSet s = new PuzzleSet();
                    s.add(d);
                    s.addAll(getPrice(start));
                    return s;
                }
            });
        }

        List<Future<PuzzleSet>> results = exec.invokeAll(tasks);
        PuzzleSet max = new PuzzleSet();
        double maxD = 0.0;
        for (int i=0; i<results.size(); i++)
        {
            PuzzleSet temp = results.get(i).get();
            double sum = temp.sum();
            if (sum > maxD)
            {
                maxD = sum;
                max = temp;
            }
        }
        return max;
    }

    private PuzzleSet getPrice(PuzzleSet input)
    {
        if (input == null || input.size() == 0)  return new PuzzleSet();

        double maxD = 0.0;
        PuzzleSet max = new PuzzleSet();
        for (int i=0; i<input.size(); i++)
        {
            PuzzleSet vs = input.higherThan(input.get(i).rangeUpper);
            PuzzleSet s = getPrice(vs);
            double d = s.sum();
            double pTemp = input.get(i).price + d;
            if (pTemp > maxD)
            {
                maxD = pTemp;
                s.add(input.get(i));
                max = s;
            }
        }       
        return max;
    }

    public static void main(String arg[]) throws Exception
    {
        PuzzleSet s = new PuzzleSet();

        PuzzleData v1 = new PuzzleData();
        v1.rangeLower = 1;
        v1.rangeUpper = 6;
        v1.price = 10;
        v1.ID = 1;
        s.add(v1);      

        PuzzleData v2 = new PuzzleData();
        v2.rangeLower = 7;
        v2.rangeUpper = 11;
        v2.price = 0;
        v2.ID = 2;
        s.add(v2);

        PuzzleData v3 = new PuzzleData();
        v3.rangeLower = 12;
        v3.rangeUpper = 14;
        v3.price = 7;
        v3.ID = 3;
        s.add(v3);      

        PuzzleData v5 = new PuzzleData();
        v5.rangeLower = 7;
        v5.rangeUpper = 9;
        v5.price = 0;
        v5.ID = 4;
        s.add(v5);

        PuzzleData v6 = new PuzzleData();
        v6.rangeLower = 10;
        v6.rangeUpper = 14;
        v6.price = 5;
        v6.ID = 5;
        s.add(v6);

        PuzzleData v7 = new PuzzleData();
        v7.rangeLower = 1;
        v7.rangeUpper = 3;
        v7.price = 5;
        v7.ID = 6;
        s.add(v7);

        PuzzleData v8 = new PuzzleData();
        v8.rangeLower = 4;
        v8.rangeUpper = 9;
        v8.price = 0;
        v8.ID = 7;
        s.add(v8);

        PuzzleData v10 = new PuzzleData();
        v10.rangeLower = 1;
        v10.rangeUpper = 5;
        v10.price = 3;
        v10.ID = 8;
        s.add(v10);

        PuzzleData v11 = new PuzzleData();
        v11.rangeLower = 6;
        v11.rangeUpper = 11;
        v11.price = 2;
        v11.ID = 9;
        s.add(v11);

        PuzzleData v12 = new PuzzleData();
        v12.rangeLower = 12;
        v12.rangeUpper = 14;
        v12.price = 7;
        v12.ID = 10;
        s.add(v12);

        PuzzleData v14 = new PuzzleData();
        v14.rangeLower = 4;
        v14.rangeUpper = 8;
        v14.price = 1;
        v14.ID = 11;
        s.add(v14);

        PuzzleData v15 = new PuzzleData();
        v15.rangeLower = 9;
        v15.rangeUpper = 14;
        v15.price = 8;
        v15.ID = 12;
        s.add(v15);

        PuzzleData v16 = new PuzzleData();
        v16.rangeLower = 1;
        v16.rangeUpper = 5;
        v16.price = 3;
        v16.ID = 13;
        s.add(v16);

        PuzzleData v17 = new PuzzleData();
        v17.rangeLower = 6;
        v17.rangeUpper = 8;
        v17.price = 1;
        v17.ID = 14;
        s.add(v17);

        PuzzleData v18 = new PuzzleData();
        v18.rangeLower = 7;
        v18.rangeUpper = 8;
        v18.price = 3;
        v18.ID = 15;
        s.add(v18);

        PuzzleSet x = new Puzzle().calculateResults(s); 
        for (int i=0; i<x.size(); i++)
        {
            System.out.println(x.get(i));
        }

    }
}

public class PuzzleData implements Serializable
{
    public int rangeLower;
    public int rangeUpper;
    public int ID;
    public double price;

    public String toString()
    {
        return "ID=" + ID + " Price=" + price + " Range=" + rangeLower + "-" + rangeUpper;
    }
}

public class PuzzleSet extends ArrayList<PuzzleData> implements Serializable
{
    public PuzzleSet higherThan(int lowBound)
    {
        PuzzleSet s = new PuzzleSet();
        for (int i=0; i<size(); i++)
        {
           if (get(i).rangeLower > lowBound)
               s.add(get(i));
        }
        return s;
    }

    public PuzzleSet startsAtPoint(int point)
    {
        PuzzleSet s = new PuzzleSet();
        for (int i=0; i<size(); i++)
        {
           if (get(i).rangeLower == point)
               s.add(get(i));
        }
        return s;
    }

    public double sum()
    {
        double sum = 0.0;
        for (int i=0; i<size(); i++)
            sum += get(i).price;
        return sum;
    }

    public String toString()
    {
        StringBuffer b = new StringBuffer();
        for (int i=0; i<size(); i++)
        {
            b.append(get(i).toString());
        }
        return b.toString();
    }
}

Answer 1

The type of problem reminds me of genetic algorithms. You already have a fitness function (the cost) and the layout of the problem seems suited to crossover and mutation. You could use one of the available G.A. engines and run multiple pools/generations in parallel. G.A's tend to find good solutions quite fast, although finding the absolute best solution is not guaranteed. On the other hand I believe the puzzle you describe does not necessarily have a single optimal solution anyway. G.A. solutions are often used for scheduling (for example to create a roster of teachers, classrooms and classes). The solutions found are usually 'robust' in the sense that a reasonable solution catering a change in the constraints can often be found with a minimal number of changes.

As to parallelizing the given recursive algorithm. I tried this recently (using Terracotta) for the n-Queens problem and did something simlar to what you descibe. The first-row queen is placed in each possible column to create n subproblems. There is a pool worker threads. A job scheduler checks if there is an idle worker thread available in the pool, and assigns it a subproblem. The worker thread works through the subproblem, outputting all found solutions, and returns to idle state. Because there are typically far fewer worker threads than subproblems, it is not a big issue if subproblems don't take equal amounts of time to solve.

I'm curious to hear other ideas.

Answer 2

JSR-166Y is intended to facilate the implementation of parallel recursion in Java 7 by taking care of thread coordination. You may find their discussions, code, and papers (especially Doug Lea's paper A Java Fork/Join Framework) useful.

Answer 3

you could use monte carlo and run them parallely. add some randomness in term of selection of piece to get based on constraints.