stevendiaz / compressed-graph-sssp

Performance-first parallel graph search in C++

SSSP on a compressed graph

How to run

The makefile separates by experiment. To run the experiments, run the following commands, respectively

$ make chaotic
$ make delta
$ make dijkstra
$ make deltaOptimal

Documentation

Files

• CSR.cpp/h
  • Compressed Sparse Row class
• Parser.cpp/h
  • Parsing input class, returns an instance of CSR
• SSSP.cpp/h
  • Contains delta step algorithm
• Worklist.cpp/h
  • Worklist class, abstracts a map of 'buckets'
• *Experiment.cpp
  • Different runners for the various experiments

CSR.cpp - Compressed Sparse Row implementation

void put (int32_t x, int32_t y, int32_t val)

• Sets x,y in the adjaceny matrix to val
• x is from edge, y is to edge

int32_t get (int32_t x, int32_t y)

• Returns the weight for edge x->y

vector<vector<int32_t>> iterate()

• Returns a vector of vectors
• Each vector will have the format <u, v, weight>

void printNodeLabels()

• print all the labels for each of given nodes

long getTent (int32_t u)

• returns the tentative cost of node u

void setTent (int32_t u, long val)

• set the tentative cost of node u to cost val

void debugInfo()

• print out the inner workings of the CSR
• IA, JA, and the values

bool nodeFullyRelaxed (int32_t node)

• returns true if all the nodes out of node have been relaxed

void relaxNode (int32_t src, int32_t dest):

• sets the edge as relaxed

Worklist.cpp - Worklist implementation

bool hasElements()

• returns true if there are still items in a bucket

long getIndex()

• returns the index of the first non-empty bucket

set<int32_t> get(long i)

• returns the bucket stored at i

void put(long i, set<int32_t> nodes)

• puts a set of nodes at bucket i

void relaxNodes(set<csrTuple> req, int seed)

• relaxes the set of nodes in req, shuffles with seed seed

void printRelaxCount()

• prints the number of edge and node relaxations

set<vector<int32_t>> getLight()

• returns the light edges

void setLight(set<vector<int32_t>> s)

• sets the light edges to set s

set<vector<int32_t>> getHeavy()

• returns the heavy edges

void setHeavy(set<vector<int32_t>> s)

• sets the heavy edges to s

set<csrTuple> match(set<int32_t> bucket, set<vector<int32_t>> s)

• returns a set to be relaxed, the nodes in both bucket and s

SSSP.cpp - DeltaStep implementaton

DeltaStep(CSR csr, int32_t step, int seed)

• Constructor
• takes in a CSR graph, step size, and a seed for shuffling

run(bool printNLabels, bool printRelaxCount)

• Runs the delta step algorithm
• If printNLabels is true, the node labels are printed
• If printRelaxCount is true, the number of relaxations are printed

Parser.cpp - Input parser

CSR parseInput()

• returns a created CSR from the input file

Runner Files - *Experiment.cpp

chaoticExperiment.cpp

• Measures clock time and node relaxations across different seeds
• Seeds: 10, 20, 50

deltaStepExperiment.cpp

• Measures node relaxations across different step sizes
• Prints out node labels and number of steps

dijkstraExperiment.cpp

• Runs dijkstra by setting delta to 1
• prints out node labels and node relaxations

deltaOptimalExperiment.cpp

• runs the optimal delta across all the different graphs
• prints node relaxations and clock time

Finding Highest Outdegree

General Approach

The graph is represented by a NxN matrix, where the rows represent from vertices and the columns represent the to vertices. Therefore, if A[u][v] = w, there is edge from u to v with edge weight w.

With this definition, calculating the highest outdegree is equivalent to finding the row with the most non-zero entries.

Finding most non-zero entries with Compressed Sparse Row

The number of non-zero entries can be computed with the IA vector of Compressed Sparse Row.

The IA vector has the following definition:

• IA[0] = 0
• IA[i] = IA[i - 1] + number of non-zero entries for row i - 1

Code

for(int i = 0; i < numRows){
    int currDegree = IA[i + 1] - IA[i];
    if(currDegree > oldDegree){
        row = i;
        oldDegree = currDegree;
    }
}
return row;

compressed-graph-sssp's Issues

rmat15 changing delta

Largest Out Degree Node Experiment

Extend chaotic relaxation from delta step

Implement a time-out if the number of relaxations exceeds some bound

From the project:

Chaotic relaxation sssp algorithm:

• Chaotic relaxation can take a very long time even for small graphs for some schedules of node relaxations. Your code should terminate the computation if the number of relaxations exceeds some bound that depends on the size of the graph.

Make 2 sample graphs of 5 nodes and 20 edges in DIMACS

Convert delta step in c++

Clean up CSR in c++

Routine to find node with highest degree

Experiments to be implemented

1. Largest out-degree -> record largest out-degree for each graph and confirm they match given data
2. Experiment with 3 different random seeds for chaotic relaxation (delta = INT_MAX)
3. Djikstras on rmat15 and road-NY (delta = 1)
4. Compute analytically the number of relaxations with number of nodes and number of edges
5. Iterate over different delta step for rmat-15 and road-NY for number of relaxations
6. Use the optimal delta from above to run delta step on all other graphs, count number of relaxations AND runtime

CSR, to_dimacs() method

Routine to print out node labels

rmat22 delta Optimal (dijkstra)

pass seed into random_shuffle

road-FLA deltaOptimal (dijkstra)

Convert Worklist into c++

Parse dimacs in c++

djikstra rmat15

dmat23 deltaOptimal (dijkstra)

dijkstra roadNY

rmat20 delta Optimal

roadNY changing delta

rmat15 & road NY experimental delta

Extend Dijkstra from delta step

rmat15 delta experiment