The KLA Paradigm: Putting Things Together

Once we have our initializer, vertex and neighbor operators, we can provide them to our graph paradigm to initialize and process the graph. The graph paradigm applies the operators on vertices of the graph as required, in order to execute the algorithm. A BFS is simply written as shown below:

template<typename GraphView>
void BFS(GraphView& graph, size_t source) {
// Initialize the graph.
map_func(BFSInit(source), graph);

// Execute the BFS.
}


Figure-5: The BFS/SSSP intializer.

Here, we assume the GraphView represents the input graph, which has the properties required for BFS to execute (size_t distance, bool active and size_t parent on the vertices). For executing an SSSP algorithm, we would simply replace the BFSVertexOp with the SSSPVertexOp, while the initializer and neighbor operators remain the same.

To improve performance, we can control the amount of asynchrony in the algorithm, while it executes. This is done by providing an optional parameter to the graph_paradigm, k. k is an integer between 0 and INT_MAX, which controls how many iterations are executed asynchronously per KLA Superstep:

int k = 5;
graph_paradigm(BFSVertexOp(), BFSNeighborOp(), graph, k);


Figure-6: The k-level Asynchronous Paradigm -- Making the execution more asynchronous.

Technical Specification of the KLA Paradigm

• Integer k specifies the level of asynchrony in the execution of the algorithm. When k = 0 or 1, the execution is BSP/level-synchronous.
• For asynchronous execution, the neighbor operator must be idempotent.