Research On The Algorithms For VLSI Placement Based On Gate Array

From the 1960's, the Integrate Circuit(IC) has passed from Small Scale Integration(SSI) and Medium Scale Integration(MSI) to Large Scale Integration(LSI) in its development, now it steps into a new stage of Very Large Integration(VLSI) and Ultra Large Scale Integration(ULSI), it's the time of System On Chip. The technology of IC develops towards more integrated, much smaller, higher performance and higher reliability. There may have several hundred million or even several billion transistors in one chip. With the increase of integration, IC Design is more complicated. Nowadays, without the help of Computer Aided Design (CAD) and Electronic Design Automation (EDA), it's impossible to process IC design.In this paper, algorithms for VLSI placement are summarized including the Pair-wise Interchange Algorithm, the Algorithm of Placement by Partition, the Simulated Annealing Algorithm, the Genetic Algorithm, the Mathematical Program Algorithm, ANN Algorithm, the Tabu Search Algorithm and Ant Colony System. The elements, process and parameters about all the algorithms above are given.An initial placement of 36 modules is designed to test the performance of SA, GA and GASA, to compare the optimized results and give the improved placement. The influence of every parameter in SA on the placement result is discussed in detail.A new method for optimizing the placement is given. The principle is based on the conjunction of modules, the modules have bigger conjunction to be placed together.