Tree distribution and traversal performance

User 409 | 7/7/2014, 11:58:31 PM

Hi, I have two questions: 1) I am trying to traverse a distributed tree in preorder fashion and update the state of vertices while traversing. Also, as a node is visited, it produces some data that is being used by the next vertex in the traversal. The tree has two edges(one in each direction) between a vertex and its child. I am using the vertex engine program: graphlab::omniengine<trav> engine(dc, graph, "synchronous") The following functions are overridden: gather: INEDGES, collects the results from the previous vertex. scatter: OUT_EDGES, signals the next vertex. apply: updates the current vertex state.

As you can see, at any point of time, only one/two vertices are active.

However, the performance is bad. It takes around 300secs to traverse a tree of 2000 nodes (I am traversing the tree repeatedly 1000 times) with a single process.

I have tried the following performance tuning options mentioned here: http://graphlab.org/projects/tutorials.html#perf_tuning i)release build ii)--ncpus=2 and also --ncpus=1

I know that the the vertex-centric model is not best suited for traversals. How can I improve the performance, Is there something very wrong I am doing?

2) I would like to have parts of the tree (entire subtrees of certain height) owned by a single process. I am unable to find a way to do this.

Partial Snapshot of the output while traversal:

INFO: distributedingressbase.hpp(finalize:199): Finalizing Graph... INFO: distributedingressbase.hpp(finalize:199): Finalizing Graph... INFO: synchronousengine.hpp(start:1299): Iteration counter will only output every 5 seconds. INFO: synchronousengine.hpp(start:1314): 0: Starting iteration: 0 INFO: synchronousengine.hpp(start:1363): Active vertices: 1 INFO: synchronousengine.hpp(start:1412): Running Aggregators INFO: synchronousengine.hpp(start:1314): 0: Starting iteration: 5389 INFO: synchronousengine.hpp(start:1363): Active vertices: 2 INFO: synchronousengine.hpp(start:1412): Running Aggregators INFO: synchronousengine.hpp(start:1314): 0: Starting iteration: 10793 INFO: synchronousengine.hpp(start:1363): Active vertices: 1 INFO: synchronousengine.hpp(start:1412): Running Aggregators INFO: synchronousengine.hpp(start:1314): 0: Starting iteration: 16297 INFO: synchronousengine.hpp(start:1363): Active vertices: 1 ==================================================================

Thank you.

Nikhil

Comments

User 6 | 7/8/2014, 5:57:08 AM

Hi Nikhil, The meaning of synchronous engine, is that it traverses the FULL GRAPH (each and every node) on each iteration. This is not what you want since your algorithm has a DFS like functionality. In that case we recommend using the asynchronous engine.


User 409 | 7/8/2014, 8:47:18 PM

Thanks Danny. Aynchronous engine performance is much better and it took around 1.6 seconds now. Where can I find documentation about engines? Also, regarding my second question, is it possible to specify that a vertex is owned by a specific process? In line parser, I tried something like: if(dc.procid() == procRank) //create vertex, //call graph finalize This did not work.