nested parallel execution...is that even possible?

[Jim foo.bar]

Hi all,

this may sounds like a silly question but I have to ask it!

Let's assume there are 2 nested opportunities for parallel execution of
some code...so for example I've got a genetic algorithm (scoring the
organisms can be run in parallel) and some reducers code that does the
actual minimax searching in parallel...

So my question is:
Who wins? What will run in parallel? presumably the most outer layer of
code yes? (in this case the GA). I do have the option of running either
the GA or the minimax serially but i spent a lot of time to make the
minimax parallel...

If i manage to find a machine with more than 16 cores (I think there are
a couple in my Uni) could I assign 6 cores for the minimax and the rest
for the GA? Has anyone done something similar?

thanks in advance...

Jim

[Herwig Hochleitner]

Have you looked into work-stealing algorithms? Fork-Join (of which reducers can take advantage) implements that. The basic idea is that you split your work into delays (as in clojure.core/delay, called Tasks in Fork-Join) where convenient in your algorithm and push them onto your work queue. You then force the delays later in your algorithm when, you need the result. Meanwhile other workers have the opporunity to compute delays from your work queue, so that their result is already available when you force them.

The net effect can be pretty optimal parallelism.

I don't know if this answers your question precisely, but it might provide an angle to think about the problem. 

kind regards

[Jim foo.bar]

Hi Herwig,

Your suggestion doesn't really apply to my problem because the GA and
the minimax are completely separate...The GA runs in a fixed-size thread
pool which I'm in control of so i can easily set how many threads I want
the GA to spawn, so that is solved (at least theoretically!)...Now, with
regards to the parallel minimax I cannot exactly tune the thread-pool
but i can increase the chunking size when folding (currently set to 2)
but that doesn't imply ignoring some cores but rather more workload for
each forking branch...so basically my problem is how to make the
reducers code run on only 6 cores and devote the rest 10 for the GA...as
I said setting the chunking size will only result in more work for each
thread, thus less threads, however since i've got no fixed branching
factor there is no obvious way to tune the chunking size to guarantee
that the algorithm will ignore some of the cores.

for example:

with chunking of 2 and branching factor of 20 reducers will try to use
10 cores yes?
with chunking of 5 and branching factor of 40 reducers will try to use 8
cores yes?

so in essence:

fixed chunking size + not-fixed branching-factor = no way to predict
how many cores will be used at any given time...

Jim

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient
> with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

[Herwig Hochleitner]

TBH, I wasn't sure what exactly the question was. I'll assume for the rest of this answer, that by 'opportunities for parallel execution' you mean uses of fold.

So if you're asking how to control the number of threads used for folding: That's a constructor argument of ForkJoinPool, which defaults to the number of available processors.

It's not currently exposed in the reducers API, but you could hack it with alter-var-root, if you need to: https://github.com/clojure/clojure/blob/master/src/clj/clojure/core/reducers.clj#L41

As for invoking fold from inside a reducer operation: I'm not that familiar with the implementation yet, but since it's based on ForkJoin, which means recursively splitting the work into lambdas, I suspect that it might just work as expected. See also the implementation of fold for vectors: https://github.com/clojure/clojure/blob/master/src/clj/clojure/core/reducers.clj#L336

[Jim foo.bar]

On 21/09/12 16:54, Herwig Hochleitner wrote:
> So if you're asking how to control the number of threads used for
> folding: That's a constructor argument of ForkJoinPool, which defaults
> to the number of available processors.
> It's not currently exposed in the reducers API, but you could hack it
> with alter-var-root, if you need to:
> https://github.com/clojure/clojure/blob/master/src/clj/clojure/core/reducers.clj#L41
>

oooo this is exactly what I needed!!! thanks a million Herwig...
Now I've got a way to limit the number of threads in the GA and the
reducers bit as well...

this is brilliant! One tiny issue though...

alter-var-root takes a fn to transform the var plus any potential args.
In this case 'ForkJoinPool' does not have a 'setParallelism(int x)'
method...You can only pass it the ctor when you create the object...

In other words, I cannot simply do:

(alter-var-root pool #(.setParallelism % 6))

and obviously I cannot do :

(alter-var-root pool (ForkJoinPool. 6))

I need to call the ctor and somehow rebind the 'pool' var to that
object. How do I do that? any ideas?
Would 'compare-and-set!' work in this case? are all vars wrapped in atoms?

Jim

[Jim foo.bar]

Ok I can see there is a 'var-set' fn that seems to behave exactly as i
need...this is good stuff!

I can now do:

(var-set clojure.core.reducers/pool (ForkJoinPool. 6))

Jim

[Herwig Hochleitner]

 (alter-var-root pool #(.setParallelism % 6))

Sorry for the nitpick, but that would just have been (.setParallelism pool 6), were it possible.

 

I need to call the ctor and somehow rebind the 'pool' var to that object. How do I do that? any ideas?

(alter-var-root #'clojure.core.reducers/pool (constantly (ForkJoinPool. 6)))

var-set only works on dynamically bound vars.

Would 'compare-and-set!' work in this case? are all vars wrapped in atoms?

 

No, vars are much more primitive; basically wrappers around a volatile field, or a ThreadLocal, when dynamically bound. Their 'concurrency semantics' is just good old stochastic 'last one in wins'. So they should normally be considered read-only, except for special use cases like repl, testing, crude hacks, ...

kind regards

[Jim foo.bar]

On 21/09/12 17:42, Herwig Hochleitner wrote:
>
> Sorry for the nitpick, but that would just have been (.setParallelism
> pool 6), were it possible.

aaa yes of course... my brain has turned into mash!

> (alter-var-root #'clojure.core.reducers/pool (constantly
> (ForkJoinPool. 6)))

awesome!
:-) :-) :-) :-) :-) :-) :-)

> No, vars are much more primitive; basically wrappers around a volatile
> field, or a ThreadLocal, when dynamically bound. Their 'concurrency
> semantics' is just good old stochastic 'last one in wins'. So they
> should normally be considered read-only, except for special use cases
> like repl, testing, crude hacks, ...

that is good to know...


thanks a million!

Jim