Constraint-based VLSI Placement Algritnems And Impleimentations

At present, with the development of SoC designs and NoC designs, many researchers add some extra constraints into the optimizing process of floorplanning to meet the different functionality and performance requirements, including the location between modules, such as alignment constraints, boundary constraint, power integrity constraints and performance constraints and so on. Modern placement of the problem has been from the simple and traditional to a variety of constraints and complex. In solving problems with the placement of constrained, we use B*-Tree representation of the placement. It is a flexible and efficient representation of the ordered binary tree.This thesis studies two kinds of placement constraints, the alignment constraints and performance constraints. Because the modules are arranged with coordinates, the alignment constraints can be divided into horizontal alignment constraints and vertical alignment constraints. This constrained placement was based on the B*-tree representation. We achieved the mixed constraints placement with horizontal alignment constraints, vertical alignment constraints and performance constraints. We in-depth study of the B*-tree of the structure and characteristics and proposed three sufficient conditions for the corresponding constraints, and proposed an optimization process can be quickly sifted legal solutions. For the simulated annealing algorithm, we also raised its optimization process. That is, in every iteration of the process of cooling, we have to test the legality of its placement. If it is illegal, then the dynamic would legitimize this temperature to complete the placement. In the cooling iteration process of generating solution space, added to determine steps to reduce time to improve efficiency. The experimental data demonstrated, this thesis realized constraints were successful, and optimized process were effective.With the VLSI continuous large-scale and complexity, the number of wafer is being exponential growth. At the chip design process stage, the delay of placement has become the bottleneck. Therefore, to eliminate duplication in the placement, aim to reduce delay of the incremental algorithm become the research hotspot. This thesis through in-depth analysis, we have taken a compromise of the three divided incremental placement basing on constraints. The incremental constrained placement divided into two stages. First is by using tripartite method to solve incremental placement. Second stage is incremental placement based on the constrained placement. Since both constraints methods and dealing with illegal restraint solution method is the same, the constraint of the incremental placement is not repeated. With the increasing the number of modules of the test case, the advantages of incremental placement is gradually enhance. Thus can be inferred that incremental constraint placement of VLSI has a certain impact in the future. Experimental results show that the incremental constrained placement design has been completed, and it can avoid some repetition well in the operation and save placement time.