Paper
Well, I just finished my 20 page paper, 'A Comparison of Floorplanning Algorithms'. Attached is an excerpt for your reading enjoyment:
Aside from looking at the Cai and Hegge paper to provide us with quantitative comparisons, one may also look at the current array of floorplanning and placement tools, sometimes described as floorplacement, to get a feel for what techniques are actually implemented. First off, one must outline exactly which tools are to be examined. In the current literature, much attention has been paid to the following tools: Dragon, Capo, FastPlace, TimberWolf, and Feung Shui. Of these tools, Dragon and TimberWolf both use simulated annealing, while Capo and Feung Shui use various forms of the min-cut algorithm. Other techniques in use by these tools include clustering and quadratic placement. It is interesting to note the absence of the force-directed approach and the sequence heuristic in any of these popular packages. One might hypothesize that the force-directed approach is too simple and naïve to produce good area and net length results. Additionally, it is also possible that the force directed approach is not as good of an analog, that is, equating a physical system to the floorplanning sphere may be less appropriate than previously thought. As for the sequence heuristic, the results of Cai and Hegge point to the fact that the sequence heuristic does not converge to an optimal solution as well as simulated annealing, and when eking out every last bit of performance is a must, it would seem that the sequence heuristic would be valuable only in the case where there is not enough computing power at hand to provide a rigorous simulated annealing treatment. Furthermore, with cheap, powerful hardware so readily available, and the fact that floorplanning problems are inherently parallelizable and able to be multithreaded, the consequences of long running optimizations can likely be mitigated by throwing more hardware at the problem.
Pretty hot, right?
-Kerry
Currently Listening To:
logh - All the Trees
