Quote from: bisovskiy on September 02, 2025, 02:17:59 PM

Quote from: RetiredCoder on June 25, 1975, 03:30:16 PM

there is one more problem in original JLP GPU code: every GPU thread processes A LOT of kangs. It will cause an issue with DPs for high-number puzzles like #130. It's obvious but it seems nobody understands it. Don't you see it too?

Yes, thanks. I noticed that as well. Too bad it’s impossible to parallelize a sequential process. For now, it looks like any restart can affect finding a collision, since we can only detect it on the second occurrence of the same DP along a trajectory — which takes time. I’ve been thinking about this in two ways: first, adding progress checkpoints and setting an acceptable DP threshold; second, deliberately forcing trajectories to reset right after a DP is found. That way, we slightly improve the speed of reaching a DP — though not to be confused with overall performance.

The DPs and the kang's position are already the checkpoints. RC's rightfully outlined that having too many kangs (which is JLP's strategy) increases the DP overhead, so much that it can easily outmatch the core complexity. When dealing with tens or hundreds of GPUs, and a high DP (which is needed to lower storage requirements) that would be a very, very stupid scenario to end up in.

I don't get why you would reset the trajectory once you have a DP. If you read the analysis, the whole argument is that continuing the walks increases the chances of an eventual collision. And this does not depend at all on whether a DP was found or not.

kTimesG

Posts

Merits