Adjacency lista in jCUDA

[Luis]

Hello,

I have a problem in creating a struct using jcuda, someone could give me a hand?

Thank you in advance.

[Luis]

After making the post I noticed a similar post in http://forum.byte-welt.de/showthread.php?t=2915 but relevant
to comments posted by Marco13, but have been reading some articles that the authors cite the creation of these
structure within the CUDA. If you are interested I can even send them the paper.

And we can think together in order to define these structures, what do you think?

[Marco13]

Hello Luis,

As menitioned in the other thread, structs are not trivial, considering the possible differences between host and device and the resulting alignment issues for 32/64 bit systems. But it's probably time to get the discussion started and focus on possible solutions. I'll collect my thoughts, and tomorrow I'll open a dedicated thread for this topic. I'd be happy to discuss about your ideas then

bye
Marco

[Luis]

Hello Marco,

Glad to be an interesting topic, I want to address an adjacency list, need for such a Struct to make notes for the vertices that has a connection with the vertex.

As here, is in Portuguese has more structures may serve as a thought: http://www.lcad.icmc.usp.br/~nonato/...os/node76.html.

Based on Structs we will discuss, with your help I can start thinking in that structure, today my graph is in java so it is needed, passes it to the GPU via jCUDA.

Thanks again for the help.

[Luis]

Hi Marco,

I've been doing some consideration, I've been thinking about it, the mapping of C struct to Java using JNI, i want to
ask if there is any possibility how to map C struct to Java using JNI. I need to move some data provided in struct
application to Java using JNI. Is there some JNI predefined type which i could use mapping for that?

[Marco13]

Hello Luis

The most difficult aspect about Adjacency Lists is, that each struct contains pointers. Supporting structs in general may be challenging. But if you have a structure on Java side like

class Node
{
    public int index;
    public Node next;
}

and want to use such a struct on the device, you have to take care that the "next" pointer must always be a device pointer. That means that creating the Graph (which is represented by this adjacency list) may not be done by simply copying or mapping structs from the host to the device. Instead, you have to build the whole graph on the device (otherwise the pointers will not really point to the "next" Nodes).

In fact, I think that specifically for adjacency lists, you might even consider replacing the pointers by indices, and storing all nodes in arrays. (You should also consider that traversing a Graph using adjacency lists with a GPU might have disadvantages, since you are "randomly" accessing elements of the global memory, so there is practically no memory coalescing).

However, I created a thread for the discussion about struct support, maybe we can find a general solution that works for arbitrary structs, and, if possible, even for structs creating pointers to other structs.

bye
Marco

[Luis]

Yeah I was thinking something similar as it had once mounted a structure like this for an adjacency list for java.

I'll put the diagram representing my graph to give you an idea.

[Luis]

Also I'm reading a paper in which the author has built a structure using the native CUDA C, but may help us think, I have been relying on it to be well optimized.

I'll take a look at the new topic as well and see if something new emerges.

[Marco13]

Hi

Concerning the first diagram: You'll have to think about an appropriate data structure for your problem anyhow. You cannot port something like a "Vector<Edge>" to CUDA. Most likely it will be possible to boil it down to a "minimalistic" data structure that is appropriate for the algorithm that you want to run on the graph. I think that the most straighforward representation of a graph (as an adjacency list) on the GPU could use indexes. And I assume that this was also meant with the second image: When that you know the maximum number of edges that any vertex has, you could probably represent the adjacency list as something like

struct Node
{
    int index;
 
    // An array containing the indices of the adjacent edges. 
    // Each Node has such a pointer, and each has the size
    // of "maximum number of edges that any node has"
    int *edgeIndices;
    int numberOfEdges;
 
    // All the fields from GraphNode and NodeRecord that 
    // are required for the specific algorithm    
    int posX;
    ...
}
 
struct Edge
{
    int index;
    int vertexIndex0;
    int vertexIndex1;
    float cost;
}

But you should carefully think about that, because there are most likely some representations of graphs that are better suited for massively parallel programming on the GPU. For example: If you have a complete graph (every vertex connected to every other vertex) then the "edgeIndices" of each Node togeher simply form an adjacency matrix, and I assume that for many algorithms (on dense graphs) an adjacency matrix may be much faster than an adjacency list - at least, on the GPU.

bye

[Luis]

Dear Marco13,

Trying to answer their questions, my number is at least 50 vertices and edges in number 6 for each vertex. I think I would rather a complete graph (Every Every Other vertex connected to vertex), this means that each vertex has a single path (edge) that connects to another vertex. This will facilitate me in that point after the processing to be performed on the GPU can only return the vertices of the path calculated.

The initial idea that I would represent the shape of the second diagram, by two vectors, two vectors of struct's.

typedef struct no;
typedef struct heads;
 
struct nos{
    int VERTEX;
    no *NEXT;
};
 
struct heads{
    int FLAG;
    no *ADJ;
};
 
/* Make an allocation in this way, maybe! */
 
G = (heads *) malloc(NUMVERT*sizeof(head));

cheers