Dynamic repartitioning and PageRank

[Young Han]

Hi,

Dynamic repartitioning seems to work okay for rev-110 on SSSP, WCC, and a diameter estimation alg I wrote. However, it doesn't work for PageRank. I tried versions all the way back to rev-90 and the same bug occurs. It only happens when >1 worker is used (even for 2 workers on 1 machine) and is due to a NullPointerException during the second superstep, when reading the total # of vertices from the global object map.

The pertinent part of the log:

13392 [main] INFO  gps.node.AbstractGPSNode  - ************************ Start of dumping global objects superstepNo: 2 ************************
13392 [main] INFO  gps.node.AbstractGPSNode  - key: num-total-active-vertices value: -1 396803
13392 [main] INFO  gps.node.AbstractGPSNode  - key: num-total-edges value: -1 3356824
13392 [main] INFO  gps.node.AbstractGPSNode  - key: num-total-vertices value: -1 410236
13392 [main] INFO  gps.node.AbstractGPSNode  - ************************ End of dumping global objects superstepNo: 2 ************************
13392 [main] INFO  gps.node.worker.dynamic.greedy.twosync.TwoSyncGreedyDynamicGPSWorker  - machineId: 1 starting superstepNo: 2 vertexSize: 205118 edgeSize:1677953
13392 [main] INFO  gps.node.worker.dynamic.greedy.twosync.TwoSyncGreedyDynamicGPSWorker  - Start of dumping denseMachines. superstepNo: 2
13392 [main] INFO  gps.node.worker.dynamic.greedy.twosync.TwoSyncGreedyDynamicGPSWorker  - machineId: 0 isDense: false
13393 [main] INFO  gps.node.worker.dynamic.greedy.twosync.TwoSyncGreedyDynamicGPSWorker  - End of dumping denseMachines. superstepNo: 2
13393 [main] INFO  gps.node.worker.dynamic.greedy.twosync.TwoSyncGreedyDynamicGPSWorker  - graphPartition.getNumEdges(): 1677953 is less than (1.05 * numEdgesInTheBeginning): 1761850.6500000001 numEdgesInTheBeginning: 1677953
Exception in thread "main" java.lang.NullPointerException
    at gps.examples.pagerank.PageRankVertex.compute(PageRankVertex.java:60)
    at gps.node.worker.dynamic.greedy.twosync.TwoSyncGreedyDynamicGPSWorker.doExtraWorkBeforeStartingSuperstep(TwoSyncGreedyDynamicGPSWorker.java:181)
    at gps.node.worker.AbstractGPSWorker.startWorker(AbstractGPSWorker.java:202)
    at gps.node.GPSNodeRunner.startGPSWorker(GPSNodeRunner.java:293)
    at gps.node.GPSNodeRunner.main(GPSNodeRunner.java:165)


Note that I've added some comments to PageRankVertex, so line 60 is actually the one right below compute():

    int numVertices = ((IntSumGlobalObject) getGlobalObjectsMap().getGlobalObject(
      GlobalObjectsMap.NUM_TOTAL_VERTICES)).getValue().getValue();


Thanks,
Young

[Semih Salihoglu]

Hi Young,

I can't remember exactly which version we had when we were working on dynamic repartitioning but you should use the OneSyncGreedy one. That one, I remember for sure. Maybe go to some version around 70s (say 73 or earlier) and try one sync.

Also, you should note that we never got very much benefit out of dynamic repartitioning. If you read our paper, you see that our improvements were only on very limited settings, (for very long running PageRank computations). In general, I advice not to do dynamic repartitioning and also not to work on it. I think it's very difficult to get benefits out of it in a real system implementation. The overheads are just too high.

Best,

semih

--
You received this message because you are subscribed to the Google Groups "stanfordgpsusers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to stanfordgpsuse...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Young Han]

Hi,

Is the default TwoSyncGreedy fine to use in general (vs. OneSyncGreedy)? It's worked so far for shortest path and WCC... the results are correct too. As for PageRank, it actually runs so long as we don't try to get |V|, which is fine because we can compute PageRank another way: start with 1.0 and use (0.85 * value-from-neighbours + 0.15).

Yup, this is part of an experiment to compare some systems/features. My results reaffirm your findings (slight drop in network I/O, but running time overheads). LALP works great though.

Thanks,
Young

--
You received this message because you are subscribed to a topic in the Google Groups "stanfordgpsusers" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/stanfordgpsusers/HV04gc-2Tcs/unsubscribe.
To unsubscribe from this group and all its topics, send an email to stanfordgpsuse...@googlegroups.com.

[Semih Salihoglu]

TwoSync was fine to use but after a while we started focusing on OneSync. So we may have introduced bugs to TwoSync. That's why I said try to use OneSync.