from Hacker News

A Simulated Annealing FPGA Placer

by stefanpie on 1/2/24, 4:46 PM with 35 comments

• by ttul on 1/2/24, 9:05 PM

  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.

• by dekhn on 1/2/24, 10:00 PM

  I used simulated annealing in my previous work doing molecular dynamics- it was great for not getting your protein trapped in a local minima, which gradient descent is prone to doing. I got excellent results for very little work.

  I asked my intern, who was knowledgeable in deep networks as well as molecular stuff, "it looks like ML training mainly does gradient descent, how can that work, don't you get stuck in local minima?" and they said "loss functions in ML are generally believed to be bowl-shaped" and I've been wondering how that could be true.

  It's interesting to read up on the real-world use of annealing for steel - it's quite intersting how you can change steel properties through heat treatment. Want it really strong? Quench it fast, that will lock it into an unstable structuer that's still strong. Quench it slow, it will find a more stable minimum, and be more ductile.

• by duskwuff on 1/2/24, 11:31 PM

  Does this actually result in a routable design when used on a real FPGA?

  Optimizing for the lowest value of a distance metric isn't necessarily going to be ideal - a highly compact placement (like the results shown) is going to require a lot of wires to pass through the center of the design. Some FPGAs may not have sufficient routing resources to support this, especially if there are many wires that cross over the center without interacting with it.

• by lindig on 1/2/24, 6:39 PM

  My understanding of simulated annealing is that solutions that are not improvements are still accepted with some probability in early steps but that this probability decreases as "temperature" drops. Looking at your description (but not code) I did not see that aspect but it looked like you would only accept improvements of the cost function. Is this correct or where does your solution accept slight regressions with some probability, too?

• by iamflimflam1 on 1/2/24, 7:04 PM

  My final year undergrad project (1992?) used an FPGA. The router for that used simulated annealing.

• by cevans01 on 1/2/24, 6:48 PM

  To the author: the source link https://github.com/stefanpie/sa-placer appears to be private.

• by ris on 1/3/24, 1:45 AM

  If you're getting into the territory of Global Optimization algorithms like SA it can be helpful to implement your problem generically enough that it can be plugged into a general purpose optimization package like pagmo2, where you can experiment with a dozen or more similar algorithms.

• by akivabamberger on 1/2/24, 7:56 PM

  Wondering how this compares to nextpnr (https://github.com/YosysHQ/nextpnr) ?

• by belkarx on 1/3/24, 12:01 AM

  force/spring based placement also seems to work pretty well- surprised that wasnt simpler to implement as a toy method

• by amelius on 1/2/24, 8:11 PM

  Do any methods exist that utilize deep learning to drive the optimization?