cholla-hydro / cholla-hydro/cholla
Rethinking the Particle Data Structures
- Dominant language
- C++
- Stars
- 74
- Forks
- 41
- Avg merge
- 1d 17h
- Merged PRs (30d)
- 3
Description
While thinking about how to modify the particle system to better support star-particle creation, I had some thoughts on how we could potentially improve the particle system in general.
These are mostly thoughts for an "ideal world." I'm not really suggesting that anybody should spend time doing this.
1. support different particle "types": so that we could support star particles and sink particles. (Ideally with the option for them to have different particle attributes -- but that's obviously **far** less important)
2. rather than organizing particles in a giant array, it would be worth reorganizing them into "batches" (or "chunks")
- For some datatype `T`, rather than storing the values in 1 giant array, we would instead store the values in a series of chunks.
- For the sake of concreteness, a naive implementation of this might look like:
```c++
template
struct Batch{
int size;
T values[CHUNK_CAPACITY]; };
template
struct ChunkedStorage{
int num_batches;
Batch* batches;
};
```
In the above snippet, ``CHUNK_CAPACITY`` is some compile-time constant (e.g. 8, 16, 32, etc.).
The control-flow would change from
```c++
for (int i =0; i < num_particles; i++) {
// do work
}
```
to
```c++
for (int batch_ind =0; batch_ind < obj.num_batches; batch_ind++) {
for (int i =0; i < obj.num_batches[batch_ind].size; i++) {
// do work on obj.batches[batch_ind].values[i]
}
}
```
- The above snippets made a number of simplifications. We could make a bunch of optimizations[^1]
- The primary benefit is that it is much faster to remove values from this data structure (the worst-case cost is based on the max-size of a chunk) in comparison to the existing approach (the worst-case cost scales with the number of contained values). This comes up now whenever particles move between processors.
- The obvious drawback: we are introducing complexity and we slightly increase the cost to access an arbitrary element.
- It's not entirely obvious to me whether the extra complexity is worthwhile on GPUs
- I imagine that most of the semantics for adding/removing values could be modeled after an [unrolled linked list](https://en.wikipedia.org/wiki/Unrolled_linked_list)
[^1]: For example, it may be better to store batch size separately from the data in a given batch (you could do away with the `Batch` Class template and store the values directly within Batches). If we also pre-allocate the memory for the maximum allowed number of particles (which would probably be beneficial), you could allocate all of the memory for all batches in a single array (rather than storing pointers to each batch, you could then store the index of each batch).
Contributor guide
No contributing guide indexed for this repository
Research direction
No files, tests, or entry points are named. Start by locating the existing particle storage and the code that moves particles between processors, then assess the proposed particle types and chunked storage against CPU and GPU costs. Done would require an agreed, scoped design rather than the open-ended ideas described here.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- hpc, performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 20/100