Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Change memory of graphs from vector<vector<node_t>> to views on flat memory CSR #18

Open
jamesavery opened this issue Dec 26, 2023 · 2 comments
Assignees

Comments

@jamesavery
Copy link
Owner

jamesavery commented Dec 26, 2023

Major rewrite.

Want to use the fullerene graph library together with SYCL code and full isomer-space code / collections of graphs, allocated on flat memory. Three issues: 1) vector<vector<node_t>> forces many allocations/deallocations, becomes a problem when we're aiming at nanosecond-range processing per graph; 2) std::vector does not allow wrapping existing memory (allocated from outside), so we can't just overlay the functionality on contiguous memory allocated for graph collections such as the IsomerBatches; and 3) code using any heap allocated memory cannot be used in GPU kernels, so std::vector needs to be culled completely also for that reason.

Want:

  1. Graph classes should be light-weight views on flat memory that simply provide functionality.
  2. But it should still be easy to "just get a graph object", i.e. since the various graph classes can no longer allocate memory, we need to make a convenient separate collection of allocators that make allocation and object life-time simple and feel natural.
  3. In order to share the C++ code with GPU kernels, we must also hunt down and kill all in-library dynamic memory allocation, even for temporaries.

Pt. (1) will be implemented using std::span, forcing shift to C++20. Hence, from now on, C++20 features will become fair game.

@jamesavery
Copy link
Owner Author

jamesavery commented Dec 26, 2023

The first iteration will simple change neighbours_t from vector<vector<node_t>> to a flat-memory boolean sparse matrix CSR-format.

I will support both

  1. The format currently used in the GPU code: Rectangular sparse matrix with memory N*Dmax node_ts per graph, where Dmax is the maximal degree of any vertex, and row u starts at offset u*Dmax. Empty arcs have value EMPTY_NODE=-1.
  2. A variant of Compressed Sparse Row format congruent with (1).

This is done using the following data:

  1. span<node_t> values of length M=N*Dmax if using the rectangular format (1), and of length M=total number of arcs if using CSR (2).
  2. span<node_t> row_start of length N with offsets into memory where each row starts. For the rectangular format, we have row_start[u] = u*Dmax.
  3. span<nnz_t> row_nnz of length N: the row size (number of actual nonzero elements per row / number of actual arcs incident to each vertex). This is what makes it possible to support both Formats 1 and 2, and what allows us to have dynamic graphs in which edges can be inserted and removed, as it makes it possible to differentiate between the neighbour capacity and the actual number of neighbours for each row. For cubic graphs, row_nnz[u] = 3, for fullerene duals row_nnz[u] = 5 or row_nnz[u] = 6. For CSR, we have row_nnz[u] = row_start[u+1]-row_start[u]. The type nnz_t = uint8_t for all fullerene/fulleroid purposes, and could even safely be reduced to 4 bits, so I have deemed that the extra memory is offset by the added flexibility.

Methods will be added to convert between rectangular-sparse and CSR.

jamesavery added a commit that referenced this issue Dec 26, 2023
TODO: How to make sensible constructors, when not allowed to allocate memory?
@jamesavery
Copy link
Owner Author

jamesavery commented Dec 27, 2023

Obstacle to solve: All current constructors (from spirals, transforms, etc.) rely on being able to allocate memory.

Idea for solving this without introducing a huge cascade of rewriting:

  1. Add new constructors matching the old ones, but which take pre-allocated memory as extra arguments.
  2. Move all old constructors to Allocators namespace with the semantics: allocate memory, apply new constructors on said memory.

jamesavery added a commit that referenced this issue Dec 27, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant