multi-threaded priority_queue in C++?

Discussion in 'C++' started by robin.chauhan, Jul 22, 2006.

  1. I'm stuck while trying to make this C++ app multi-threaded! Any advice
    would be appreciated.

    Basically I have a very big graph data structure in memory. And I want
    to run an algorithm on it, using a priority_queue to track which order
    I will inspect the nodes :


    goal_location L;
    priority_queue<EID, vector<EID>, locComparison > openq;

    struct locComparison {
    bool operator () ( EID i1, EID i2 ) {
    ... compare i1 and i2 based on distance from goal location
    ....
    };
    };

    Right now I am just using a mutex on the algorithm so only one can run
    at a time, and then using a global variable to hold the goal location
    (which is fine because I allow only one algo-instance at a time). But
    then I'm not using my multiple cores.

    So I would like to be able to run more than one instance of this
    algorithm on the data structure at once in multiple threads.

    I just cant tell the "locComparison" functor what the per-algorithm
    goal location is. If I wrap the priority_queue in a class:

    class algo
    {
    goal_location L;
    priority_queue( ... locComparison );
    }

    .... each instance of the class would use the same locComparison
    function, and I have no way of passing parameters to locComparison it
    to tell it what the goal location is for this particular priority
    queue.

    Any thoughts? Places you would suggest I look?

    Thanks!

    -Robin
    robin.chauhan, Jul 22, 2006
    #1
    1. Advertising

  2. robin.chauhan

    mlimber Guest

    robin.chauhan wrote:
    > I'm stuck while trying to make this C++ app multi-threaded! Any advice
    > would be appreciated.
    >
    > Basically I have a very big graph data structure in memory. And I want
    > to run an algorithm on it, using a priority_queue to track which order
    > I will inspect the nodes :
    >
    >
    > goal_location L;
    > priority_queue<EID, vector<EID>, locComparison > openq;
    >
    > struct locComparison {
    > bool operator () ( EID i1, EID i2 ) {
    > ... compare i1 and i2 based on distance from goal location
    > ...
    > };
    > };
    >
    > Right now I am just using a mutex on the algorithm so only one can run
    > at a time, and then using a global variable to hold the goal location
    > (which is fine because I allow only one algo-instance at a time). But
    > then I'm not using my multiple cores.
    >
    > So I would like to be able to run more than one instance of this
    > algorithm on the data structure at once in multiple threads.
    >
    > I just cant tell the "locComparison" functor what the per-algorithm
    > goal location is. If I wrap the priority_queue in a class:
    >
    > class algo
    > {
    > goal_location L;
    > priority_queue( ... locComparison );
    > }
    >
    > ... each instance of the class would use the same locComparison
    > function, and I have no way of passing parameters to locComparison it
    > to tell it what the goal location is for this particular priority
    > queue.
    >
    > Any thoughts? Places you would suggest I look?


    You might try comp.programming or comp.programming.threads, or try
    rephrasing it as a C++ language question. If you do that latter, note
    the guidelines on posting code here:

    http://parashift.com/c -faq-lite/how-to-post.html#faq-5.8

    One approach might be to show us how you might solve this problem in C
    or pseudocode since we're not concerned with algorithms here (see this
    FAQ: http://parashift.com/c -faq-lite/how-to-post.html#faq-5.9), and
    then maybe we can be of some language assistance.

    Cheers! --M
    mlimber, Jul 23, 2006
    #2
    1. Advertising

  3. robin.chauhan

    Guest

    robin.chauhan wrote:
    > I'm stuck while trying to make this C++ app multi-threaded! Any advice
    > would be appreciated.
    >
    > Basically I have a very big graph data structure in memory. And I want
    > to run an algorithm on it, using a priority_queue to track which order
    > I will inspect the nodes :
    >
    >
    > goal_location L;
    > priority_queue<EID, vector<EID>, locComparison > openq;
    >
    > struct locComparison {
    > bool operator () ( EID i1, EID i2 ) {
    > ... compare i1 and i2 based on distance from goal location
    > ...
    > };
    > };
    >
    > Right now I am just using a mutex on the algorithm so only one can run
    > at a time, and then using a global variable to hold the goal location
    > (which is fine because I allow only one algo-instance at a time). But
    > then I'm not using my multiple cores.
    >
    > So I would like to be able to run more than one instance of this
    > algorithm on the data structure at once in multiple threads.
    >
    > I just cant tell the "locComparison" functor what the per-algorithm
    > goal location is. If I wrap the priority_queue in a class:
    >
    > class algo
    > {
    > goal_location L;
    > priority_queue( ... locComparison );
    > }
    >
    > ... each instance of the class would use the same locComparison
    > function, and I have no way of passing parameters to locComparison it
    > to tell it what the goal location is for this particular priority
    > queue.
    >
    > Any thoughts? Places you would suggest I look?


    Why don't you make 'locComparison' stateful, and instantiate it with
    the goal location?
    , Jul 23, 2006
    #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. Tino

    clearing a priority_queue

    Tino, Jul 9, 2003, in forum: C++
    Replies:
    4
    Views:
    1,153
    Stuart Golodetz
    Jul 9, 2003
  2. newsock

    queue, deque, priority_queue

    newsock, Oct 24, 2003, in forum: C++
    Replies:
    15
    Views:
    2,422
    Tim Clacy
    Nov 4, 2003
  3. Dave
    Replies:
    7
    Views:
    542
    Jerry Coffin
    Apr 22, 2004
  4. Tino
    Replies:
    3
    Views:
    758
    rossum
    May 28, 2004
  5. ian douglas
    Replies:
    2
    Views:
    981
    Randy Howard
    Jul 30, 2004
Loading...

Share This Page