Hello everyone,
I’m a newbie in CUDA, just wonder if CUDA data model is
suitable to solve constraint satisfaction problem (CSP).
Thank you in advance.
Perigee
It should work well theoretically. Without getting into specific algorithms, the work that needs to be done is to check many possible combinations of values that lie within the variables’ domains and that satisfy a set of conditions. You can check the combinations in parallel easily, say let each thread check one combination (just one way to do it, not necessarily the best). Conditions are usually defined more or less globally, ie. they are not per-thread data and are read only (you don’t modify constraints while you check a combination) so they’re a candidate to go to constant memory, for example. If they’re defined functionally, even better - computation is often cheaper than memory access.
Good thing about CSPs is that in their basic formulation there’s not really much data that needs to be read during evaluation of potential solutions. Of course whether that is true or whether you actually do need to look things up in memory is dependent on the form of your constraints and implementation.
You’ll probably need to come up with a kind of algorithm that maps well to the hardware. Classic CSP algorithms are usually sequential and might need some adaptation to work on a massively parallel architecture. It shouldn’t be that hard though.