3 ms·
Simulated annealing has been useful for decades. My undergrad VLSI project was to lay out a 32-bit CRC chip and test it with SPICE (an analog simulation tool).
by ttul 3y ago
Simulated annealing has been useful for decades. My undergrad VLSI project was to lay out a 32-bit CRC chip and test it with SPICE (an analog simulation tool). To get the capacitance down, you need short wires. But a CRC-32 has many many interdependencies. Laying one out by hand would take a very very long time.
So my partner wrote the Verilog code for the annealer and I wrote a C++ program that attached virtual springs to each gate, iteratively moving gates closer together if they were far apart. At first, the movements are dramatic, but over time, the total length of all gates converges onto an asymptotic limit that is much better than the starting point.
Once we had a gate layout implemented in an obscure EDM language, we were able to bring it into SPICE and damn right it worked the first time! I think the professor was somewhat mystified why we didn’t just build a simple 4-bit adder instead, but spend 50 hours on this project was a lot more fun than doing a hand layout.
- ttul 3y agoAnd here is the layout: https://www.dropbox.com/scl/fi/ksxru0lmnp0oha356fdby/layout.eps?rlkey=vxiz11vippdzck6czcbi36zoc&dl=0 https://www.dropbox.com/scl/fi/ksxru0lmnp0oha356fdby/layout.... With apologies, it was a CRC-8. Still so many nodes and so many wires…
- bcrl 3y agoWow, that looks complicated. I ended up implementing the 32 bit ethernet CRC in Verilog for use on a Kintex 7 a few years ago, but I never looked at the mess of wiring that ended up generating. The code had to work with an arbitrarily wide bus as the PCIe core required a 256 bit wide bus to close timing at an achievable clock speed that was able to fully utilize PCIe x4 gen 2.
- Taniwha 3y agoYears ago I figured out how to get the best first approximation ... borrow a gym for a day, make 1000s of metal plates with hooks and a bar code, one for each gate, have a robot take rubber bands and use the netlist to hook up the plates. Then pick up the whole thing by the pads and give it a bit of a shake, lay it all carefully back down and have the robot go around and read the position of each bar code ....