« first day  last day (15 days later) » 

01:08
1
Q: What structure to use for large 2-D euclidean grid with multithreaded access?

Edward PetersI've got a simulation I'm playing with, in which I have a large (1024x1024 or bigger) euclidean space. Each square of this space can hold various data, of fixed but not totally trivial size. (Below is an example square; while it is very subject to change, I don't expect it to grow more by a fact...

Why the Mutex jammed in the middle? This is likely something you'll want to dump on the GPU eventually, so think about some simple structure. In this case: A 2D texture.
"with a thread handling a single point at a time" - This is a design decision I'd challenge. You most likely want to space-partition your entire grid, so that you handle all points within a region at once by the same thread. You don't even need a mutex for that, you can split_at_mut() them onto different threads dynamically. Or use rayon's parallel iterators to iterate over the vector.
And as @tadman already pointed out, approaching the problem from this side will make it easier to move it to the GPU later.
@tadman My reasoning for the mutex being in the middle was that if it were at the top level, only one thread would be able to do anything at once, but if it were on every element, that would both increase the size and add a ton of overhead of re-acquiring locks when no one is competing.
@EdwardPeters Don't use a mutex at all; if partitioned properly, it's not necessary. With tools like std::thread::scope or Rayon it's possible to distribute your data on threads without mutexes.
If space allows it, you could use double buffering: Duplicate your entire grid, and alternate between them from step to step. Then have one thread compute the new state of every region. If the new state of a region requires data from a different region, no problem: The previous time step is available for all threads, due to being immutable. That's most likely how a GPGPU implementation would look like, as well.
@Finomnis So the reason I don't "handle all points in in a region at once" is that by the current rules of the simulation, there's nothing to do with those points. I edited the question to hopefully make that clearer. To give a bit more detail, in the diagram shown, the red line is a particle that moves around the grid; if certain conditions are met it sticks, thus growing the fern patterns.
01:08
@EdwardPeters Then partition those particles in space, and handle those in regions. Migrate them between regions if they drift from one region to another. You need some kind of partitioning if you want to parallelize it efficiently. Of course you could also simply partition the list of particles, but then you would have to lock the cells again. The goal is to avoid locking and breaking the problem down into multiple smaller problems. And space partitioning is ideal for that.
@Finomnis If I'm understanding you, I think everything you're saying is probably good answers for the bonus question.. I'm trying to think of how it would work with the "small number of drifting particles" thing I've got now.
@EdwardPeters "the threads should be able to operate atomically on the 3x3 space centered on their particle's current position" - what if two particles are close to each other? Which one updates first? Why do you even need partitions, if you operate on particles alone?
@Finomnis If two particles are close to each other, one will get to update, and the other will see the result of that update - I don't care what order it happens in. What I want to avoid is, for instance, both of them eating the same bit of food at once, or trying to grow on the same empty square. I'm not clear on the second question - the particles drive the behavior, but they operate on the grid (reading and writing to it). The partitioning is there so that different particles can operate in different regions in parallel.
Different question: if you only use a hand full of particles, why concern yourself with multithreading? It's most likely faster if updated by a single thread, and you don't need to concern yourself with locking and similar.
So I'd argue: don't do multithreading. Until you have a large enough number of particles that it's worth doing space-partitioning; then partition your space and treat each section again as a single-threaded grid.
@Finomnis I should review the tests, but I have checked and found that the threading is speeding it up (at least, increasing the number of threads does greatly increase the performance). I don't see why it would be faster with a single thread, unless locking was taking up like 7/8 of my time?
@Finomnis " don't do multithreading. Until you have a large enough number of particles that it's worth doing space-partitioning; then partition your space and treat each section again as a single-threaded grid." Sorry, is that not still multithreading? You'd have one thread per section, right?
01:08
@EdwardPeters I mean, don't do multithreading until you have a large enough number of particles to partition by space; do not partition by particle. Although that's of course a gut feeling, benchmarking should bring more appropriate answers.
"I don't see why it would be faster with a single thread, unless locking was taking up like 7/8 of my time?" - If that's the case, why ask the question here in the first place? If the overhead of locking is irrelevant in your case, why not just keep your current solution?
I feel like this question is too opinion-based for Stackoverflow; I'd vote to close it. It might be better suited for codereview.
@Finomnis Well there's a big difference between "The overhead of locking is costly and I'd like to reduce it" and "The overhead of locking is so prohibitive that I don't benefit from having multiple processors running at once". If I have 8 processors and locking is taking up 3/4 of my time, that should still be twice as fast as an unthreaded solution, right?
Jmb
Jmb
Why not have a Mutex for each square? Then each thread only needs to hold the 9 mutexes that concern it.
@EdwardPeters Might be ... but threading is more complicated than that, there is a lot of things that play a role, like cache locality and similar
@Finomnis I'd like to argue that the original question of "What structure is efficient" is answerable - I do think you and I have gotten lost in the weeds a bit, regarding my implementation. But even so I think you're giving me valuable ideas, I'm just not understanding how the space-partioned model would work in a few regards (specifically, communicating that points have moved between regions, or what happens with points on the boundary needing to see both regions)
@Jmb That will introduce a huge deadlock potential if not done correctly, but in principle, you are correct.
01:08
@Jmb My first thought is "How big is a mutex?" If it's big, that's going to make cache locality a lot worse. My model also allows for the possibility of a particle grabbing the lock for its region, then using it for a while (until it reaches a boundary, potentially) - that could be one lock acquisition per hundreds of steps, rather than 9 per step.
@EdwardPeters This last answer kind of already explains how to space partition: Now imagine two particles are in the region at once. You could lock that region, update both particles in series by the same thread and then unlock that region again. Your current approach has the same problems as a full space partitioning: If you lock it for hundrets of steps, how do you know that another particle might have entered the region?
@Finomnis Okay, so thread 1 locks region A, and updates for particles P1 and P2... after some number of timesteps P2 moves to region B. Thread 1 then locks region B, adds P2 to the particles listed there, then continues on with P1? (Presumably occasionally yielding its lock to allow new particles to be added?) Do I have that right? In my solution the entering thread will be left waiting until the first particle leaves the region, resolves, or "pauses" itself to voluntarily yield the thread... that wait can be significant but if there are many more regions than threads, it should be fine.
@EdwardPeters Your question is non-trivial, how to efficiently space-partition and border exchange a particle simulation is a question a lot of papers were already written about. If you do it right, you don't need locks at all. But I think this is a vary complex topic for a stackoverflow post.
@tadman I know nothing about GPU programming, but this is a good candidate for me to learn. That said, what structure would represent a 2d texture? Quick googling shows me a bunch of very image-specific stuff that does not look like what I want...
@EdwardPeters Maybe trying to understand this crate is a good starting point: github.com/timokoesters/nbodysim
01:08
An image texture is just 2D data at the end of the day. It can be integer or float. It can be greyscale, RGB, RGBA, or sometimes other forms, but really this is just either 1, 3, or 4 components to each "pixel" or cell. You can use that to represent things other than image data, and you can manipulate these with simple GPU kernel code. For anything involving lots and lots of parallel processing, like you have here, doing it in the GPU is really the only way to get reasonable performance.
@tadman So I'm probably getting ahead of myself, but in terms of implementation, does this mean Vec<(usize, usize, usize, usize)>? Something like docs.rs/macroquad/0.3.7/macroquad/texture/struct.Texture2D.h‌​tml , with an interface clearly intended for actual visuals? I know a smidge of the theory, but nothing about the actual atoms of putting it to practice.
It doesn't mean creating a Vec at all, GPU buffers are allocated differently, but internally the structure will be a lot like that, except as i32 most likely. You could try using something like OpenCL to get a taste of how to manipulate data on the GPU, or CUDA if that's more your style.

« first day  last day (15 days later) »