Paper Review: Fixed-outline floorplanning through better local search

Abstract

Classical floorplanning minimizes a linear combination of area and wirelength. When Simulated Annealing is used, e.g., with the Sequence Pair representation, the typical choice of moves is fairly straighgorward. In this work, we study the fixed-outline jloorplan for- mulation that is more relevant to hierarchical design style and is justijied for very large ASICs and SOCs. We empirically show that the bed-outlinejloorplan problem in- stances are signijicantly harder than the well-researched instances without jived outline. Furthermore, we suggest new objective functions to drive simulated annealing and new types of moves that better guide local search in the new context. Our empirical evaluation is based on a new jloorplanner implementation Parquet-1 that can operate in both outline-free and fixed-outline modes. Our proposed moves are based on the notion offloor- plan slack. The proposed slack computation can be imple- mented with all existing algorithms to evaluate sequence pairs, of which we use the simplest, yet semantically in- distinguishable from the fastest reported ([16]). A similar slack computation is possible with many other jloorplan representations. In all cases, the slowdown is by a con- stant factor - roughly 2x.

Paper Location

IEEEXplore

Citation

[1] S. Adya and I. Markov, "Fixed-outline floorplanning through better local search," Proceedings 2001 IEEE International Conference on Computer Design: VLSI in Computers and Processors. ICCD 2001, 2001, pp. 328-334.

Positive

• Strong introduction of atypical terms, with a few exceptions. (NDF, is an example of it being properly introduced.)
• Clearly addresses their algorithm choice and defines valid reasoning as to why an improved version was not used - complexity.
• Lovely empirical data.

Negative

• Introduces terminology such as "hypergraph" without defining the term. 
• Fails to address the research of B*-trees from the year prior.
• While their results show they are competetive - and in fact show a runtime improvement, they are almost universally ending with a larger area. The trade off may not be worth it, and they fail to address this.