Study And Implementation Of BBL Placement Based On Less Flexibility First (LFF) Principles

In recent years, the VLSI circuit technology has advanced profoundly, rapidly, this fact is due to the strong support from high performance integrated circuit (IC) CAD tools, (Electronic Design Automation ) which in turn improve the EDA software environment significantly. As is known that the physical design (namely, the layout design) of VLSI circuits plays a key role in the area of EDA design tools. As regard to the layout design, the placement problem constitutes a significant part, and its objective is to minimize chip area and interconnection of blocks under feasible constraints through locating given blocks.With the progress in ultra large scale integrated (ULSI) circuits deep-submicron (DSM) and very-deep-submicron (VDSM) technology, placement has a great impact on chip size and global interconnect structure. This trend makes module placement much more critical to the quality of a VLSI design than ever. To facilitate placement, we desire an efficient, flexible and effective representation which induces a solution structure for placement optimization to model the geometric relationship among modules. Under this background and support of Sichuan Science and Technology Bureau Foundation, this dissertation is intended to report some of our research results in solving BBL (Building Block Layout) problems in VLSI circuit physical design.In this dissertation, we give a survey of recent development on non-slicing floorplan representations, e.g., CBL, BSG, Sequence Pair and O-tree etc. Meanwhile, based on the so-called "Less Flexibility First" principles which are developed through human's accumulated experience when rectangle packing problem is just a simplified case of the polygon-shape stone plate packing problem that ancient masons needed to face, we handle placement of L/T-shaped blocks and blocks with abutment constraints.Main contribution of the author in solving the placement problem mentioned above can be addressed below:1. Proposed a novel placement representation called EDGR(Encoded Directional Graph Representation);2. By using the EDGR together with the LFF(Less Flexibility First) principles, developed a placement algorithm for solving the specific placement problem mentioned above;3. Designed a benchmark in this regard to verify the placement algorithm, then performed a computer simulation to demonstrate the effectiveness both for the EDGR and the placement algorithm.