CODEWITHSUNDEEP
c++calgorithmlanguage-agnosticcpu-cache
MaiaVictor
MaiaVictor

Reputation: 53027

How to store graphs in order to maximize locality for graph-reduction algorithms?

I'm implementing an algorithm based on graph-reduction rules. This video explains the algorithm better than words could, but, for completion's sake, here's a quick summary:

The algorithm operates in a graph where every node has 3 edges, one of which is the "main" one. When main edges intersect, a node is said to be active and a reduction rule is applied. It is also worth noting that, when two nodes interact, it is very likely that another node very close to them will become active.

I'm currently storing this graph with no sense of locality whatsoever: I just append new nodes to a buffer. This is the code for the naive allocation strategy I'm using, prototyped in JavaScript:

function Node(type,tag){
    var idx = garbage.pop() || memory.length;
    memory[idx+0] = type;      // Node type (used on readback)
    memory[idx+1] = 0;         // Port 0 target port
    memory[idx+2] = 0;         // Port 1 target port
    memory[idx+3] = 0;         // Port 2 target port
    memory[idx+4] = 0;         // Port 0 target node
    memory[idx+5] = 0;         // Port 1 target node
    memory[idx+6] = 0;         // Port 2 target node
    memory[idx+7] = ++next_id; // Unique id
    memory[idx+8] = tag;       // Tag (used to decide which reduction rule apply)
    return idx;
};

What is a superior way to organize this graph in memory in order to maximize locality and cache-efficiency for that kind of graph algorithm?

Upvotes: 2

Views: 325

Answers (1)

vdolez
vdolez

Reputation: 1118

I only know of two ways to "store" a graph. By "storing" I mean implementing.

Either the edges are stored in a linked-list for each node, with all the benefits from it : adding and removing an edge is fast, but finding one is long.

Either the edges are stored in a matrix of nodes and the value of Array[node1][node2] is the weight of the edge. Adding and removing a node is long, but finding a node or an edge is fast.

With the linked-list method, you store only what exists, with the matrix method, you store every edge even if it does not exist, you have to provide a value for it.

Upvotes: -1

Related Questions