On Block Coordinate Descent Algorithms For Global Placement Problem In Integrated Circuits Design

The physical design in integrated circuit greatly impact circuit performance,which is a very important part in the process of large scale integrated circuit design.With the increasingly high demand for manufacturing process,the traditional mechanic design may be impossible,so it is of partial value and academic significance to research the method of automated layout.The layout process is the first step in the physical design of integrated circuit,which can be divided into global and local layout.In the previous researches,many improved effective methods have been proposed.Due to the standard cell global placement problem,the thesis constructs a linearly constrained optimization and proposes an extended block coordinate descent method.Two different algorithms are proposed in the thesis,they are coordinate independently method and coordinate alternate method.The global convergence of the proposed methods is proved.Numerical tests indicate that,the proposed methods are efficient on both within or without overlap-blocks.This thesis is organized as follows:Chapter 1 introduces the current research status,background,as well as the research significance of global placement problem.Chapter 2 reviews the domain decomposition method and the coordinate descent,particularly the traditional coordinate descent method.Chapter 3 and Chapter 4 are the main parts of the thesis.Chapter 3 proposes a block coordinate descent for the general linearly inequality constrained optimization problem,and whether the adjacent block overlapped are considered.The global convergence of the proposed algorithm is proved.Numerical experiments show that,the block-coordinate descent method is more effective than the full-coordinate descent method,and the performance in the case with overlapping block is not worse than that one of without overlapping block.Chapter 4 presents a linearly inequality constrained minimization model for the integrated circuits global placement problem,two different global placement methods are proposed.Numerical experiments show that,the proposed model is practical and the proposed algorithm is effective.Chapter 5 summarizes this thesis,and gives some suggestions for future researches.