[rules-users] Drools Planner - split and join parallelism

[Geoffrey De Smet]

Op 20-12-12 00:46, Willem van Asperen schreef:
> Hi All,
>
> I have an idea that I would like to bounce of the list.
>
> As far as I understand, Drools Planner does not do any parallel
> searching. It uses a single solver thread that does all the work.
There are these forms of multi-threading (and multi-JVMing) Planner:

A) "Expert parallelism": Multi-threading Drools Expert score calculation 
(which is the deepest loop of Planner).
Mark Proctor is working on this with his new NoRete algorithm.
Because Planner calls Expert about 5000 / second, so 200ns per work unit,
this might not be suitable for multi-JVMing (due to network overhead).

B) "MoveScope parallelism": Multi-threading the MoveScopes in Planner 
(Local Search, Construction Heuristics, ...)
I have recently started laying the ground work for this,
but it will probably only be completed by 6.1 (Q3 2013).
https://issues.jboss.org/browse/JBRULES-681

The whole difficulty is going parallel without breaking "incremental 
score calculation (delta's)".
The scalability gain of delta's is bigger than parallelization (see 
image in manual).
Combining the 2 will be a major step forward, game changing.
After the 6.0 release I am going focus exclusively on JBRULES-681 for a 
month or 3.

This can also support multi-JVMing by sending bulk loads of MoveScopes 
across the network.

C) "run 2 or more Solvers separately":
Basically take a problem and build 2 Solvers (with different 
configuration) and run both of them on the problem.
At the end, return the best result. I wouldn't call this parallelism really
because if you're already running the statistically-best Solver config, 
the other Solver configs won't do much better.
> What if I would forage not only the best solution so far, but a couple
> of "promising" solutions and split these off to run on a separate
> thread. I would split these itteratively down to a given level of iteration.
Interesting thought: the higher your level of iteration, the less you 
kill delta's, avoid the difficulty of B.
Of course, the higher your level of iteration, the more you become 
problem C), lowering the potential gain...
Lets call this
D) "map-reducing Solvers".

>
> When these threads return I would then pick the best solution from the
> returned values.
>
> Using a multi-core box or even a server farm I could massively increase
> the searched problem space and do it without loosing too much time (some
> parallel management overhead).
This my goal for B) too :)
>
> Has anyone thought of such scheme before? Any luck in implementing?
> Do you see any flaws?
Read up on incremental score calculation (delta's). See Planner manual.
>
> Just a thought.
Go for it: fork Planner and see what you come up with :)
Let me know what works well (and more importantly) what does not work.
>
> Regards,
> Willem
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>