On Friday, 18 October 2013 at 11:40:24 UTC, qznc wrote:
On Friday, 18 October 2013 at 07:20:07 UTC, tbttfox wrote:
So I've got a project in mind, and at the core of that project
is a DAG with lots of nodes. This seems to be a great
candidate for concurrent evaluation. The problem is that a
node can only be evaluated after all of its parents have.
I'm really new to D and static typing in general (coming from
Python-it was way too slow for this), and I'm having trouble
navigating the shared/const/immutables and keeping within the
concurrency structure in D.
The actual question: Will the following strategy work? I've
tried coding this a couple times, and it just doesn't seem to
be working. Is there something wrong with my logic?
I make a shared list of linked nodes and pass that to each
thread on spawn. Then the indexes of any node without a parent
go into a queue. The main thread then passes list indexes to
the worker threads from that queue. When a worker thread gets
an index, it makes a local copy of that node, evaluates it,
and stores the data it computes with the node.
Then every child of that node is checked to see if its parents
have all been processed. If so, that child is added to the
queue and the thread requests another item from the queue.
When the queue is empty, the job is done.
I assume your goal is to exploit parallelism for a speedup? How
expensive is the "evaluates it" step? Is the traversal or the
evaluation dominating the run time in the single-threaded
version? How scalable do you need to be (e.g. Desktop Multicore
or Cluster or Cloud)?
In terms of logic, I can see no error. Though it is not clear,
if you use push or pull. The master might push to the workers
or the workers might pull from the master.
Correct, I'm trying to exploit the parallelism for a speedup. The
evaluation will eventually be the expensive part (once I write
it, of course.). And this is for a desktop application, so only
multicore.
My not currently not working implementation has the workers make
a pull request from the master. I'll post the code when I have a
minute later in the day.
And thanks much for the help
~tbttfox
