cholla-hydro / cholla-hydro/cholla

Rethinking the Particle Data Structures

Open
#413 1 comment 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.