[graph-tool-tickets] [graph-tool] Ticket #156: OpenMP problem in katz and pagerank

graph-tool webmaster at skewed.de
Sun Jun 8 20:10:18 UTC 2014

#156: OpenMP problem in katz and pagerank
closed enhancement
Reporter: anonymous
Owner: tiago peixoto
Priority: normal
Milestone: 2.2

Comment (by td):

I am reopening the bug as a matter of discussion on OpenMP for the Graph-Tool's PageRank implementation.

I am not the original guy who opened the bug. And OpenMP does use multiple CPU on my computer. 

BUT I still have noticed that for PageRank computation, depending on the graph, it is sometimes very efficient and sometimes very inefficient in doing so.

For instance, I have to large graphs I am testing with, and I am testing on a 4CPU computer:

* Wikipedia graph (~500k nodes, ~4.5M edges) -> Graph-Tool PR uses all my CPU @ 100%, great (convergence in ~27 iterations, 1.1 second)
* A Web crawl graph (~450k nodes, ~30M edges) -> Gra[h-Tool uses 1 CPU @ 100% and the other ones @ ~20% (convergence in ~57 iterations, ~18 seconds)

I then tested on a 16 CPU machine and one the second graph Graph-Tool, would basically use CPUs @ ~10%... 

I tried to look at how PR is implemented in Graph-Tool to understand how the OpenMP splitting is done by it is not very clear to me, not being very fluent with OpenMP (nor with boost!).

Any thoughts?
Ticket URL: <URL:http://graph-tool.skewed.de/ticket/156>
graph-tool <URL:http://graph-tool.skewed.de>
An efficient python module for graph analysis and manipulation.

More information about the graph-tool-tickets mailing list