Floorplan representations: Complexity and connections

Bo Yao, Hongyu Chen, Chung-Kuan Cheng, Ronald L. GrahamACM Trans. Design Autom. Electr. Syst 2003 · DOI

TL;DR

This paper introduces a novel "twin binary trees" representation for mosaic floorplans, establishing a one-to-one mapping that eliminates redundancy. It also derives exact counts for mosaic and slicing floorplans and explores the relationships and redundancies among various floorplan representations, offering a unified perspective.

What Problem Does This Paper Address?

Designing efficient floorplans for VLSI circuits is crucial as chip complexity grows. Floorplanning algorithms often rely on effective representations of the circuit's layout. However, existing representations can be redundant (multiple representations mapping to the same floorplan) or computationally expensive. This paper addresses the need for efficient, non-redundant representations and aims to provide a clearer understanding of the combinatorial landscape of floorplans and their representations. Specifically, it tackles the problem of accurately counting distinct floorplan configurations and establishing clear, one-to-one mappings between floorplans and their representations.

Methods

The core contribution is the introduction of a "twin binary trees" structure for representing mosaic floorplans. This representation consists of a pair of binary trees that, together, uniquely encode a mosaic floorplan. The paper details the algorithm (MFTB) for converting a mosaic floorplan into these twin binary trees and its inverse (TBMF) for reconstructing a floorplan from the trees. This one-to-one mapping is key to eliminating redundancy.

The paper also revisits and formalizes the v-h tree representation for slicing floorplans, establishing a one-to-one correspondence with slicing floorplans.

Furthermore, the authors derive exact formulas for the number of mosaic floorplans (related to Baxter numbers) and slicing floorplans (related to Schröder numbers).

Finally, they analyze the relationships and redundancies between several existing representations, including sequence pairs (SP), corner block lists (CB), O-trees, and the newly proposed twin binary trees, using illustrative examples.

Datasets

Not discussed in the paper. The paper focuses on theoretical aspects and combinatorial analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Twin Binary Trees: A Perfect Match: The "twin binary trees" representation offers a one-to-one mapping for mosaic floorplans, meaning each unique pair of trees corresponds to exactly one floorplan, and vice-versa. This is a significant improvement over representations with redundancy.
  • Unlocking Exact Counts: By establishing these one-to-one mappings, the paper provides precise mathematical formulas for the number of distinct mosaic and slicing floorplans, connecting them to known combinatorial sequences (Baxter and Schröder numbers).
  • A Unified View of Representations: The paper bridges the gap between various floorplan representations, illustrating how they relate to each other and highlighting their respective strengths and weaknesses (especially regarding redundancy and expressiveness).
  • Mosaic Floorplans as a Generalization: The paper clarifies the hierarchy: slicing floorplans are a subset of mosaic floorplans, which are themselves a subset of general floorplans.

Key Results

  • Exact Number of Mosaic Floorplans: The number of distinct mosaic floorplans with n blocks is given by the n-th Baxter number, B(n).
  • Exact Number of Slicing Floorplans: The number of slicing floorplans with n > 1 blocks is twice the n-th Schröder number, A<sub>n</sub>.
  • Twin Binary Trees Algorithm (MFTB): An O(n) algorithm is presented to convert a mosaic floorplan into its unique twin binary tree representation.
  • Decoding Algorithm (TBMF): An O(n) algorithm is presented to reconstruct a mosaic floorplan from its twin binary tree representation.
  • Relationships Mapped: The paper visually and mathematically demonstrates the connections between twin binary trees, sequence pairs, corner block lists, and O-trees, showing how they can be transformed into one another or how one can be derived from another.

Limitations and Future Work

  • Focus on Combinatorics: The paper is primarily theoretical, focusing on the combinatorial aspects of floorplan representations and counts. While it establishes the efficiency of the twin binary trees representation in terms of one-to-one mapping and O(n) transformation times, it doesn't delve into the performance of floorplanning algorithms that might use these representations in practice.
  • General Floorplans: While the paper discusses general floorplans, its primary focus and novel contributions are on mosaic and slicing floorplans. The relationships explored are mainly among representations that can handle these types.
  • Future Work: The paper implicitly suggests that the proposed twin binary trees representation could be a strong candidate for use in practical floorplanning algorithms due to its efficiency and lack of redundancy. Further research could explore how algorithms can leverage this representation for faster and more effective floorplan generation. The detailed analysis of relationships also opens avenues for developing conversion tools between different representation types.

Summary updated

BibTeX
@article{yao2003floorplan,
  author = {Bo Yao and Hongyu Chen and Chung-Kuan Cheng and Ronald L. Graham},
  title = {{Floorplan representations: Complexity and connections}},
  journal = {ACM Trans. Design Autom. Electr. Syst.},
  year = {2003},
  doi = {10.1145/606603.606607},
}
Figure