Study On The Floorplanning Algorithom Based On Transitive Closure Graph Representation

Due to the fast development of technology, the circuit size and design complexity in the Very Large Scale Integration (VLSI) are increasing dramatically. The hierarchical design and Intellectual Property (IP) reused are widely applied to deal with the complex design problem. The Floorplanning, as the core of VLSI physical design, is used to decide the position of blocks on a chip, so that the object to minimize some predefined cost metric can be reached, such as the target area and/or total wire length etc. However, floorplanning has been proved to be NP-hard.After studying current main floorplanning algorithms, some key problems in floorplanning are researched based on the transitive closure graph in this dissertation, such as area minimization, wire length optimization. The main achievements are the following:1. Most of the existing floorplanning algorithms are implemented in Simulated Annealing (SA) scheme. The target area is evaluated after packing all of the blocks. Then it is decided that the corresponding permutation is accepted or not. In this dissertation, the specific algorithm, area prejudged transitive closure graph (AP-TCG) algorithm for non-slicing floorplans, is proposed, which can estimate the target area without packing. The AP-TCG algorithm performing in an iteration scheme is effective and efficient.2. In practical physical design, there is the requirement of placing some blocks along the boundaries of the chip, so that the blocks can be connected to I/O pads. To handle the floorplanning with boundary constraints, a novel AP-TCG algorithm, which integrates the feasible conditions of boundary constraints into each perturbation, is proposed in this dissertation. Unlike other algorithms, which need to transform the infeasible solution to feasible one, our approach can guarantee the intermediate solutions of perturbations are all feasible.3. The traditional floorplanners mostly compact all blocks to the left-bottom corner. It has been observed that other floorplans with different wire length can be gotten by redistributing the white space, without changing the original topology and area. To handle the wire length optimizing problems, a greedy algorithm is proposed based on the block moving in this dissertation. First, a unique moving range of every block is calculated. Then, a moving cost tree is constructed to represent the relationship between block moving and wire length. Finally, the optimization solution with shorter wire length can be obtained without changing the original topology and area.4. After intensive research, we have derived that the white space redistributing problem can be formulated into a Mixed Integer Linear Programming (MILP) problem. The floorplanning result of optimal position for each block and minimization of total wire length can be obtained by using the Linear Programming Solver.5. It is found that some blocks can be flipped to reduce total wire length, without affecting the original floorplan. A new approach, in which some white spaces are redistributed and some of the blocks are flipped concurrently to reduce the total wire length, is proposed in this dissertation. The mixed approach is advisable to be applied as an addition to the traditional floorplanner.