High Speed Simulated Annealing Approach for Non-Slicing VLSI Floorplanning

Abstract

In Very Large Scale Integration (VLSI) flow, Physical Design Automation plays a very important role. VLSI Floorplanning is a very important stage in the Physical Design of VLSI. Area, power and speed are the major parameters that affect the design and performance of any VLSI chip. The major focus of research in this VLSI is always on optimisation of any parameter or parameters listed above. In VLSI floorplanning the research is focused on the area of the chip, interconnection module wirelength and dead space between the modules. In VLSI floorplanning it is also taken into consideration that the modules which are going to be placed for the optimisation cannot overlap with each other. In this research work, High speed simulated annealing algorithm (HSSA) is implemented for the solving of VLSI non-slicing floorplanning problem as it is NPhard problem and is nearly impossible to solve if manually. The SA uses a new acquisitive method to construct an initial B*-tree and a new process to explore the search space. B*-tree is used and implemented as the input for the high speed simulated algorithm. In this dissertation, not only optimisation of area of modules, interconnection wirelength of modules and dead space between modules is done but all optimisations are done with very high speed. Nowadays all floorplans are coming from the nonslicing category so in this research work, non-slicing VLSI floorplans are taken into consideration. HSSA is implemented along with the B*-tree in the C++ language. The HSSA has been implemented and experimental result with optimisation of area, dead space, wirelength and best timing constraints have been tested on Microelectronic Center of North Carolina (MCNC) benchmarks and also compared with the results mentioned in other research papers. In this, Ubuntu 14.04 OS and GPP compiler is used to compile the C++ code generated for the objectives. Maximum 11.17% reduction in area and 21.73% reduction in wirelength have been found with compared to other research work while in case of computation time, maximum 99.69% reduction has been observed.