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

graph-tool webmaster at skewed.de
Mon Jun 9 18:13:53 UTC 2014

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

 * Status from 'reopened' to 'closed'
 * Resolution from '' to 'worksforme'

The difference in performance you are observing is easy to understand. In the current code, the 'static' schedule is used, which means the loop is divided into equal chunks which are run in different threads. Each chunk visits an equal number of vertices. However these vertices can have very different degrees, and hence the total number of **edges** visited will vary from chunk to chunk, and the whole computation has to wait for the last chunk to finish. By shuffling the vertex order, it guarantees that, on average, the degrees will be evenly spread across all threads, but there will be stochastic fluctuations, as you are observing. If the vertices are unbalanced, for instance if the vertices are sorted according to degree, it would be better to use a different schedule. There are a couple of options:

1. static schedule, chunk size 1: This will **interleave** the iterations so that threads do not get consecutive vertices.
2. static schedule, chunk size n, where n << N / num threads: Having a smaller chunk size will also improve balancing
3. dynamic schedule: Thread balancing is performed dynamically at run time. This can achieve near-optimal balancing, but at the expense of some overhead.

Determining which option is best requires some experimentation. In the git version you can now select the schedule at runtime, as I explained above, so you can play with that.

Unfortunately there are no binaries for the git version. If you do not want to compile the git version you will need to wait until the next release.

Since the git version includes this improvement, and what you are observing is not really a bug, but a characteristic of how OpenMP works, I'll go ahead and close this bug. (Feel free to post to the mailing list, if you are still having questions, or reopen the bug if you believe there is something that needs to be fixed.)
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