Trouble developing API for easy parallel/multithreaded programming

[k04jg02]

I have an idea for an easy to use API that would allow some degree of
parallelism without the programmer thinking too hard about it. I'm
having some trouble figuring out how to implement it though. The idea
is you have tasks, and some tasks depend on other tasks having been
completed. These dependencies form a tree, e.g.:

R
/ \
A B
/ \ / \
C D E

So in this case, tasks A and B depend on R having finished, C depends
on A and R being finished, D depends on R, A, and B being finished,
etc. The programmer would explicitly build this tree, writing
something like this:

A.depends(R);
B.depends(R);
D.depends(A);
D.depends(B);

etc. After the user constructs the tree, they should just be able to
tell it to run: R.start(). This is where the parallelism comes in.
When R finishes, it should create two threads, one that runs A and one
that runs B. When A finishes, it should run C and somehow register to
D that it is ready. When B is finished it should run E and somehow
indicate to D that it is ready. When A and B are both done, a thread
running D should start.

What I've described so far isn't too difficult -- the only tricky part
is who creates the thread that runs D. Using either a mutex guarding a
pointer to D's thread or boost::call_once, I can make sure that the
thread running D only gets created once.

Where I'm stuck is for how these tasks should pass data to one
another. The idea is that child tasks depend on their parent being
completed because their parent is going to generate some data that
they will use. Rather than relying on the user to avoid accessing data
too early, I'd like to try and setup for this to be checked at compile
time. Basically, I need to somehow indicate that say A produces output
X, which should be input to task's C and D. C and D should know the
type of input they expect, and A should know the type of output it
produces, and that these match should be typechecked. My intuition is
that some template magic is the solution here, but the best solutions
I've come up with so far involve runtime checks.

Ideas?

 

[Jim Langston]

I have an idea for an easy to use API that would allow some degree of
parallelism without the programmer thinking too hard about it. I'm
having some trouble figuring out how to implement it though. The idea
is you have tasks, and some tasks depend on other tasks having been
completed. These dependencies form a tree, e.g.:

R
/ \
A B
/ \ / \
C D E

So in this case, tasks A and B depend on R having finished, C depends
on A and R being finished, D depends on R, A, and B being finished,
etc. The programmer would explicitly build this tree, writing
something like this:

A.depends(R);
B.depends(R);
D.depends(A);
D.depends(B);

etc. After the user constructs the tree, they should just be able to
tell it to run: R.start(). This is where the parallelism comes in.
When R finishes, it should create two threads, one that runs A and one
that runs B. When A finishes, it should run C and somehow register to
D that it is ready. When B is finished it should run E and somehow
indicate to D that it is ready. When A and B are both done, a thread
running D should start.

What I've described so far isn't too difficult -- the only tricky part
is who creates the thread that runs D. Using either a mutex guarding a
pointer to D's thread or boost::call_once, I can make sure that the
thread running D only gets created once.

Where I'm stuck is for how these tasks should pass data to one
another. The idea is that child tasks depend on their parent being
completed because their parent is going to generate some data that
they will use. Rather than relying on the user to avoid accessing data
too early, I'd like to try and setup for this to be checked at compile
time. Basically, I need to somehow indicate that say A produces output
X, which should be input to task's C and D. C and D should know the
type of input they expect, and A should know the type of output it
produces, and that these match should be typechecked. My intuition is
that some template magic is the solution here, but the best solutions
I've come up with so far involve runtime checks.

Ideas?

This question is a combination of comp.programming.threads and
comp.programming. We usually don't deal so much with algorithms here but
more specific C++ issues.

Now, there are a few ways to say
A depends on R at compile time.
class A: public R
{
};

class A
{
R inst;
};

But your input is at run time, not compile time.

If A and R were both derived from some common class I could see a
constructor requiring the creation of the other.

class A: public Base
{
public:
A( /* something */ ) { /* instantize Base* depending on something */ };
private:
Base* Required;
};

something could be a character such as 'R', or a type if used as a template.

You really haven't said what A, B, C etc.. are so can only guess.

I don't know, even this portion might be better served in comp.programming.

 

[k04jg02]

Sorry, I was unclear. The graph is _not_ meant to be any sort of
inheritance relationship between classes. The idea is each letter, R,
A, B, C, D, E would be objects of some sort of Task class. The Task
class would have a method, call it Run(), that would cause the task to
do some work, generating data. When this work was finished, that data
would somehow be passed on to tasks dependent on the current task, and
if the dependent tasks had no other tasks to wait for they would
Run().

This is a C++ question rather than an algorithms/threading question in
the sense that I'm trying to figure out how to do the passing of data
from parent tasks to child tasks in a type safe way. I could just have
a bunch of globals representing each tasks output, but I'm going for
something generic and that will make sure children don't have access
to their parents data until it's done "cooking" (the parent task has
finished).