Accessing Properties of Vertices with Null Out-Degree

[pf-un]

Hi everyone.

I'm wondering about accessing the property of vertices with out-degree equal to 0. I understand these are somehow filtered out of certain computations since they generate no updates, but they should still receive updates so I'd like to access their property after some number of supersteps.

I would also appreciate an explanation on the various MEM_ID pointers.

[HongshiTan]

We only consider the directed graph, and the edge for receive update should be represented in the input edge list. For example, if vertex A wants to receive an update from vertex B, there should be an edge B A in the edge list.

MEM_ID is our abstraction and unification of device memory (FPGA) and host memory (CPU), it aims to enable the expansion of multiple memory channels (Multi SLRs) and unified operation. For a different type of data required by the accelerator, a unique ID is assigned, and for some hierarchical memory structures, they will be assigned with a range of indexes and some reservation for future expansion.

[pf-un]

Thanks for the explanation! I think I'm still a bit confused, though.

Please consider the following graph 1->2->0:

1 2
2 0

with prop(0) = 1, prop(1) = 2, prop(2) = 3

So, as you mentioned, 0 should receive an update from 2 each superstep; meaning its property might change. However, 0 has out-degree 0, so it gets elided. From my experience, accessing both acceleratorQueryProperty() and MEM_ID_PUSHIN_PROP_MAPPED will give [2, 3, 0], so the property of vertex 0 just vanishes even though it could have been updated.

How can I access the vertex property of 0? Is there a specific MEM_ID pointer, or some other mechanism, that gives me the properrty of all vertices, after updates (so not MEM_ID_PUSHIN_PROP)?

[HongshiTan]

Hi pfsi,

Apologies for the delayed response.

You need to use the he_mem with MEM_ID_VERTEX_INDEX_MAP to access remapped index of the vertex, then use the remapped index to access the property. For example (pseudo code):

// get the compressed vertex map
vertexMap = get_host_mem_pointer(MEM_ID_VERTEX_INDEX_MAP);
// the property array
vertexPushinProp = get_host_mem_pointer(MEM_ID_PUSHIN_PROP);
// access the property of the 3rd vertex
vertexPushinProp[vertexMap[2]] 

In your example, the vertexMap should be like this [0, 0, 1]

[pf-un]

I see. I'm having to recompile to verify this, so I'll only be able to reply tomorrow. However, I've checked MEM_ID_PUSHIN_PROP. It seems to work like an input-only buffer. In other words, it doesn't seem to update after running supersteps. Is this wrong?

[HongshiTan]

Hi pfsi,

you may use acceleratorQueryProperty to access the property after running supersteps. Note that we have a ping-pong mechanism inside, the input argument step can be 0 or 1. The partitioning related code is quite tricky, we will try to refactor it soon or later.

[pf-un]

Hongshi, I was just about to start a new issue regarding the verification I've mentioned above. If you could take a look, I'd appreciate it.

[HongshiTan]

I can have a check this weekend, could you share with me the xclbin file you generated?

[pf-un]

So sorry, I ended up deleting it (limited disk space!). I'll recompile and share it in the other issue.

[HongshiTan]

Will provide an API to access the property as you expected.

[pf-un]

Thank you!

Meanwhile, I've prepared an example application using SSSP showing this and another issue which I believe is likely related to partitioning. Host and FPGA binaries are included. Please check it out and let me know if you need any other logs. The README has information on the changes I've made and the datasets I've added.

• So, regarding the first issue (vertices with null out-degree having null properties), please execute using the comb.txt dataset. Notice how every odd vertex is elided, making the output property vector equivalent to an "arrow" dataset with half the number of nodes (the even ones). The number of null properties is equal to the number of vertices with null out-degree, plus one (the source vertex). I would expect the output property vector to follow P[i] = (i+i%2)/2 <=> P = [0, 1, 1, 2, 2, 3, 3, ...], as mentioned in the README; instead, it's [0, 1, 2, 3, ...] (which ignores the "teeth" of the comb).

• Regarding the second issue, which seems to be related to partitioning, please execute using the arrow.txt dataset. You may redirect stderr to /dev/null or something to get at the initial log lines, one of which reads "[PART] src. vertex from 6144 to 8191". I am not 100% clear on the significance of this last value, so I'll call it v. Notice how the vertex frontier, which starts at 0 and should end at 9999, stops at v+1 (so the last valid property is at v; this also holds for the "comb" dataset). I would expect the output property vector to follow P[i] = i.

• Also notice the first issue also shows in the "arrow" dataset: vertex 9999 has its property set to 0.

I don't know how much of this is fixed by accessing the new API you've mentioned, but I'd really appreciate it if you'd continue working with me to try and get this up and running!