multi-threaded priority_queue in C++?

[robin.chauhan]

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

 

[mlimber]

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

 

[davidrubin]

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?