Hacker News Reader

Comment by anigbrowl | Hacker News Reader

Interesting points. However, it's a bit hard to complain about it being slow (#3) considering the enormous complexity involved, no? I remember compiling things on a 486 (when I got into Linux) being pretty damn slow as well for anything substantial.

I don't mean to excuse the manufacturers, but at the same time they seem to be selling into a pretty small market and it's not clear to me that opening things up will magically lead to a big expansion in chip sales that will negate the competitive risk of being the first to open up. If you have time, I'd like to learn more about this since you seem to have a lot of experience with this technology.

View on HN

I am certainly not expecting compiling HDL to be the same as compiling software, as yes it is drastically more complicated. However, compile times are growing more than linearly with respect to the number of gates (or logic blocks) that are in each FPGA. Whereas software grows linearly as the programs get larger. Also you have the other dimension of getting your block timed, so it can run on the FPGA at a guaranteed frequency. This is definitely a non-trivial problem, but one that I believe would be better solved by some hackers if there were a "GCC" for Verilog FPGA synthesis.

In my opinion there is very little for the manufacturers to gain by keeping their bitstream formats proprietary and undocumented. I don't think there is a competitive advantage, as all the manufacturers are pretty much doing the same thing. And their FPGA block diagrams are already open and documented (you can see how many flip flops, clocks, and muxes are in each logic cell, how the routing works, and where the memory cells and other units are).

I have only passing familiarity with FPGAs, so perhaps you can excuse my ignorance.

I was under the impression that FPGA vendors often license functional blocks (like PCIe SERDES) to FPGA users. Might it be that part of the purpose of obscuring the bitstream format is to make it more difficult for customers to use those functional blocks without paying the toll?

The bitstream format, at least for Xilinx, is not that obscure. Actually was documented in an old application note.

Take a look at VTR (formerly VPR): http://code.google.com/p/vtr-verilog-to-routing/. It's an academically developed tool for doing FPGA place and route. At the end of the day, you'll still need to use the proprietary tools to convert to the appropriate bitstream, but this an open source solution for the "heavy lifting" portion. However, last I checked the solutions produced by VPR aren't as good as the commercial tools.

> However, last I checked the solutions produced by VPR aren't as good as the commercial tools.

Well, that's no surprise: FPGA vendors spend a lot of manpower on improving their Place&Route software. If you wanted to build something competitive, you'd need a lot of money plus access to proprietary, non-public, information.

Bingo. FPGA routing is NP-Hard; Compiling software is generally P.

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.

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

a bit hard to complain about it being slow (#3) considering the enormous complexity involved, no?

It is if the original premise was to make Photoshop filters fast. A GPU can make my Photoshop filters fast now an FPGA implementation can make them fast 8 to 24 hours from now.

Not if you upload precompiled bitstreams into the FPGA.

Laying out components on a chip and routing non overlapping edges (ie wires) is call "orthogonal edge routing". Graph drawing algorithms don't get much attention outside their niche (oddly to me at least). But this is one area that has profound importance.

I've made a note of the term "orthogonal edge routing", hopefully for eventual incorporation into my own software (http://www.nitrogenlogic.com/docs/palace/). Thanks.

Reply on news.ycombinator.com