graphit-dsl / graphit Goto Github PK

Very nice project as well as your paper.

I noticed the proposed algorithms are with number variables (int, float, double, vector<..>).
I was wondering if other variables like string could be added.

For example, to implement label propagation algorithm,
we may want:
const label: vector{Vertex}(string)

Is that possible and how to initialized the label variable?
Any comments would be appreciated. Thanks.

Hi there,

When I was trying to run the C++ test suite, infinite runtime occurs at the SetCover_test in RumtimeLibTest. The last while loop in this test is causing this issue, which is around line 538. Since I am able to pass the rest of tests, I guess something unique in this test was the reason. Perhaps this test use some technique which is not supported by the M1 chip?

Thank you for your feedback.

Hi Yunming,
I've been testing the sssp implementation of Ligra and Galois on a 10-thread machine and a 24-thread machine. It shows that Bellman-ford algorithm in Ligra takes more than 200 seconds on both machines for solving a single SSSP query on USA road network.
The results of Delta-stepping on Galois is roughly 2 to 3 seconds.
As you mentioned in the Paper, "We run Galois with the Bellman-Ford algorithm so that the algorithms are the same across systems." would like to share how is the implementation you used for testing GraphIt with Ligra and Galois? I suppose it would be similar to Ligra that takes about hundreds of seconds?

Hello,
I am trying to install Graphit but I got several errors during 'test_with_schedules.py' tests.
From starting the error at "graphitc.py", line 76, "CalledProcessError", a tons of errors is printed out.
I guess it would be invoked due to specifying paths.
Could you help me to solve the issue?

Thank you,

I noticed within tc.gt, if you call
src_nghs.getVertexSetSize()
this will always be 0, even though the true size is edges.getOutDegree(src), I noticed similar behavior on a file I'm working on right now. Is the size of src_nghs actually 0, or is it an issue w. getVertexSetSize()?

Hi,
I generated a test.cpp using the command: python graphitc.py -a ../../test/input/pagerank_with_filename_arg.gt -f ../../test/input_with_schedules/pagerank_pull_parallel.gt -o test.cpp
I was able to compile and run the same using OpenMP flags of varying thread count from 1 to 24. The error value(part of pagerank algorithm) it prints is the same for varying numbers of threads for a given input graph.

Similarly I generated another test.cpp using the command: python graphitc.py -a ../../test/input/pagerank_with_filename_arg.gt -f ../../test/input_with_schedules/pagerank_push_parallel.gt -o test.cpp
The schedule file is push instead of pull here. I was able to compile and run using the OpenMP flags of varying thread count 1 to 24. The error value it prints was the same for the given input graph with number of threads = 1. But with an increase in the thread count the error value is changing for push-based scheduling which should not be the case, right?

Kindly help in resolving the issue. Thank you

I am trying to implement this algorithm: https://arxiv.org/pdf/1209.1688.pdf . In section 2.2 is suggests "Finally, to ensure that each row-sum is exactly one, we add a self-loop to each node".

Essentially I need to add an edge. I can't find a function to do this in examples/source/documentation.

My current idea is to either 1) include |V| self edges from python wrapper script, modify them in graphit 2) make a custom cpp function that adds a self edge somehow (would like guidance on this), 3) run the getOutDegrees() in one graphit script, then use those values from python to construct self edges, then feed them to another graphit script. 4) calculate getOutDegrees() in python, then put the self edges into the first script.

Would like some guidance on this.. tysm for very cool project.

Ideally,
const vertexArray: vector{Vertex}(int) = 0; should initialize a vector with size of number of vertices. But it initializes to a vector of size 0. We had to add this to make it work:
const vertices : vertexset{Vertex} = edges.getVertices();
const vertexArray: vector{Vertex}(int) = 0;

Currently the new operator for vectors works fine with Vertex type but not for a constant size vector.

For example the following works,

var vec: vector{Vertex}(int) = new vector{Vertex}(int)();

But this doesn't work -

var vec: vector[10](int) = new vector[10](int)();

and returns the error -

Error: expected '{' but got '[', at 1

Not sure if it is allowed, but when I do #s1# some statement in a global scope, Scanner thinks there is a comma before and after s1, thus the parser errors out. But this seems to be working fine if the scheduling symbol is inside a function

Need to make sure that a global vertex can be specified for vertex queries.

First of all Thank you for this impressive software !!
But I won't use it until i've found a benhcmark comparison against https://developer.nvidia.com/nvgraph on a modern gpu.
A comparison against AMD gpu would be Nice too https://www.google.com/search?q=AMD+graph+algorithms+opencl&client=firefox-b&oq=AMD+graph+algorithms+opencl&gs_l=mobile-heirloom-serp.3..30i10.17126.20484.0.20921.13.12.1.0.0.1.480.2284.4j5j0j2j1.12.0....0...1c.1j4.34.mobile-heirloom-serp..7.6.593.WaazgBmCg_E
I had read that FPGAs are the fastest at graph analytics until graph processors become a reality (aren't they already ? https://www.google.com/search?q=graph+processor&client=firefox-b&oq=graph+processor&gs_l=mobile-heirloom-serp.3...5156.5156.0.5686.1.1.0.0.0.0.0.0..0.0....0...1c.1j4.34.mobile-heirloom-serp..1.0.0.QKVdUYR0fFo but I understanding that it is difficult to find such accelerators for testing)

And if GPUs or HSA are faster than cpus for graph analytics, you could think about the possibility of porting the graphit to gpu backends, i've heard it became « relatively » easy to make since gpu llvm backends are mature and SPIR-V is a thing.

as far as I can tell, edges with this property evaporate when they get loaded

I'm trying to implement all pairs shortest path using GraphIt and I'm having trouble.

I'd like to have a 2D vector distance that for any two vertices u and v distance[u][v] holds a an integer. I'd like this vector to be accessible from within an apply and filter function.

GraphIt doesn't seem to have support for this feature. Can this be supported?
Thank you.

From your paper six of the seven algorithms are included in the apps directory but Betweenness Centrality looks to be missing. Is this available for sharing? Thanks!

Hello @AjayBrahmakshatriya

I am trying to run bfs_verifier on included sample graph 4_sym.el. This gives a crash error.

$ cd build/bin
$ ./bfs_verifier -f ../../test/graphs/4_sym.el 
# running BFS verifier 
# Segmentation fault (core dumped)

I was trying it on web-Stanford graph, both in edge list (.el) and matrix market (.mtx) formats. graphit_test passes all tests.

Hi!
I am a student who is learning to use graphit. I noticed that the link to ICPC, the compiler that supports Cilk and OpenMP, had been changed to a download link to OneAPI. And the download link of ICPC seems to be hard to find. Could you send me a copy if it is convenient for you? Also, does Graphit support OneAPI? and is it possible to install Cilk and OpenMP separately?