Trouble developing API for easy parallel/multithreaded programming

Discussion in 'C++' started by k04jg02@gmail.com, Feb 18, 2008.

  1. Guest

    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?
    , Feb 18, 2008
    #1
    1. Advertising

  2. Jim Langston Guest

    wrote:
    > 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.

    --
    Jim Langston
    Jim Langston, Feb 18, 2008
    #2
    1. Advertising

  3. Guest

    Re: Trouble developing API for easy parallel/multithreadedprogramming

    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).

    On Feb 18, 4:36 pm, "Jim Langston" <> wrote:
    > wrote:
    > > 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.
    >
    > --
    > Jim Langston
    >
    , Feb 18, 2008
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paul Perrone
    Replies:
    0
    Views:
    14,418
    Paul Perrone
    Aug 21, 2003
  2. Svein Seldal

    Multithreaded C API Python questions

    Svein Seldal, Nov 9, 2006, in forum: Python
    Replies:
    9
    Views:
    3,222
    robert
    Nov 17, 2006
  3. Soren
    Replies:
    4
    Views:
    1,250
    c d saunter
    Feb 14, 2008
  4. Vivek Menon
    Replies:
    5
    Views:
    3,336
    Paul Uiterlinden
    Jun 8, 2011
  5. Vivek Menon
    Replies:
    0
    Views:
    1,760
    Vivek Menon
    Jun 10, 2011
Loading...

Share This Page