Global Placement Method Based On Electrostatic System Modeling

In very large scale integration(VLSI for short)physical design,the placement problem is to place circuit blocks into a fixed region such that no block overlaps with each other and some cost metric(e.g.,wirelength)is optimized.Placement plays an important role in VLSI physical design which performance affects the subsequen-t design,such as routability,delay,power optimization,circuit reliability and so on to a great extent.However,with the increasing constraints of the current placement problem and the rapid growth of the number of objects on the chip,especially the widespread application of the billion-gate chip,the algorithm design of the VLSI placement problem has presented a great challenge.VLSI placement problem is a typical large scale NP-hard combinatorial optimization problem,any new effective progress will directly improve the existing VLSI electronic design automation soft-ware.Thus,the placement problem draws great attention in both the academic and industrial fields.Based on the previous research of VLSI placement design in academic circle,this thesis investigates the placement engine design and gives efficient algorithm.The contents are as follows.In the first chapter,the main steps of VLSI design process and physical design are described.Then the VLSI placement problem is introduced.Finally,the main contributions of this thesis are briefly explained.In Chapter 2,we model the placement problem as a two-dimensional electro-static system and derive a PDE equation.In order to reduce the numerical error,we directly solve the Poisson's equation to obtain an explicit solution,which is an infinite series and converges absolutely.Unlike the previous work that uses a series of uni-form bins to control block overlaps,we present an global exact density function for VLSI placement in order to make the explicit solution computable.To make a good tradeoff between runtime and solution quality,we present a fast computation scheme of Poisson's equation based on our explicit solution.In Chapter3,based on our fast computation,we develop an effective and efficient global placer called PePlace.Based on the ISPD 2005 benchmarks which were used to evaluate the wirelength-driven contest,we performed comparative studies with the leading placers on wirelength optimization.Experimental results show that our PePlace placer is effectiveness,efficiency,and robustness.In Chapter 4,we summarize the main works of this thesis,and introduce the future research directions.