Increamental Floorplan With Multi-constraint

Floorplan is an important stage on physical design of VLSI. This thesis is for the floorplan, and set up an incremental floorplan tool to optimize the floorplan results obtained pre-calibrated and optimized. In this thesis, we study the simulated annealing, B* tree, TCG and other algorithms and try to improve them. At the same time, we give the solution on constraints of fixed modules, fixed out-line constraints. Finally, we study ZSA algorithm and enlargRegion operation which can be applied to optimize the hot spots and deadspace.SA is a common and standard algorithm used on floorplan. But the process of it cost too much time. B*-tree is a common VLSI representation. We improve the process of floorplan based on SA and B*-tree, and propos OPSA (order perturbation simulated annealing) process to reduce its running time, and to obtain better solutions.TCG representation is a graph-based representation. There are two parts of its theory which are difficult to achieve, and they have a greater impact disturbance on operations. The first is that if we do moving operation on result by translate the floorplan into the TCG representation, a ring maybe occure. The second is that it is easy to make redundant edge by the moveing operation. This thesis will describe these two points in detail and give specific analysis and case. Then, we give the improved mathematical description of TCG in order to avoid these two problems which affect the operation of the disturbance.we present a post-processing optimization algorithm to solve fixed module constraint based on fixed out-line constraints. Firstly, we adjust the critical path of TCG iteratively until the floorplan satisfy the fixed out-line constraints. Then, we add virtual nodes into the TCG to deal with a fixed module to make the fixed out-line constraints and the fixed module constraint unified. So if the fixed out-line constrant is satisfied by the post-processing optimization process, the fixed modules constraint will be satisfied.In this thesis, we present incremental relaxation algorithm based on slack. When the floorplanning is completed, we translate the floorplan into the TCG. According to the relaxation volume of distribution amone modules, we can operate on the modules with enlargeRegion operation to obtained result by relocate/resize/reshape operation. This algorithm is mainly to do with slack distribution. And it can take advantage usage of TCG and graph structure and basic algorithms. The algorithm can be applied to optimize deadspace, length, and distribute hot spots.In this thesis, we do a deeply study on SA and TCG, give a solution for fixed-outline and fixed blocks, and study the usage of ZSA on TCG. The experience show that all what I do are useful, and remain much to be improved.