| Taskflow: A General-purpose Task-parallel Programming System

Loading...
Searching...
No Matches
Graph Traversal

We study the graph traversal problem by visiting each vertex in parallel following their edge dependencies. Traversing a graph is a fundamental building block of many graph applications especially for large-scale graph analytics.

# Problem Formulation

Given a directed acyclic graph (DAG), i.e., a graph that has no cycles, we would like to traverse each vertex in order without breaking dependency constraints defined by edges. The following figure shows a graph of six vertices and seven edges. Each vertex represents a particular task and each edge represents a task dependency between two tasks.

Traversing the above graph in parallel, the maximum parallelism we can acquire is three. When Task1 finishes, we can run Task2, Task3, and Task4 in parallel.

# Graph Representation

We define the data structure of our graph. The graph is represented by an array of nodes of the following structure:

struct Node {
std::string name;
size_t idx; // index of the node in a array
bool visited {false};
std::atomic<size_t> dependents {0}; // number of incoming edges
std::vector<Node*> successors; // number of outgoing edges
void precede(Node& n) {
successors.emplace_back(&n);
n.dependents ++;
}
};

Based on the data structure, we randomly generate a DAG using ordered edges.

std::unique_ptr<Node[]> make_dag(size_t num_nodes, size_t max_degree) {
std::unique_ptr<Node[]> nodes(new Node[num_nodes]);
// Make sure nodes are in clean state
for(size_t i=0; i<num_nodes; i++) {
nodes[i].idx = i;
nodes[i].name = std::to_string(i);
}
// Create a DAG by randomly insert ordered edges
for(size_t i=0; i<num_nodes; i++) {
size_t degree {0};
for(size_t j=i+1; j<num_nodes && degree < max_degree; j++) {
if(std::rand() % 2 == 1) {
nodes[i].precede(nodes[j]);
degree ++;
}
}
}
return nodes;
}

The function, `make_dag`, accepts two arguments, `num_nodes` and `max_degree`, to restrict the number of nodes in the graph and the maximum number of outgoing edges of every node.

# Static Traversal

We create a taskflow to traverse the graph using static tasks (see Static Tasking). Each task does nothing but marks `visited` to `true` and subtracts `dependents` from one, both of which are used for validation after the graph is traversed. In practice, this computation may be replaced with a heavy function.

tf::Taskflow taskflow;
tf::Executor executor;
std::unique_ptr<Node[]> nodes = make_dag(100000, 4);
std::vector<tf::Task> tasks;
// create the traversal task for each node
for(size_t i=0; i<num_nodes; ++i) {
tf::Task task = taskflow.emplace([v=&(nodes[i])](){
v->visited = true;
for(size_t j=0; j<v->successors.size(); ++j) {
v->successors[j]->dependents.fetch_sub(1);
}
}).name(nodes[i].name);
tasks.push_back(task);
}
// create the dependency between nodes on top of the graph structure
for(size_t i=0; i<num_nodes; ++i) {
for(size_t j=0; j<nodes[i].successors.size(); ++j) {
tasks[i].precede(tasks[nodes[i].successors[j]->idx]);
}
}
executor.run(taskflow).wait();
// after the graph is traversed, all nodes must be visited with no dependents
for(size_t i=0; i<num_nodes; i++) {
assert(nodes[i].visited);
assert(nodes[i].dependents == 0);
}
tf::Executor
class to create an executor
Definition executor.hpp:62
tf::Executor::run
tf::Future< void > run(Taskflow &taskflow)
runs a taskflow once
tf::FlowBuilder::emplace
Task emplace(C &&callable)
creates a static task
Definition flow_builder.hpp:1352
tf::Task
class to create a task handle over a taskflow node
Definition task.hpp:263
tf::Taskflow
class to create a taskflow object
Definition taskflow.hpp:64

The code above has two parts to construct the parallel graph traversal. First, it iterates each node and constructs a traversal task for that node. Second, it iterates each outgoing edge of a node and creates a dependency between the node and the other end (successor) of that edge. The resulting taskflow structure is topologically equivalent to the given graph.

With task parallelism, we flow computation naturally with the graph structure. The runtime autonomously distributes tasks across processor cores to obtain maximum task parallelism. You do not need to worry about details of scheduling.