PowerSwitch: Adaptive Prediction and Mode Switch on Graph-parallel Computation

Large-scale graph-structured computation usually exhibits iterative and convergence-oriented computing nature, where input data is computed iteratively until a convergence condition is reached. Such features have led to the development of two different computation modes for graph-structured programs, namely synchronous and asynchronous modes. Unfortunately, there is currently no in-depth study on their execution properties and thus programmers have to manually choose a model, either requiring a deep understanding of underlying graph engines, or suffering from suboptimal performance.

PowerSwitch project makes the comprehensive characterization on the performance of the two modes on a set of typical graph-parallel applications. Our study shows that the performance of the two modes varies significantly with different graph programs, partitioning methods, execution stages, input graph and cluster scales and no single mode consistently outperforms the other. This project proposes Hsync, a hybrid graph computation mode that adaptively switches a graph-parallel program between the two modes for optimal performance. Hsync constantly collects execution statistics on-the-fly and leverages a set of heuristics to predict future performance and determine when a mode switch could be profitable. We have built both an online sampling and an offline neural-network approaches to allow accurate prediction of future execution performance. PowerSwitch has been built based on PowerGraph, a state-of-the-art graph-parallel systems, to support Hsync execution of graph applications. On a 48-node EC-like cluster, PowerSwitch consistently outperforms the best of both modes, with a speedup ranging from 9% to 73% due to accurate switching between two modes.

• SYNC or ASYNC: Time to Fuse for Distributed Graph-parallel Computation (slides) (poster)
  Chenning Xie, Rong Chen, Haibing Guan, Binyu Zang and Haibo Chen.
  ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'15).
  Bay Area, California, USA, February, 2015.

If you use PowerSwitch in your work or research, please let us know about it. We also encourage you to reference our papers.

The PowerSwitch source code is distributed with a Apache license 2.0. The copyright is held by Shanghai Jiao Tong University.
You can checkout the newest code from github mirror, which is based on GraphLab 2.2 (Jul. 8, 2013. commit:fc3d6c6).
To use the full functions, we strongly suggest you checkout source code from the github mirror. But if you are interested in estimating or working with powerswitch hybrid engine, you can also obtain a snapshot (~14MB) from Dec. 16 2013, which is based on GraphLab 2.2 (Jul. 8, 2013. commit:fc3d6c6).

Once you've downloaded PowerSwitch, you can find instructions for installing and building it on the GraphLab's documentation page.
For Sampling-Switch mode, you just need to set the Hsync engine with configuration in command line.
For a nerual network based switch mode, besides setting the configuration with Hsync engine, please follow the instructions in Neural Network Training part.

Usage#1: Running PageRank algorithm on LiveJournal graph using PowerSwitch engine. (Online Sampling Strategy)

  $mpiexec -f ~/mpd.hosts -n 48 ./pagerank --graph /path/to/livejornal_ --format tsv --engine msync 
  --engine_opts s_auto=true,a_tasknum=5,t_sample=1000,rate_AvsS=0.75
	
   NOTE:
     --engine engine : set execution engine (msync: mix-adaptive engine of PowerSwtich)
     --engine_opts   : set engine options
          s_auto     : set estimation and switch strategy to be sampling and adaptive switch.
          a_tasknum  : set executed task number(x1000) on each machine during sampling in async, 
                       which should be set according to input size. 
                       (suggested to be < 20, and default is 5, which means 5x1000=5000)
          t_sample   : set time interval of monitor in asynchronous scheduling, and default is 1000 (1000ms).
          rate_AvsS  : set task number proportion of synchronous and asynchronous schedulings.
                       (range:0.5 to 1, and default is 0.75)

Usage#2: Running PageRank algorithm on LiveJournal graph using PowerSwitch engine. (Neural Network Strategy)

  $mpiexec -f ~/mpd.hosts -n 48 ./pagerank --graph /path/to/livejornal_ --format tsv --engine msync 
  --engine_opts auto=true,t_sample=1000,rate_AvsS=0.75

   NOTE:
     --engine_opts    : set engine options
          auto        : set estimation and switch strategy to be neural network estimation and adaptive switch. 
                        This should be set together with "graph.set_async_thro(double thro)" after loading the graph, 
                        in which the throughput could be calculated based on input from "|E|/|V|" and "R"
                        (|E|/|V|= graph.num_edges/graph.num_vertices and R = graph.num_replicas/graph.num_vertices).
   

   TIPS: You can follow the Neural Network Training part to generate the c++ function 
         for profiling the throughput with the two input. 

Usage#3: Running Loopy BP Algorithm on synthetic image data using PowerSwitch engine.

  $mpiexec -f ~/mpd.hosts -n 48 ./lbp_structured_prediction --prior /path/to/synth_vdata_ --graph /path/to/synth_edata_ 
  --output /path/to/output --graph_opts ingress=grid --engine msync --engine_opts s_auto=true,a_tasknum=5,t_sample=1000

   TIPS: The input data could be produced according to GraphLab's documentation page of Loopy BP Algorithm.

Usage#4: Running SSSP on directed weighted graph using PowerSwitch engine.
  $mpiexec -f ~/mpd.hosts -n 12 ./sssp_x --graph_opts ingress=grid --graph /path/to/weight-ca-road-dataset 
  --engine msync --engine_opts s_auto=true,start_async=true,rate_AvsS=0.5

   NOTE:
     --engine_opts:
          start_async  : set starting mode to be asynchronous or not. The sssp_x program is implemented as same as 
                         original sssp program but loads a derected graph as input (line format : source target weight).

You should insert the following code into your application to load the training graphs produced by PowerSwitch system, (A sample is provided in the pagerank_x.cpp applications under the toolkits/graph_analytics directory of the source code) or you could provide any other training graphs by yourself, e.g., the subgraphs of your real input data.

  /** NOTE:
   *  The default vertex number of training graphs is 200,000, 
   *  which may be adjusted to ensure that "piped-thread x #machine > vertex number".
   *  (piped-thread in PowerSwitch is 3000 currently.)
   *  You could add vertex number as the second parametter, when loading, 
   *  e.g., graph.load_synthetic_powerlaw(powerlaw_alpha, vertex_number);
   */

  double powerlaw_alpha = 0;
  clopts.attach_option("powerlaw_alpha", powerlaw_alpha,
                       "Apha for generate a synthetic powerlaw out-degree graph. ");
  size_t randomdegree = 0;
  clopts.attach_option("random", randomdegree,
                       "Generate a random graph with the parametter as average degree.");
					 
  // make a synthetic graph
  if(powerlaw_alpha > 0) { 
    dc.cout() << "Loading synthetic Powerlaw graph. alpha " << powerlaw_alpha << std::endl;
    graph.load_synthetic_powerlaw(powerlaw_alpha);
  }
  // make a random graph
  else if(randomdegree> 0) {
    dc.cout() << "Loading Random graph. #e/#v " << randomdegree << "." << std::endl;
    graph.load_random_graph(randomdegree);
  }

To produce the training data of neural network, you could refer to the training script as an example. It should be noted that the training computation should be executed under stable network environment.
We suggest that Neural Network Toolbox in MATLAB could be used to build the neural network.
You can run the command in MATLAB to start the toolbox with a friendly UI:

	>>nnstart

Then choose the "Fitting Tool", and follow the guide. You could generate cpp interface in MATLAB with the script or MATLAB object produced by neural network toolbox. The generated function would receive two parametters as input and return a throughput as output.

• Chenning Xie
• Rong Chen
• Haibing Guan
• Binyu Zang
• Haibo Chen

Please contact Chenning Xie for further information. Welcome to let us know about bug reports and suggested improvements, while we may not be able to provide technical support timely. If you make some correction or improvement to PowerSwitch, we would appreciate receiving a patch that we can include in the next release.

PowerLyra: differentiated parallel graph computation and partitioning on skewed graph.
Polymer: NUMA-aware graph-structured analytics framework.