Some Algorithms Research On VLSI Floorplanning And Placement

Floorplannning is a very important step in Very Large Scale Integrated Circuits (VLSI) physical design. It mainly plans the shapes and locations of the modules on a chip. With the development of IC (Integrated Circuit) designs, more and more issues need to be considered. Especially with the increasing of the operate frequency and high integration of the chip, area, delay, and temperature are become very tough issues in VLSI design.This thesis has done some research on the floorplanning/placement algorithms, used in VLSI physical design, including Simulated Annealing (SA), Tabu Search (TS) etc. And it also proposed approaches to solve some problems, such as area optimization, wirelength optimization, congestion optimization. The main contributions of this thesis are as followings:(?) We proposed a hybrid algorithm based on simulated annealing algorithm and tabu search algorithm to search the optimal solution in finite solution space. The simulated annealing was applied to generate neighborhood solutions and the B*-tree was embedded to represent a floorplan. The preorder and inorder sequences of B*-tree are acted as a tabu object. Experimental results showed that our approach can improve area utilization in shorter time.(?) As a multi-objective optimization problem (MOP), it is difficult for floorplanning to balance various objectives simultaneously using traditional linear weighted sum approach. To overcome this problem, fuzzy rules and membership function were employed to combine different objectives. It is a convenient method to combine conflicting objectives and it also can use the expert human knowledge. Experimental results showed that this approach was stable and efficient which could obtain encouraging results in shorter time. Through the experimental results, we could have an intuitive understanding of objectives with various changes in parameter settings. This approach would also be extended to handle other large scale MOP problems.(?) In order to avoid the rip-up and reroute which is a timing-consuming process, we proposed a new two-stage congestion reduction approach for floorplanning. We applied the method of probability-estimation to evaluate the routing of nets. We also made use of the strategy of cell perturbing to eliminate the routing congestion. Further congestion reduction was obtained by using our algorithm, guided by congestion. The experiments results showed that our algorithm is efficient, stable and can reduce congestion largely. Compared with the traditional congestion-driven floorplanning, our two-stage approach can alleviate the congesiton efficiently in much shorter time.