TL;DR
This paper introduces ECBL, an extended corner block list representation for non-slicing floorplans that can handle empty rooms, unlike its predecessor. By proving that ECBL's solution space encompasses optimal placements and demonstrating its efficiency on MCNC benchmarks, the authors offer a more flexible and performant approach to VLSI floorplanning.
What Problem Does This Paper Address?
VLSI floorplanning is a critical step in chip design, aiming to arrange rectangular blocks on a chip to minimize area and wire length. Traditional methods often fall into two categories: slicing floorplans (representable by binary trees) and non-slicing floorplans. While non-slicing floorplans offer more design freedom, representing them efficiently and ensuring optimal solutions has been challenging. Existing topological representations like sequence pairs and bounded-sliceline grids can guarantee optimal solutions but suffer from high computational complexity. The "corner block list" (CBL) offered a linear-time solution but was limited to "mosaic floorplans" – those without any empty rooms, which can lead to suboptimal area usage. This paper addresses the need for a representation that can handle general non-slicing floorplans, including those with empty rooms, while retaining efficiency and guaranteeing the possibility of finding an optimal solution.
Methods
The core contribution is the Extended Corner Block List (ECBL). ECBL extends the original CBL by introducing an "extending factor" ($\lambda$) that allows for more rooms than actual blocks, effectively accommodating empty rooms. This is achieved by conceptually adding "false blocks" (zero width/height) to these empty rooms.
The paper details two key algorithms:
- ECBL Deletion Algorithm: This algorithm transforms a floorplan (potentially with empty rooms) into an ECBL. It works by iteratively deleting corner blocks, recording their orientation and associated T-junction information. False blocks are added to empty rooms before deletion.
- ECBL Insertion Algorithm: This is the inverse process, reconstructing a floorplan from an ECBL. It uses the recorded information to insert blocks and create rooms.
Crucially, the authors prove that ECBL's solution space includes the optimal placement by establishing a mapping between Bounded-Sliceline Grids (BSG) and ECBL. Since BSG is known to contain optimal solutions, and ECBL can represent BSG-based assignments, ECBL inherits this property. The paper also leverages simulated annealing for generating new solutions within the ECBL framework, allowing exploration of the solution space.
Datasets
The paper evaluates its approach using MCNC benchmarks. Specific circuits mentioned include apte, xerox, hp, Ami33, and Ami49. No new benchmarks were introduced.
Key Insights and Ideas
- Empty Rooms are Key: The paper highlights that allowing empty rooms, even if filled with "false blocks" conceptually, is crucial for representing general non-slicing floorplans and achieving better area utilization.
- ECBL Bridges the Gap: ECBL effectively bridges the gap between efficient representations (like CBL) and representations that guarantee optimality (like BSG), by extending CBL to encompass the solution space of BSG.
- The Power of $\lambda$: The extending factor $\lambda$ is shown to be a critical parameter. While a larger $\lambda$ increases the likelihood of finding an optimal solution by expanding the search space, it also increases runtime. The paper empirically finds a sweet spot for $\lambda$ (around 1.5 to 3) that balances solution quality and computational efficiency.
- Mapping BSG to ECBL: The formal proof that a BSG-based assignment can be represented by an ECBL is a significant theoretical contribution, directly linking ECBL's solution space to the known optimality guarantees of BSG.
Key Results
- Improved Performance: ECBL-based algorithms achieved a 7% improvement in wire length and a 2% decrease in dead space compared to CBL on MCNC benchmarks.
- Competitive Runtime: While ECBL might have a slightly longer runtime than CBL in some cases, it offers comparable or better results than other algorithms (O-tree, Cluster refinement) in significantly less time.
- Optimal Solution Guarantee: The paper proves that the solution space of ECBL includes the optimal block placement, meaning an optimal solution can theoretically be found.
- Efficient Complexity: For a constant $\lambda$, the ECBL-based algorithms maintain a linear time complexity of O(n), where n is the number of blocks.
Limitations and Future Work
- Practical $\lambda$ Selection: While theoretically $\lambda=n$ would guarantee the largest solution space, it's impractical due to combinatorial explosion and increased runtime. The paper empirically suggests $\lambda \in [1.5, 3]$ as a good trade-off. Future work could involve more sophisticated methods for automatically determining the optimal $\lambda$.
- Soft Blocks Not Included: The experiments were conducted without soft blocks, which are blocks whose dimensions can be adjusted. Incorporating soft blocks could be a direction for future research.
- Simulated Annealing Parameters: The paper uses simulated annealing but doesn't delve deeply into the optimization of its parameters beyond the choice of $\lambda$. Further tuning of the annealing schedule could potentially yield even better results.
Summary updated