Lack of hardware accelerators for NP/PSPACE decision problems?
Posted by JakeGinesin@reddit | hardware | View on Reddit | 11 comments
With lots of excitement around hardware acceleration for common algorithms in machine learning (a la tensor processing units), I'm very curious why there's virtually no attention around hardware acceleration for NP/PSPACE decision problems. Is there some sort of fundamental issue underpinning SAT algorithms, model checking algorithms, etc explaining why they're less applicable to dedicated hardware accelerators?
erik@reddit
I'm speculating a little bit here, but:
The sort of stuff that is hardware accelerated like scientific computing, graphics rendering, tensor/AI processing, crypto, etc all tend to be:
Which means you can build hardware accelerators optimized for those traits and gain a big advantage over a CPU.
Whereas algorithms for NP-hard problems like SAT tend to be:
Which means it's not obvious how specialized hardware could outperform existing CPUs.
Another factor is economics, there probably isn't really demand for solving SAT the way there has always been demand for rendering graphics.
eclab@reddit
The most basic approach to solve any NP-hard problem is extremely parallelisable (checking each possible solution). The problem is that the number of possible solutions grows exponentially with the input size, so you'd need impossibly many parallel cores to make solutions tractable.
BookPlacementProblem@reddit
That sounds like something to be thrown at a quantum computer, once they work the butterflies out?
eclab@reddit
No, they are unlikely to have a substantial speed-up on NP-hard problems generally. This is the BQP vs NP problem. Quantum computers can speed up some tasks like factoring, which are in NP (and probably not in P), but factoring is not NP-hard.
BookPlacementProblem@reddit
Thanks, good to ~~know~~ sort-of understand. My math skills can be summed as "enough linear algebra to put triangles on a screen".
ET3D@reddit
It looks like some people didn't like my answer, even though I think it was more on point than others, but granted it was short and didn't provide details, so I figure I could add some.
Creating an ASIC to accelerate a specific algorithm is a lot of work and has a high cost. That's why it's rarely done. The only reason any algorithm ever gets acceleration is if it's so common that many millions of those accelerators are likely to be sold. It has to be something that: a) is well define; b) can gain significantly from being hardcoded; c) is so common, or expected to be so common, that it will make money.
NP/PSPACE algorithms fail mainly (c) and (b). The normal solution to them is to run an alternative algorithm, either stochastic or ML, which is P. The problem is that an NP algorithm, as is, is exponential (until proven otherwise). Even if you improve its constant considerably, you won't be able to significantly change how quickly it runs. If you use an alternate algorithm which is polynomial, you will gain a lot more than hardware accelerating the original algorithm. As a result, it's not likely that there will ever be actual demand to accelerate the original algorithms.
That is not to say that algorithms can gain any acceleration. Certainly GPUs are fine for accelerating many algorithms, including NP ones. However, specialised ASICs for them are unlikely to happen, because they're not worth the effort.
randomkidlol@reddit
i assume its because NP/P decision problems are used as part of something larger rather than the need to solve these problems on its own in vacuum. so even if you accelerate the solutions for these, the results still have to be interpreted/processed by something else which leads you run into another bottleneck.
also there are approximation algorithms that give "good enough" solutions to these problems in polynomial time. the need to compute the definitive correct answer but spend exponential time is rare.
last_useful_man@reddit
I don’t think the translation is the hard part, which is why you translate in the first place.
last_useful_man@reddit
Well, I think they can be parallelized, but in that case you really just want rafts or maybe roomfuls of cheap CPUs. But NP, with its exponential Big O, outstrips even that. I think those are either quantum or, just by their nature intractable.
I don’t claim to be an expert, just dumping loose thoughts.
ET3D@reddit
Because there's not enough market.
AutoModerator@reddit
Hello! It looks like this might be a question or a request for help that violates our rules on /r/hardware. If your post is about a computer build or tech support, please delete this post and resubmit it to /r/buildapc or /r/techsupport. If not please click report on this comment and the moderators will take a look. Thanks!
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.