A NOVEL FLOORPLANNING FOR HIERARCHICAL VLSI DESIGN

摘要

Floorplanning is one of the most challenging tasks at the early stage of VLSI physical design to determine the shapes, positions and orientations of modules under various constraints. Most floorplanning algorithms utilize techniques of perturbations with heuristics and random searches. It is critical to investigate a unified, efficient and flexible representation for general floorplans. Moreover, succinct and even canonical schemes for general floorplan are crucially needed. A new class of binary trees, called Floorplan Binary Trees (FBTs) is introduced in [12] to represent all three types of floorplans: slicing, nonslicing and mosaic. There is a one-to-one correspondence between a floorplan. This paper introduces the operating procedures of FBTs. FBTs can be constructed, operated and optimized using binary tree operations. The focus of this paper is the operations and optimizations of FBTs associated with hierarchical floorplanning algorithms. The construction and transformation has been demonstrated between a FBT and a floorplan. The definitions and algebraic properties of a FBT associated with a floorplan have been formally defined.