News for hackers. Stuff that matters.
Re:How many 32-bit RISC CPUs fit in an FPGA? Now vs. 1995? by morcheeba on Thursday March 27, 2014 @11:48PM (#7485249)
Bingo. FPGA routing is NP-Hard; Compiling software is generally P.
Re:How many 32-bit RISC CPUs fit in an FPGA? Now vs. 1995? by demallien on Friday March 28, 2014 @06:48AM (#7486357)
If you take the travelling salesman problem, you can dramatically simplify the problem by constraining the salesman to visit all of the cities within the same state sequentially.

Similarly, you can reduce the complexity of routing calculations by applying some constraints. You will potentially lose the possibility of an optimal solution, but you will gain a far faster compilation time. As always with engineering, it's a trade-off.

Re:How many 32-bit RISC CPUs fit in an FPGA? Now vs. 1995? by morcheeba on Friday April 04, 2014 @01:57AM (#7529571)
Yep, global vs. local routers are kinda like stay-withing-the-state.

One of my favorite ideas on this is space-filling curves: http://www2.isye.gatech.edu/~jjb/mow/mow.pdf