3 ms·

I've actually been working on a personal project using asynchronous ring oscillators on FPGAs to perform meaningful computation. If you make the oscillators int

I've actually been working on a personal project using asynchronous ring oscillators on FPGAs to perform meaningful computation. If you make the oscillators interact in the right way, you can leverage them to solve certain graph problems! Once I finish the write-up I'm planning on posting it on HN :) https://github.com/zbelateche/digial-ising https://github.com/zbelateche/digial-ising

fpgamlirfanboy 3y ago
I promise I'm not trying to rain on your parade, and I blame the academics for this, but: 1. NP-complete problems are (today) global search problems (3-SAT algos search for a satisfying assignment...); 2. Combinatorial search spaces are not only non-convex, they don't have gradients (sub-gradients don't count) and even if they did, without convexity, it's still hopeless. Thus, you cannot (today) appreciably parallelize NP-complete algos, you can only draw more lottery tickets (for where to seed your search), i.e., constant factor improvement. I'm just putting this out there in case someone gets tantalized by the "fancy math/physics/fpga thing solves NP-complete problems" hook. Yes it can but no better than your computer (despite what paper authors claim in order to get published). To wit: if this were a compelling solution to NP-complete problems it would either a) already be a proof that NP=P or b) be implemented in absolutely every single SAT solver (using GPU or whatever rather than FPGA). In contrast, every single SAT solver uses CDCL which is ~roughly DFS with clever backtracking. And I say this as someone that has investigated solving ILPs on FPGA - i.e., I wish it were true but it ain't.
- zachbee 3y ago
  This is a personal project aiming to replicate analog coupling dynamics with asynchronous digital circuits FPGAs, not a claim that we can solve NP complete problems with a fundamental speedup. Also, these sorts of Ising architectures get their speed-up are based on oscillator interaction, not parallelism. It's relevant to this article because it leverages oscillators on FPGAs in a nifty way :)
  - fpgamlirfanboy 3y ago
    > This is a personal project aiming to replicate analog coupling dynamics with asynchronous digital circuits FPGAs, not a claim that we can solve NP complete problems with a fundamental speedup. Then you shouldn't have led with that? It's like academic clickbait to say "here's this thing I'm working on, it uses XYZ technique to solve REALLY HARD PROBLEM" but omit the "...very poorly" part. Like I said I don't entirely blame you, I blame the academics that have an entire cottage industry and culture around these kinds of "results". > These sorts of Ising architectures get their speed-up are based on oscillator interaction, not parallelism. Not sure what you're trying to say - it's quantum annealing "brought to life" using simple 2-state (up/down) particles/phonos/whatever you want to call them. The quantum in quantum annealing means superposition ie parallelism; your implementation is basically a D-Wave machine without the qubits.
    - zachbee 3y ago
      I dunno man, I think saying "this is a personal project of mine" and linking to an open source github repo implies that it's a casual side project. I never made any performance claims, it's just for fun. I'm not trying to put up clickbait. And yeah, I think the fact that you can build a classical, analog, D-Wave-sans-qubits machine on an FPGA is cool!
pclmulqdq 3y ago
The digital ising thing was a very interesting line of research that Fujitsu has been trying to sell for 10 years or so: https://www.fujitsu.com/global/services/business-services/digital-annealer/ https://www.fujitsu.com/global/services/business-services/di... They presented their v1 chip architecture at ISSCC in 2015 much to the consternation of a few quantum computing people who (rightly) objected to the characterization of it as an "Ising" chip, because it cannot represent superposition. It's a pretty cool sort of system that should be able to solve pseudo-energy-minimization problems, but they are only theoretically sound when energy minimization corresponds to minimizing a Lyapunov function. Sadly, it's not clear that there is a way to generically construct a Lyapunov function with a minimum that corresponds to an NP-complete problem. The Fujitsu device supposedly is good at "easy" versions of problems, but so is a SAT solver.
- zachbee 3y ago
  The Fujitsu device is a synchronous digital architecture. I'm using asynchronous oscillators, more like Lo et. al. (https://www.nature.com/articles/s41593-024-01607-5 https://www.nature.com/articles/s41593-024-01607-5) I personally think it's super cool that we can replicate analog coupling dynamics using asynchronous digital logic!
  - pclmulqdq 3y ago
    I hate to burst your bubble, but when you do the dynamic systems math, they are sadly equivalent. You are working in the continuous time domain while the synchronous devices are working in the discrete time domain.
    - zachbee 3y ago
      In practice, though, asynchronous systems can run a lot faster than their synchronous counterparts! Also, I'm mostly working on this project because it's cool and interesting to build oscillator-based computing systems on FPGAs, not because I'm trying to build a practical system. That's why I posted it here: it's a fun use-case for asynchronous stuff you can do on FPGAs.
nickpsecurity 3y ago
I just skimmed it. Quite over my head in electronics. Is it stuff like this that you’re doing and looking for? https://www.dcs.gla.ac.uk/~wpc/reports/HwRelaxParadigm-submitted-BCS-IARC.pdf https://www.dcs.gla.ac.uk/~wpc/reports/HwRelaxParadigm-submi...

fpgamlirfanboy 3y ago

I promise I'm not trying to rain on your parade, and I blame the academics for this, but: 1. NP-complete problems are (today) global search problems (3-SAT algos search for a satisfying assignment...); 2. Combinatorial search spaces are not only non-convex, they don't have gradients (sub-gradients don't count) and even if they did, without convexity, it's still hopeless. Thus, you cannot (today) appreciably parallelize NP-complete algos, you can only draw more lottery tickets (for where to seed your search), i.e., constant factor improvement. I'm just putting this out there in case someone gets tantalized by the "fancy math/physics/fpga thing solves NP-complete problems" hook. Yes it can but no better than your computer (despite what paper authors claim in order to get published). To wit: if this were a compelling solution to NP-complete problems it would either a) already be a proof that NP=P or b) be implemented in absolutely every single SAT solver (using GPU or whatever rather than FPGA). In contrast, every single SAT solver uses CDCL which is ~roughly DFS with clever backtracking. And I say this as someone that has investigated solving ILPs on FPGA - i.e., I wish it were true but it ain't.

zachbee 3y ago
This is a personal project aiming to replicate analog coupling dynamics with asynchronous digital circuits FPGAs, not a claim that we can solve NP complete problems with a fundamental speedup. Also, these sorts of Ising architectures get their speed-up are based on oscillator interaction, not parallelism. It's relevant to this article because it leverages oscillators on FPGAs in a nifty way :)
- fpgamlirfanboy 3y ago
  > This is a personal project aiming to replicate analog coupling dynamics with asynchronous digital circuits FPGAs, not a claim that we can solve NP complete problems with a fundamental speedup. Then you shouldn't have led with that? It's like academic clickbait to say "here's this thing I'm working on, it uses XYZ technique to solve REALLY HARD PROBLEM" but omit the "...very poorly" part. Like I said I don't entirely blame you, I blame the academics that have an entire cottage industry and culture around these kinds of "results". > These sorts of Ising architectures get their speed-up are based on oscillator interaction, not parallelism. Not sure what you're trying to say - it's quantum annealing "brought to life" using simple 2-state (up/down) particles/phonos/whatever you want to call them. The quantum in quantum annealing means superposition ie parallelism; your implementation is basically a D-Wave machine without the qubits.
  - zachbee 3y ago
    I dunno man, I think saying "this is a personal project of mine" and linking to an open source github repo implies that it's a casual side project. I never made any performance claims, it's just for fun. I'm not trying to put up clickbait. And yeah, I think the fact that you can build a classical, analog, D-Wave-sans-qubits machine on an FPGA is cool!

pclmulqdq 3y ago

The digital ising thing was a very interesting line of research that Fujitsu has been trying to sell for 10 years or so: https://www.fujitsu.com/global/services/business-services/digital-annealer/ https://www.fujitsu.com/global/services/business-services/di... They presented their v1 chip architecture at ISSCC in 2015 much to the consternation of a few quantum computing people who (rightly) objected to the characterization of it as an "Ising" chip, because it cannot represent superposition. It's a pretty cool sort of system that should be able to solve pseudo-energy-minimization problems, but they are only theoretically sound when energy minimization corresponds to minimizing a Lyapunov function. Sadly, it's not clear that there is a way to generically construct a Lyapunov function with a minimum that corresponds to an NP-complete problem. The Fujitsu device supposedly is good at "easy" versions of problems, but so is a SAT solver.

zachbee 3y ago
The Fujitsu device is a synchronous digital architecture. I'm using asynchronous oscillators, more like Lo et. al. (https://www.nature.com/articles/s41593-024-01607-5 https://www.nature.com/articles/s41593-024-01607-5) I personally think it's super cool that we can replicate analog coupling dynamics using asynchronous digital logic!
- pclmulqdq 3y ago
  I hate to burst your bubble, but when you do the dynamic systems math, they are sadly equivalent. You are working in the continuous time domain while the synchronous devices are working in the discrete time domain.
  - zachbee 3y ago
    In practice, though, asynchronous systems can run a lot faster than their synchronous counterparts! Also, I'm mostly working on this project because it's cool and interesting to build oscillator-based computing systems on FPGAs, not because I'm trying to build a practical system. That's why I posted it here: it's a fun use-case for asynchronous stuff you can do on FPGAs.

nickpsecurity 3y ago

I just skimmed it. Quite over my head in electronics. Is it stuff like this that you’re doing and looking for? https://www.dcs.gla.ac.uk/~wpc/reports/HwRelaxParadigm-submitted-BCS-IARC.pdf https://www.dcs.gla.ac.uk/~wpc/reports/HwRelaxParadigm-submi...