Application Of An Improved O-tree Representation In Solving The VLSI Ciruit BBL Placement Problem With Predefined Coordinate Alignment Constraint

With the continuous development and application of EDA design methodologyfor VLSI circuit and systems as well as the advent of the Intellectual Property (IP)module technology, floorplanning and placement have become a key section in theprocess of their physical design. Main objective of floorplanning is to locate eachcircuit module in a suitable position with an optimal shape and ascertain the positionof the pad of the module in order to minimize chip area and length of interconnectionamong blocks under condition of fulfilling the requirement of placement constraints.Because is the first step in physical design, its result will affect the finalperformance of a chip.People always seek for effective optimum algorithm to solve the placement.Through appropriate strategies, we can not only solve problems in placement butdecrease the complexity of algorithm simultaneously then whole time spent inimplementation can be saved quite a lot. Under such a background and based onsupport of Sichuan Science and Technology Bureau Foundation, we have conducteda research project on BBL placement in (Building Block Layout) mode which is akey step in physical design of VLSI .This thesis would indicate some fruitful resultsof our research.In this thesis, the placement problem with predefined coordinator alignment(PCA) constraint is studied. Improved O-Tree encoding method and simulatedannealing algorithm are adopted to solve this problem. At present, there are somesuccessful algorithms to solve placement problem with PCA constrait. However,these algorithms are either complicated or time consuming. Motivated by this fact,we propose a new packing algorithm based on O-tree structure, aiming at reducingthe total run time. As compared with the results given in reference[32], our...