Re: Efficient CPU usage with recursively parallelizable problem
On Sat, 17 Oct 2009, Tomas Mikula wrote:
I have a purely computational (no I/O) problem that can be recursively
split into concurrent tasks. Each task needs to wait for its child tasks
to complete. How would I implement this efficiently, meaning to keep all
the CPU cores busy, while keeping the context-switching overhead low
(i.e. maintain the number of running threads roughly equal to the number
of cores)?
You appear to have rediscovered what is called the "fork-join" parardigm
for parallelism. Sometimes known as "work stealing", although that name
refers to its usual implementation, rather than its surface semantics.
I think this must be a common problem, but can't find a straightforward
solution in the Java SE API. Therefore I'm asking here, maybe I'm
overlooking something.
Just upgrade to Java 7, which will have classes for fork/join via JSR
166y.
Or, if you don't have a time machine, read Doug Lea's paper:
http://gee.cs.oswego.edu/dl/papers/fj.pdf
And then download his library:
http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html
Or even the prototypes of the JSR-166y classes:
http://gee.cs.oswego.edu/dl/concurrency-interest/
Related reading:
http://www.ibm.com/developerworks/java/library/j-jtp11137.html
tom
--
It's Brains you want!