Re: [rules-users] Drools Planner - split and join parallelism
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(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users