What is the the Simulated Annealing Algorithm used for placement in FPGAs, complete description and in simple words.
1
-
5\$\begingroup\$ How hard is it to type "simulated annealing" into a search engine? en.wikipedia.org/wiki/Simulated_annealing \$\endgroup\$– starblueCommented Jan 10, 2015 at 17:55
Add a comment
|
2 Answers
\$\begingroup\$
\$\endgroup\$
3
The optimization of layout in an FPGA is complicated by the many physical constraints that are built into the basic chip. One method that has been found to work well without having to deal explicitly with those constraints is called "simulated annealing" (by analogy to metallurgy).
At a high level, the algorithm starts by placing the logic elements randomly across the chip, paying no attention to their connectivity to the other elements. Then, it iterates through all of the elements one at a time and evaluates the connections to that element, checking which direction and how far those connections go. If there is a strong bias in a particular direction, the position of the element is swapped with one that is in that general direction, but with a random offset added. Once all of the elements have been evaluated in this manner, the process is repeated. On each iteration, the probability distribution of the random offset is gradually "dialed down" — this is the analogy to annealing in matallurgy; the random offset represents the falling "temperature" of the migration process.
After many iterations, the logic elements will generally have moved in such a way that their connections are shorter, with elements that are part of the same subfunction grouped together.
This method generally finds good solutions, but it can sometimes get "stuck" in a suboptimal configuration of the elements. For this reason, the whole thing is often done several times, starting with a different random distribution each time. The best result of the several runs is the one that is kept.
answered Jan 10, 2015 at 16:00
-
\$\begingroup\$ That sounds kind of like a bubble sort. \$\endgroup\$ Commented Jan 10, 2015 at 16:06
-
2\$\begingroup\$ @Adam: No, a bubble sort is deterministic and there is a single right answer. This algorithm works by probably making this better each time, until eventually you get a good solution, probably, maybe. \$\endgroup\$ Commented Jan 10, 2015 at 16:55
-
\$\begingroup\$ If anything, it's more akin to BogoSort ;) \$\endgroup\$– drxzclCommented Feb 4, 2015 at 23:02
\$\begingroup\$
\$\endgroup\$
A good article on this appeared in the September 1989 issue of Dr. Dobbs
I used that article to implement an optimization routine for instrumentation design and was able to get it to work well. You pretty much have to work interactively with the results- if the simulated cooling is too rapid you'll tend to miss the global optimal results.
answered Jan 10, 2015 at 18:04