GraphIt is a programming language created in 2017.
| #751on PLDB | 6Years Old | 397Users |
| 0Books | 0Papers |
GraphIt is a new DSL for graph computations that generates fast implementations for algorithms with different performance characteristics running on graphs with different sizes and structures. GraphIt separates what is computed (algorithm) from how it is computed (schedule). Programmers specify the algorithm using an algorithm language, and performance optimizations are specified using a separate scheduling language. The scheduling language enables programmers to easily search through this complicated tradeoff space by composing together a large set of edge traversal and vertex data layout optimizations.
element Vertex end
element Edge end
const edges : edgeset{Edge}(Vertex,Vertex) = load (argv[1]);
const vertices : vertexset{Vertex} = edges.getVertices();
const old_rank : vector{Vertex}(double) = 1.0/vertices.size();
const new_rank : vector{Vertex}(double) = 0.0;
const out_degree : vector {Vertex}(int) = edges.getOutDegrees();
const contrib : vector{Vertex}(double) = 0.0;
const error : vector{Vertex}(double) = 0.0;
const damp : double = 0.85;
const beta_score : double = (1.0 - damp) / vertices.size();
func computeContrib(v : Vertex)
contrib[v] = old_rank[v] / out_degree[v];
end
func updateEdge(src : Vertex, dst : Vertex)
new_rank[dst] += contrib[src];
end
func updateVertex(v : Vertex)
var old_score : double = old_rank[v];
new_rank[v] = beta_score + damp*(new_rank[v]);
error[v] = fabs(new_rank[v] - old_rank[v]);
old_rank[v] = new_rank[v];
new_rank[v] = 0.0;
end
func printRank(v : Vertex)
print old_rank[v];
end
func reset(v: Vertex)
old_rank[v] = 1.0/vertices.size();
new_rank[v] = 0.0;
end
func main()
for trail in 0:10
startTimer();
vertices.apply(reset);
for i in 0:20
vertices.apply(computeContrib);
#s1# edges.apply(updateEdge);
vertices.apply(updateVertex);
end
var elapsed_time : double = stopTimer();
print "elapsed time: ";
print elapsed_time;
end
end
% specify schedules here or use a separate schedule file| title | date | score | comments |
|---|---|---|---|
| GraphIt: A High-Performance Domain-Specific Language for Graph Analytics | 11/21/2018 | 34 | 2 |